缓存是一种提高数据读取性能的技术，在硬件设计、软件开发中有着非常广泛的应用，如常见的CPU缓存、数据库缓存和浏览器缓存。 缓存的大小有限，当缓存被填满时，哪些数据应该被清理？哪些数据应该被保留？这就需要缓存淘汰算法来决定。 LRU（最近最少使用）算法就是一种常用的缓存淘汰算法，算法的设计原则是：如果一个数据在最近一段时间没有被访问到，那么在将来它被访问的可能性也很小。也就是说，当限定的空间已存满数据时，应当把最久没有被访问到的数据淘汰。 我们可以用一个数据结构来维护缓存，访问新的数据时，若缓存未满，可以直接放入缓存，若缓存已满，删除最久未访问的数据后再放入新的数据。当再次访问缓存中已有的数据时，将该数据调整为最新访问。 即该数据结构可能需要做频繁的插入和删除操作，请完成以下问题： （1）为该数据结构设计一种存储结构，用C语言写出类型定义，每个成员加上注释，其中数据定义为int类型。 （2）使用（1）中定义的存储结构，实现LRU算法中的插入新数据操作（需要考虑缓存已满和未满两种情况），自行定义函数名和参数。

(1) 一种存储结构的类型定义如下：

typedef struct {
    int key;    // 数据的键值
    int value;  // 数据的值
    struct Node *prev;  // 指向前驱节点的指针
    struct Node *next;  // 指向后继节点的指针
} Node;

typedef struct {
    int capacity;  // 缓存的容量
    int size;      // 缓存中已有数据的数量
    Node *head;    // 指向链表头部的指针
    Node *tail;    // 指向链表尾部的指针
    Node **hash;   // 指向哈希表的指针
} LRUCache;

(2) 插入新数据操作的实现如下，我们假设LRUCache中的哈希表采用开放地址法实现：

void put(LRUCache* cache, int key, int value) {
    Node *node = cache->hash[key % cache->capacity];  // 找到哈希表中对应的节点
    if(node == NULL) {  // 如果节点不存在，说明缓存中没有该数据
        node = malloc(sizeof(Node));  // 创建一个新的节点
        node->key = key;  // 设置节点的键值
        node->value = value;  // 设置节点的值
        node->prev = NULL;  // 设置节点的前驱指针为空
        node->next = cache->head;  // 设置节点的后继指针指向链表头部
        if(cache->head != NULL) {  // 如果链表不为空
            cache->head->prev = node;  // 将链表头部节点的前驱指针指向新节点
        } else {
            cache->tail = node;  // 如果链表为空，将链表尾部指针指向新节点
        }
        cache->head = node;  // 将链表头部指针指向新节点
        cache->hash[key % cache->capacity] = node;  // 将新节点插入哈希表中
        cache->size++;  // 缓存大小加1
        if(cache->size > cache->capacity) {  // 如果缓存已满
            Node *tail = cache->tail;  // 找出链表尾部节点
            cache->tail = tail->prev;  // 将链表尾部指针指向倒数第二个节点
            cache->tail->next = NULL;  // 将倒数第二个节点的后继指针置为空
            cache->hash[tail->key % cache->capacity] = NULL;  // 将链表尾部节点在哈希表中的位置置为空
            free(tail);  // 释放链表尾部节点的内存空间
            cache->size--;  // 缓存大小减1
        }
    } else {  // 如果节点存在，说明缓存中已有该数据
        node->value = value;  // 更新节点的值
        if(node != cache->head) {  // 如果节点不在链表头部，需要将节点移动到链表头部
            node->prev->next = node->next;  // 将节点的前驱节点的后继指针指向节点的后继节点
            if(node->next != NULL) {  // 如果节点不在链表尾部
                node->next->prev = node->prev;  // 将节点的后继节点的前驱指针指向节点的前驱节点
            } else {
                cache->tail = node->prev;  // 如果节点在链表尾部，将链表尾部指针指向节点的前驱节点
            }
            node->prev = NULL;  // 将节点的前驱指针置为空
            node->next = cache->head;  // 将节点的后继指针指向链表头部
            cache->head->prev = node;  // 将链表头部节点的前驱指针指向节点
            cache->head = node;  // 将链表头部指针指向节点
        }
    }
}