[数据结构与算法]C语言----设计LRU缓存结构

?用双向链表，头插法，思路很简单链表头是最常访问的地方，链表尾是最不常访问的地方：

1，如果操作为1，说明要加入到链表，插入到表头

2，如果操作为2，说明节点被访问，从当前节点删除并移动到表头

????????其中要考虑到缓冲区的大小，即链表长度，如果加入前链表长度已经到了最大，则需要删除链表尾节点，再加入

/**
 * 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 返回数组行数
 */
#define FALSE 0
#define TRUE 1
typedef struct LruLink
{
    int key;
    int value;
    struct LruLink *pre;
    struct LruLink *next;
}LruLink;
int addNodeToLink(LruLink *head,int key, int value)
{
    LruLink *node = (LruLink *)malloc(sizeof(LruLink));
    if(node == NULL)
        return FALSE;
    node->key = key;
    node->value = value;
    if(head ->next == NULL)
    {
        node ->next = head ->next;
        head ->next = node;
        node ->pre = head;
    }
    else
    {
        node ->next = head->next;
        head ->next->pre = node;
        node ->pre = head;
        head ->next = node;
    }
    
    return TRUE;
}
void delTail(LruLink *head)
{
    LruLink *p = head->next;
    while( p != NULL)
    {
        if(p->next == NULL)
        {
            p->pre->next = NULL;
            p->pre = NULL;
            free(p);
        }
        p = p->next;
    }
}
int getNode(LruLink *head,int key)
{
    LruLink *p = head;
    while(p != NULL)
    {
        if(p->key == key)
        {
            if(p->next == NULL)
            {
                p->pre->next = NULL;
                p ->next = head->next;
                head ->next->pre = p;
                p ->pre = head;
                head ->next = p;
            }
            else
            {
                p->next->pre = p->pre;
                p->pre->next = p->next;
                p ->next = head->next;
                head ->next->pre = p;
                p ->pre = head;
                head ->next = p;
            }
            return p->value;
        }
        p = p->next;
    }
    return -1;
}

int* LRU(int** operators, int operatorsRowLen, int* operatorsColLen, int k, int* returnSize ) 
{
    // write code here
    LruLink *pHead = (LruLink *)malloc(sizeof(LruLink));
    LruLink *pIndex;
    pHead -> next = NULL;
    int LruLinkLen = 0;
    int *retArr = (int *)malloc(sizeof(int)*operatorsRowLen);
    int retLen = 0;
    memset(retArr,0,operatorsRowLen);
    
    int i = 0,j=0;
    for(i=0; i<operatorsRowLen; i++)
    {
        if(operators[i][0] == 1)
        {
            //头插法插入到表头,表头始终为最常用的,如果缓存队列满则删除队尾节点
            if(0 == k)
            {
                delTail(pHead);
                addNodeToLink(pHead,operators[i][1],operators[i][2]);
            }
            else
            {
                addNodeToLink(pHead,operators[i][1],operators[i][2]);
                k--;
            }
        }
        else if(operators[i][0] == 2)
        {
            //查找操作，如果没找到输出-1，如果找到将节点移动到头
            retArr[retLen++] = getNode(pHead,operators[i][1]);
        }
    }
    for (pIndex = pHead->next; pIndex != NULL; pIndex = pIndex->next)
    {
        free(pIndex);
    }
    free(pHead);
    if (returnSize)
    {
        *returnSize = retLen;
    }
    return retArr;
}

?

?

关注博主即可阅读全文