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 != cur)    //cur不是第一个节点
        {
            //将cur前一个节点和cur后一个节点拼接
            cur->pre->next = cur->next;
            cur->next->pre = cur->pre;
            
            //插入头部
            cur->pre = head;
            cur->next = head->next;      
            head->next->pre = cur;
            head->next = cur;
        }
    }
}

/*创建LRU内存块*/
LRUCache* LRUCacheCreate(int capacity)
{
    //创建内存
    LRUCache* lruObj = (LRUCache*)malloc(sizeof(LRUCache));
    lruObj->hashTable = (Hash*)malloc(sizeof(Hash) * capacity);
    memset(lruObj->hashTable, 0, sizeof(Hash) * capacity);    //初始为0   
    lruObj->head = (LinkList*)malloc(sizeof(LinkList));
    lruObj->tail = (LinkList*)malloc(sizeof(LinkList));
    //初始化链表头尾
    lruObj->head->pre = NULL;
    lruObj->head->next = lruObj->tail;
    lruObj->tail->pre = lruObj->head;
    lruObj->tail->next = NULL;
    //初始化大小、容量
    lruObj->curSize = 0;
    lruObj->capacity = capacity;
    
    return lruObj;
}

/*查找函数*/
int lruGet(LRUCache* obj,int key)
{
    Hash* addr = hashMap(obj->hashTable, key, obj->capacity);
    addr = addr->next;    //跳过头节点
    if(addr==NULL)    //不存在
    {
        return -1;
    }
    while(addr->next!=NULL && addr->store->key!=key)
    {    //遍历哈希地址相同的哈希链表找到相同的key
        addr = addr->next;
    }
    if(addr->store->key == key)    //查找成功
    {
        headInset(obj->head, addr->store);    //更新至列表头部
        return addr->store->val;
    }
    return -1;
    
}

/*存放函数*/
void lruSet(LRUCache* obj,int key,int value)
{
    Hash* addr = hashMap(obj->hashTable, key, obj->capacity);    //获取哈希地址
    if(lruGet(obj, key) == -1)    //没有相同的key
    {
        if(obj->curSize >= obj->capacity)    //LRU缓存满了
        {
            //删除尾部节点
            LinkList* last = obj->tail->pre->pre;
            LinkList* del = obj->tail->pre;    //要删除的节点
            last->next = obj->tail;
            obj->tail->pre = last;
            
            /*从哈希表中删除该key对应的节点*/
            //找到要删除的地址
            Hash* deladdr = hashMap(obj->hashTable, del->key, obj->capacity);
            Hash* temp = deladdr;    //?????
            //在拉链上找到最久远的key即del->key
            deladdr = deladdr->next;
            while(deladdr->store->key != del->key)
            {
                temp = deladdr;
                deladdr = deladdr->next;
            }
            temp->next = deladdr->next;
            deladdr->next = NULL;
            deladdr->store = NULL;
            free(deladdr);
            //插入新节点
            Hash* new_insert = (Hash*)malloc(sizeof(Hash));
            new_insert->next = addr->next;
            addr->next = new_insert;
            del->key = key;
            del->val = value;
            new_insert->store = del;
            headInset(obj->head, new_insert->store);
        }
        else    //LRU缓存未满
        {
            Hash* new_node = (Hash*)malloc(sizeof(Hash));
            new_node->store = (LinkList*)malloc(sizeof(LinkList));
            new_node->next = addr->next;
            addr->next = new_node;
            new_node->store->pre = NULL;
            new_node->store->next = NULL;
            new_node->store->key = key;
            new_node->store->val = value;
            headInset(obj->head, new_node->store);
            (obj->curSize++);
        }
    }
    else    //有相同的key值，直接替换
    {
        //执行lruGet（）函数如果找成功会将节点放在链表头部
        obj->head->next->val = value;
    }
}

void lruCacheFree(LRUCache* obj)
{
    free(obj->hashTable);
    free(obj->head);
    free(obj->tail);
    free(obj);
    
}

/**
 * lru design
 * @param operators int整型二维数组 the ops
 * @param operatorsRowLen int operators数组行数
 * @param operatorsColLen int* operators数组列数
 * @param k int整型 the k
 * @return int整型一维数组
 * @return int* returnSize 返回数组行数
 */
int* LRU(int** operators, int operatorsRowLen, int* operatorsColLen, int k, int* returnSize ) {
    LRUCache* obj = LRUCacheCreate(k);
    int* retbuff = (int*)malloc(operatorsRowLen*sizeof(int));
    int j = 0;
    int value = 0;
    for(int i=0;i<operatorsRowLen;i++)
    {
        if(operators[i][0] == 1)
        {
            lruSet(obj, operators[i][1],operators[i][2]);
        }
        else
        {
            retbuff[j] = lruGet(obj, operators[i][1]);
            j++;
        }
        
    }
    lruCacheFree(obj);
    *returnSize = j;
    return retbuff;
 
}