实现最不经常使用算法（LFU）代码c语言

LFU（Least Frequently Used）算法是一种缓存淘汰算法，它根据缓存中每个条目的使用频率来选择要淘汰的条目。以下是一个简单的 LFU 算法的 C 语言实现：

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

typedef struct node {
    int key;
    int value;
    int freq;
    struct node* prev;
    struct node* next;
} Node;

typedef struct {
    int size;
    int capacity;
    Node* head;
    Node* tail;
    Node** freqList;
} LFUCache;

Node* createNode(int key, int value) {
    Node* node = (Node*) malloc(sizeof(Node));
    node->key = key;
    node->value = value;
    node->freq = 1;
    node->prev = NULL;
    node->next = NULL;
    return node;
}

LFUCache* createLFUCache(int capacity) {
    LFUCache* cache = (LFUCache*) malloc(sizeof(LFUCache));
    cache->size = 0;
    cache->capacity = capacity;
    cache->head = NULL;
    cache->tail = NULL;
    cache->freqList = (Node**) calloc(capacity + 1, sizeof(Node*));
    return cache;
}

void deleteNode(LFUCache* cache, Node* node) {
    if (node == cache->head) {
        cache->head = node->next;
    } else if (node == cache->tail) {
        cache->tail = node->prev;
        cache->tail->next = NULL;
    } else {
        node->prev->next = node->next;
        node->next->prev = node->prev;
    }
    cache->size--;
    cache->freqList[node->freq] = NULL;
    free(node);
}

void insertNode(LFUCache* cache, Node* node) {
    if (cache->head == NULL) {
        cache->head = node;
        cache->tail = node;
    } else {
        node->next = cache->head;
        cache->head->prev = node;
        cache->head = node;
    }
    cache->size++;
    cache->freqList[node->freq] = node;
}

int get(LFUCache* cache, int key) {
    Node* node = cache->freqList[key];
    if (node == NULL) {
        return -1;
    }
    node->freq++;
    if (node != cache->head) {
        deleteNode(cache, node);
        insertNode(cache, node);
    }
    return node->value;
}

void put(LFUCache* cache, int key, int value) {
    if (cache->capacity == 0) {
        return;
    }
    Node* node = cache->freqList[key];
    if (node != NULL) {
        node->value = value;
        node->freq++;
        if (node != cache->head) {
            deleteNode(cache, node);
            insertNode(cache, node);
        }
    } else {
        node = createNode(key, value);
        if (cache->size == cache->capacity) {
            Node* tail = cache->tail;
            deleteNode(cache, tail);
        }
        insertNode(cache, node);
    }
}

void printCache(LFUCache* cache) {
    Node* node = cache->head;
    while (node != NULL) {
        printf("(%d:%d:%d) ", node->key, node->value, node->freq);
        node = node->next;
    }
    printf("\n");
}

int main() {
    LFUCache* cache = createLFUCache(2);
    put(cache, 1, 1);
    put(cache, 2, 2);
    printCache(cache);
    printf("%d\n", get(cache, 1));
    printCache(cache);
    put(cache, 3, 3);
    printCache(cache);
    printf("%d\n", get(cache, 2));
    printf("%d\n", get(cache, 3));
    put(cache, 4, 4);
    printf("%d\n", get(cache, 1));
    printf("%d\n", get(cache, 3));
    printf("%d\n", get(cache, 4));
    printCache(cache);
    return 0;
}

在这个实现中，LFUCache 结构体维护了缓存的大小和容量，以及缓存中每个访问频率的节点。Node 结构体表示缓存中的每个元素。createNode 函数用于创建新节点，insertNode 函数用于将节点插入到缓存中，deleteNode 函数用于从缓存中删除节点，get 函数用于获取缓存中指定键的值，并将节点的访问频率加一，put 函数用于将新元素放入缓存中。最后，printCache 函数用于打印缓存中的所有元素。

在 main 函数中，我们创建一个大小为 2 的 LFU 缓存，向其中插入两个元素，打印缓存中的所有元素，然后获取键为 1 的元素，再次打印缓存中的所有元素，向缓存中插入一个新元素，打印缓存中的所有元素，获取键为 2 和 3 的元素，向缓存中插入一个新元素，并打印缓存中的所有元素。