本文主要介绍了C语言入门到精通--双向循环链表的实现，通过具体的内容向大家展现，希望对大家C语言开发的学习有所帮助。

双向链表的存储结构

        在双向循环链表中，每个结点包括三个域，分别是数据域（data域）、指向后继结点的指针域（next域）和指向前驱结点的指针域（pre域）。

双向循环链表结点结构 

和单链表相同，双向链表也有带头结点结构和不带头结点结构两种，带头结点结构的双向链表更为常见，故本篇讨论带头结点结构的双向循环链表。

空链表 

非空链表 

双向循环链表的指针关系

双向循环链表的指针关系

p->next->pre = p;

p->pre->next = p;

 双向循环链表的操作实现

链表尾部插入结点

//直接插入链表尾部

void AddList(DLNode *head, DLNode *node){

DLNode *temp = head;  //头结点不能动，所以需要辅助遍历指针temp 

while(temp->next != head)  //遍历找到temp最后一个结点位置 

temp = temp->next;  //没有到最后就指向下一个结点位置

//当推出while循环时，temp指向了最后一个结点

temp->next = node;  //插入步骤① 

node->pre = temp;  //插入步骤② 

node->next = head;  //插入步骤③ 

head->pre = node;  //插入步骤④ 

} 

按照编号顺序插入结点

 双向链表插入结点

//按照编号顺序插入链表

int AddByOrder(DLNode *head, DLNode *node){

DLNode *temp = head->next;  //头结点不能动，所以需要辅助遍历指针temp 

//temp == head 时，直接插入最后即可。

//temp->no > node->no时，说明已经找到。

//这里要特别注意是 temp->no，而不是temp->no，因为 temp->no是头结点的，而头结点没有信息 

while(temp != head && temp->no < node->no) {

temp = temp->next;

}

//判断temp->no是否等于node->no ,如果等于，则说明该编号结点已存在，不能插入

//要加上 temp != head 这个判断条件，否则，在链表为空时，temp->no会出现错误 

if(temp != head && temp->no == node->no){

printf("编号为 %d 的结点已存在，不能插入\n", node->no);

return 0;

}

//否则，则可以插入链表

node->pre = temp->pre;  //插入步骤① 

temp->pre->next = node;  //插入步骤② 

node->next = temp;  //插入步骤③ 

temp->pre = node;  //插入步骤④ 

return 1;

} 

删除结点

双向链表删除结点

//删除编号为 no 的结点

int DelNode(DLNode *head, int no){

//定义辅助指针 ,head暂时不能没有，故temp1指向head->next

DLNode *temp = head->next;

//查找待修改结点的前一个结点

//temp->next == head 时，没有找到该节点 

//这里要特别注意是 temp->no，而不是temp->no，因为 temp->no是头结点的，而头结点没有信息  

while(temp->next != head && temp->no != no){

temp = temp->next;

}

//判断temp->no是否等于no ,如果等于，则说明该编号结点已找到

//要加上 temp->next != head 这个判断条件，否则，在链表为空时，temp->no会出现错误 

if(temp->next != head && temp->no == no){

temp->pre->next = temp->next;  //删除步骤①temp2指向要删除的结点 

temp->next->pre = temp->pre;  //删除步骤②删除

free(temp);

temp = NULL; 

return 1;

}else{

printf("没有找到编号为 %d 的结点\n", no);

return 0;

}

}

 求当前结点个数

//求当前数据元素个数

int ListLength(DLNode *head){

DLNode *temp = head;  //头结点不能动，temp指向head

int count = 0;   //count初始化为0 

while(temp->next != head){  //循环计数，temp->next == NULL时，指向单链表的最后一个元素 

temp = temp->next;  //指向下一个结点 

count++;  //计数器加1 

}

return count;

}

修改结点信息（和单链表修改节点信息思路一样）

//修改结点信息

