链表之“带头双向循环链表”

���录

​编辑

1.链表的分类

2.带头双向循环链表的实现

1.创建结构体

2.创建返回链表的头节点

3.双向链表销毁

4.双向链表打印

5.双向链表尾插

6.双向链表尾删

7.双向链表头插

8.双向链表头删

9.双向链表查找

10.双向链表在pos的前面进行插入

11.双向链表删除pos位置的节点

3.源码

 4.顺序表和链表的区别

---

1.链表的分类

        链表会根据是单向或者双向，带头或者不带头，循环或者非循环进行分类组合。以上情况组合起来就有8种链表结构。

其中，头指针和头节点是两个概念：

• 头指针： 它是一个指针，指向链表中第一个节点的地址。
• 头节点：它是一个结构体，区分数据域和指针域。数据域不存储元素，指针域则存放第一个节点的地址。
  • 无头单向非循环链表：结构简单，一般不会单独用来存数据。实际中更多是作为其他数据结构的子结构，如哈希桶、图的邻接表等等。
  • 带头双向循环链表：带头是指链表最前面有一个头节点，它是一个结构体变量，分为数据域和指针域，数据域一般不存储数据，指针域存放的是第一个元素的地址。双向是指一个节点中有两个指针域，一个叫前驱指针，指向当前节点的前一个节点的指针，用于向前遍历；一个叫后继指针，指向当前节点的后一个节点的指针，用于向后遍历。循环是指链表最后一个节点的指针域存放的是头节点的地址，这样一来，整个链表就形成了循环的效果。

    2.带头双向循环链表的实现

    1.创建结构体

    因为是带头双向循环链表，所以我们要定义两个指针，一个前驱指针，指向当前节点的前一个节点；还有一个后继指针，指向当前节点的后一个节点。

    typedef int LTDataType;typedef struct ListNode{struct ListNode* next;//后继指针struct ListNode* prev;//前驱指针LTDataType val;}LTNode;

    2.创建返回链表的头节点

    //返回创建链表的头节点LTNode* CreateLTNode(LTDataType x){LTNode* newnode = (LTNode*)malloc(sizeof(LTNode));if (newnode == NULL){perror("malloc");exit(-1);}newnode->val = x;newnode->next = NULL;newnode->prev = NULL;return newnode;}

    3.双向链表销毁

    //销毁void LTDestory(LTNode* phead){assert(phead);LTNode* cur = phead->next;while (cur != phead){LTNode* next = cur->next;free(cur);cur = next;}free(phead);}

    4.双向链表打印

    要想打印链表中的值，就得找到跳出循环的条件。因为哨兵位不存储有效的值，所以我们可以定义一个cur变量，让它指向哨兵位的下一个节点，如果cur != phead，就打印值，直到cur走到哨兵位就跳出循环。

    //打印void LTPrint(LTNode* phead){assert(phead);LTNode* cur = phead->next;printf("哨兵位");while (cur != phead){printf("%d", cur->val);cur = cur->next;}printf("\n");}

    5.双向链表尾插

    带哨兵位的头节点不可能为空，哪怕链表一个值都没有，它也是指向自己的，所以要断言一下。尾插的第一步首先要找到尾，双向链表中找尾非常简单，哨兵位的前一个节点phead->prev就是尾，然后将尾节点tail的后继指针指向新节点newnode，新节点newnode的前驱指针指向tail；再将新节点newnode的后继指针指向哨兵位phead，哨兵位phead的前驱指针指向新节点newnode。

    //尾插void LTPushBack(LTNode* phead, LTDataType x){assert(phead);LTNode* tail = phead->prev;//找尾节点LTNode* newnode = CreateLTNode(x);//phead       tail   newnodetail->next = newnode;newnode->prev = tail;newnode->next = phead;phead->prev = newnode;}

    6.双向链表尾删

    因为哨兵位不可能为空，所以还是得先断言一下。当链表为空时，我们不能在进行尾删，但是此时链表里边还有个哨兵位，我们得保证不能将哨兵位也删掉，所以哨兵位也得断言一下，因为链表为空时哨兵位是指向它自己的，所以断言的条件应该写成assert(phead->next != phead)。尾删时一样得先找到尾，即哨兵位得前一个节点phead->prev，因为要free掉尾，所以还得找到尾的前一个节点tailprev = tail->prev。这两个都找到后，先free掉tail，然后让tail的前一个节点tailprev的后继指针指向哨兵位phead，再让哨兵位phead的前驱指针指向tailpeev。

    //尾删void LTPopBack(LTNode* phead){assert(phead);assert(phead->next != phead);LTNode* tail = phead->prev;LTNode* tailprev = tail->prev;free(tail);tailprev->next = phead;phead->prev = tailprev;}

    7.双向链表头插

    头插时我们先搞一个新节点newnode出来，然后将newnode与哨兵位和第一个节点链接起来就可以了。但是这儿得注意一下，我们要先将newnode与第一个节点链接，然后再将哨兵位与newnode链接，如果先将哨兵位与newnode链接容易找不到第一个节点，就会很麻烦。

    //头插void LTPushFront(LTNode* phead, LTDataType x){assert(phead);LTNode* newnode = CreateLTNode(x);//第1种方法//newnode->next = phead->next;//phead->next->prev = newnode;//phead->next = newnode;//newnode->prev = phead;//第2种方法LTNode* first = phead->next;newnode->next = first;first->prev = newnode;phead->next = newnode;newnode->prev = phead;}

    8.双向链表头删

    头删时我们还得注意链表不能为空的情况，即哨兵位不能被删掉，所以还得断言assert(phead->next != phead)。只有销毁链表的时候才能将哨兵位free掉。

    //头删void LTPopFront(LTNode* phead){assert(phead);assert(phead->next != phead);LTNode* first = phead->next;LTNode* second = first->next;phead->next = second;second->prev = phead;free(first);first = NULL;}

    9.双向链表查找

    查找可以配合其它函数来使用，如果找到了，就返回那个节点的地址，找不到，则返回空。

    //查找LTNode* LTFind(LTNode* phead, LTDataType x){assert(phead);LTNode* cur = phead->next;while (cur != phead){if (cur->val == x){return cur;}cur = cur->next;}return NULL;}

    10.双向链表在pos的前面进行插入

    将这个函数写完后，我们在回过头看头插、尾插，发现头插、尾插刚好可以利用这个函数以一种更简便的方式来实现。LTInsert(phead->next, x)就是头插，因为phead的下一个节点刚好就是头节点，在头节点的前面插入就是头插；LTInsert(phead, x)就是尾插，因为phead的前一个节点刚好就是尾。

    //在pos的前面进行插入void LTInsert(LTNode* pos, LTDataType x){assert(pos);LTNode* posprev = pos->prev;LTNode* newnode = CreateLTNode(x);posprev->next = newnode;newnode->prev = posprev;newnode->next = pos;pos->prev = newnode;}

    11.双向链表删除pos位置的节点

    这个删除操作也可以用来头删和尾删，头删就是LTErase(phead->next)，尾删就是LTErase(phead->prev)。

    //删除pos的值void LTErase(LTNode* pos){assert(pos);LTNode* posprev = pos->prev;LTNode* posnext = pos->next;posprev->next = posnext;posnext->prev = posprev;free(pos);}

    3.源码

    List.h

    #pragma once#include #include #include typedef int LTDataType;typedef struct ListNode{struct ListNode* next;//后继指针struct ListNode* prev;//前驱指针LTDataType val;}LTNode;//初始化LTNode* LTInit();//返回创建链表的头节点LTNode* CreateLTNode(LTDataType x);//打印void LTPrint(LTNode* phead);//尾插void LTPushBack(LTNode* phead, LTDataType x);//尾删void LTPopBack(LTNode* phead);//头插void LTPushFront(LTNode* phead, LTDataType x);//头删void LTPopFront(LTNode* phead);//查找LTNode* LTFind(LTNode* phead, LTDataType x);//在pos的前面进行插入void LTInsert(LTNode* pos, LTDataType x);//删除pos的值void LTErase(LTNode* pos);//销毁void LTDestory(LTNode* phead);

     List.c

    #include "List.h"//初始化LTNode* LTInit(){LTNode* phead = CreateLTNode(-1);phead->next = phead;phead->prev = phead;return phead;}//返回创建链表的头节点LTNode* CreateLTNode(LTDataType x){LTNode* newnode = (LTNode*)malloc(sizeof(LTNode));if (newnode == NULL){perror("malloc");exit(-1);}newnode->val = x;newnode->next = NULL;newnode->prev = NULL;return newnode;}//打印void LTPrint(LTNode* phead){assert(phead);LTNode* cur = phead->next;printf("哨兵位");while (cur != phead){printf("%d", cur->val);cur = cur->next;}printf("\n");}//尾插void LTPushBack(LTNode* phead, LTDataType x){assert(phead);//第1种方法LTNode* tail = phead->prev;//找尾节点LTNode* newnode = CreateLTNode(x);tail->next = newnode;newnode->prev = tail;newnode->next = phead;phead->prev = newnode;//第2种方法//LTInsert(phead, x);}//尾删void LTPopBack(LTNode* phead){assert(phead);assert(phead->next != phead);//第1种写法LTNode* tail = phead->prev;LTNode* tailprev = tail->prev;free(tail);tailprev->next = phead;phead->prev = tailprev;//第2种写法//LTErase(phead->prev);}//头插void LTPushFront(LTNode* phead, LTDataType x){assert(phead);LTNode* newnode = CreateLTNode(x);//第1种方法//newnode->next = phead->next;//phead->next->prev = newnode;//phead->next = newnode;//newnode->prev = phead;//第2种方法LTNode* first = phead->next;newnode->next = first;first->prev = newnode;phead->next = newnode;newnode->prev = phead;//第3种方法//LTInsert(phead->next, x);}//头删void LTPopFront(LTNode* phead){assert(phead);assert(phead->next != phead);//第1种写法LTNode* first = phead->next;LTNode* second = first->next;phead->next = second;second->prev = phead;free(first);first = NULL;//第2种写法//LTErase(phead->next);}//查找LTNode* LTFind(LTNode* phead, LTDataType x){assert(phead);LTNode* cur = phead->next;while (cur != phead){if (cur->val == x){return cur;}cur = cur->next;}return NULL;}//在pos的前面进行插入void LTInsert(LTNode* pos, LTDataType x){assert(pos);LTNode* posprev = pos->prev;LTNode* newnode = CreateLTNode(x);posprev->next = newnode;newnode->prev = posprev;newnode->next = pos;pos->prev = newnode;}//删除pos的值void LTErase(LTNode* pos){assert(pos);LTNode* posprev = pos->prev;LTNode* posnext = pos->next;posprev->next = posnext;posnext->prev = posprev;free(pos);}//销毁void LTDestory(LTNode* phead){assert(phead);LTNode* cur = phead->next;while (cur != phead){LTNode* next = cur->next;free(cur);cur = next;}free(phead);}

     4.顺序表和链表的区别