怎样做黄色网站,推广神器app,湖南建设工程信息网站,wordpress description前言#xff1a; 小编在之前已经写过单链表的创建了#xff0c;接下来要开始双链表的讲解了#xff0c;双链表比单链表要复杂一些#xff0c;不过确实要比单链表更好进行实现#xff01;下面紧跟小编的步伐#xff0c;开启今天的双链表之旅#xff01; 目录 1.概念和结构…前言 小编在之前已经写过单链表的创建了接下来要开始双链表的讲解了双链表比单链表要复杂一些不过确实要比单链表更好进行实现下面紧跟小编的步伐开启今天的双链表之旅 目录 1.概念和结构 1.1.哨兵位 1.2.双链表的结构 2.双向链表的实现 2.1.初始化双链表 2.2.双链表的尾插 2.3.双链表的打印 ·2.4.双链表的头插 2.5.双链表的尾删 2.6.双链表的头删 2.7.查找双链表的数据 2.8.在指定位置之后插入数据 2.9. 删除指定结点的数据 3.0.销毁双链表 3.链表的分类 1.单向不带头不循环链表也就是小编前面写的单链表 2.单向带头不循环链表 编辑 3.单向不带头循环链表 4.单向带头循环链表 编辑 5.双向带头循环链表 编辑 6.双向不带头不循环链表 7.双向带头不循环链表 编辑 8.双向不带头循环链表 4.代码展示 4.1.List.h 4.2.List.c 总结 正文
1.概念和结构 在前面的博客中小编讲述了单链表其实单链表的全程叫做单向不带头不循环链表这里有很多读者朋友就好奇了单向和不循环还是比较容易理解的那么不带头又是什么意思呢其实这里就牵扯到了一个全新的知识点哨兵位
1.1.哨兵位 哨兵位这个名字看起来是很威武的其实了解它之后就知道它仅仅就是名字威武点它才是真正意义上的头结点哨兵位是不存数据的它的存在仅仅就是为了说明这个链表是带头的是用来“放哨的”小编在讲述单链表的时候曾多次提到了头结点这个名字那个时候头结点是链表第一个结点这个叫法是不太规范的不过为了让读者朋友更好的去理解链表的知识小编于是就直接头结点来代替链表第一个结点了不过各位读者朋友一定要清楚真正的头结点其实就是哨兵位。
1.2.双链表的结构 首先双链表是带头的链表说明它的第一个结点是不存数据的是哨兵位双链表也是双向的说明它的结点不仅仅存放着下个结点的数据也存放着的前一个结点的数据看着非常复杂其实有了这个特点以后在写双链表代码的时候要比单链表要简单许多等会各位就清楚小编为什么这么说了它的最后一个特点是循环这个小编在之前讲解环形链表习题的时候就牵扯到了一点循环链表下面小编给上双链表的结构图以便大家在等会写代码的时候可以更好的理解 小编已经讲述了双链表的概念和结构了下面就是各位最喜欢的节目双链表代码的书写下面跟随小编的脚步开启我们今天的代码之旅喽~ 2.双向链表的实现 在写双链表之前这里小编还是说一下我们依旧需要创建两个源文件和一个头文件头文件是负责声明一下写的函数一个源文件是负责实现函数功能的另一个是测试用的废话不多说开始进入正文
2.1.初始化双链表 在初始话双链表之前我们肯定要写双向链表结点的结构体这个结构体其实就是比单链表多了一个存放上一个结点的地址其他都是一样的下面直接上代码
typedef int LTDataType;
typedef struct List {LTDataType date;struct List* next; //存放下一个结点的地址struct List* prev; //存放上一个函数结点的地址
}LTNode; 对于双链表的初始化这里可不是简简单单的就是把它的下一个结点为空上一个结点为空了双链表是带头的所以其实这里的初始化操作就是创建一个哨兵位按理说哨兵位是不存放任何数据的不过我们也是可以给它赋值的只不过不用它这个值罢了这里我们就把哨兵位的数据暂时弄为-1因为这个链表是循环的所以我们需要让它的下一个结点和上一个结点统一指向自己这里就可以形成死循环小编在下面通过图文来让大家去理解 此时我们已经完成了尾插的操作下面开始进行链表常见操作尾插操作
2.2.双链表的尾插 对于插入操作肯定需要先设置一个新的结点不然尾插就没有什么结点可插了对于新节点的创建小编在之前单链表也写过不过双链表与单链表最大的不同就是它的下一个结点和上一个结点都要去指向自己下面直接上手代码图了这里由于难度不大小编就不在多赘述了
//先创建一个新的结点对于任何插入操作都得有这个玩意
LTNode* LTbuynode(LTDataType x)
{LTNode* p1 (LTNode*)malloc(sizeof(LTNode));assert(p1);p1-date x;p1-next p1-prev p1;
} 接下来就进行插入操作了小编经过深思熟虑以后决定搭配着图文进行配套讲解感觉这样讲起来不费劲各位理解起来也不算太费劲下面小编随机弄个图来进行讲解 先创建好结点创建好后开始进行尾插操作 之后我们需要让哨兵位的下一个结点指向新创立的结点newlode让newlode的上一个结点指向哨兵位 之后我们为了达成循环的效果我们要让哨兵位的上一个结点指向新结点让新结点的下一个结点的指针指向哨兵位此时我们就完成了尾插操作其实这里小编感觉我给的例子不是很好各位读者朋友最好用用一个比较长的链表来实现那个更容易理解这里我先对各位说声抱歉。 下面小编给上尾插操作的代码通过这个代码各位读者朋友就知道为什么小编推荐用长一点的链表来实现这个尾插操作了
void LTPushBack(LTNode* phead, LTDataType x)
{assert(phead); //首先哨兵位不能是空的LTNode* newnode LTbuynode(x);phead-prev-next newnode;newnode-next phead;newnode-prev phead-prev;phead-prev newnode;
} 这个代码值得注意的就是我们再传参的时候并不是像单链表一样传的二级指针我们传的是一级指针因为我们并不会对头结点哨兵位做出改变故不用传地址这个代码还是比较好理解的各位读者朋友一定要自己先思考自己先写一遍代码然后再看小编写的如果直接复制粘贴的话写完之后知识也不是你的小编写这篇文章的目的就是让读者朋友去理解的也让我自己在复习一遍。
2.3.双链表的打印 双链表的打印其实是蛮容易的不过写这个函数的目的就是为了测试其他函数写的对不对对于双链表的打印它和单链表的打印有些许不同因为双链表我·是一个带头的死循环的链表所以我们需要通过控制循环条件来实现对于双链表的打印 首先我们需要先设置一个结点来代表哨兵位下一个结点因为哨兵位理论上是不存数据的然后我们开始循环打印结点的数据结束的条件自然就是我们不能让设置的这个指针循环到哨兵位结点一旦循环到了哨兵位结点则说明此时已经完成了一轮循环所以此时我们无须在进行循环直接结束就好了由于本小节内容无须图像所以我们便直接展示代码了
void LTPrint(LTNode* phead)
{LTNode* pour phead-next;while (pour ! phead){printf(%d-, pour-date);pour pour-next;}printf(\n);
} ·2.4.双链表的头插 这里一定要注意双链表的头插可不是把新节点插到哨兵位之前而是插在哨兵位之后哨兵位之后的第一个节点才是有实际意义的头一个结点下面小编用图文的方式来给大家讲述一下头插的原理 这里我们需要设置一个新节点对于设置新节点的代码小编在上面已经讲述清楚了为了让文章更加清楚小编这里用一个长的链表来进行头插操作 之后我们让d1的上一个结点不在指向哨兵位而是指向新节点让新节点的下一个结点指向d1 之后我们让新节点的上一个结点指向哨兵位让哨兵位的下一个结点指向新节点 此时我们已经完成了头插操作此时哨兵位的下一个结点就是新节点了下面小编给出这个操作的代码
void LTPushFront(LTNode* phead, LTDataType x)
{assert(phead);LTNode* newnode LTbuynode(x);LTNode* next phead-next;newnode-next next;next-prev newnode;phead-next newnode;newnode-prev phead;
} 此时我们已经完成了头插尾插操作下面就要进行删除操作我们先从头删和尾删操作开始喽读者朋友们继续加油。 2.5.双链表的尾删 双链表的尾删操作也不难我们都会插入数据了尾部删除自然而然也会显得很简单小编之前就说过双链表的代码要比单链表的代码要简单许多因为此时我们用不到循环来找尾结点对于尾结点我们仅需通过哨兵位的上一个结点便可以找到尾结点从这点就可以看出双链表的便利行了废话不多说下面进入尾删讲解环节 我们在尾删之前一定要判断我们想要删除的链表是否是除了哨兵位结点之外还有别的结点所以我们需要写一个布尔类型的函数来进行对于链表是否为空来进行判断下面是代码
bool Listpanduan(LTNode * phead) //在使用bool关键字的时候记得先有头文件这里是判断是否除了哨兵位还有没有别的结点了
{return phead phead-next;
} 首先我们继续使用上面的链表作为例子 首先我们想要删除尾部的数据我们就要改变指针的指向此时我们需要通过尾结点找到它的上一个结点此时我们直接用d2来说我们让d2的下一个指针指向哨兵位再让哨兵位的上一个结点指向d2 此时我们便让d2成为了新的尾结点至于d3我们直接将它free掉 我们已经完成了双链表的尾删操作下面小编直接展示代码
void LTPopBack(LTNode* phead)
{assert(phead);//先判断是不是只有哨兵位assert(!Listpanduan(phead));LTNode* prev phead-prev;prev-prev-next phead;phead-prev prev-prev;free(prev);prev NULL;
} 尾删操作已经结束了下面我们快马加鞭来进入头删环节
2.6.双链表的头删 双链表的头删操作类似尾删操作无非就是把指针的指向来回改变指针指向的问题不过这里也要记住头删头删并不是删掉链表的哨兵位而是删掉哨兵位的下一个结点这个结点才是真正意义上的头结点下面我们来进行头删的讲解 在进行这个代码之前因为涉及到了删除我们还是要判断这个链表是否只含有哨兵位判断完以后就可以进行正常的代码书写了 首先我们还是选取上述使用的链表来进行讲解 之后我们的任务就是把d2变成头结点这里我们需要改变指针的指向我们可以想让哨兵位的下一个结点指向它原本下一个结点的下一个结点也就是d2再让d2的上一个指针直接指向哨兵位结点 之后我们直接讲d1结点free掉就可以实现头删操作 上面就是头删操作的实现图是不是感觉很easy悄咪咪的说小编当初学的时候可没这样感觉到嘿嘿下面小编给大家展示下这个代码如何书写
void LTPopFront(LTNode* phead)
{assert(phead);assert(!Listpanduan(phead));LTNode* next phead-next;phead-next next-next;next-prev phead;free(next);next NULL;
} 此时的我们已经实现了如何进行头删和尾删操作下面我们开始进行一些特定位置的查找插入删除操作下面跟随小编的脚步一起实现这些代码吧 2.7.查找双链表的数据 这个操作可以类比我们在单链表的时候写过的查找单链表数据来记这个和我们上文在打印时是一样的操作我们可以通过循环操作来实现这个查找小编认为就不需要图文进行解释了小白在这里用文字进行解释我们也是同样从哨兵位下一个结点开始进行循环寻找我们想要的数据如果循环到了我们直接返回这个结点如果经历完循环以后我们还没有找到那么我们就直接返回空就好下面是代码实现图这个操作还是蛮简单的
LTNode* LTFind(LTNode* phead, LTDataType x)
{LTNode* pour phead-next;while (pour ! phead){if (pour-date x)return pour;pour pour-next;}return NULL;
}
2.8.在指定位置之后插入数据 这个操作类似我们之前的插入函数也是改变指针指向就好了下面小编就直接开讲啦 首先我们需要先设置一个长点的链表小编就在这里还是以上面的链表为例子并且记住一旦涉及到插入函数我们首先需要设置一个新的结点这里我们指定的结点就拿d2进行举例子 此时我们需要先保存一下d2的下一个结点d3然后我们可以让d2这个结点的下一个结点指向新结点让新结点的下一个结点指向d3 之后我们再让新结点的上一个结点指向d2让d3的上一个结点指向新结点此时我们就完成了指定位置之后插入数据 此时我们已经完成了对于此函数的书写经过了头插尾插的洗礼后读者朋友们是不是感觉这个代码变的非常简单呢下面给出代码
//在pos位置之后插入节点
void LTInsert(LTNode* pos, LTDataType x)
{assert(pos);LTNode* newnode LTBuyNode(x);//pos newnode pos-nextnewnode-next pos-next;newnode-prev pos;pos-next-prev newnode;pos-next newnode;
}
2.9. 删除指定结点的数据 这个操作就类似前面的头删尾删操作废话不多说直接进入正题 在我们想要删除数据的时候一定要判断该链表是不是只有哨兵位这个操作在删除操作是必须的为了不让大家忘记小编就在这里多叨叨几句。 首先我们还是以上面的链表举例ps这个链表是真好用此时我们就以删除d2为例我可不是跟他有仇(。-ω-)zzz。 之后我们进行的操作还是那几部我们直接让d1的下一个结点指向d3让d3的上一个结点指向d1此时我们就建立起了d1和d3之间的联系 此时我们直接把d2free掉这里就实现了对于指定位置结点的数据的删除 这里小编多说一句如果想要设置指定结点这里我们可以搭配上面的查找双链表的数据操作来进行同步实现下面小编给上代码
void LTErase(LTNode* pos)
{assert(pos);assert(!Listpanduan(pos));LTNode* prev pos-prev;LTNode* next pos-next;prev-next next;next-prev prev;
} 3.0.销毁双链表 终于我们实现了对于双链表的部分代码上面的代码并不是全部而是小编学过的一部分双链表指定不可能只有这一点功能就比如我们可以在指定结点之后插入数据那么我们是不是也可以在指定位置之前插入数据呢知识是无穷的各位读者朋友感兴趣的话可以继续来扩展双链表的功能下面废话不多说我们要进入链表销毁喽 对于双链表的销毁对比于单链表双链表的销毁是有点麻烦的不过麻烦程度是比较小的我们这里也是用到了循环我们需要把双链一个一个的进行销毁此时需要注意的是我们对哨兵位做出了改变所以需要传双指针此时我们可以用一个指针记录哨兵位之后我们对链表每一个结点进行销毁最后我们需要把哨兵位也销毁掉此时我们就实现了对于链表的销毁写到这里小编突然觉得前面说的话有点错删除也没有那么麻烦可能小编刚才脑子瓦特了下面展示代码
void LTDestroy(LTNode** phead)
{LTNode* pour *phead;while (pour ! phead){LTNode* next pour-next;free(pour);pour NULL;pour next;}free(*phead);*phead NULL;pour NULL;
} 此时我们已经实现了双链表的各种功能小编本来想要写到这里就展示所有的源代码不过小编想起我似乎没讲过链表的分类于是小编先讲分类等会在给大家的源码对此不感兴趣的读者朋友可以直接跳到文章最后~ 3.链表的分类 小编在文章开头说过本文讲的是双向不带头循环链表所以细心的读者朋友已经知道了链表其实根据类别分为八类分别是
1.单向不带头不循环链表也就是小编前面写的单链表 2.单向带头不循环链表 3.单向不带头循环链表 4.单向带头循环链表 5.双向带头循环链表 6.双向不带头不循环链表 7.双向带头不循环链表 8.双向不带头循环链表 4.代码展示
4.1.List.h
//现在我们来进行双链表的书写
//双链表是带头双向循环链表
#includestdio.h
#includestdlib.h
#includeassert.h
#includestdbool.h
typedef int LTDataType;
typedef struct List {LTDataType date;struct List* next; //存放下一个结点的地址struct List* prev; //存放上一个函数结点的地址
}LTNode;//初始化双链表
void LTInit(LTNode** pphead);//双链表的尾插
void LTPushBack(LTNode* phead, LTDataType x);//双链表的打印
void LTPrint(LTNode* phead);//双链表的头插
void LTPushFront(LTNode* phead, LTDataType x);//双链表的尾删
void LTPopBack(LTNode* phead);//双链表的头删
void LTPopFront(LTNode* phead);//查找双链表的数据
LTNode* LTFind(LTNode* phead, LTDataType x);//在指定位置之后插入数据
void LTInsert(LTNode* pos, LTDataType x);//删除指定节点的数据
void LTErase(LTNode* pos);//销毁双链表
void LTDestroy(LTNode** phead);
4.2.List.c
void LTInit(LTNode** pphead)
{*pphead (LTNode*)malloc(sizeof(LTNode));assert(*pphead);(*pphead)-date -1;(*pphead)-next (*pphead)-prev *pphead;
}//先创建一个新的结点对于任何插入操作都得有这个玩意
LTNode* LTbuynode(LTDataType x)
{LTNode* p1 (LTNode*)malloc(sizeof(LTNode));assert(p1);p1-date x;p1-next p1-prev p1;
}
void LTPushBack(LTNode* phead, LTDataType x)
{assert(phead); //首先哨兵位不能是空的LTNode* newnode LTbuynode(x);phead-prev-next newnode;newnode-next phead;newnode-prev phead-prev;phead-prev newnode;
}void LTPrint(LTNode* phead)
{LTNode* pour phead-next;while (pour ! phead){printf(%d-, pour-date);pour pour-next;}printf(\n);
}void LTPushFront(LTNode* phead, LTDataType x)
{assert(phead);LTNode* newnode LTbuynode(x);LTNode* next phead-next;newnode-next next;next-prev newnode;phead-next newnode;newnode-prev phead;
}bool Listpanduan(LTNode * phead) //在使用bool关键字的时候记得先有头文件
{return phead phead-next;
}
void LTPopBack(LTNode* phead)
{assert(phead);//先判断是不是只有哨兵位assert(!Listpanduan(phead));LTNode* prev phead-prev;prev-prev-next phead;phead-prev prev-prev;free(prev);prev NULL;
}void LTPopFront(LTNode* phead)
{assert(phead);assert(!Listpanduan(phead));LTNode* next phead-next;phead-next next-next;next-prev phead;free(next);next NULL;
}LTNode* LTFind(LTNode* phead, LTDataType x)
{LTNode* pour phead-next;while (pour ! phead){if (pour-date x)return pour;pour pour-next;}return NULL;
}//在pos位置之后插入节点
void LTInsert(LTNode* pos, LTDataType x)
{assert(pos);LTNode* newnode LTBuyNode(x);//pos newnode pos-nextnewnode-next pos-next;newnode-prev pos;pos-next-prev newnode;pos-next newnode;
}void LTErase(LTNode* pos)
{assert(pos);assert(!Listpanduan(pos));LTNode* prev pos-prev;LTNode* next pos-next;prev-next next;next-prev prev;
}void LTDestroy(LTNode** phead)
{LTNode* pour *phead;while (pour ! phead){LTNode* next pour-next;free(pour);pour NULL;pour next;}free(*phead);*phead NULL;pour NULL;
}
总结 可算写完这篇文章了双链表的知识相对于单链表难度是大了一点不过双链表的代码到是写着没有那么复杂我以后绝对每次学完了直接写博客来巩固记忆如果文章有错误的地方大家请在评论区指出小编一定会听取大家的意见那么我们下一篇文章见啦
