关于双向循环列表的插入、删除、遍历

目录

双向循环链表公式

初始化双向循环链表

构建双向循环链表结构体

// 双向循环链表节点定义 typedef struct double_loop_node { char data[DATA_LEN]; // 数据域，存储数据长度 struct double_loop_node *next; // 指向下一个节点的指针 struct double_loop_node *prev; // 指向前一个节点的指针 } Double_Node, *Double_link_p; // 定义节点类型和指针类型别名

创建一个头节点

// 创建一个头节点 Double_link_p head_node = Create_Node(); if (head_node == (Double_link_p)-1) // 检查头节点创建是否成功 { printf("创建双向循环链表失败！\n"); // 输出失败信息 return -1; // 返回错误码 } else { printf("创建双向循环链表成功！\n"); // 输出成功信息 }

创建一个新节点

`// 定义一个函数Create_Node，来创建一个新节点
Double_link_p Create_Node()
{
// 申请新节点的内存空间
Double_link_p new_node = (Double_link_p)malloc(sizeof(Double_Node));
if (new_node == (Double_link_p)NULL) // 检查内存申请是否成功
{
perror("malloc failed ...");
return (Double_link_p)-1;
}

// 清空新节点的数据区域,进行初始化
memset(new_node, 0, sizeof(Double_Node));// 将新节点的前驱和后继指针指向自身，体现“循环”
new_node->next = new_node;
new_node->prev = new_node;return new_node; // 返回新节点的指针

}`

创建一个功能函数用来进行检测操作链表的插入、删除、遍历

`int Mode_Select(Double_link_p head_node)
{
// 如果头节点为空，输出提示信息并返回错误码
if (head_node == (Double_link_p)NULL)
{
printf("头节点为空！\n");
return -1;
}

int select_num; // 用于存放用户输入的选择编号
while (1)       // 无限循环，直到用户选择退出
{system("clear"); // 清屏// 显示菜单项printf("<<<< 1 头插添加数据节点 >>>>\n");printf("<<<< 2 尾插添加数据节点 >>>>\n");printf("<<<< 3 指定检索数据节点 >>>>\n");printf("<<<< 4 指定添加数据节点 >>>>\n");printf("<<<< 5 指定删除数据节点 >>>>\n");printf("<<<< 6 遍历链表数据节点 >>>>\n");printf("<<<< 8 退出双向循环链表 >>>>\n");// 获取用户的指令输入scanf("%d", &select_num);// 根据用户选择进行相应的操作switch (select_num){case 1:Head_Add_Node(head_node);break;                  // 头插法添加数据节点case 2:Tail_Add_Node(head_node);break;                  // 尾插法添加数据节点case 3:Retrieve_Add_Node(head_node);break;              // 检索目标数据节点并返回case 4:Appoint_Add_Node(head_node);break;               // 目标位置添加数据节点case 5:Del_Add_Node(head_node);break;                   // 指定位置删除节点  case 6:Ergodic_List_Node(head_node);break;              // 遍历整个链表并输出显示case 8:return 0;                                        // 直接退出双向循环链表default:printf("没有此项指令，请重新输入！\n");break;     // 输入无效，提示重新输入}sleep(1); // 延时1秒，使用户能看到执行结果
}
return 0; // 正常退出

}`

插入数据节点

头插

`// 定义函数 Head_Add_Node，用于在双向循环链表中头部位置删除节点
int Head_Add_Node(Double_link_p head_node)
{
// 判断头节点是否异常
if (head_node == (Double_link_p)NULL)
{
printf("头节点异常！\n");
return -1;
}

// 创建一个新节点
Double_link_p new_node = Create_Node();
if (new_node == (Double_link_p)NULL) // 判断创建新节点是否成功
{printf("Create new node faile!\n");return -1;
}printf("输入头插数据："); // 提示输入头插数据
scanf("%s", new_node->data);
while (getchar() != '\n'); // 清空输入缓冲区new_node->next = head_node->next; // 新节点的下一个节点指向原头节点的下一个节点
head_node->next->prev = new_node; // 原头节点的下一个节点的前驱指向新节点
head_node->next = new_node;       // 原头节点的下一个节点指向新节点
new_node->prev = head_node;       // 新节点的前驱指向原头节点printf("头插成功！\n"); // 打印头插成功
return 0;

}`

