lru算法用c语言的实现

LRU（Least Recently Used）算法是一种缓存淘汰算法，它的基本思想是根据数据的使用频率来淘汰最近最少使用的数据。以下是用C语言实现LRU算法的示例代码：

#include <stdio.h>
#include <stdlib.h>

// 定义LRU结点的结构体
typedef struct Node {
    int key;  // 结点的键
    int value;  // 结点的值
    struct Node* next;  // 指向下一个结点的指针
    struct Node* prev;  // 指向前一个结点的指针
} Node;

// 定义LRU缓存的结构体
typedef struct LRUCache {
    int capacity;  // 缓存的容量
    int size;  // 缓存的当前大小
    Node* head;  // 指向链表头节点的指针
    Node* tail;  // 指向链表尾节点的指针
    Node** hashmap;  // 哈希表，保存结点的指针
} LRUCache;

// 初始化LRU缓存
LRUCache* lRUCacheCreate(int capacity) {
    LRUCache* cache = (LRUCache*)malloc(sizeof(LRUCache));
    cache->capacity = capacity;
    cache->size = 0;
    cache->head = NULL;
    cache->tail = NULL;
    cache->hashmap = (Node**)calloc(capacity, sizeof(Node*));
    return cache;
}

// 获取LRU缓存中指定key对应的value
int lRUCacheGet(LRUCache* obj, int key) {
    if (obj->hashmap[key] == NULL) {
        return -1;
    }

    // 将访问的结点移到链表头部
    Node* node = obj->hashmap[key];
    if (node != obj->head) {
        if (node == obj->tail) {
            obj->tail = obj->tail->prev;
        } else {
            node->next->prev = node->prev;
            node->prev->next = node->next;
        }
        node->next = obj->head;
        node->prev = NULL;
        obj->head->prev = node;
        obj->head = node;
    }

    return node->value;
}

// 向LRU缓存中插入新的key-value对
void lRUCachePut(LRUCache* obj, int key, int value) {
    if (obj->hashmap[key] == NULL) {
        // 如果缓存已满，删除最近最少使用的结点
        if (obj->size == obj->capacity) {
            Node* tail = obj->tail;
            obj->hashmap[tail->key] = NULL;
            obj->tail = tail->prev;
            if (obj->tail != NULL) {
                obj->tail->next = NULL;
            } else {
                obj->head = NULL;
            }
            free(tail);
            obj->size--;
        }

        // 创建新的结点并加入链表头部
        Node* node = (Node*)malloc(sizeof(Node));
        node->key = key;
        node->value = value;
        node->next = obj->head;
        node->prev = NULL;
        if (obj->head != NULL) {
            obj->head->prev = node;
        } else {
            obj->tail = node;
        }
        obj->head = node;
        obj->hashmap[key] = node;
        obj->size++;
    } else {
        // 更新结点的值并移到链表头部
        Node* node = obj->hashmap[key];
        node->value = value;
        if (node != obj->head) {
            if (node == obj->tail) {
                obj->tail = obj->tail->prev;
            } else {
                node->next->prev = node->prev;
                node->prev->next = node->next;
            }
            node->next = obj->head;
            node->prev = NULL;
            obj->head->prev = node;
            obj->head = node;
        }
    }
}

// 释放LRU缓存的内存
void lRUCacheFree(LRUCache* obj) {
    Node* curr = obj->head;
    while (curr != NULL) {
        Node* tmp = curr->next;
        free(curr);
        curr = tmp;
    }
    free(obj->hashmap);
    free(obj);
}

int main() {
    LRUCache* cache = lRUCacheCreate(2);
    lRUCachePut(cache, 1, 1);
    lRUCachePut(cache, 2, 2);
    printf("%d\n", lRUCacheGet(cache, 1));  // 输出1
    lRUCachePut(cache, 3, 3);
    printf("%d\n", lRUCacheGet(cache, 2));  // 输出-1
    lRUCachePut(cache, 4, 4);
    printf("%d\n", lRUCacheGet(cache, 1));  // 输出-1
    printf("%d\n", lRUCacheGet(cache, 3));  // 输出3
    printf("%d\n", lRUCacheGet(cache, 4));  // 输出4
    lRUCacheFree(cache);
    return 0;
}

以上代码是用C语言实现LRU算法的简单示例，包括创建缓存、获取键对应的值、插入新的键值对以及释放内存的功能。代码中使用了双向链表和哈希表来实现LRU缓存，保证了缓存的快速查找和结点的插入/删除操作。在main函数中演示了LRU缓存的使用过程，并输出了一些操作的结果。