C 语言：用双向链表与哈希表实现高效 LRU 缓存及代码示例

以下是一个使用 C 语言实现的结合双向链表和哈希表的 LRU 缓存示例代码： ```c #include <stdio.h> #include <stdlib.h> // 双向链表节点结构体 typedef struct Node { int key; int value; struct Node *prev; struct Node *next; } Node; // 双向链表结构体 typedef struct DoublyLinkedList { Node *head; Node *tail; } DoublyLinkedList; // 创建新的双向链表节点 Node* createNode(int key, int value) { Node* newNode = (Node*)malloc(sizeof(Node)); newNode->key = key; newNode->value = value; newNode->prev = NULL; newNode->next = NULL; return newNode; } // 创建双向链表 DoublyLinkedList* createList() { DoublyLinkedList* list = (DoublyLinkedList*)malloc(sizeof(DoublyLinkedList)); list->head = NULL; list->tail = NULL; return list; } // 将节点添加到双向链表头部 void addToHead(DoublyLinkedList* list, Node* node) { if (list->head == NULL) { list->head = node; list->tail = node; } else { node->next = list->head; list->head->prev = node; list->head = node; } } // 移除双向链表尾部节点 Node* removeTail(DoublyLinkedList* list) { if (list->tail == NULL) { return NULL; } Node* tail = list->tail; if (list->tail->prev!= NULL) { list->tail->prev->next = NULL; list->tail = list->tail->prev; } else { list->head = NULL; list->tail = NULL; } return tail; } // 移动节点到双向链表头部 void moveToHead(DoublyLinkedList* list, Node* node) { if (node == list->head) { return; } if (node == list->tail) { list->tail = node->prev; list->tail->next = NULL; } else { node->prev->next = node->next; node->next->prev = node->prev; } node->next = list->head; node->prev = NULL; list->head->prev = node; list->head = node; } // 哈希表节点结构体 typedef struct HashNode { int key; Node* node; struct HashNode* next; } HashNode; // 哈希表结构体 typedef struct HashTable { HashNode buckets; int capacity; } HashTable; // 创建哈希表 HashTable* createHashTable(int capacity) { HashTable* table = (HashTable*)malloc(sizeof(HashTable)); table->buckets = (HashNode)malloc(capacity * sizeof(HashNode*)); table->capacity = capacity; for (int i = 0; i < capacity; i++) { table->buckets[i] = NULL; } return table; } // 哈希函数 int hashFunction(int key, int capacity) { return key % capacity; } // 在哈希表中查找节点 HashNode* findInHashTable(HashTable* table, int key) { int index = hashFunction(key, table->capacity); HashNode* curr = table->buckets[index]; while (curr!= NULL) { if (curr->key == key) { return curr; } curr = curr->next; } return NULL; } // 在哈希表中插入节点 void insertIntoHashTable(HashTable* table, int key, Node* node) { int index = hashFunction(key, table->capacity); HashNode* newNode = (HashNode*)malloc(sizeof(HashNode)); newNode->key = key; newNode->node = node; newNode->next = table->buckets[index]; table->buckets[index] = newNode; } // LRU 缓存结构体 typedef struct LRUCache { int capacity; DoublyLinkedList* list; HashTable* hashTable; } LRUCache; // 创建 LRU 缓存 LRUCache* createLRUCache(int capacity) { LRUCache* cache = (LRUCache*)malloc(sizeof(LRUCache)); cache->capacity = capacity; cache->list = createList(); cache->hashTable = createHashTable(capacity); return cache; } // 获取缓存中的值 int get(LRUCache* cache, int key) { HashNode* hashNode = findInHashTable(cache->hashTable, key); if (hashNode == NULL) { return -1; } Node* node = hashNode->node; moveToHead(cache->list, node); return node->value; } // 向缓存中添加值 void put(LRUCache* cache, int key, int value) { HashNode* hashNode = findInHashTable(cache->hashTable, key); if (hashNode!= NULL) { Node* node = hashNode->node; node->value = value; moveToHead(cache->list, node); return; } Node* newNode = createNode(key, value); addToHead(cache->list, newNode); insertIntoHashTable(cache->hashTable, key, newNode); if (cache->list->tail!= NULL && cache->list->tail->key!= key) { Node* removedNode = removeTail(cache->list); HashNode* removedHashNode = findInHashTable(cache->hashTable, removedNode->key); if (removedHashNode!= NULL) { int index = hashFunction(removedNode->key, cache->hashTable->capacity); HashNode* curr = cache->hashTable->buckets[index]; if (curr == removedHashNode) { cache->hashTable->buckets[index] = removedHashNode->next; } else { while (curr->next!= removedHashNode) { curr = curr->next; } curr->next = removedHashNode->next; } free(removedHashNode); free(removedNode); } } } // 打印双向链表 void printList(DoublyLinkedList* list) { Node* curr = list->head; while (curr!= NULL) { printf("Key: %d, Value: %d ", curr->key, curr->value); curr = curr->next; } printf("\n"); } // 测试示例 int main() { LRUCache* cache = createLRUCache(2); put(cache, 1, 10); put(cache, 2, 20); printf("Get 1: %d\n", get(cache, 1)); put(cache, 3, 30); printf("Get 2: %d\n", get(cache, 2)); put(cache, 4, 40); printf("Get 1: %d\n", get(cache, 1)); printf("Get 3: %d\n", get(cache, 3)); printf("Get 4: %d\n", get(cache, 4)); return 0; } ``` 这段代码实现了一个简单的 LRU 缓存，使用双向链表维护缓存的访问顺序，使用哈希表加速查找。在 `main` 函数中进行了一些基本的操作和测试。 ######[AI写代码神器 | 1855点数解答 | 2024-11-12 22:46:34]