尾插

`// 定义函数 Tail_Add_Node，用于在双向循环链表中尾部位置删除节点
int Tail_Add_Node(Double_link_p head_node)
{
//判断头节点是否异常
if(head_node == (Double_link_p)NULL)
{
printf("头节点异常！\n");
return -1;
}

//创建一个新节点
Double_link_p new_node = Create_Node();
if(new_node == (Double_link_p)NULL)  //判断新节点是否创建成功
{printf("Create new node faile!\n");return -1;
}printf("输入尾插数据:");
scanf("%s",new_node->data);
while(getchar()!='\n');  //清空输入缓存区new_node->prev        = head_node->prev;   //新节点的前驱指向头节点的前驱
head_node->prev->next = new_node;          //头节点的前驱的下一个next指向新节点
new_node->next        = head_node;         //新节点的下一个指针指向头节点
head_node->prev       = new_node;          //头节点的前驱指向新节点printf("尾插成功！\n");
return 0;

}`

检索特定位置节点

`// 定义函数 Retrieve_Add_Node，用于在双向循环链表中检索特定数据并返回对应节点指针
Double_link_p Retrieve_Add_Node(Double_link_p head_node)
{
// 判断头节点是否异常
if(head_node == (Double_link_p)NULL)
{
printf("头节点异常！\n");
return (Double_link_p)-1; // 返回异常指针值
}
// 判断循环链表是否为空
else if(head_node->next == head_node && head_node->prev == head_node)
{
printf("空链表，无需检索！\n");
return (Double_link_p)-1; // 返回异常指针值
}
else
{
printf("输入要操作的数据：");
char obj_data[DATA_LEN] = "\0"; // 声明字符数组，用于存储用户输入的数据
scanf("%s", obj_data);

    // 循环遍历链表for(Double_link_p tmp_node = head_node->next; tmp_node != head_node; tmp_node = tmp_node->next){// 检查当前节点数据是否匹配目标数据if(strcmp(tmp_node->data, obj_data) == 0){printf("目标节点已找到！数据：%s---地址：%p\n",tmp_node->data,tmp_node);return tmp_node; // 返回匹配节点指针}}
}
printf("在此库中找不到该数据！\n");
// 若未找到匹配节点，则返回空指针
return (Double_link_p)0;

}`

指定位置插

`// 定义函数 Appoint_Add_Node，用于在双向循环链表中指定位置插入新节点
int Appoint_Add_Node(Double_link_p head_node)
{
// 判断头节点是否异常
if(head_node == (Double_link_p)NULL)
{
printf("头节点异常！\n");
return -1; // 返回异常值
}
// 判断链表是否为空，空链表默认头插
else if(head_node->next == head_node && head_node->prev == head_node)
{
printf("空链表，默认头插！\n");
// 调用头插函数进行插入
if(Head_Add_Node(head_node) == -1)
{
printf("头插失败！\n");
return -1; // 头插失败，返回异常值
}
}
// 链表非空时，检索找到目标节点进行节点插入
else
{
// 创建目标节点
Double_link_p obj_node = Retrieve_Add_Node(head_node);
// 判断目标节点是否创建成功
if(obj_node == (Double_link_p)-1)
{
printf("链表异常，创建目标节点失败！\n");
return -1; // 目标节点创建失败，返回异常值
}
// 判断在此链表中是否有此节点
else if(obj_node == (Double_link_p)0)
{
printf("未找到目标节点！\n");
return 0; // 未找到目标节点，返回0
}
else
{
// 创建要插入的新节点
Double_link_p new_node = Create_Node();
// 判断新节点是否创建成功
if(new_node == (Double_link_p)NULL)
{
printf("创建新节点失败！\n");
return -1; // 新节点创建失败，返回异常值
}

        printf("输入新节点数据：");// 从标准输入读取新节点数据scanf("%s", new_node->data);while(getchar() != '\n'); // 清空输入缓冲区// 调整指针指向，完成插入操作new_node->next = obj_node->next;    // 新节点的下一个指针指向目标节点的下一个节点obj_node->next->prev = new_node;    // 目标节点的下一个节点的前一个指针指向新节点new_node->prev = obj_node;          // 新节点的前一个指针指向目标节点obj_node->next = new_node;          // 目标节点的下一个指针指向新节点printf("指定位置插入成功！\n");}
}return 0; // 返回成功值

}`

