双向循环链表
定义
双向循环链表和它名字的表意一样，就是把双向链表的两头连接，使其成为了一个环状链表。只需要将表中最后一个节点的next指针指向头节点，头节点的prior指针指向尾节点，链表就能成环儿，如图所示：
需要注意的是，虽然双向循环链表成环状，但本质上还是双向链表，因此在双向循环链表中，依然能够找到头指针和头节点等。双向循环链表和双向链表相比，唯一的不同就是双向循环链表首尾相连，其他都完全一样。
注意：因为我上面已经讲了双向链表，所以这里只注重讲他们的实现差异。另因为带头节点会更好操作，所以我的代码都有头节点。
1、双向循环链表的创建
初始化时需要将头节点的next和prior都指向自己。
//1、初始化双向循环链表（带头节点）Status initLinkList(LinkList *list){ //创建头节点 *list = malloc(sizeof(Node)); if (*list == NULL) { return ERROR; } //前驱和后继都指向自己 (*list)->prior = *list; (*list)->data = -1; (*list)->next = *list; printf("已初始化链表~\n"); return OK;}
2、遍历双向循环链表
注意它的尾节点的next不再是Null，而是头节点
//2、遍历双向循环链表void printfLinkLisk(LinkList list){ printf("遍历链表：\n"); if (list == NULL || list->next == list) { printf("这是一个空链表\n"); return; } LinkList p = list; //判断next是否全部正确 printf("根据next从前往后遍历："); while (p->next != list) { printf("%d ",p->next->data); p = p->next; } printf("\n"); //判断prior是否全部正确 printf("根据prior从后往前遍历："); while (p != list) { printf("%d ",p->data); p = p->prior; } printf("\n");}
3、根据索引位置添加节点
这里不需要判断尾节点的next是否为Null，因为它会指向头节点。
//3、根据索引位置插入数据至链表中Status insertLinkList(LinkList *list, int index, ElemType data){ if (list == NULL || index < 0) { return ERROR; } int i = 0; LinkList priorNode = *list; //判断插入的位置，这里开始位置是0，index超过链表长度则插入末尾 while (i < index && priorNode->next != *list) { priorNode = priorNode->next; i++; } LinkList newNode = malloc(sizeof(Node)); if (newNode == NULL) { return ERROR; } newNode->data = data; //插入操作共四步，看好了，别眨眼 //1.将priorNode->next节点的前驱指向新节点 priorNode->next->prior = newNode; //2.将新节点->next指向原来的priorNode->next newNode->next = priorNode->next; //3.将priorNode->next指向新节点 priorNode->next = newNode; //4.新节点的前驱指向priorNode newNode->prior = priorNode; return OK;}
4、根据索引位置删除节点
这里不需要判断尾节点的next是否为Null，因为它会指向头节点。
//4、根据索引位置删除节点Status deleteLinkListByIndex(LinkList *list, int index, ElemType *data){ if (*list == NULL || index < 0) { return ERROR; } LinkList locaNode = *list; int i = 0; //注意别删了头节点 while (i <= index) { locaNode = locaNode->next; if (locaNode == *list) { printf("没有这个你想要删除的节点\n"); return ERROR; } i++; } //开始删除，只需要做两步 locaNode->prior->next = locaNode->next; locaNode->next->prior = locaNode->prior; *data = locaNode->data; free(locaNode); return OK;}
5、根据存储的值删除节点
这里不需要判断尾节点的next是否为Null，因为它会指向头节点。
//5、根据存储的值删除节点Status deleteLinkListByData(LinkList *list, ElemType data){ if (*list == NULL) { return ERROR; } LinkList locaNode = (*list)->next; while (locaNode != *list) { if (locaNode->data == data) { break; } locaNode = locaNode->next; } if (locaNode == *list) { printf("没有这个你想要删除的节点\n"); return ERROR; } //开始删除，只需要做两步 locaNode->prior->next = locaNode->next; locaNode->next->prior = locaNode->prior; free(locaNode); return OK;}
6、根据值查找节点
尾节点的next可是头节点哦，找到它就是最后一个了。
//6、查找元素Status selectNode(LinkList list, ElemType data, LinkList *locaNode){ if (list == NULL) { return ERROR; } LinkList p = list->next; while (p != list) { if (p->data == data) { *locaNode = p; break; } p = p->next; } if (*locaNode == 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 = 0; i < 10; i ++) { insertLinkList(&list, i, i); } printfLinkLisk(list); int index, data; printf("输入你想插入的位置（从0开始）和存储的值:"); scanf("%d %d",&index,&data); insertLinkList(&list, index, data); printfLinkLisk(list); printf("输入你想删除的位置（从0开始）:"); scanf("%d",&index); deleteLinkListByIndex(&list, index, &data); printfLinkLisk(list); printf("输入你想删除的节点的值（只删最前的那个）:"); scanf("%d",&data); deleteLinkListByData(&list, data); printfLinkLisk(list); printf("\n"); return 0;}
输出结果：
热门跟贴