``` #include <stdio.h> #include <stdlib.h> // 双向链表节点 typedef struct DLinkedNode { int key; int value; struct DLinkedNode* prev; struct DLinkedNode* next; } DLinkedNode; // 哈希表节点（用于处理冲突） typedef struct HashNode { int key; DLinkedNode* cacheNode; struct HashNode* next; } HashNode; // LRU缓存结构体 typedef struct { int capacity; int size; DLinkedNode* head; // 哨兵头节点 DLinkedNode* tail; // 哨兵尾节点 HashNode** hashTable; // 哈希表数组 int hashSize; // 哈希表大小 } LRUCache; // 创建LRU缓存 LRUCache* lRUCacheCreate(int capacity) { LRUCache* cache = (LRUCache*)malloc(sizeof(LRUCache)); cache->capacity = capacity; cache->size = 0; // 初始化双向链表 cache->head = (DLinkedNode*)malloc(sizeof(DLinkedNode)); cache->tail = (DLinkedNode*)malloc(sizeof(DLinkedNode)); cache->head->prev = NULL; cache->head->next = cache->tail; cache->tail->prev = cache->head; cache->tail->next = NULL; // 初始化哈希表 cache->hashSize = capacity * 2; // 简化处理哈希表大小 cache->hashTable = (HashNode**)calloc(cache->hashSize, sizeof(HashNode*)); return cache; } // 哈希表辅助函数 DLinkedNode* findInHashTable(LRUCache* obj, int key) { int idx = key % obj->hashSize; HashNode* entry = obj->hashTable[idx]; while (entry != NULL) { if (entry->key == key) { return entry->cacheNode; } entry = entry->next; } return NULL; } void insertIntoHashTable(LRUCache* obj, int key, DLinkedNode* node) { int idx = key % obj->hashSize; HashNode* newEntry = (HashNode*)malloc(sizeof(HashNode)); newEntry->key = key; newEntry->cacheNode = node; newEntry->next = obj->hashTable[idx]; obj->hashTable[idx] = newEntry; } void removeFromHashTable(LRUCache* obj, int key) { int idx = key % obj->hashSize; HashNode* curr = obj->hashTable[idx]; HashNode* prev = NULL; while (curr != NULL) { if (curr->key == key) { if (prev == NULL) { obj->hashTable[idx] = curr->next; } else { prev->next = curr->next; } free(curr); return; } prev = curr; curr = curr->next; } } // 链表操作辅助函数 void moveToHead(LRUCache* obj, DLinkedNode* node) { // 断开原链接 node->prev->next = node->next; node->next->prev = node->prev; // 插入头部 node->prev = obj->head; node->next = obj->head->next; obj->head->next->prev = node; obj->head->next = node; } void addToHead(LRUCache* obj, DLinkedNode* node) { node->prev = obj->head; node->next = obj->head->next; obj->head->next->prev = node; obj->head->next = node; } DLinkedNode* removeTail(LRUCache* obj) { DLinkedNode* node = obj->tail->prev; node->prev->next = obj->tail; obj->tail->prev = node->prev; return node; } // 获取缓存值 int lRUCacheGet(LRUCache* obj, int key) { DLinkedNode* node = findInHashTable(obj, key); if (node == NULL) return -1; moveToHead(obj, node); // 更新为最近使用 return node->value; } // 插入缓存值 void lRUCachePut(LRUCache* obj, int key, int value) { DLinkedNode* node = findInHashTable(obj, key); if (node != NULL) { // 存在则更新 node->value = value; moveToHead(obj, node); } else { // 不存在则新建 DLinkedNode* newNode = (DLinkedNode*)malloc(sizeof(DLinkedNode)); newNode->key = key; newNode->value = value; insertIntoHashTable(obj, key, newNode); addToHead(obj, newNode); obj->size++; // 超过容量则淘汰尾部 if (obj->size > obj->capacity) { DLinkedNode* tailNode = removeTail(obj); removeFromHashTable(obj, tailNode->key); free(tailNode); obj->size--; } } } // 释放缓存 void lRUCacheFree(LRUCache* obj) { // 释放链表节点 DLinkedNode* curr = obj->head->next; while (curr != obj->tail) { DLinkedNode* tmp = curr; curr = curr->next; free(tmp); } free(obj->head); free(obj->tail); // 释放哈希表 for (int i = 0; i < obj->hashSize; i++) { HashNode* entry = obj->hashTable[i]; while (entry != NULL) { HashNode* tmp = entry; entry = entry->next; free(tmp); } } free(obj->hashTable); free(obj); }```给出这段代码的完整形式，包括头文件，输出输出，输入输出要求可以在控制台自由控制，并给出代码详细的注释

