数据结构：双向循环链表的实现

一.基本功能概述双向循环链表弥补了单链表的许多不足。首先在结构上它增加了访问前驱的指针prev这样访问前一个节点就变得很方便了其次就是循环链表的头尾是相连的这样在实现头尾删插的时候也更加简便了。双向循环链表的定义与需要实现的功能。双向循环链表的功能和单链表几乎无异只是在实现方法上有所不同头文件的详情如下#pragma once #include stdio.h #include assert.h #include stdbool.h #include stdlib.h typedef int DoublelistData; typedef struct Doublelist { DoublelistData data; struct Doublelist* next; struct Doublelist* prev; }Dlist; //初始化双链表 Dlist* DlistInit(); //创建新的双链表节点 Dlist* DlistBuyNode(DoublelistData x); //打印双链表 void DlistPrint(Dlist* head); //获取数据x所在的下标 int GetDlistElem(Dlist* head, DoublelistData x); //在下标i处后方插入数据x void DlistInsert(Dlist* head, int i, DoublelistData x); //删除下标为i的位置的节点 void DlistDelete(Dlist* head, int i); //删除第一个数据等于x的节点 void DlistDataDelete(Dlist* head, DoublelistData x); //获取双向链表的有效数据个数 int GetDlistSize(Dlist* head); //销毁双向链表 void DlistDestroy(Dlist** phead); //尾删 void DlistPopBack(Dlist* head); //尾插 void DlistPushBack(Dlist* head, DoublelistData x); //头删 void DlistPopFront(Dlist* head); //头插 void DlistPushFront(Dlist* head, DoublelistData x);二.功能实现先来说初始化链表。要初始化链表首先就需要在堆上创建一个哨兵节点即我们使用malloc函数但需要注意的是对于双向循环链表即使是单个节点我们也要使其头尾相连即新节点的prev和next都指向自己。建立新节点我们写一个创建新节点的函数方便以后调用。使用malloc需要进行返回值检查Dlist* DlistBuyNode(DoublelistData x) { Dlist* NewNode (Dlist*)malloc(sizeof(Dlist)); if (NewNode NULL) { perror(malloc); exit(-1); } NewNode-data x; NewNode-next NewNode; NewNode-prev NewNode; return NewNode; }我们在这里约定哨兵节点的数据部分存储-1。接下来DlistInit就很好实现了初始化链表Dlist* DlistInit() { Dlist* head DlistBuyNode(-1); return head; }打印链表为了后续方便检查和调试这里我们先把打印链表的功能实现好。首先需要知道循环链表并没有尾部所以我们不能通过查找尾部NULL来停止打印。这边的方法是通过判断当前指针是否等于头指针如果是就停止打印。再者我们的接口传的都是哨兵指针因此需要断言判空。需要注意的点就这俩个具体如下void DlistPrint(Dlist* head) { assert(head); Dlist* pcur head-next; int j 0; while (pcur ! head) { printf(%d[%d]-, pcur-data, j); pcur pcur-next; j; } printf(\n); }这里为了方便调试我增加了打印下标的功能。获取元素下标与节点个数这两个功能也相对简单这里不做过多讨论。int GetDlistElem(Dlist* head, DoublelistData x) { assert(head); Dlist* pcur head-next; int j 0; while (pcur ! head) { if (pcur-data x) { return j; } pcur pcur-next; j; } printf(节点不存在\n); return -1; }int GetDlistSize(Dlist* head) { assert(head); Dlist* pcur head-next; int size 0; while (pcur ! head) { size; pcur pcur-next; } return size; }需要注意的是我们这里约定-1是无效数据所以在未找到数据x的情况下将返回值设置为-1,这个可以视情况而调整。插入数据这是整个功能的重点也是难点。在考研408中关于链表的相关考察经常涉及到节点的插入。在这里我们定义在i下标位置插入是插入在其后方。当然我们更常见的做法是在前方插入在下面我们会实现这两种方式。先来看插入在i后方的代码void DlistInsert(Dlist* head, int i, DoublelistData x) { assert(head i -1); Dlist* pcur head; int j -1; while (j i pcur-next ! head) { pcur pcur-next; j; } if (j i) { printf(下标位置超过尾部\n); exit(-1); } Dlist* NewNode DlistBuyNode(x); NewNode-next pcur-next; NewNode-prev pcur; pcur-next-prev NewNode; pcur-next NewNode; }这里我们使用索引 j 来判断输入的下标 i 是否越界。因为我们将pcur赋值为head---哨兵节点的指针为保证 j 和pcur的下标对应我们只能将j初始化为-1。注意在上述断言中我们允许 i -1 是为了方便后续实现头插功能时可以直接调用这个接口。至于while循环的跳出条件是pcur-next ! head,而不是pcur head是为了后续调用这个接口实现尾插。关于边界情况我们都稍后讨论先把关键的插入捋清楚。想要插入数据x首先先创建这个节点根据上文pcur目前下标i位置的节点而我们要在其后方插入那第一步先让新节点的后继指向pcur的后一个即NewNode-next pcur-next;再让NewNode的前驱指向位置 i 即pcurNewNode-prev pcur;这时pcur-next没有被修改仍然指向pcur的下一个而非NewNode所以我们通过pcur-next访问到下一个节点再将它的前驱prev指向NewNodepcur-next-prev NewNode;最后我们才能修改pcur的后继即pcur-next.再次强调由于我们访问 i 的下一个节点需要pcur-next所以它一定是留在最后一个修改的。当然如果你事先把i的下一个节点的指针存好了那就不用考虑这个问题了。现在我们处理好了一般情况的插入功能那接下来就要考虑边界情况了顺便解释一下刚刚没填的坑。输入错误i 越界其实在链表的实际应用中头尾插入或删除才是常用的而这些功能一般是实现了一般位置的插入或删除功能后直接调用这些接口实现的。比如现在假如一个链表有4个节点那么最后一个节点的下标就是 3我要在尾部插入按现在的代码直接输入三是没有问题的j 会在等于 i 时跳出而pcur自然指向最后一个节点。但如果我们输入一个4呢虽然双向循环链表的性质会防止越界但再加上while的循环条件会直接让这个违规插入操作退化为尾插使用者不会收到任何错误提醒所以我们设置了if判断语句来解决这个问题。边界情况尾插那现在尾插的代码似乎就很好处理了我们直接调用之前实现的获取节点个数的接口获得节点个数size那么size - 1就是尾部的下标再输入插入代码中不就行了吗由于 j 被我们初始化为-1所以即使我们要尾插一个空表size - 1 -1刚好可行详情如下void DlistPushBack(Dlist* head, DoublelistData x) { assert(head); int size GetDlistSize(head); DlistInsert(head, size - 1, x); }边界情况头插头插的代码就更加显然了。我们直接把-1作为下标传入插入接口就能实现void DlistPushFront(Dlist* head, DoublelistData x) { assert(head); DlistInsert(head, -1, x); }删除节点删除节点的接口我们定义为删除下标为 i 的节点。由于链表的所有节点都是通过malloc在堆上创建的所以删除自然也就是free对应的结构体指针。这里需要注意的点和刚刚的插入大同小异也是要注意指向下一个节点的指针不能先被free否则我们就找不到下一个节点还会非法访问到已释放内存。所以我们要么先把pcur-next存起来要么先让pcur前后的节点连接起来再free由于大部分考题都是考察后者故这里我们也采用后者方案。具体代码如下void DlistDelete(Dlist* head, int i) { assert(head i 0); if (head-next head) { printf(输入空表删除失败\n); exit(-1); } Dlist* pcur head-next; int j 0; while (pcur-next ! head j i) { pcur pcur-next; j; } if (j i) { printf(下标越界无法执行删除操作\n); exit(-1); } pcur-next-prev pcur-prev; pcur-prev-next pcur-next; free(pcur); }边界情况头删与尾删由于删除功能中i 越界的情况比较容易处理这里不做讨论。我们来看到头删和尾删的实现代码上。这里也是直接调用已有接口头删就是把参数 i 置为 0 尾删便是讲尾部的下标传入与上述大同小异。唯一需要注意的就是我们传入的head实际上是哨兵指针我们既要assert哨兵本身不能为空又要assert它是否是指向空链表即它是否是自循环的。具体代码如下void DlistPopBack(Dlist* head) { assert(head head-next ! head); int size GetDlistSize(head); DlistDelete(head, size - 1); } void DlistPopFront(Dlist* head) { assert(head); DlistDelete(head, 0); }不过由于循环链表拥有前驱指针prev所以要实现尾插我们也可以直接使用哨兵节点的前驱来访问尾部从而达到删除效果这样拥有更高的效率void DlistPopBack(Dlist* head) { assert(head head-next ! head); Dlist* del head-prev; del-prev-next head; head-prev del-prev; free(del); }删除x数据节点我们对这个功能的定义是删除第一个数据等于x的节点。刚刚我们实现了获取元素下标的接口结合删除接口我们就可以直接实现这个功能void DlistDataDelete(Dlist* head, DoublelistData x) { assert(head); int i GetDlistElem(head, x); DlistDelete(head, i); }销毁链表这是很多同学会忽略的一个功能。由于链表在堆上建立的若不进行销毁就会造成内存泄漏。销毁链表需要注意的点和删除链表时差不多我们需要循环遍历每一个节点并free释放它。但注意由于哨兵节点也要释放所以我们需要将参数设置为指向哨兵节点的二级指针在free完所有节点后再释放哨兵节点并置空。再次注意哨兵指针一定要置空void DlistDestroy(Dlist** phead) { assert(phead); Dlist* pcur (*phead)-next; while (pcur ! *phead) { Dlist* next pcur-next; free(pcur); pcur next; } free(*phead); *phead NULL; }总结链表是非常经典和常用的数据结构种类多样经常出现在各种考核中希望这篇文章能帮助大家学习和巩固相关知识点也感谢大家积极指正不足之处。