提供了编程的基础技术教程

zl程序教程

您现在的位置是：首页 >  Java

当前栏目

单循环链表-这么好的单链表结构怎么能不会呢？带哨兵位头节点双向循环链表

2023-02-18 16:46:38 时间

  带头循环双向链表

  优势是什么

  先看看长啥样子

  每一个节点都记录该节点的前后的节点，这会有什么好处呢？

  头插头删，尾插尾删特别方便时间复杂度都是O(1)

  另一个优势是既能从前往后走，又能从后往前走。

  带哨兵位头节点双向循环链表的基本操作

  这一次，会写的规范一点。

  准备3个文件，一个头件，一个链表操作文件，一个主函数所在的文件，和通讯录那一篇设计是一样的。

  H:带头，D:双向，Loop:循环，List:链表

  

   #include

    #include
    #include
    typedef int LTDataType;
    typedef struct ListNode
    {
        LTDataType _data;
        struct ListNode* _next;
        struct ListNode* _prev;
    }ListNode;
    //开辟+初始化头节点
    ListNode* AollocListNode(int x);
    // 双向链表销毁
    void ListDestory(ListNode* pHead);
    // 双向链表打印
    void ListPrint(ListNode* pHead);
    // 双向链表尾插
    void ListPushBack(ListNode* pHead, LTDataType x);
    // 双向链表尾删
    void ListPopBack(ListNode* pHead);
    // 双向链表头插
    void ListPushFront(ListNode* pHead, LTDataType x);
    // 双向链表头删
    void ListPopFront(ListNode* pHead);
    // 双向链表查找
    ListNode* ListFind(ListNode* pHead, LTDataType x);
    // 双向链表在pos的前面进行插入
    void ListInsert(ListNode* pos, LTDataType x);
    // 双向链表删除pos位置的节点
    void ListErase(ListNode* pos, ListNode* pHead);

  开辟节点+初始化

  申请一个节点，并初始化。

  有下面两种形式，但当链表为空的时候，是成环的，建议用下面一种。

  这样设计以后函数形参中的指针是不可为NULL的，可以加一个assert判断一下。

   ListNode* AollocListNode(LTDataType x)

    {
        ListNode* newnode = (ListNode*)malloc(sizeof(ListNode));
        newnode->_data = x;
        newnode->_next = newnode;
        newnode->_prev = newnode;
        return newnode;
    }

  打印

  这里需要另外一个指针遍历去遍历链表，当回到头节点的时候即结束，如果使用pHead去遍历，那就死循环了。

   void ListPrint(ListNode* pHead)

    {
        ListNode* p = pHead->_next;//指向第一个节点
        while (p != pHead)
        {
            printf("%d->", p->_data);
            p = p->_next;
        }
        printf("NULL\n");
    }

  销毁

  销毁链表，释放所有节点

  循环中，先把除头节点外的所有节点删除，出了循环再删除头节点。

  循环结束的条件和打印一样，当指向头节点的时候就结束了

  删除一个节点，指针的指向怎么改变呢？

  拷贝第一个节点，头节点指向指向第二个节点，第二个节点指向头节点，指向完成后，就可以删除了。

   void ListDestory(ListNode* pHead)

    {
        assert(pHead);
        while (pHead->_next != pHead)
        {
            struct ListNode* t = pHead->_next;//先记录要被释放的节点(第一个节点)
            pHead->_next = t->_next;
            t->_next->_prev = pHead;
            free(t);
        }
        free(pHead);
    }

  插入 头插

  头插指的是在头节点后面插入一个新的节点作为第一个节点。

  改变指向有两种形式，一种是再来一个临时变量记录中间节点。另一种是在原有的变量种改变指向。

  这里详细介绍原有变量改变指向

  ①②顺序可以颠倒

  有两种形式去找原第一个节点，可以通过，也可以通过头节点。

  通过头节点去找原第一个节点，③④顺序不可颠倒。通过去找原第一个节点，③④顺序无所谓。

  ④：pHead->_next =

  ③：pHead->_next->_prev =

  先执行④单循环链表，pHead->_next不再指向原第一个节点

   void ListPushFront(ListNode* pHead, LTDataType x)

    {
        assert(pHead);
        ListNode* newnode = AollocListNode(x);
        newnode->_prev = pHead;
        newnode->_next = pHead->_next;
        pHead->_next->_prev = newnode;
        pHead->_next = newnode;
        //newnode->_next->_prev = newnode;
    }

  有中间变量的形式

  这样看起来逻辑会更清晰，但我还是会用上面一种，要多用才多熟悉，这些指针指向，所以下面我都是不用中间变量的。

   void ListPushFront(ListNode* pHead, LTDataType x)

    {
        assert(pHead);
        ListNode* newnode = AollocListNode(x);
        ListNode* t = pHead->_next;//记录原第一个节点
        newnode->_next = t;
        t->_prev = newnode;
        pHead->_next = newnode;
        newnode->_prev = pHead;
    }

  尾插

  尾插：的下一个指向的是头节点，一种是靠pHead，另一种是靠原最后一个节点去找头节点。组合方式很多不一一列举，不创建另外的变量记录原最后一个节点时，原最后一个节点改变指向之前，头节点的指向不能动。

   void ListPushBack(ListNode* pHead, LTDataType x)

    {
        assert(pHead);
        ListNode* newnode = AollocListNode(x);
        newnode->_next = pHead;
        newnode->_prev = pHead->_prev;
        
        pHead->_prev->_next = newnode;//原最后一个节点 指向新节点
        pHead->_prev = newnode;//头节点指向新节点
    }

  删除 头删

  这个很简单了，就是刚刚销毁操作，不带循环，当个快乐的cv工程师吧。

   void ListPopFront(ListNode* pHead)

    {
        assert(pHead);
        ListNode* t = pHead->_next;//记录第一个节点
        pHead->_next = t->_next;
        t->_next->_prev = pHead;
        free(t);
    }

  尾删

  也很简单，记录最后一个节点，在将倒数第二个节点和头节点相互连接，再去释放。

   void ListPopBack(ListNode* pHead)

    {
        assert(pHead);
        ListNode* t = pHead->_prev;//记录最后一个节点
        t->_prev->_next = pHead;
        pHead->_prev = t->_prev;
        free(t);
    }

  找并返回地址，pos接收

  通过data找节点，再把节点的地址返回。在通过这个pos执行下面两个操作。

  循环结束的条件是回到了头节点。

   ListNode ListFind(ListNode pHead, LTDataType x)

    {
        assert(pHead);
        ListNode* p = pHead->_next;//指向第一个节点
        while (p != pHead)
        {
            if (x == p->_data)
                return p;
            p = p->_next;
        }
        return NULL;
    }

  在pos前插入

  双向单链表的优势来了，只要知道地址，不需要遍历，可以直接插入，时间复杂度O(1)。如果是单向的，还要找前驱。

  需要对pos判断一下不能为NULL

   void ListInsert(ListNode* pos, LTDataType x)

    {
        assert(pos);
        ListNode* newnode = AollocListNode(x);
        newnode->_next = pos;
        newnode->_prev = pos->_prev;
        pos->_prev->_next = newnode;
        pos->_prev = newnode;
    }

  删除在pos前的节点

  删除的时同样要注意pos不能为NULL。不能删除头节点单循环链表，不然主函数中的头指针会非法访问。

   void ListErase(ListNode pos, ListNode pHead)

    {
        assert(pos);
        assert(pos->_prev != pHead);//判断pos前一个节点不为头节点
        ListNode* t = pos->_prev;//记录pos前一个节点
        t->_prev->_next = pos;
        pos->_prev = t->_prev;
        free(t);
    }

  .c

   #include"HDLoopList.h"

    //开辟+初始化节点
    ListNode* AollocListNode(LTDataType x)
    {
        ListNode* newnode = (ListNode*)malloc(sizeof(ListNode));
        newnode->_data = x;
        newnode->_next = newnode;
        newnode->_prev = newnode;
        return newnode;
    }
    void ListPrint(ListNode* pHead)
    {
        ListNode* p = pHead->_next;//指向第一个节点
        while (p != pHead)
        {
            printf("%d->", p->_data);
            p = p->_next;
        }
        printf("NULL\n");
    }
    void ListDestory(ListNode* pHead)
    {
        assert(pHead);
        while (pHead->_next != pHead)
        {
            struct ListNode* t = pHead->_next;//先记录要被释放的节点(第一个节点)
            pHead->_next = t->_next;
            t->_next->_prev = pHead;
            free(t);
        }
        free(pHead);
    }
    void ListPushFront(ListNode* pHead, LTDataType x)
    {
        assert(pHead);
        ListNode* newnode = AollocListNode(x);
        newnode->_prev = pHead;
        newnode->_next = pHead->_next;
        pHead->_next->_prev = newnode;
        pHead->_next = newnode;
        //newnode->_next->_prev = newnode;
    }
    //void ListPushFront(ListNode* pHead, LTDataType x)
    //{
    //    ListNode* newnode = AollocListNode(x);
    //    ListNode* t = pHead->_next;
    //
    //    newnode->_next = t;
    //    t->_prev = newnode;
    //
    //    pHead->_next = newnode;
    //    newnode->_prev = pHead;
    //}
    void ListPushBack(ListNode* pHead, LTDataType x)
    {
        assert(pHead);
        ListNode* newnode = AollocListNode(x);
        newnode->_next = pHead;
        newnode->_prev = pHead->_prev;
        
        pHead->_prev->_next = newnode;//原最后一个节点 指向新节点
        pHead->_prev = newnode;//头节点指向新节点
    }
    void ListPopFront(ListNode* pHead)
    {
        assert(pHead);
        ListNode* t = pHead->_next;//记录第一个节点
        pHead->_next = t->_next;
        t->_next->_prev = pHead;
        free(t);
    }
    void ListPopBack(ListNode* pHead)
    {
        assert(pHead);
        ListNode* t = pHead->_prev;//记录最后一个节点
        t->_prev->_next = pHead;
        pHead->_prev = t->_prev;
        free(t);
    }
    ListNode* ListFind(ListNode* pHead, LTDataType x)
    {
        assert(pHead);
        ListNode* p = pHead->_next;//指向第一个节点
        while (p != pHead)
        {
            if (x == p->_data)
                return p;
            p = p->_next;
        }
        return NULL;
    }
    void ListInsert(ListNode* pos, LTDataType x)
    {
        assert(pos);
        ListNode* newnode = AollocListNode(x);
        newnode->_next = pos;
        newnode->_prev = pos->_prev;
        pos->_prev->_next = newnode;
        pos->_prev = newnode;
    }
    void ListErase(ListNode* pos, ListNode* pHead)
    {
        assert(pos);
        assert(pos->_prev != pHead);//判断pos前一个节点不为头节点
        ListNode* t = pos->_prev;//记录pos前一个节点
        t->_prev->_next = pos;
        pos->_prev = t->_prev;
        free(t);
    }

  test.c

#include"HDLoopList.h"
int main()
{
    ListNode* phead = NULL;
    phead = AollocListNode(0);
    for (int i = 1; i 
[1]: https://xuan.ddwoo.top/index.php/archives/372/
[2]: https://xuan.ddwoo.top/index.php/archives/368/                
        本文共 1179 个字数,平均阅读时长 ≈ 3分钟

相关文章