制作京东网站建设,网站制作哪里好,如何制作app应用,游戏行业seo整站优化双链表及其基本操作的实现 导言一、单链表与双链表二、双链表类型的创建三、双链表的初始化四、双链表的创建五、双链表的遍历六、双链表的查找七、双链表的插入八、双链表的删除结语 导言
大家好#xff0c;很高兴又和大家见面啦#xff01;#xff01;#xff01;
经过… 双链表及其基本操作的实现 导言一、单链表与双链表二、双链表类型的创建三、双链表的初始化四、双链表的创建五、双链表的遍历六、双链表的查找七、双链表的插入八、双链表的删除结语 导言
大家好很高兴又和大家见面啦
经过前面几个篇章的内容分享相信大家对顺序表和单链表的基本操作都已经熟练掌握了。今天咱们将继续分享线性表的链式存储的第二种形式——双链表。在今天的内容中咱们将介绍双链表的创建以及一些基本操作接下来跟我一起来看看吧
一、单链表与双链表
线性表的链式存储称为链表链表是由数据域和指针域组成。
由一个数据域和一个指针域组成的链表我们称为单链表单链表的指针域指向后继结点所以我们在访问单链表时只能从前往后访问。这就导致了一个问题我们在访问后继结点时的时间复杂度为O(1)但是在访问前驱结点时的时间复杂度却是O(n)。
为了克服单链表的这种单一访问的缺点于是我们在单链表的结点上新增了一个指针域使得链表上的每个结点都由一个数据域和两个指针域组成双链表的结点结构如下所示 这两个指针域一个指向后继结点(next)一个指向前驱结点(prior)我们将由这种结构的结点构成的链表称为双链表。
双链表和单链表一样双链表也有带头结点的双链表与不带头结点的双链表在没有特殊说明的情况下我们都是以带头结点的双链表进行说明。接下来我们就来看一下与双链表相关的基本操作
二、双链表类型的创建
我们首先来看一下双链表的类型创建的基本格式
//双链表类型创建的基本格式
typedef struct DNode {ElemType data;//数据域struct DNode* prior, * next;//指针域
}DNode, * DLinkList;//数据类型重命名
//DNode——Double Node——强调的是双链表的结点
//DLinkList——强调的是指向双链表的指针也就是整个双链表
//prior——在先的在前的先前的——指向前驱结点的指针
//next——下一个的紧接着的接下来的——指向后继结点的指针
//ElemType——数据元素的数据类型
//data——存储链表数据元素的变量从格式中可以看到其实双链表与单链表的类型创建格式是一致的它们之间的差别有以下几点
为了对这两种类型的链表有所区分单链表的结点类型我们将其定义为LNode双链表则是DNode单链表的类型我们将其定义为LinkList双链表则是DLinkList在双链表中我们定义了一个额外的指针prior用于指向前驱结点
有了这个基本格式我们同样还是以整型类型的数据元素为例来定义一个双链表如下所示
//创建双链表类型
typedef struct DNode {int data;struct DNode* prior, * next;
}DNode, * DLinkList;
int main()
{DLinkList L;//定义指向双链表的头指针return 0;
}有了双链表的头指针接下来我们就可以来创建双链表的头结点并将其初始化了
三、双链表的初始化
我们先来看一下双链表初始化的基本格式
//双链表初始化的基本格式
bool InitDLinkList(DLinkList* L)
{*L (DNode*)calloc(1, sizeof(DNode));//创建头结点assert(*L);//如果头结点创建失败则报错(*L)-prior NULL;//初始化前驱指针(*L)-next NULL;//初始化后继指针return true;
}可以看到对于双链表来说我们在初始化头结点时不仅要将后继指针进行初始化还要将前驱指针进行初始化这样是为了防止这两个指针变成野指针。 在单链表中有一点我们没有提到就是我们在通过malloc和calloc申请空间后一定要及时的对接收空间的指针进行检测看是否为空指针。 当空间申请失败后这两个函数返回的就是一个空指针所以为了避免出现问题我们可以通过assert来进行断言也可以通过条件语句来进行判断。 对指针这一块的知识掌握的不牢固的朋友可以通过【C语言必学知识点五】指针这篇博客来复习一下指针的相关知识点 我们在对双链表初始化之后就可以来通过头插法或者尾插法来创建一个双链表了
四、双链表的创建
由于双链表的结点结构与单链表的结点结构不同因此我们在创建双链表时的逻辑也是稍有区别的如下图所示 由于多了一个前驱结点这就导致我们在创建链表时通过头插法在创建第一个表头元素与创建其他的表头元素的步骤稍有不同如下所示 用头插法创建第一个表头结点的步骤 新结点的后继指针指向头结点的后继指针指向的对象即NULL新结点的前驱指针指向头结点头结点的后继指针指向新结点
用C语言来描述的话则是
//头插法创建第一个表头结点的插入步骤
New_Node-next Head-next;//新结点的后继指针指向头结点后继指针指向的对象即NULL
New_Node-prior Head;//新结点的前驱指针指向头结点
Head-next New_Node;//头结点的后继指针指向新结点注这个插入顺序要确保第3步的操作一定在第1步操作完后再执行第2步的操作顺序可以随意放置 用头插法创建第二个及以上的表头结点的步骤 新结点的后继指针指向头结点的后继指针指向的对象即表头结点头结点后继指针指向对象的前驱结点指向新结点新结点的前驱指针指向头结点头结点的后继指针指向新结点
用C语言描述的话则是
//头插法创建第二个及以上的头结点的插入步骤
New_Node-next Head-next;//新结点的后继指针指向头结点后继指针指向的对象即NULL
Head-next-prior New_Node;//头指针的后继指针指向对象的前驱指针指向新结点
New_Node-prior Head;//新结点的前驱指针指向头结点
Head-next New_Node;//头结点的后继指针指向新结点注这个插入顺序要确保第4步的操作一定在第1步与第2步操作完之后执行第3步操作的顺序可以随意放置
接下来我们来看一下在这个逻辑下的双链表的头插法的基本格式
//头插法创建双链表的基本格式
DLinkList DList_HeadInsert(DLinkList* L)
{DNode* p;//指向新结点的指针ElemType x 0;//接收数据元素的变量……;//获取需要存储的数据元素while (x ! EOF)//通过给循环设置结束条件来控制创建的结束{p (DNode*)calloc(1, sizeof(DNode));//创建新结点assert(p);//当创建新结点失败时assert会对指针p进行报错if (!(*L)-next)//当头结点的后继指针指向空指针时{p-data x;//将数据元素存储到新结点的数据域中p-next (*L)-next;//新结点的后继指针指向头结点后继指针指向的对象p-prior *L;//新结点的前驱指针指向头结点(*L)-next p;//头结点的后继指针指向新结点}else{p-data x;//将数据元素存储到新结点的指针域中p-next (*L)-next;//新结点的后继指针指向头结点后继指针指向的对象(*L)-next-prior p;//头结点的后继指针指向的对象的前驱指针指向新结点p-prior *L;//新结点的前驱指针指向头结点(*L)-next p;//头结点的后继指针指向新结点}……;//获取需要存储的数据元素}return (*L);//创建好链表后返回头指针
}但是对于尾插法而言不管是第一个结点还是最后一个结点的创建在插入步骤上都是不影响的因为表尾结点的后继指针肯定是指向NULL的因此通过尾插法创建的双链表则不需要分情况讨论对应的尾插法创建格式如下所示
//尾插法创建双链表的基本格式
DLinkList DList_TailInsert(DLinkList* L)
{DNode* r *L;//指向表尾的指针DNode* s;//指向新结点的指针ElemType x 0;//接收数据元素的变量……;//获取需要存储的数据元素while (x ! EOF)//通过给循环设置结束条件来控制创建的结束{s (DNode*)calloc(1, sizeof(DNode));//创建新结点assert(s);s-data x;//将数据元素存储到新结点的数据域中s-next r-next;//新结点的后继指针指向表尾结点的后继指针即NULLs-prior r;//新结点的前驱指针指向表尾结点r-next s;//表尾结点的后继指针指向新结点r s;//表尾指针指向新结点……;//获取新的数据元素}return(*L);//当链表创建结束返回头指针
}在创建好双链表后我们又该如何遍历双链表来访问某个结点呢
五、双链表的遍历
在给定一个结点后要想对单链表进行遍历的话我们只能从该结点往后遍历但是在双链表中我们既可以从给定结点开始往后遍历又可以从给定结点开始往前遍历。遍历的方式也很简单我们只需要将指向双链表的指针往我们需要遍历的方向进行移动就行如下所示
//给定结点指针p遍历双链表
while (p-next)//p的后继结点不为空指针
{p p-next;//从结点p往后遍历
}
while (p-prior)//p的前驱结点不为空指针
{p p-prior;//从结点p往前遍历
}想要对某一个结点进行想过操作时我们就可以通过这个遍历的方式来找到对应结点并执行相关操作。
六、双链表的查找
由于双链表是与前驱结点以及后继结点进行双向链接的因此我们在给定双链表的一个结点后不管是查找该结点的后继结点还是前驱结点对应的时间复杂度都为O(1)
在未给定结点的情况下我们要想查找对应的结点我们同样可以通过按值查找与按位查找两种查找方式来执行下面我们来看一下在双链表中这两种查找方式的基本格式又是如何
//双链表的按位查找
DNode* GetElem(DLinkList L, int i)
{if (i 1)return NULL;//当查找的位序不合理时返回空指针DNode* p L-next;//指向表头结点的指针int j 1;//表头结点的位序while (p j i)//当查找结点为空指针时结束循环当查找结点的位序与目标位序相等时结束循环{p p-next;//继续往后遍历j;}return p;//查找结束后返回指针p
}如果是已知某一个结点的位序需要查找另一个结点的位序我们可以将函数的参数换成已知的结点以及需要查找的结点位序就行这里就不再展开。下面我们来看一下按值查找的基本格式
//双链表的按位查找
DNode* LocateElem(DLinkList L, ElemType e)
{DNode* p L-next;//指向表头结点的指针while (p p-data ! e)//当查找结点为空指针时结束循环//当查找结点的数据域存储的元素与目标元素相等时结束循环{p p-next;//继续往后遍历}return p;//查找结束后返回指针p
}对于双链表而言在进行查找操作时对应的时间复杂度就有以下几种情况
如果是从表头结点或者表尾结点开始进行查找的话那对应的时间复杂度就是O(n)如果是已知结点要查找对应的前驱结点或者后继结点的话那对应的时间复杂度就是O(1)如果是已知某一结点需要查找位序在该结点前面或者后面的结点的话那对应的时间复杂度就是O(n)
七、双链表的插入
双链表的插入操作也是有前插与后插操作前插操作的逻辑与单链表一致都是通过在指点结点的后面插入一个新的结点再对数据域中存储的数据进行移动从而完成前插操作下面我们先来看一下双链表前插操作的基本格式
//双链表的前插操作
bool InsertPriorDNode(DNode* p, ElemType e)
{assert(p);//指针p为空指针时报错DNode* q p-prior;//指针p的前驱结点assert(q);//指针q为空指针时报错DNode* s (DNode*)calloc(1, sizeof(DNode));//创建新结点assert(s);//指针s为空指针时报错s-data e;//将要插入的元素e放入新结点的数据域中s-next p;//将新结点的后继指针指向进行前插操作的结点pp-prior s;//将结点p的前驱指针指向新结点sq-next s;//将前驱结点的后继指针指向新结点ss-prior q;//将新结点的前驱指针执行前驱结点qreturn true;//完成前插操作后返回true
}在双链表中进行前插操作时我们有几点需要注意
首先要确定该结点不是头结点也就是该结点的前驱结点不为空指 当该结点为头结点时不能进行前插操作此时给予一定的信息进行提示当该结点不为头结点时则可以正常进行前插操作 因为双链表结点的前驱指针直接指向的是前驱结点因此我们不需要像单链表一样调用函数来查找前驱结点在进行插入操作时前驱结点的后继指针执行新结点的操作最好放在最后一步执行
下面我们来看一下双链表的后插操作
//双链表的后插操作
bool InsertNextDNode(DNode* p, ElemType e)
{assert(p);//指针p为空指针时报错DNode* s (DNode*)calloc(1, sizeof(DNode));//创建新结点assert(s);//指针s为空指针时报错s-data e;//将要插入的数据放入新结点的数据域中if (p-next)//结点p的后继结点不为空指针{s-next p-next;//将新结点的后继指针指向结点p的后继结点p-next-prior s;//结点p的后继结点的前驱指针执行新结点s-prior p;//新结点的前驱指针指向结点pp-next s;//结点p的后继指针指向新结点}else//结点p的后继结点为空指针{s-next p-next;//将新结点的后继指针指向结点p的后继结点s-prior p;//新结点的前驱指针指向结点pp-next s;//结点p的后继指针指向新结点}return true;//完成后插操作后返回true
}在双链表中我们要执行后插操作我们也需要注意几点
要判断当前结点的后继结点是否为空指针从而选择插入操作的执行步骤 当前结点的后继结点不为空指针时需要将后继结点的前驱指针的指向对象换成新结点当前结点的后继结点为空指针时只需要将新结点的后继指针指向空指针就行 不管当前结点的后继结点是否为空指针我们最好都是将当前结点的后继指针指向新结点的操作放在最后执行
对于双链表而言不管是前插操作还是后插操作其对应的时间复杂度都是O(1)相比于单链表双链表的执行效率会更高
八、双链表的删除
如果我想删除双链表中的某个结点时我们只需要按照以下步骤就能完成删除操作
将当前结点的前驱结点的后继指针指向当前结点的后继结点将当前结点的后继结点的前驱指针指向当前结点的前驱结点释放当前结点的空间
将其转换成C语言则是
//双链表的删除操作
DNode-prior-next DNode-next;//将前驱结点的后继指针指向后继结点
DNode-next-prior DNode-prior;//将后继结点的前驱指针指向前驱结点
free(DNode);//释放当前结点的内存空间如果是删除的结点为表尾结点则我们只需要将表尾结点的前驱结点指向空指针然后直接释放表尾结点的空间就行转换成C语言则是如下所示
//删除表尾结点
DNode-prior-next NULL;//表尾结点的前驱结点的后继指针指向空指针
DNode-prior-next DNode-next;//前驱结点的后继指针指向后继结点即空指针
free(DNode);//释放表尾结点的内存空间删除表尾结点时第一句代码与第二句代码都是可以使用的效果都一样二者选其一就行。下面我们将删除操作封装成一个函数的话则对应的格式如下所示
//双链表的删除操作
bool DeleteDNode(DNode* p)
{assert(p);//指针p为空指针时报错DNode* q p-prior;//p的前驱结点assert(q);//当q为空指针时报错DNode* r p-next;//p的后继结点if (r)//后继结点不为空指针时{q-next r;//前驱结点指向后继结点r-prior q;//后继结点指向前驱结点free(p);//释放结点p的内存}else{q-next r;//前驱结点指向后继结点即空指针free(p);//释放结点p的内存}return true;//完成删除操作后返回true
}当对结点进行前删或者后删时也是相同的逻辑这不过在这个基础上做一点小小的变动这里我就不展开介绍了。当我们相对整个双链表进行删除时我们只需要重复删除表尾结点的操作即可大家有兴趣的话可以自己尝试着编写一下
结语
双链表的内容到这里咱们就全部介绍完了在今天的篇章中咱们详细介绍了双链表的创建、初始化、查找、插入、删除等基本操作并给大家附上了对应操作的代码。希望今天的内容能够帮助大家更好的理解双链表及其基本操作。
在下一篇内容中咱们将介绍循环链表以及静态链表的相关内容大家记得关注哦最后感谢各位的翻阅咱们下一篇再见