int UpdateNode(DLNode *head, DLNode *newnode){

//根据结点 no 编号来修改，所以 no 编号不能动 

DLNode *temp = head;  //头结点不能动，所以需要辅助遍历指针temp 

//查找待修改结点的前一个结点

//temp->next == head 时，没有找到该节点 

//这里要特别注意是 temp->next->no，而不是temp->no，因为 temp->no是头结点的，而头结点没有信息  

while(temp->next != head && temp->next->no != newnode->no){

temp = temp->next;

} 

//判断temp->no是否等于newnode->no ,如果等于，则说明该编号结点已找到

//要加上 temp->next != head 这个判断条件，否则，在链表为空时，temp->next->no会出现错误 

if(temp->next != head && temp->next->no == newnode->no){

strcpy(temp->next->name, newnode->name);

return 1;

}else{

printf("没有找到编号为 %d 的结点\n", newnode->no);

return 0;

}

} 

显示链表信息（遍历）

//显示链表【遍历】

int ShowList(DLNode *head){

//定义temp辅助遍历 

DLNode *temp = head->next;

//判断链表是否为空 

if(head->next == head){

printf("链表为空\n");

return 0;

}

//遍历单链表 

while(temp != head){

printf("[%d,%s]\n",temp->no,temp->name);  //打印链表结点 

temp = temp->next;  //指向下一个结点 

}

return 1;

} 

完整代码展示

#include <stdio.h>

#include <stdlib.h>

#include <string.h>

#include <malloc.h>

/* run this program using the console pauser or add your own getch, system("pause") or input loop */

//双向循环链表的结点定义 

typedef struct Node{

int no;   //编号 

char name[10];  //姓名

struct Node *next;  //Node类型的前驱指针 

struct Node *pre;  //Node类型的后继指针

}DLNode;

//初始化 

void ListInitiate(DLNode **head){

*head = (DLNode *)malloc(sizeof(DLNode));  //申请头节点，由head指示其地址

(*head)->pre = *head;  //前驱指针循环链表 

(*head)->next = *head;  //后继指针循环链表 

} 

//求当前数据元素个数

int ListLength(DLNode *head){

DLNode *temp = head;  //头结点不能动，temp指向head

int count = 0;   //count初始化为0 

while(temp->next != head){  //循环计数，temp->next == NULL时，指向单链表的最后一个元素 

temp = temp->next;  //指向下一个结点 

count++;  //计数器加1 

}

return count;

}

//直接插入链表尾部

void AddList(DLNode *head, DLNode *node){

DLNode *temp = head;  //头结点不能动，所以需要辅助遍历指针temp 

while(temp->next != head)  //遍历找到temp最后一个结点位置 

temp = temp->next;  //没有到最后就指向下一个结点位置

//当推出while循环时，temp指向了最后一个结点

temp->next = node;  //插入步骤① 

node->pre = temp;  //插入步骤② 

node->next = head;  //插入步骤③ 

head->pre = node;  //插入步骤④ 

} 

//按照编号顺序插入链表

int AddByOrder(DLNode *head, DLNode *node){

DLNode *temp = head->next;  //头结点不能动，所以需要辅助遍历指针temp 

//temp == head 时，直接插入最后即可。

//temp->no > node->no时，说明已经找到。

//这里要特别注意是 temp->no，而不是temp->no，因为 temp->no是头结点的，而头结点没有信息 

while(temp != head && temp->no < node->no) {

temp = temp->next;

}

//判断temp->no是否等于node->no ,如果等于，则说明该编号结点已存在，不能插入

//要加上 temp != head 这个判断条件，否则，在链表为空时，temp->no会出现错误 

if(temp != head && temp->no == node->no){

printf("编号为 %d 的结点已存在，不能插入\n", node->no);

return 0;

}

//否则，则可以插入链表

node->pre = temp->pre;  //插入步骤① 

temp->pre->next = node;  //插入步骤② 

node->next = temp;  //插入步骤③ 

temp->pre = node;  //插入步骤④ 

return 1;

} 

//修改结点信息

int UpdateNode(DLNode *head, DLNode *newnode){

//根据结点 no 编号来修改，所以 no 编号不能动 

DLNode *temp = head;  //头结点不能动，所以需要辅助遍历指针temp 

//查找待修改结点的前一个结点

//temp->next == head 时，没有找到该节点 

//这里要特别注意是 temp->next->no，而不是temp->no，因为 temp->no是头结点的，而头结点没有信息  

while(temp->next != head && temp->next->no != newnode->no){

temp = temp->next;

} 

//判断temp->no是否等于newnode->no ,如果等于，则说明该编号结点已找到

//要加上 temp->next != head 这个判断条件，否则，在链表为空时，temp->next->no会出现错误 

if(temp->next != head && temp->next->no == newnode->no){

strcpy(temp->next->name, newnode->name);

return 1;

}else{

printf("没有找到编号为 %d 的结点\n", newnode->no);

return 0;

}

} 

