好的网站开发培训,中企动力z邮箱登录手机端,怎么自己做网站qq,沙田镇网站仿做#x1f525;引言 本篇将介绍带头双向循环链表底层实现以及在实现中需要注意的事项#xff0c;帮助各位在使用过程中根据底层实现考虑到效率上问题和使用时可能会导致的错误使用 #x1f308;个人主页#xff1a;是店小二呀 #x1f308;C语言笔记专栏#xff1a;C语言笔… 引言 本篇将介绍带头双向循环链表底层实现以及在实现中需要注意的事项帮助各位在使用过程中根据底层实现考虑到效率上问题和使用时可能会导致的错误使用 个人主页是店小二呀 C语言笔记专栏C语言笔记 C笔记专栏 C笔记 初阶数据结构笔记专栏 初阶数据结构笔记
喜欢的诗句:无人扶我青云志 我自踏雪至山巅 文章目录 一、前文二、实现带头双向循环链表2.1 认识头节点2.2 链表中节点成员2.3 创建双向循环链表的节点2.4 双向循环链表的插入节点2.4.1 双向循环链表的尾插 2.4.2 双向循环链表的头插 2.5 双向循环链表的删除节点2.5.1 双向循环链表的尾删2.5.2 双向循环链表的头删 2.6 双向循环链表的查找2.7 实现双向循环链表任意位置的插入和删除2.7.1 任意位置插入2.7.2 任意位置删除 2.8 双向循环链表的打印 三、双向循环链表的好处 一、前文
链表的分类有很多种只需要将无头单向非循环链表和带头双向循环链表掌握也就理解了剩下链表构成和实现。带头双向循环链表结构复杂一般只用于单独存储数据。但是也由于结构带来了很多的优势从而复杂结构反而简单低实现。
二、实现带头双向循环链表
2.1 认识头节点
头节点(哨兵位)是指链表里面第一个节点它不存放任何信息或存储任何有效元素起到放哨作用作用是减少了对一个节点是否为空的判断。
对于之前实现的单链表是不带哨兵位的但是称第一个节点为头节点是不规范的但是那样方便学习中称呼。
2.2 链表中节点成员
首先节点的成员:有效带数值前驱指针后继指针 前驱指针:以当前节点为参照物向左就是前驱指针 后继指针以当前节点为参照物向右就是后继指针
typedef int LTDataType;//处理不同的数据类型typedef struct SLTlistNode
{LTDataType val;struct SLTlistNode* next;struct SLTlistNode* prev;}SLNode;2.3 创建双向循环链表的节点
SLNode* CreatNewNode(LTDataType x)
{SLNode* newnode (SLNode*)malloc(sizeof(SLNode));if (newnode NULL){perror(malloc fail!);return ;}newnode-next newnode;newnode-prev newnode;newnode-val x;return newnode;
}这里需要注意的是:跟实现单链表的节点大体相同。但是需要前驱指针后继指针都指向自己设计为一个闭环在插入中这样子的设计有很好的优势
2.4 双向循环链表的插入节点
2.4.1 双向循环链表的尾插
void SLTPushBack(SLNode* head, LTDataType x)
{assert(head);SLNode* newnode CreatNewNode(x);SLNode* tail head-prev;//尾插需要找到尾tail-next newnode;newnode-prev tail;head-prev newnode;newnode-next head;
}这里需要注意的是:由于一开始哨兵位就是循环体一开始创建指向尾的指针也是指向自己这种结构具有很好的优势维持闭环的状态在进行插入或删除操作时提供了便利。当进行尾插时需要找到尾再进行尾插操作。
2.4.2 双向循环链表的头插
void SLTPushFront(SLNode* head, LTDataType x)//双向循环链表无空指针
{assert(head); if (head-nexthead){SLTPushBack(head, x);}else{SLNode* newnode CreatNewNode(x);SLNode* tail head-prev;head-next newnode;newnode-prev head;newnode-next tail;tail-prev newnode;}
}这里需要注意的是 : 头插是值第一个有效数据节点前面插入不是在哨兵位前面进行插入。当只有哨兵位存在时这里跟尾插操作是一样的剩下跟单链表的任意位置插入差不多主要是改变指针的指向
2.5 双向循环链表的删除节点
2.5.1 双向循环链表的尾删
void SLTPopBack(SLNode* head)//哨兵位不删
{assert(head);assert(head-next!head);SLNode* tail head-prev;SLNode* tailprev tail-prev;tailprev-next head;head-prev tailprev;free(tail);tail NULL;
}这里需要注意的是:哨兵位不参与对节点进行操作时对此不对哨兵位进行删除操作。由于循环体虽然没有空指针但是可能会出现野指针现象。可以不置空free(tail)不对tail指向空间进行访问。
2.5.2 双向循环链表的头删
void SLTPopFront(SLNode* head)
{assert(head);SLNode* cur head-next;SLNode* curnext cur-next;if (head-next head){return 1;}else{head-next curnext;curnext-prev head;free(cur);cur NULL;}
} 这里需要注意的是:哨兵位不参与对节点进行操作时对此不对哨兵位进行删除操作。双向循环的优势在此体现出来了只需在cur和curnext位置上处理。
2.6 双向循环链表的查找
SLNode* SLFind(SLNode* head, LTDataType x)
{assert(head);SLNode* cur head-next;while (cur!head){if (cur-val x){return cur;}cur cur-next;}return NULL;
}这里需要注意的是:当curhead时说明cur遍历完了链表。如果没有符合的值则表示不存在反之返回该位置的指针。
2.7 实现双向循环链表任意位置的插入和删除
2.7.1 任意位置插入
void SLInsert(SLNode* head, SLNode* pos,LTDataType x)//之前插入
{assert(head);SLNode* posprve pos-prev;if (head-next head){SLTPushBack(head,x);}else{SLNode* newnode CreateLTNode(x);posprve-next newnode;newnode-prev posprve;pos-prev newnode;newnode-next pos; }
}这里需要注意的是:当不存在有效数据时默认是尾插操作。具体实现逻辑知道pos和posprev的地址再通过改变指针完成链接 2.7.2 任意位置删除
void SLEmpty(SLNode* head, SLNode* pos, LTDataType x)
{assert(pos ! head);assert(head);SLNode* posprve pos-prev;SLNode* frist posprve-prev;if (cur-next head){SLTPopBack(head);}else{frist-next pos;pos-prev frist;free(posprve);}
}这里需要注意的是:哨兵位不参与对节点进行操作时对此不对哨兵位进行删除操作。只存在一个有效数据时只进行尾删操作即可。对于三个指针的位置关系满足pos在两个指针之间
以上就是双向循环链表的核心接口接下来实现一些实用小接口丰富我们的双向循环链表
2.8 双向循环链表的打印
void SLTPrint(SLNode* head)
{assert(head);printf(哨兵位-);SLNode* cur head-next;while (cur ! head ){printf(%d-, cur-val);cur cur-next;}
}
##2.9 双向循环链表的销毁
void SLDestroy(SLNode* head)
{assert(head);SLNode* cur head-next;//结束条件是什么这里是无死角的--先销毁哨兵位之外的空间while (cur!head){SLNode* curnext cur-next;free(cur);cur curnext;}free(head);
}这里需要注意的是:先将除哨兵位之外的空间释放最后在释放哨兵位
三、双向循环链表的好处
在实现过程中我们清晰地知道如果需要快速搭建一个链表实现双向循环链表中任意插入、删除是很快的这里利用到了结构特点。 以上就是本篇文章的所有内容在此感谢大家的观看这里是店小二初阶数据结构笔记希望对你在学习初阶数据结构中有所帮助
