c语言实现lur算法

LUR（Least Recently Used）算法，也称为最近最少使用算法，是一种常用的内存管理策略，主要用于淘汰系统中的缓存或者页面，以释放空间给新的数据。在C语言中实现LUR算法，主要是模拟LRU缓存的逻辑，通常会涉及到链表和哈希表的数据结构。

以下是一个简单的C语言版LRU缓存实现思路：

1. 定义一个LRUCache类，包含一个大小为capacity的链表和哈希表：

typedef struct Node {
    int key;
    int value;
    struct Node *prev, *next;
} Node;
typedef struct LRUCache {
    int capacity;
    Node *head, *tail;
    unordered_map<int, Node*> cache;
} LRUCache;

2. 初始化LRUCache：

LRUCache *initLRUCache(int capacity) {
    LRUCache *cache = (LRUCache*)malloc(sizeof(LRUCache));
    cache->capacity = capacity;
    cache->head = cache->tail = NULL;
    return cache;
}

3. 插入操作（删除最近最少使用的节点并添加到头部）：

void insertNode(LRUCache *cache, int key, int value) {
    Node *node = new Node{key, value, NULL, NULL};
    if (cache->cache.find(key) == cache->cache.end()) {
        if (cache->tail) {
            node->next = cache->tail;
            cache->tail->prev = node;
            cache->tail = node;
        } else {
            cache->head = node;
        }
        cache->cache[key] = node;
        if (cache->size > cache->capacity) {
            Node *temp = cache->head;
            cache->head = temp->next;
            delete temp;
        }
    } else {
        Node *oldNode = cache->cache[key];
        removeNode(oldNode);
        insertNode(cache, key, value);
    }
}

4. 删除操作（从链表和哈希表中移除指定节点）：

void removeNode(Node *node) {
    if (node->prev)
        node->prev->next = node->next;
    else
        cache->head = node->next;

    if (node->next)
        node->next->prev = node->prev;
    else
        cache->tail = node->prev;

    delete node;
    cache->cache.erase(node->key);
}

5. 获取值（检查哈希表，如果存在则移到头部）：

int get(LRUCache *cache, int key) {
    auto it = cache->cache.find(key);
    if (it == cache->cache.end())
        return -1;
    Node *node = it->second;
    removeNode(node);
    insertNode(cache, key, node->value);
    return node->value;
}