c语言实现 lru算法
时间: 2024-09-04 11:00:14 浏览: 30
LRU算法是Least Recently Used的缩写,即最近最少使用算法。它是一种用于缓存淘汰策略的算法,根据数据最近被访问的时间来判断哪些数据应该被保留,哪些数据应该被淘汰。
C语言实现LRU算法的一种常见方法是使用双向链表和哈希表结合的方式。具体实现步骤如下:
1. 定义一个双向链表节点结构体,包含key和value两个字段,以及前驱节点prev和后继节点next两个指针字段。
2. 定义一个哈希表结构体,用于存储双向链表节点的指针和对应的key值。
3. 在哈希表中维护一个指针head和一个指针tail,分别指向双向链表的头节点和尾节点。
4. 在哈希表中维护一个整数size,表示当前哈希表中存储的节点数量。
5. 当有新的key-value对需要被插入时,先在哈希表中查找key是否已存在。
6. 如果key已存在,则将对应的节点从双向链表中删除,并将其移动到链表头部。
7. 如果key不存在,则创建一个新的节点,插入到双向链表头部,并在哈希表中添加key-value对。
8. 如果插入新节点后哈希表的大小超过了缓存大小(即LRU算法中的容量),则删除双向链表尾部的节点,并在哈希表中删除对应的key-value对。
9. 每次访问一个key时,先在哈希表中查找key是否存在。
10. 如果key不存在,则返回-1。
11. 如果key存在,则将对应的节点从双向链表中删除,并将其移动到链表头部,然后返回对应的value。
下面是C语言实现LRU算法的代码示例,其中双向链表和哈希表结构体定义略去:
```
#define CACHE_SIZE 1000
struct Cache {
struct ListNode* head;
struct ListNode* tail;
struct HashMap* map;
int size;
int capacity;
};
struct Cache* createCache(int capacity) {
struct Cache* cache = (struct Cache*)malloc(sizeof(struct Cache));
cache->head = NULL;
cache->tail = NULL;
cache->map = createHashMap(capacity);
cache->size = 0;
cache->capacity = capacity;
return cache;
}
void deleteCache(struct Cache* cache) {
deleteHashMap(cache->map);
free(cache);
}
void moveToHead(struct Cache* cache, struct ListNode* node) {
if (node == cache->head) {
return;
}
if (node == cache->tail) {
cache->tail = node->prev;
cache->tail->next = NULL;
} else {
node->prev->next = node->next;
node->next->prev = node->prev;
}
node->prev = NULL;
node->next = cache->head;
cache->head->prev = node;
cache->head = node;
}
void deleteTail(struct Cache* cache) {
struct ListNode* tail = cache->tail;
if (cache->head == tail) {
cache->head = NULL;
cache->tail = NULL;
} else {
cache->tail = tail->prev;
cache->tail->next = NULL;
}
deleteListNode(tail);
}
int get(struct Cache* cache, int key) {
struct ListNode* node = getListNode(cache->map, key);
if (node == NULL) {
return -1;
}
moveToHead(cache, node);
return node->value;
}
void put(struct Cache* cache, int key, int value) {
struct ListNode* node = getListNode(cache->map, key);
if (node == NULL) {
node = createListNode(key, value);
addListNode(cache->map, node);
if (cache->size == cache->capacity) {
deleteTail(cache);
cache->size--;
}
if (cache->head == NULL) {
cache->head = node;
cache->tail = node;
} else {
node->next = cache->head;
cache->head->prev = node;
cache->head = node;
}
cache->size++;
} else {
node->value = value;
moveToHead(cache, node);
}
}
```