数据结构与算法之美day 6: 如何实现LRU缓存淘汰算法?

绝地灬酷狼 2022-03-29 10:00 177阅读 0赞

### 文章目录 ###

*  单链表的相关操作 c语言实现

# 单链表的相关操作 c语言实现 #

其中有两个重要的算法需要注意

*  判断链表是否有环
 *  翻转链表

#include <stdio.h>
    
    struct single_list {
        struct single_list *next;
        int val;
    };
    
    struct single_list_head{
        struct single_list *head;
    };
    
    bool is_empty(struct single_list_head *head)
    {
        return head->head == NULL;
    }
    
    //删除节点，传入的是节点的地址
    struct single_list* del(struct single_list **prev)
    {
        struct single_list *tmp;
        if (!prev)
            return NULL;
        tmp = *prev;
        //将节点指向的节点后移一位实现删除
        *prev = (*prev)->next;
        tmp->next = NULL;
        return tmp;
    }
    
    //删除头结点
    struct single_list* delete_head(struct single_list_head* head)
    {
        return del(&head->head);
    }
    
    
    
    //采用的是头插法进行列表的建立
    void insert(struct single_list **prev, struct single_list *elem)
    {
        if (!prev)
        {
            return;
        }
        if (*prev)
        {
            elem->next = *prev;
        }
        *prev = elem;
    }
    
    //在头结点之前插入数据
    void insert_head(struct single_list_head *head, struct single_list *elem)
    {
        insert(&head->head, elem);
    }
    
    //显示链表中的内容
    void dump(struct single_list_head *head)
    {
        struct single_list *tmp = head->head;
        int idx = 0;
        while(tmp)
        {
            printf("[%02d]: %08d\n", idx++, tmp->val);
            tmp = tmp->next;
        }
    }
    
    //查找节点值为target的节点位置
    struct single_list** search(struct single_list_head *head, int target)
    {
        struct single_list **prev, *tmp;
        for (prev = &head->head, tmp = *prev; \
             tmp && (tmp->val < target); \
             prev = &tmp->next, tmp = *prev)
            ;
        return prev;
    }
    
    //获取链表中间的节点
    struct single_list* middle(struct single_list_head* head)
    {
        struct single_list *s1, *s2;
        struct single_list pseudo_head;
        pseudo_head.next = head->head;
        s1 = s2 = &pseudo_head;
        while (true)
        {
            if (!s2 || !s2->next)
                return s1;
            s1 = s1->next;
            s2 = s2->next->next;
        }
        return NULL;
    }
    
    //判断列表是否有环，快慢指针
    bool is_cyclic(struct single_list_head* head)
    {
        struct single_list *s1, *s2;
        s1 = s2 = head->head;
        while(s1 && s2)
        {
            s1 = s1->next;
            //如果s2->next非空，则s2 = s2->next->next，否则s2 = s2->next
            s2 = s2->next ? s2->next->next : s2->next;
            if (s1 == s2)
            {
                return true;
            }
        }
        return false;
    }
    
    //翻转链表
    void reverse(struct single_list_head* head)
    {
        struct single_list_head tmp = {NULL};
        struct single_list *elem;
    
        while(!is_empty(head))
        {
            elem = delete_head(head);
            insert_head(&tmp, elem);
        }
        head->head = tmp.head;
    }
    
    
    int main()
    {
        struct single_list_head head = {NULL};
        struct single_list lists[10];
        struct single_list **prev;
        int idx;
        for (idx = 0; idx < 10; idx++)
        {
            lists[idx].val = idx;
            lists[idx].next = NULL;
        }
        insert_head(&head, &lists[6]);
        insert_head(&head, &lists[5]);
        insert_head(&head, &lists[4]);
        insert_head(&head, &lists[1]);
        insert_head(&head, &lists[0]);
    
        printf("== insert 0, 1, 4, 5, 6\n");
        dump(&head);
        //由于当前链表中没有2,所有最后找到的是4所在的位置
        prev = search(&head, 2);
        printf("find %d\n", (*prev)->val);
        insert(prev, &lists[2]);
        printf("=== insert 2\n");
        dump(&head);
        printf("middle elem is %d\n", middle(&head)->val);
        //找到值为2的节点
        prev = search(&head, 2);
        if ((*prev) && ((*prev)->val == 2))
            printf("The list contains 2\n");
        else
            printf("The list not contains 2\n");
        //删除节点为2
        printf("prev is %d\n", (*prev)->val);
    
        //prev 存放的是值为2的节点的地址
        del(prev);
        prev = search(&head, 2);
        printf("After remove 2\n");
        if ((*prev) && ((*prev)->val == 2))
            printf("The list contains 2\n");
        else
            printf("The list not contains 2\n");
        dump(&head);
        printf("After reverse \n");
        //翻转链表
        reverse(&head);
        dump(&head);
        printf("middle elem is %d\n", middle(&head)->val);
        lists[0].next = &lists[6];
        printf("list is %s cycic\n", is_cyclic(&head) ? "" : " not");
        return 0;
    }

运行结果：

== insert 0, 1, 4, 5, 6
    [00]: 00000000
    [01]: 00000001
    [02]: 00000004
    [03]: 00000005
    [04]: 00000006
    find 4
    === insert 2
    [00]: 00000000
    [01]: 00000001
    [02]: 00000002
    [03]: 00000004
    [04]: 00000005
    [05]: 00000006
    middle elem is 2
    The list contains 2
    prev is 2
    After remove 2
    The list not contains 2
    [00]: 00000000
    [01]: 00000001
    [02]: 00000004
    [03]: 00000005
    [04]: 00000006
    After reverse 
    [00]: 00000006
    [01]: 00000005
    [02]: 00000004
    [03]: 00000001
    [04]: 00000000
    middle elem is 4
    list is  cycic