【C语言教程】“双向循环链表”学习总结及其代码实现

双向循环链表和它名字的表意一样&＃xff0c;就是把双向链表的两头连接&＃xff0c;使其成为了一个环状链表。只需要将表中最后一个节点的next指针指向头节点&＃xff0c;头节点的prior指针指向尾节点&＃xff0c;链表就能成环儿&＃xff0c;如图所示&＃xff1a;

需要注意的是&＃xff0c;虽然双向循环链表成环状&＃xff0c;但本质上还是双向链表&＃xff0c;因此在双向循环链表中&＃xff0c;依然能够找到头指针和头节点等。双向循环链表和双向链表相比&＃xff0c;唯一的不同就是双向循环链表首尾相连&＃xff0c;其他都完全一样。

注意&＃xff1a;因为我上面已经讲了双向链表&＃xff0c;所以这里只注重讲他们的实现差异。另因为带头节点会更好操作&＃xff0c;所以我的代码都有头节点。

1、双向循环链表的创建

初始化时需要将头节点的next和prior都指向自己。

//1、初始化双向循环链表&＃xff08;带头节点&＃xff09;Status initLinkList(LinkList *list){//创建头节点*list &＃61; malloc(sizeof(Node));if (*list &＃61;&＃61; NULL) {return ERROR;}//前驱和后继都指向自己(*list)->prior &＃61; *list;(*list)->data &＃61; -1;(*list)->next &＃61; *list;printf("已初始化链表~\n");return OK;}

2、遍历双向循环链表

注意它的尾节点的next不再是Null&＃xff0c;而是头节点//2、遍历双向循环链表void printfLinkLisk(LinkList list){printf("遍历链表&＃xff1a;\n");if (list &＃61;&＃61; NULL || list->next &＃61;&＃61; list) {printf("这是一个空链表\n");return;}LinkList p &＃61; list;//判断next是否全部正确printf("根据next从前往后遍历&＃xff1a;");while (p->next !&＃61; list) {printf("%d ",p->next->data);p &＃61; p->next;}printf("\n");//判断prior是否全部正确printf("根据prior从后往前遍历&＃xff1a;");while (p !&＃61; list) {printf("%d ",p->data);p &＃61; p->prior;}printf("\n");}

3、根据索引位置添加节点

这里不需要判断尾节点的next是否为Null&＃xff0c;因为它会指向头节点。//3、根据索引位置插入数据至链表中Status insertLinkList(LinkList *list, int index, ElemType data){if (list &＃61;&＃61; NULL || index <0) {return ERROR;}int i &＃61; 0;LinkList priorNode &＃61; *list;//判断插入的位置&＃xff0c;这里开始位置是0&＃xff0c;index超过链表长度则插入末尾while (i next !&＃61; *list) {priorNode &＃61; priorNode->next;i&＃43;&＃43;;}LinkList newNode &＃61; malloc(sizeof(Node));if (newNode &＃61;&＃61; NULL) {return ERROR;}newNode->data &＃61; data;//插入操作共四步&＃xff0c;看好了&＃xff0c;别眨眼//1.将priorNode->next节点的前驱指向新节点priorNode->next->prior &＃61; newNode;//2.将新节点->next指向原来的priorNode->nextnewNode->next &＃61; priorNode->next;//3.将priorNode->next指向新节点priorNode->next &＃61; newNode;//4.新节点的前驱指向priorNodenewNode->prior &＃61; priorNode;return OK;}

4、根据索引位置删除节点

这里不需要判断尾节点的next是否为Null&＃xff0c;因为它会指向头节点。//4、根据索引位置删除节点Status deleteLinkListByIndex(LinkList *list, int index, ElemType *data){if (*list &＃61;&＃61; NULL || index <0) {return ERROR;}LinkList locaNode &＃61; *list;int i &＃61; 0;//注意别删了头节点while (i <&＃61; index) {locaNode &＃61; locaNode->next;if (locaNode &＃61;&＃61; *list) {printf("没有这个你想要删除的节点\n");return ERROR;}i&＃43;&＃43;;}//开始删除&＃xff0c;只需要做两步locaNode->prior->next &＃61; locaNode->next;locaNode->next->prior &＃61; locaNode->prior;*data &＃61; locaNode->data;free(locaNode);return OK;}

5、根据存储的值删除节点

这里不需要判断尾节点的next是否为Null&＃xff0c;因为它会指向头节点。//5、根据存储的值删除节点Status deleteLinkListByData(LinkList *list, ElemType data){if (*list &＃61;&＃61; NULL) {return ERROR;}LinkList locaNode &＃61; (*list)->next;while (locaNode !&＃61; *list) {if (locaNode->data &＃61;&＃61; data) {break;}locaNode &＃61; locaNode->next;}if (locaNode &＃61;&＃61; *list) {printf("没有这个你想要删除的节点\n");return ERROR;}//开始删除&＃xff0c;只需要做两步locaNode->prior->next &＃61; locaNode->next;locaNode->next->prior &＃61; locaNode->prior;free(locaNode);return OK;}

6、根据值查找节点

尾节点的next可是头节点哦&＃xff0c;找到它就是最后一个了。//6、查找元素Status selectNode(LinkList list, ElemType data, LinkList *locaNode){if (list &＃61;&＃61; NULL) {return ERROR;}LinkList p &＃61; list->next;while (p !&＃61; list) {if (p->data &＃61;&＃61; data) {*locaNode &＃61; p;break;}p &＃61; p->next;}if (*locaNode &＃61;&＃61; NULL) {printf("没有这个你想要的节点\n");return ERROR;}else {return OK;}}

其它代码

#include "stdlib.h"#define OK 1#define ERROR 0//元素类型typedef int ElemType;//状态类型typedef int Status;//定义节点结构体typedef struct Node {struct Node *prior;ElemType data;struct Node *next;} Node;typedef Node *LinkList;int main(int argc, const char * argv[]) {LinkList list;initLinkList(&list);for (int i &＃61; 0; i <10; i &＃43;&＃43;) {insertLinkList(&list, i, i);}printfLinkLisk(list);int index, data;printf("输入你想插入的位置&＃xff08;从0开始&＃xff09;和存储的值:");scanf("%d %d",&index,&data);insertLinkList(&list, index, data);printfLinkLisk(list);printf("输入你想删除的位置&＃xff08;从0开始&＃xff09;:");scanf("%d",&index);deleteLinkListByIndex(&list, index, &data);printfLinkLisk(list);printf("输入你想删除的节点的值&＃xff08;只删最前的那个&＃xff09;:");scanf("%d",&data);deleteLinkListByData(&list, data);printfLinkLisk(list);printf("\n");return 0;}

输出结果&＃xff1a;

—END—

看到这里是不是又学到了很多新知识呢~

另外&＃xff0c;对于准备学习C/C&＃43;&＃43;编程的小伙伴&＃xff0c;如果你想更好的提升你的编程核心能力&＃xff08;内功&＃xff09;不妨从现在开始&＃xff01;

C语言C&＃43;&＃43;编程学习交流圈子&＃xff0c;QQ群&＃xff1a;946108597【点击进入】微信公众号&＃xff1a;C语言编程学习基地

整理分享&＃xff08;多年学习的源码、项目实战视频、项目笔记&＃xff0c;基础入门教程&＃xff09;

欢迎转行和学习编程的伙伴&＃xff0c;利用更多的资料学习成长比自己琢磨更快哦&＃xff01;