网站怎么被搜到首页,wordpress 自动保存,网页设计免费网站推荐,培训机构哪家好前言
前面两期数据结构的文章我们介绍了顺序表和单向链表#xff0c;那么本篇博文我们将来了解双向链表#xff0c;作为最好用的一种链表#xff0c;双向链表有什么特殊之处呢#xff0c;接下来就让我们一起了解一下吧。
下面是前两篇数据结构的文章#xff1a;
数据结…前言
前面两期数据结构的文章我们介绍了顺序表和单向链表那么本篇博文我们将来了解双向链表作为最好用的一种链表双向链表有什么特殊之处呢接下来就让我们一起了解一下吧。
下面是前两篇数据结构的文章
数据结构(一)——顺序表的介绍 数据结构(二)——链表的介绍以及单链表的实现
双向链表的概念
什么是双向链表呢实际上双向链表全称是带头双向循环链表是一种最复杂但最好用的一种链表形式它不同于单项链表它拥有一个头节点正是由于头节点的存在弥补了单项链表尾插的不便同时它拥有两个指针分别指向前驱和后继从而方便链表进行数据的挪动等操作。
双向链表的实现
1.定义
目录
前言
双向链表的概念
双向链表的实现
1.定义
2.双向链表接口定义
1.初始化
2.销毁
4.打印
5.尾插/尾删
6.头插/头删
7.任意位置插入/删除
8.查找
小结 typedef int LTDataType;
typedef struct LTNode
{struct LTNode* next;struct LTNode* prev;LTDataType x;
}LTNode;
双向链表的定义如上所示我们发现在这个结构体内我们定义了两个结构体指针分别指向结构体变量双向链表的前驱和后继节点后续我们将通过这个结构体指针完成链表的头插尾插等一系列操作。
2.双向链表接口定义
接下来我们将定义一系列链表的接口通过这些函数我们将完成链表的初始化、销毁、头插、尾插、头删、尾删、打印等一系列操作。
//链表的初始化
void LTInit(LTNode** pphead);
LTNode* LTInit();
//链表的销毁
void LTDestroy(LTNode* phead);
//链表的打印
void LTPrint(LTNode* phead);//链表的尾插
void LTPushBack(LTNode* phead,LTDataType x);
//链表的头插
void LTPushFront(LTNode* phead, LTDataType x);//链表的尾删
void LTPopBack(LTNode* phead);
//链表的头删
void LTPopFront(LTNode* phead);//在指定位置之后插入
void LTInsert(LTNode* pos, LTNode* phead);
//删除指定位置的节点
void LTErase(LTNode* pos);//查找一个值返回相应节点
LTNode* LTFind(LTNode* phead, LTDataType x); 从上述节点的定义我们发现不同于单向链表我们传的大多是一级指针这是为什么呢原因在于双向链表多了一个哨兵位当链表中只有哨兵位时我们称之为空链表即哨兵位是不能删除的而我们大多数操作是不会改变哨兵位的所以只需要传一级指针。
1.初始化
我们看到我们给出了两种链表的初始化方式一种是传二级指针一种则是通过返回值接收下面我们将实现代码如下
void LTInit(LTNode** pphead)
{*pphead (LTDataType*)malloc(sizeof(LTNode));if (*pphead NULL){perror(malloc fail!);exit(1);}(*pphead)-a -1;(*pphead)-next (*pphead)-prev *pphead;
}
首先是二级指针初始化我们看到对二级指针解引用我们可以拿到这个地址然后malloc一块空间最后让前驱节点和后继节点都指向自己这样我们就完成了链表的初始化。但是细心观察我们发现这一段代码的逻辑是先开一块新的节点然后再完成初始化后续我们对链表的插入修改还要用到这一段逻辑因此我们可以把这个逻辑写成申请节点的函数这样既减少了代码量还提高了可读性所以就有了第二种初始化方式代码如下
LTNode* LTBuyNode(LTDataType x)
{//申请一个新的节点LTNode* newnode (LTDataType*)malloc(sizeof(LTNode));if (newnode NULL){perror(malloc fail!);exit(1);}newnode-a x;//让新节点的next prev指针指向自己newnode-next newnode-prev newnode;return newnode;
}
LTNode* LTInit()
{LTNode* phead LTBuyNode(-1);return phead;
}
2.销毁
由于链表的每个节点不是连续的所以我们需要循环销毁每一个节点有了这个逻辑我们就可以写下如下代码
void LTDestroy(LTNode* phead)
{assert(phead);//pcur指向第一个节点LTNode* pcur phead-next;while (pcur ! phead){//记录下一个节点LTNode* next pcur-next;//销毁该节点free(pcur);//让pcur指向下一个节点pcur next;}//销毁哨兵位头节点free(phead);phead NULL;
}
4.打印
与链表销毁类似打印每个节点的值都是先找到该节点然后再将该节点的值打印出来因此我们可以写下如下代码
void LTPrint(LTNode* phead)
{assert(phead);LTNode* pcur phead-next;while (pcur ! phead){printf(%d-, pcur-a);pcur pcur-next;}printf(\n);
}5.尾插/尾删
链表插入删除的关键是改变节点的指针对于尾插而言我们实际上是将该节点插入哨兵位的前面对于尾删而言我们实际上是删除的是哨兵位的前驱节点。因此改变指针指向实际上就是改变哨兵位前驱和后继节点的指向。代码如下
//尾插
void LTPushBack(LTNode* phead, LTDataType x)
{assert(phead);LTNode* newnode LTBuyNode(x);newnode-next phead;newnode-prev phead-prev;phead-prev-next newnode;phead-prev newnode;
}
//尾删
void LTPopBack(LTNode* phead)
{assert(phead);assert(phead-next ! phead);LTNode* del phead-next;LTNode* prve phead-next-prev;phead-prev prve;prve-nextphead;free(del);del NULL;
}
6.头插/头删
//头插
void LTPushFront(LTNode* phead, LTDataType x)
{assert(phead);LTNode* newnode LTBuyNode(x);newnode-next phead-next;newnode-prev phead;phead-next newnode;phead-next-prev newnode;
}
//头删
void LTPopFront(LTNode* phead)
{assert(phead);assert(phead-next ! phead);LTNode* prve phead-next;LTNode* del phead-next-next;phead-next del;del-prev phead;free(prve);prve NULL;
}
这里有个小技巧在我们插入时我们可以先让新节点的前驱和后继节点指向相应位置改变其他指针的指向
7.任意位置插入/删除
我们在有了前面插入删除的逻辑之后我们可以用相同的逻辑如法炮制就可以很快写出任意位置插入删除的代码
void LTInsert(LTNode* pos, LTDataType x)
{assert(pos);LTNode* newnode LTBuyNode(x);newnode-next pos-next;newnode-prev pos;pos-next-prev newnode;pos-next newnode;
}
void LTErase(LTNode* pos)
{assert(pos);pos-next-prev pos-prev;pos-prev-next pos-next;free(pos);pos NULL;
}
8.查找
查找的逻辑十分简单通过遍历链表找到相应元素然后返回当前节点如果没有找到就返回空代码如下
LTNode* LTFind(LTNode* phead, LTDataType x)
{assert(phead);LTNode* pcur phead-next;while (pcur ! phead){if (pcur-a x){return pcur;}}return NULL;
}
小结
冰冻三尺非一日之寒在之后的日子里我会持续更新与数据结构相关的内容如果喜欢的话希望能够点赞关注加转发您的支持就是对我最大的鼓励同时也希望在学习路上的你能够坚持下去半山腰很挤我想去山顶看看。
