c语言写简单的LRU算法

LRU算法（Least Recently Used）是一种缓存淘汰算法，它会淘汰最近最少使用的缓存块。下面是一个简单的C语言实现LRU算法的示例代码：

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

// 定义缓存块结构体
typedef struct CacheBlock {
    int key;  // 缓存块的键
    int value;  // 缓存块的值
    struct CacheBlock* prev;  // 前一个缓存块
    struct CacheBlock* next;  // 后一个缓存块
} CacheBlock;

// 定义缓存结构体
typedef struct Cache {
    int capacity;  // 缓存容量
    int size;  // 当前缓存大小
    CacheBlock* head;  // 头部缓存块
    CacheBlock* tail;  // 尾部缓存块
} Cache;

// 创建一个新的缓存块
CacheBlock* create_cache_block(int key, int value) {
    CacheBlock* block = (CacheBlock*)malloc(sizeof(CacheBlock));
    block->key = key;
    block->value = value;
    block->prev = NULL;
    block->next = NULL;
    return block;
}

// 创建一个新的缓存
Cache* create_cache(int capacity) {
    Cache* cache = (Cache*)malloc(sizeof(Cache));
    cache->capacity = capacity;
    cache->size = 0;
    cache->head = NULL;
    cache->tail = NULL;
    return cache;
}

// 将缓存块添加到头部
void add_to_head(Cache* cache, CacheBlock* block) {
    block->prev = NULL;
    block->next = cache->head;
    if (cache->head != NULL) {
        cache->head->prev = block;
    } else {
        cache->tail = block;
    }
    cache->head = block;
    cache->size++;
}

// 将缓存块移动到头部
void move_to_head(Cache* cache, CacheBlock* block) {
    if (block == cache->head) {
        return;
    }
    if (block == cache->tail) {
        cache->tail = block->prev;
        cache->tail->next = NULL;
    } else {
        block->prev->next = block->next;
        block->next->prev = block->prev;
    }
    block->prev = NULL;
    block->next = cache->head;
    cache->head->prev = block;
    cache->head = block;
}

// 移除尾部缓存块
void remove_tail(Cache* cache) {
    CacheBlock* tail = cache->tail;
    if (tail == NULL) {
        return;
    }
    if (tail == cache->head) {
        cache->head = NULL;
        cache->tail = NULL;
    } else {
        cache->tail = tail->prev;
        cache->tail->next = NULL;
    }
    free(tail);
    cache->size--;
}

// 获取缓存块的值
int get_cache_value(Cache* cache, int key) {
    CacheBlock* block = cache->head;
    while (block != NULL) {
        if (block->key == key) {
            move_to_head(cache, block);
            return block->value;
        }
        block = block->next;
    }
    return -1;
}

// 设置缓存块的值
void set_cache_value(Cache* cache, int key, int value) {
    CacheBlock* block = cache->head;
    while (block != NULL) {
        if (block->key == key) {
            block->value = value;
            move_to_head(cache, block);
            return;
        }
        block = block->next;
    }
    CacheBlock* new_block = create_cache_block(key, value);
    add_to_head(cache, new_block);
    if (cache->size > cache->capacity) {
        remove_tail(cache);
    }
}

// 销毁缓存
void destroy_cache(Cache* cache) {
    CacheBlock* block = cache->head;
    while (block != NULL) {
        CacheBlock* next = block->next;
        free(block);
        block = next;
    }
    free(cache);
}

// 测试LRU缓存算法
int main() {
    Cache* cache = create_cache(2);
    set_cache_value(cache, 1, 1);
    set_cache_value(cache, 2, 2);
    printf("%d\n", get_cache_value(cache, 1));  // 输出1
    set_cache_value(cache, 3, 3);
    printf("%d\n", get_cache_value(cache, 2));  // 输出-1
    set_cache_value(cache, 4, 4);
    printf("%d\n", get_cache_value(cache, 1));  // 输出-1
    printf("%d\n", get_cache_value(cache, 3));  // 输出3
    printf("%d\n", get_cache_value(cache, 4));  // 输出4
    destroy_cache(cache);
    return 0;
}

在上面的代码中，我们首先定义了一个缓存块结构体和一个缓存结构体，然后分别实现了创建缓存块、创建缓存、添加缓存块、移动缓存块、移除缓存块、获取缓存块值、设置缓存块值和销毁缓存等函数。最后我们在main函数中测试了LRU缓存算法的正确性。