DS线性表之带头双向循环链表的讲解和实现(3)
前言
前文所讲的是不带头单向不循环链表，三个条件都相反的带头循环链表就是我们今天所要讲的内容
它也很常用，所以我们有必要好好了解它一下
一、带头双向循环链表的理解
头节点的认识
我们可以发现，所谓的“带头”就是比单链表多一个看似“无用”的头节点，该节点不存储任何信息或存储任何有效元素，起到"放哨"作用，作用是减少了对一个节点是否为空的判断
所以，带头双向循环链表也是要初始化的
二、带头双向循环链表的实现
嗯，理解就这么结束了，乐~
节点成员
因为不仅有后驱指针，也有前驱指针，才能达到所需要的双向，所以我们的节点内容要稍微修改一下：
typedef int LTDataType;//定义数据类型，可以根据需要更改
typedef struct ListNode
{
LTDataType data; //数据域 存储数据
struct ListNode* next;//指针域 存储指向下一个结点的指针
struct ListNode* prev;//指针域 存储指向前一个结点的指针
}ListNode;
申请一个新节点
我们先实现一个申请新节点函数，而不是先考虑初始化，这是因为初始化其实也要申请一个新的节点
ListNode* BuyList(LTDataType x)
{
ListNode* newnode = (ListNode*)malloc(sizeof(ListNode));
if (newnode == NULL)
{
printf("malloc fail\n");
exit(-1);
}
newnode->data = x;
newnode->next = NULL;
newnode->prev = NULL;
return newnode;
}
初始化
此链表的初始化就是创建一个头节点，注意因为是双向循环的，所以对于只有一个哨兵节点的链表来说，不管是前驱指针还是后驱指针，都是指向自己的，这可能需要你结合下图来理解一下：
ListNode* ListInit()
{
ListNode* phead = BuyList(0); // 数字随便取，不重要，指针指对就行
phead->next = phead;//构成循环
phead->prev = phead;//构成循环
return phead;
}
销毁
尤其要注意这个循环的条件，不是cur所指向空，cur在这里由于循环的缘故永远不会指向为空的，而是cur不为头节点的时候，就说明还有节点没被销毁，而出了循环之后，头节点也是节点，也要手动销毁并置空指针
先将除哨兵位之外的空间释放，最后在释放哨兵位
void ListDestory(ListNode* phead)
{
assert(phead);
ListNode* cur = phead->next;
while (cur != phead)
{
ListNode* next = cur->next;
free(cur);
cur = next;
}
free(phead);
phead = NULL; //养成好习惯，释放之后手动置为NULL
}
尾插
好，这个时候你就会发现循环的优势了，之前我们要从头节点开始遍历到尾部，而这里我们直接通过哨兵节点的前驱指针直接来到了最后一个节点，这时候再插入就很方便了
void ListPushBack(ListNode* phead, LTDataType x)
{
assert(phead);
//1.创建结点
ListNode* newnode = BuyList(x);
ListNode* tail = phead->prev;//先找到尾结点
//2.链接next
tail->next = newnode;
newnode->prev = tail;
//3.链接prev
newnode->next = phead;
phead->prev = newnode;
}
头插
这也很方便，因为有哨兵节点的缘故，即使我们的链表没有一个有效数据，下列代码也适用
void ListPushFront(ListNode* phead, LTDataType x)
{
assert(phead);
ListNode* newnode = BuyList(x);
ListNode* first = phead->next;
phead->next = newnode;
newnode->prev = phead;
newnode->next = first;
first->prev = newnode;
}
头删
这里就不仅要检查一下哨兵节点的存在，也要检验一下是否有有效数据了，不然的话，就要把哨兵位给删掉了，这是我们所不愿看到的
void ListPopFront(ListNode* phead)
{
assert(phead);
assert(phead->next != phead);//没有数据则报错
ListNode* first = phead->next;
ListNode* second = first->next;
phead->next = second;
second->prev = phead;
free(first);
first = NULL;
}
尾删
同样要检查一下是否真的有有效数据
void ListPopBack(ListNode* phead)
{
assert(phead);
assert(phead->next != phead);
ListNode* tail = phead->prev;
ListNode* prev = tail->prev;
prev->next = phead;
phead->prev = prev;
free(tail);
tail = NULL;
}
查找
遍历一遍链表，如果该结点的data等于x则返回该结点的地址，遍历一遍没有找到则返回NULL，跟后面在pos位置插入函数结合起来用
ListNode* ListFind(ListNode* phead, LTDataType x)
{
assert(phead);
ListNode* cur = phead->next;
while (cur != phead)
{
if (cur->data == x)
{
return cur;
}
cur = cur->next;
}
return NULL;
}
在pos之前插入
跟头插尾插思想差不多，可以自己画图理解理解，先ListFind找到所要插入的位置，再执行插入操作
void ListInsert(ListNode* pos, LTDataType x)
{
assert(pos);
ListNode* newnode = BuyList(x);
ListNode* prev = pos->prev;
prev->next = newnode;
newnode->prev = prev;
newnode->next = pos;
pos->prev = newnode;
}
删除pos位置
也是要先ListFind找到节点的地址
void ListErase(ListNode* pos)
{
assert(pos);
ListNode* prev = pos->prev;
ListNode* next = pos->next;
prev->next = pos->next;
next->prev = prev;
}
判断链表是否为空
还是要注意这里的判断条件不是cur是否指向空，而是是否指向自身
bool ListEmpty(ListNode* phead)
{
assert(phead);
return phead->next == phead;//相等则为真，不相等则为假
}
总结
我们发现此链表虽然听起来复杂，但是实现起来竟然比单链表好很多，这其实启发我们不要被事物的表面所吓到，说不定再撑一会儿，就拨云见日了呢~
原文地址：https://blog.csdn.net/2301_80392199/article/details/142906549
免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！