<think>嗯，用户给了一段用C语言实现的LRU缓存代码，现在需要补充完整的头文件、输入输出处理，并且让用户可以在控制台自由控制。首先，我得仔细看看用户提供的代码结构，理解各个部分的功能。 首先，用户的代码已经定义了LRUCache的结构体，包括双向链表和哈希表。然后有创建缓存、哈希表操作、链表操作、get和put函数，以及释放缓存的函数。但缺少main函数和输入输出的处理部分。 接下来，我需要添加main函数，让用户能够通过控制台输入命令，比如get和put操作。用户可能需要输入类似“put 1 1”或者“get 1”这样的指令，所以需要解析这些输入。同时，输出需要显示操作结果，比如执行get后返回的值，或者缓存已满时的淘汰情况。 然后，头文件方面，用户已经包含了stdio.h和stdlib.h，可能还需要string.h来处理字符串分割，因为需要将输入的指令按空格分割成命令和参数。比如用strtok函数来分割输入的字符串。 另外，用户提供的代码中，哈希表处理可能存在潜在的问题。比如，哈希表的大小设置为capacity的两倍，这在冲突处理上可能不够高效，但用户可能只是简化处理，所以暂时保持原样。需要注意在插入和删除哈希表节点时的正确性。 在添加main函数时，需要处理用户输入的循环，直到用户输入exit为止。每个输入行需要解析命令，判断是put、get还是其他操作。例如，对于put命令，需要提取key和value，调用lRUCachePut函数；对于get命令，提取key并调用lRUCacheGet，然后输出结果。 此外，在释放缓存的时候，用户提供的lRUCacheFree函数是否正确释放了所有内存？需要检查是否有内存泄漏。比如，哈希表中的每个条目都需要遍历链表逐个释放，双向链表也需要释放所有节点，这部分代码用户已经写了，可能没问题。 还有，输入错误处理需要考虑，比如用户输入的命令格式不正确，或者参数不是整数，这时候需要给出提示，而不是让程序崩溃。因此，在解析输入时，应该检查参数的数量和类型是否正确。 比如，当用户输入“put 1 a”时，第二个参数应该是整数，但这里输入了字母a，程序应该提示错误。这可以通过检查sscanf的返回值来判断是否成功转换参数。 然后，关于代码注释，用户要求详细的注释，所以需要在添加的main函数和输入处理部分加上注释，解释每一步的作用。比如，解释如何解析输入命令，如何处理不同的操作，以及如何调用相应的LRU缓存函数。 测试用例方面，可能需要考虑各种情况，比如缓存满时的淘汰策略是否正确，最近访问的节点是否被移动到头部等。但用户可能只需要代码能运行，输入输出正确，所以这部分可能在注释中说明即可。 最后，将所有部分整合成一个完整的代码，包括头文件、结构体定义、函数实现、main函数和输入输出处理。确保代码编译运行无误，并且符合用户的要求。</think>以下是为您补充完整并添加详细注释的LRU缓存实现代码： ```c #include <stdio.h> #include <stdlib.h> #include <string.h> // 用于字符串处理 /* 双向链表节点结构体 */ typedef struct DLinkedNode { int key; // 键 int value; // 值 struct DLinkedNode* prev; // 前驱指针 struct DLinkedNode* next; // 后继指针 } DLinkedNode; /* 哈希表节点结构体（链地址法处理冲突） */ typedef struct HashNode { int key; // 键 DLinkedNode* cacheNode; // 指向对应的缓存节点 struct HashNode* next; // 下一个哈希节点 } HashNode; /* LRU缓存结构体 */ typedef struct { int capacity; // 缓存容量 int size; // 当前缓存大小 DLinkedNode* head; // 哨兵头节点 DLinkedNode* tail; // 哨兵尾节点 HashNode** hashTable; // 哈希表数组 int hashSize; // 哈希表大小 } LRUCache; /* 创建LRU缓存 */ LRUCache* lRUCacheCreate(int capacity) { LRUCache* cache = (LRUCache*)malloc(sizeof(LRUCache)); cache->capacity = capacity; cache->size = 0; // 初始化双向链表（带哨兵节点） cache->head = (DLinkedNode*)malloc(sizeof(DLinkedNode)); cache->tail = (DLinkedNode*)malloc(sizeof(DLinkedNode)); cache->head->prev = NULL; cache->head->next = cache->tail; cache->tail->prev = cache->head; cache->tail->next = NULL; // 初始化哈希表（大小为容量的2倍以减少冲突） cache->hashSize = capacity * 2; cache->hashTable = (HashNode**)calloc(cache->hashSize, sizeof(HashNode*)); return cache; } /* 哈希表查找辅助函数 */ DLinkedNode* findInHashTable(LRUCache* obj, int key) { int idx = key % obj->hashSize; // 简单哈希函数 HashNode* entry = obj->hashTable[idx]; while (entry != NULL) { if (entry->key == key) { return entry->cacheNode; // 找到对应节点 } entry = entry->next; } return NULL; // 未找到 } /* 哈希表插入辅助函数 */ void insertIntoHashTable(LRUCache* obj, int key, DLinkedNode* node) { int idx = key % obj->hashSize; HashNode* newEntry = (HashNode*)malloc(sizeof(HashNode)); newEntry->key = key; newEntry->cacheNode = node; newEntry->next = obj->hashTable[idx]; // 头插法 obj->hashTable[idx] = newEntry; } /* 哈希表删除辅助函数 */ void removeFromHashTable(LRUCache* obj, int key) { int idx = key % obj->hashSize; HashNode* curr = obj->hashTable[idx]; HashNode* prev = NULL; while (curr != NULL) { if (curr->key == key) { if (prev == NULL) { // 删除的是头节点 obj->hashTable[idx] = curr->next; } else { prev->next = curr->next; } free(curr); return; } prev = curr; curr = curr->next; } } /* 将节点移动到链表头部（表示最近使用） */ void moveToHead(LRUCache* obj, DLinkedNode* node) { // 从原位置断开连接 node->prev->next = node->next; node->next->prev = node->prev; // 插入到头部哨兵节点之后 node->prev = obj->head; node->next = obj->head->next; obj->head->next->prev = node; obj->head->next = node; } /* 添加新节点到链表头部 */ void addToHead(LRUCache* obj, DLinkedNode* node) { node->prev = obj->head; node->next = obj->head->next; obj->head->next->prev = node; obj->head->next = node; } /* 移除链表尾部节点（最近最少使用） */ DLinkedNode* removeTail(LRUCache* obj) { DLinkedNode* node = obj->tail->prev; node->prev->next = obj->tail; obj->tail->prev = node->prev; return node; } /* 获取缓存值 */ int lRUCacheGet(LRUCache* obj, int key) { DLinkedNode* node = findInHashTable(obj, key); if (node == NULL) return -1; moveToHead(obj, node); // 更新为最近使用 return node->value; } /* 插入/更新缓存值 */ void lRUCachePut(LRUCache* obj, int key, int value) { DLinkedNode* node = findInHashTable(obj, key); if (node != NULL) { // 已存在则更新 node->value = value; moveToHead(obj, node); } else { // 新建节点 DLinkedNode* newNode = (DLinkedNode*)malloc(sizeof(DLinkedNode)); newNode->key = key; newNode->value = value; insertIntoHashTable(obj, key, newNode); addToHead(obj, newNode); obj->size++; // 超过容量时淘汰尾部节点 if (obj->size > obj->capacity) { DLinkedNode* tailNode = removeTail(obj); removeFromHashTable(obj, tailNode->key); free(tailNode); obj->size--; } } } /* 释放缓存 */ void lRUCacheFree(LRUCache* obj) { // 释放双向链表节点 DLinkedNode* curr = obj->head->next; while (curr != obj->tail) { DLinkedNode* tmp = curr; curr = curr->next; free(tmp); } free(obj->head); free(obj->tail); // 释放哈希表 for (int i = 0; i < obj->hashSize; i++) { HashNode* entry = obj->hashTable[i]; while (entry != NULL) { HashNode* tmp = entry; entry = entry->next; free(tmp); } } free(obj->hashTable); free(obj); } /* 控制台交互界面 */ int main() { int capacity; printf("请输入LRU缓存容量："); scanf("%d", &capacity); getchar(); // 吸收换行符 LRUCache* cache = lRUCacheCreate(capacity); printf("缓存创建成功！\n"); printf("支持命令：\n"); printf("1. get [key] - 查询缓存值\n"); printf("2. put [key] [value] - 插入缓存值\n"); printf("3. exit - 退出程序\n"); char command[20]; while (1) { printf("\n> "); fgets(command, sizeof(command), stdin); command[strcspn(command, "\n")] = '\0'; // 去除换行符 // 解析命令 char* token = strtok(command, " "); if (token == NULL) continue; if (strcmp(token, "get") == 0) { // 处理get命令 int key; if (sscanf(strtok(NULL, " "), "%d", &key) == 1) { int value = lRUCacheGet(cache, key); if (value != -1) { printf("Key %d 的值为：%d\n", key, value); } else { printf("Key %d 不存在\n", key); } } else { printf("参数错误！格式：get [key]\n"); } } else if (strcmp(token, "put") == 0) { // 处理put命令 int key, value; char* keyStr = strtok(NULL, " "); char* valueStr = strtok(NULL, " "); if (keyStr && valueStr && sscanf(keyStr, "%d", &key) == 1 && sscanf(valueStr, "%d", &value) == 1) { lRUCachePut(cache, key, value); printf("已插入键值对 (%d, %d)\n", key, value); } else { printf("参数错误！格式：put [key] [value]\n"); } } else if (strcmp(token, "exit") == 0) { break; } else { printf("未知命令！支持命令：get/put/exit\n"); } } lRUCacheFree(cache); printf("缓存已释放，程序退出\n"); return 0; } ``` ### 使用说明 1. **输入要求**： - 启动时输入缓存容量（正整数） - 支持三种命令： - `get [key]`：查询指定键的值 - `put [key] [value]`：插入/更新键值对 - `exit`：退出程序 2. **输出说明**： - 执行`get`命令时显示值或不存在提示 - 执行`put`命令时显示插入结果 - 自动处理缓存淘汰，无需手动操作 3. **功能特点**： - 使用双向链表维护访问顺序 - 哈希表实现$O(1)$时间复杂度的查找 - 自动淘汰最近最少使用的条目 - 内存管理完善，避免内存泄漏 4. **示例操作**： ```bash 请输入LRU缓存容量：2 缓存创建成功！ 支持命令： 1. get [key] - 查询缓存值 2. put [key] [value] - 插入缓存值 3. exit - 退出程序 > put 1 10 已插入键值对 (1, 10) > put 2 20 已插入键值对 (2, 20) > get 1 Key 1 的值为：10 > put 3 30 # 触发淘汰 已插入键值对 (3, 30) > get 2 Key 2 不存在 ``` ### 实现原理 1. **数据结构**： - 双向链表：维护访问顺序，头节点表示最近访问 - 哈希表：通过$key \rightarrow node$映射实现快速访问 2. **核心操作**： - `get`操作：通过哈希表查找，命中后移动节点到链表头部 - `put`操作：更新或插入节点，维护容量限制 3. **复杂度分析**： - 时间复杂度：$O(1)$ 对于所有操作 - 空间复杂度：$O(n)$，其中$n$为缓存容量 该实现通过结合哈希表的快速访问和双向链表的顺序维护，完整实现了LRU缓存机制。