//删除编号为 no 的结点

int DelNode(DLNode *head, int no){

//定义辅助指针 ,head暂时不能没有，故temp1指向head->next

DLNode *temp = head->next;

//查找待修改结点的前一个结点

//temp->next == head 时，没有找到该节点 

//这里要特别注意是 temp->no，而不是temp->no，因为 temp->no是头结点的，而头结点没有信息  

while(temp->next != head && temp->no != no){

temp = temp->next;

}

//判断temp->no是否等于no ,如果等于，则说明该编号结点已找到

//要加上 temp->next != head 这个判断条件，否则，在链表为空时，temp->no会出现错误 

if(temp->next != head && temp->no == no){

temp->pre->next = temp->next;  //删除步骤①temp2指向要删除的结点 

temp->next->pre = temp->pre;  //删除步骤②删除

free(temp);

temp = NULL; 

return 1;

}else{

printf("没有找到编号为 %d 的结点\n", no);

return 0;

}

}

//显示链表【遍历】

int ShowList(DLNode *head){

//定义temp辅助遍历 

DLNode *temp = head->next;

//判断链表是否为空 

if(head->next == head){

printf("链表为空\n");

return 0;

}

//遍历单链表 

while(temp != head){

printf("[%d,%s]\n",temp->no,temp->name);  //打印链表结点 

temp = temp->next;  //指向下一个结点 

}

return 1;

} 

//撤销单链表

void Destroy(DLNode **head){

//定义辅助指针 ,head暂时不能没有，故temp1指向head，temp2配合释放掉 

DLNode *temp1 = NULL, *temp2 = NULL;

int i, n = ListLength(*head);

//定义temp1辅助遍历 

temp1 = *head;

for(i = 0; i <= n; i++){  //最终：temp1 = NULL，temp2被释放 

temp2 = temp1;   //temp2指向temp1，便于释放 

temp1 = temp1->next;  //temp1指向下一个，避免链表丢失 

free(temp2);  //释放temp2 

temp2 = NULL;  //避免free都成为“野指针” 

}

*head = NULL;  //最后让head = NULL 

}

//测试 

int main(int argc, char *argv[]) {

DLNode *head;  //定义头指针变量

DLNode *node1, *node2, *node3, *newnode;   //定义测试结点

//初始化各结点

ListInitiate(&head);

ListInitiate(&node1);

ListInitiate(&node2);

ListInitiate(&node3);

ListInitiate(&newnode);

//定义各结点 

node1->no = 1;

strcpy(node1->name, "Lucy");

node2->no = 2;

strcpy(node2->name, "Jimy");

node3->no = 3;

strcpy(node3->name, "Zoma");

newnode->no = 3;

strcpy(newnode->name, "Candy");

printf("当前数据个数：%d\n", ListLength(head));

/*

//测试插入链表尾部

AddList(head, node1);

printf("当前数据个数：%d\n", ListLength(head));

AddList(head, node3);

printf("当前数据个数：%d\n", ListLength(head));

AddList(head, node2);

printf("当前数据个数：%d\n", ListLength(head));

*/

//按照编号插入

AddByOrder(head, node2);

printf("当前数据个数：%d\n", ListLength(head));

//测试插入一样编号的结点结果是否正确 

AddByOrder(head, node2);

printf("当前数据个数：%d\n", ListLength(head));

AddByOrder(head, node1);

printf("当前数据个数：%d\n", ListLength(head));

AddByOrder(head, node3); 

printf("当前数据个数：%d\n", ListLength(head));

//显示链表

printf("修改前链表信息如下：\n");

ShowList(head);

//测试修改结点信息

UpdateNode(head, newnode); 

//显示链表

printf("修改后链表信息如下：\n");

ShowList(head);

//测试删除结点信息

DelNode(head, 2); 

//显示链表

printf("删除后链表信息如下：\n");

ShowList(head);

//撤销单链表

Destroy(&head);

return 0;

}

我是小职，记得找我

✅ 解锁高薪工作

✅ 免费获取基础课程·答疑解惑·职业测评