网站活泼在哪里做推广效果好

当前位置： 首页 > news >正文

网站活泼,在哪里做推广效果好,如何跑网站建设业务,哪个网站公司做的好LRU缓存机制的C语言实现详解 参考1. 数据结构设计双向链表节点哈希表节点哈希表LRU缓存结构 2. 初始化哈希表和双向链表哈希函数初始化哈希表初始化双向链表创建LRU缓存 3. 更新双向链表4. 实现Get操作5. 实现Put操作更新节点值删除最久未使用节点插入或更新节点 6. 释放缓存释… LRU缓存机制的C语言实现详解 参考1. 数据结构设计双向链表节点哈希表节点哈希表LRU缓存结构 2. 初始化哈希表和双向链表哈希函数初始化哈希表初始化双向链表创建LRU缓存 3. 更新双向链表4. 实现Get操作5. 实现Put操作更新节点值删除最久未使用节点插入或更新节点 6. 释放缓存释放双向链表释放哈希表释放LRU缓存 7. 完整代码及测试测试用例输出结果 总结 参考 建议先参考下面的视频 1. 数据结构设计 双向链表节点 typedef struct DulNode {int key; // 缓存项的键int value; // 缓存项的值struct DulNode* pre; // 前驱节点指针struct DulNode* next; // 后继节点指针 } DulNode;作用维护缓存项的使用顺序最近访问的节点靠近链表头部未使用的节点靠近尾部。 哈希表节点 typedef struct HashTableNode {DulNode* node; // 指向双向链表中的节点struct HashTableNode* next; // 处理哈希冲突的链表指针 } HashTableNode;作用通过哈希表快速定位缓存项键为key值为对应的双向链表节点。 哈希表 typedef struct HashTable {int capacity; // 哈希表容量桶数量hash_cal_f hash_func; // 哈希函数指针HashTableNode** bucket; // 桶数组存储链表头节点 } HashTable;作用以O(1)时间复杂度查找键是否存在结合双向链表实现LRU策略。 LRU缓存结构 typedef struct {int cur_node; // 当前缓存中的节点数HashTable* hash_table; // 哈希表DulNode* head; // 双向链表头节点哨兵DulNode* tail; // 双向链表尾节点哨兵 } Solution;作用整合哈希表和双向链表封装LRU缓存的核心操作。 2. 初始化哈希表和双向链表 哈希函数 int hash_cal(int capacity, int val) {return val % capacity; // 简单取模哈希 }设计意图将键值映射到哈希表的桶索引均匀分布以减少冲突。 初始化哈希表 void InitHashTable(Solution* lruCache, int capacity) {HashTable* hash_table malloc(sizeof(HashTable));hash_table-capacity capacity;hash_table-hash_func hash_cal;hash_table-bucket calloc(capacity, sizeof(HashTableNode));lruCache-hash_table hash_table; }关键点动态分配桶数组并初始化为NULL避免野指针问题。 初始化双向链表 void InitDoubleList(Solution lruCache) {// 创建头尾哨兵节点并连接成环lruCache-head (DulNode)malloc(sizeof(DulNode));lruCache-tail (DulNode)malloc(sizeof(DulNode));lruCache-head-pre lruCache-tail;lruCache-head-next lruCache-tail;lruCache-tail-pre lruCache-head;lruCache-tail-next lruCache-head; }设计优势哨兵节点简化链表操作无需处理头尾边界条件。 创建LRU缓存 Solution* SolutionCreate(int capacity) {Solution* lruCache malloc(sizeof(Solution));lruCache-cur_node 0;InitHashTable(lruCache, capacity);InitDoubleList(lruCache);return lruCache; }流程分配内存后初始化哈希表和双向链表。 3. 更新双向链表 void DulLinkLinkUpdateNode(DulNode* head, DulNode* node) {if (node-pre head) return; // 已在头部无需处理// 摘除节点node-pre-next node-next;node-next-pre node-pre;// 插入到头部node-pre head;node-next head-next;head-next-pre node;head-next node; }作用将节点移动到链表头部表示最近被访问。 4. 实现Get操作 int SolutionGet(Solution* obj, int key) {if (obj-cur_node 0) return -1;int h_index obj-hash_table-hash_func(obj-hash_table-capacity, key);HashTableNode* hash_node obj-hash_table-bucket[h_index];// 遍历哈希冲突链表while (hash_node hash_node-node-key ! key) hash_node hash_node-next;if (hash_node) {DulLinkLinkUpdateNode(obj-head, hash_node-node); // 更新链表return hash_node-node-value;}return -1; }时间复杂度O(1)哈希表平均情况。 5. 实现Put操作 更新节点值 void LRUCacheUpdateNode(Solution* obj, int key, int value) {// 查找并更新值随后移动节点到头部int h_index obj-hash_table-hash_func(obj-hash_table-capacity, key);HashTableNode* hash_node obj-hash_table-bucket[h_index];while (hash_node hash_node-node-key ! key) hash_node hash_node-next;if (hash_node) {hash_node-node-value value;DulLinkLinkUpdateNode(obj-head, hash_node-node);} }删除最久未使用节点 void LRUCacheDelLastNode(Solution* obj) {DulNode* del_node obj-tail-pre; // 尾节点的前驱为LRU节点// 从哈希表中删除int h_index obj-hash_table-hash_func(obj-hash_table-capacity, del_node-key);HashTableNode *pre NULL, cur obj-hash_table-bucket[h_index];while (cur cur-node-key ! del_node-key) {pre cur;cur cur-next;}if (cur) {if (pre) pre-next cur-next;else obj-hash_table-bucket[h_index] cur-next;free(cur);}// 从链表中删除del_node-pre-next del_node-next;del_node-next-pre del_node-pre;free(del_node);obj-cur_node–; }插入或更新节点 void SolutionPut(Solution obj, int key, int value) {if (obj-cur_node obj-hash_table-capacity)LRUCacheDelLastNode(obj); // 缓存满时删除LRU节点if (SolutionGet(obj, key) ! -1) { // Key存在则更新LRUCacheUpdateNode(obj, key, value);return;}// 创建新节点并插入链表头部DulNode* new_dul_node malloc(sizeof(DulNode));new_dul_node-key key;new_dul_node-value value;new_dul_node-pre obj-head;new_dul_node-next obj-head-next;obj-head-next-pre new_dul_node;obj-head-next new_dul_node;// 插入哈希表HashTableNode* new_hash_node malloc(sizeof(HashTableNode));new_hash_node-node new_dul_node;int h_index obj-hash_table-hash_func(obj-hash_table-capacity, key);new_hash_node-next obj-hash_table-bucket[h_index];obj-hash_table-bucket[h_index] new_hash_node; // 头插法obj-cur_node; }6. 释放缓存 释放双向链表 void DulLinkLinkFree(DulNode* head) {DulNode* cur head-next;while (cur ! head) {DulNode* tmp cur;cur cur-next;free(tmp);}free(head-pre); // 释放尾节点free(head); }释放哈希表 void HashTableNodeFree(Solution* obj) {for (int i 0; i obj-hash_table-capacity; i) {HashTableNode* cur obj-hash_table-bucket[i];while (cur) {HashTableNode* tmp cur;cur cur-next;free(tmp);}}free(obj-hash_table-bucket); }释放LRU缓存 void SolutionFree(Solution* obj) {DulLinkLinkFree(obj-head);HashTableNodeFree(obj);free(obj-hash_table);free(obj); }7. 完整代码及测试 测试用例 int main() {Solution* cache SolutionCreate(2);SolutionPut(cache, 1, 1);SolutionPut(cache, 2, 2);printf(Get(1) - %d\n, SolutionGet(cache, 1)); // 1SolutionPut(cache, 3, 3); // 淘汰2printf(Get(2) - %d\n, SolutionGet(cache, 2)); // -1SolutionFree(cache);return 0; }输出结果 Get(1) - 1 Get(2) - -1总结 核心机制通过双向链表维护访问顺序哈希表实现快速查找。时间复杂度Get和Put操作均摊时间复杂度为O(1)。优化点哈希表采用链地址法处理冲突双向链表使用哨兵节点简化操作。适用场景高频访问的缓存系统需快速淘汰最久未使用数据。 反正以我的能力远远不能解决问题。还是只能勉强把代码看懂。这题还是很难得感觉没有一天时间完全搞不定。放弃了放弃了。