给我一个Linux中LRU算法的c语言模拟代码,简单一点就好
时间: 2024-02-13 19:01:04 浏览: 54
模拟LRU算法
好的,以下是一个简单的LRU算法的C语言模拟代码:
```c
#include <stdio.h>
#include <stdlib.h>
#define CACHE_SIZE 5 //缓存大小
typedef struct node {
int key;
int value;
struct node *prev;
struct node *next;
} Node;
typedef struct list {
Node *head;
Node *tail;
int size;
} List;
List* init_list() {
List *lst = (List*)malloc(sizeof(List));
lst->head = NULL;
lst->tail = NULL;
lst->size = 0;
return lst;
}
void delete_head(List *lst) {
Node *node = lst->head;
if (node == NULL) return;
if (node == lst->tail) {
lst->head = NULL;
lst->tail = NULL;
}
else {
lst->head = node->next;
lst->head->prev = NULL;
}
free(node);
lst->size--;
}
void add_node(List *lst, int key, int value) {
Node *node = (Node*)malloc(sizeof(Node));
node->key = key;
node->value = value;
node->prev = NULL;
node->next = lst->tail;
if (lst->tail != NULL) {
lst->tail->prev = node;
}
lst->tail = node;
if (lst->head == NULL) {
lst->head = node;
}
lst->size++;
}
void move_to_tail(List *lst, Node *node) {
if (node == lst->tail) return;
if (node == lst->head) {
lst->head = node->next;
lst->head->prev = NULL;
}
else {
node->prev->next = node->next;
node->next->prev = node->prev;
}
node->prev = lst->tail;
node->next = NULL;
lst->tail->next = node;
lst->tail = node;
}
void print_cache(List *lst) {
printf("Cache: ");
Node *node = lst->head;
while (node != NULL) {
printf("(%d, %d) ", node->key, node->value);
node = node->next;
}
printf("\n");
}
int main() {
List *cache = init_list();
int num = 0;
int key, value;
while (1) {
printf("请输入键值对(key,value),输入(0,0)结束:");
scanf("%d,%d", &key, &value);
if (key == 0 && value == 0) break;
Node *node = cache->head;
while (node != NULL) {
if (node->key == key) {
node->value = value;
move_to_tail(cache, node);
break;
}
node = node->next;
}
if (node == NULL) {
if (cache->size >= CACHE_SIZE) {
delete_head(cache);
}
add_node(cache, key, value);
}
print_cache(cache);
}
return 0;
}
```
这个模拟程序使用双向链表实现了一个LRU缓存,可以根据用户输入的键值对进行插入和查询操作,并且在缓存达到最大值时使用LRU算法进行淘汰。
阅读全文