算法题设计LRU缓存结构(c语言)_c语言设计lru(最近最少使用)缓存结构,该结构在构造时确定一小,假设大小为 capacit

c语言实现LRU缓存结构

LRU缓存结构
LRU是Least Recently Used的缩写，即最近最少使用，是一种常用的页面置换算法，选择最近最久未使用的页面予以淘汰。

题目描述
设计LRU缓存结构，该结构在构造时确定大小，假设大小为K，并有如下两个功能
set(key, value)：将记录(key, value)插入该结构
get(key)：返回key对应的value值
[要求]
set和get方法的时间复杂度为O(1)
某个key的set或get操作一旦发生，认为这个key的记录成了最常使用的。
当缓存的大小超过K时，移除最不经常使用的记录，即set或get最久远的。
若opt=1，接下来两个整数x, y，表示set(x, y)
若opt=2，接下来一个整数x，表示get(x)，若x未出现过或已被移除，则返回-1
对于每个操作2，输出一个答案

具体思路：
链表结构能够实现快速的插入和删除，但不利于查找
哈希表可以实现快速查找
用哈希表和双向链表结合来实现LRU结构
（1）对于get操作，首先判断key是否存在：如果key不存在，则返回一1
如果key存在，则key对应的节点是最近被使用的节点。通过哈希表定位到该节点在双向链表中的位置，并将其移动到双向链表的头部，最后返回该节点的值。
（2）对于set 操作，首先判断key是否存在：如果key 不存在，创建一个新的节点，在双向链表的头部添加该节点，并将key和该节点添加进哈希表中。然后判断双向链表的节点数是否超出容量，如果超出容量，则删除双向链表的尾部节点，并删除哈希表中对应的项；。如果key存在，则与get操作类似，先通过哈希表定位，再将对应的节点的值更新为value，并将该节点移到双向链表的头部。

本代码在牛客网上提交出现段错误，我也不知道为啥，求大佬指点

/*双向链表数据结构*/
typedef struct node {
   
    int val;
    int key;
    struct node* pre;
    struct node* next;
}LinkList;

/*哈希表数据结构*/
typedef struct hashnode{
   
    LinkList* store;  //用来存放数据  
    struct hashnode* next;    //用于拉链法解决数据冲突
} Hash;

/*LRU数据结构*/
typedef struct {
   
    int curSize;    //当前缓存大小
    int capacity;    //缓存容量
    Hash* hashTable;    //哈希表
    LinkList* head;    //指向最近使用的数据
    LinkList* tail;    //指向最久未使用的数据
} LRUCache;

/*哈希映射*/
Hash* hashMap(Hash* table,int key,int capacity)
{
   
    int addr = key%capacity;
    return &table[addr];
}

/*双链表头插法*/
void headInset(LinkList* head,LinkList* cur)
{
   
    if(cur->pre==NULL && cur->next==NULL)//节点不存在链表中
    {
   
        cur->pre = head;
        cur->next = head->next;      
        head->next->pre = cur;
        head->next = cur;
    }
    else    //节点在链表中
    {
   
        if(head->next 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50