删除数据节点

`// 定义函数 Del_Add_Node，用于删除双向循环链表中的指定节点
int Del_Add_Node(Double_link_p head_node)
{
// 判断头节点是否异常
if(head_node == (Double_link_p)NULL)
{
printf("头节点异常，无法删除！\n");
return -1; // 返回异常值
}
// 判断链表是否为空
else if(head_node->next == head_node && head_node->prev == head_node)
{
printf("空链表，无法删除！\n");
return 0; // 返回0，表示无需删除
}
else
{
// 检索要删除的节点
Double_link_p del_node = Retrieve_Add_Node(head_node);
// 判断链表异常情况
if(del_node == (Double_link_p)-1)
{
printf("链表异常，无法删除！\n");
return -1; // 返回异常值
}
else if(del_node == (Double_link_p)0)
{
printf("无此数据或者链表为空，无需删除！\n");
return 0; // 返回0，表示无需删除
}
else
{
// 调整指针指向，完成删除操作
del_node->prev->next = del_node->next; // 被删除节点的前一个节点的下一个指针指向被删除节点的下一个节点
del_node->next->prev = del_node->prev; // 被删除节点的下一个节点的前驱指针指向被删除节点的前一个节点
del_node->next = NULL; // 被删除节点的下一个指针置空
del_node->prev = NULL; // 被删除节点的前驱指针置空
}

    free(del_node); // 释放被删除节点的空间printf("删除节点成功！\n");
}return 0; // 返回成功值

}`

遍历双向循环链表并在用户终端显示

`// 定义函数 Ergodic_List_Node，用于遍历双向循环链表并在用户终端显示
int Ergodic_List_Node(Double_link_p head_node)
{
// 判断头节点是否异常
if (head_node == (Double_link_p)NULL)
{
printf("头节点异常！\n");
return -1; // 返回异常值
}
// 判断链表是否为空
else if(head_node->next == head_node && head_node->prev == head_node)
{
printf("空链表，无需遍历！\n");
}
else
{
printf("--------------\n");
// 循环链表输出
for(Double_link_p tmp_node = head_node->next; tmp_node != head_node; tmp_node = tmp_node->next)
{
printf("输出数据:%s----地址：%p\n", tmp_node->data, tmp_node); // 打印节点数据和地址
}
printf("--------------\n");
}

return 0; // 返回成功值

}`

其他

头文件

`#include <stdio.h> // 标准输入输出头文件

include <string.h> // 字符串处理头文件 memset/清空

include <stdlib.h> // 标准库头文件 malloc/申请堆空间

include <unistd.h> // POSIX操作系统API头文件 sleep延时

define DATA_LEN 60 // 定义数据域长度为60`

函数声明

Double_link_p Create_Node(); // 声明创建新节点函数 Double_link_p Retrieve_Add_Node(Double_link_p head_node); // 声明一个检索函数用来检索目标节点并返回 int Mode_Select(Double_link_p head_node); // 声明模式选择函数 int Head_Add_Node(Double_link_p head_node); // 声明一个头插函数 int Appoint_Add_Node(Double_link_p head_ndoe); // 声明一个指定位位置添加函数 int Tail_Add_Node(Double_link_p head_node); // 声明一个尾插函数 int Del_Add_Node(Double_link_p head_node); // 声明一个删除节点函数 int Ergodic_List_Node(Double_link_p head_node); // 声明一个遍历链表函数用来检测是否成功实现功能

main函数

`int main()
{
// 创建一个头节点
Double_link_p head_node = Create_Node();
if (head_node == (Double_link_p)-1) // 检查头节点创建是否成功
{
printf("创建双向循环链表失败！\n"); // 输出失败信息
return -1; // 返回错误码
}
else
{
printf("创建双向循环链表成功！\n"); // 输出成功信息
}

// 选择操作模式
Mode_Select(head_node);return 0; // 返回正常退出码

}`