双向循环链表
目录:
- 实现的操作:
- 结构体定义:
- 相关函数定义:
- 完整程序:
-
- .c文件:
- .h文件:
实现的操作:
void Init_Double_Circular_List(Double_Circular_List *list); //初始化双向循环链表List_Node *__malloc_List_Node(Data_Node *dataNode); //为插入元素申请节点空间--方便操作,将内存申请定义为函数void Insert_Tail(Double_Circular_List *list,Data_Node *dataNode); //尾部插入结点void Insert_Head(Double_Circular_List *list,Data_Node *dataNode); //头部插入结点void Delete_Tail(Double_Circular_List *list); //尾部删除结点void Delete_Head(Double_Circular_List *list); //头部删除结点void Show_List(Double_Circular_List *list); //显示结点元素void Reverse_List(Double_Circular_List *list); //链表逆置void Show_List_Reverse(Double_Circular_List *list); //逆序显示结点元素boolean isEmpty(Double_Circular_List *list); //判断链表结点是否为空void Get_Size(Double_Circular_List *list); //获取链表数量void Id_Modify(Double_Circular_List *list,int ID); //按ID修改结点元素void Id_Find(Double_Circular_List *list,int ID); //按ID查找结点void Id_Insert(Double_Circular_List *list,Data_Node *dataNode,int ID);//按ID插入结点void Id_Delete(Double_Circular_List *list,int ID); //按ID删除结点void Sort(Double_Circular_List *list); //按ID从小到大排序void clear(Double_Circular_List *list); //清空链表void Destory(Double_Circular_List *list); //销毁链表void Test(Double_Circular_List *list,Data_Node *dataNode); //测试案例
结构体定义:
typedef struct {int ID; //存储元素id int val; //此结构体可以存储需要存储的数据元素}Data_Node;typedef struct ListNode{ Data_Node DataNode; //保存数据结点 struct ListNode *pre;//指向前一个结点 struct ListNode *next; //指向后一个结点}List_Node;typedef struct { List_Node *head; //头结点 List_Node *tail; //尾结点 int Size; //存储结点数量}Double_Circular_List;
相关函数定义:
1、初始化双向循环链表:
void Init_Double_Circular_List(Double_Circular_List *list){ List_Node *Node = (List_Node *)malloc(sizeof(List_Node)); if(Node == NULL) { printf("内存申请失败...\n"); exit(-1); } //初始化结点指向自身 --- 头结点不存储元素,作为辅助结点方便操作 Node->next = Node; Node->pre = Node; //初始化头尾结点指向Node结点并初始化结点大小为 0 list->head = Node; list->tail = Node; list->Size = 0;}
2、新结点内存空间申请:
List_Node *__malloc_List_Node(Data_Node *dataNode){ List_Node *Node = (List_Node *)malloc(sizeof(List_Node)); //为插入节点申请内存 if(Node == NULL) { printf("内存申请失败...\n"); return NULL; } Node->DataNode.ID = dataNode->ID;//新结点的ID 存储插入结点的ID Node->DataNode.val = dataNode->val; //新结点的val 存储插入结点的val Node->next = NULL; //结点指向为空 Node->pre = NULL; return Node;//将申请到的结点返回}
3、尾部插入结点:
void Insert_Tail(Double_Circular_List *list,Data_Node *dataNode){ List_Node *Node = __malloc_List_Node(dataNode); //获取申请到的结点 List_Node *nodePre = list->tail; //nodePre指向链表尾部结点 List_Node *nodeNext = list->head; //nodeNext指向链表头结点 Node->next = nodePre->next; //新结点的next指向尾结点的next指向(即头结点) Node->pre = nodePre; //新结点的pre指向尾结点 nodePre->next = Node; //尾结点的next指向新结点 nodeNext->pre = Node; //头结点的pre指向新结点 list->tail = Node; //更新尾结点为新插入结点 list->Size ++; //结点数量加 1 }
4、头部插入结点:
void Insert_Head(Double_Circular_List *list,Data_Node *dataNode){ List_Node *Node = __malloc_List_Node(dataNode); //获取申请到的结点 List_Node *nodeNext = list->head; //nodeNext指向链表头结点 Node->next = nodeNext->next; //新结点的next指向头结点的next指向 Node->pre = nodeNext; //新结点的pre指向头结点或者头结点的next结点的pre指向(两种指向位置相同)亦可用 Node-> pre = nodeNext->next->pre nodeNext->next->pre = Node; //首结点pre指向新结点 nodeNext->next = Node; //头结点的next指向新结点 /* 在头部插入时有两种情况: 已经存在结点元素和无结点元素两种 一、如果已经存在结点元素以上步骤已经实现插入结点, 二、如果无结点元素,此结点是第一个结点则需要改变尾指针指向 */ if(list->Size == 0) { list->tail = Node; } list->Size ++; //结点数量加 1}
5、尾部删除结点:
void Delete_Tail(Double_Circular_List *list) { if(isEmpty(list)) { printf("结点元素为空,无法删除。。。\n"); return ; } List_Node * tmp = list->head; //tmp临时指针存储头结点位置 List_Node *delete = list->tail; //delete临时指针存储尾结点位置 delete->pre->next = delete->next;//尾结点的前一个结点的next指向头结点(或者说是尾结点的next指向) tmp->pre = delete->pre; //头结点的pre指向尾结点的前一个结点(或者说删除节点的前一个结点) list->tail = delete->pre; //更新尾结点为删除结点的前一个结点 free(delete); //释放尾结点空间 list->Size --; //结点元素减 1}
6、头部删除结点:
void Delete_Head(Double_Circular_List *list){ if(isEmpty(list)) { printf("结点元素为空,无法删除。。。\n"); return ; } List_Node * tmp = list->head; //tmp临时指针存储头结点位置 List_Node *delete = list->head->next; //delete临时指针存储首结点位置 delete->next->pre = delete->pre; //首结点的下一结点的pre指向头结点(或删除节点的pre指向) tmp->next = delete->next; //头结点的next指向首结点的next指向(或删除结点的next指向) free(delete); //释放首结点空间 list->Size --; //结点元素减 1}
7、显示链表内容:
void Show_List(Double_Circular_List *list){ if(isEmpty(list)) { printf("结点元素为空,无结点数据显示。。。\n"); return ; } List_Node *tmp = list->head->next; //临时指针保存首结点位置 printf("--------------------------------\n"); printf("| ID | Val |\n"); printf("--------------------------------\n"); while(tmp != list->head) //当临时结点指向的位置和头结点位置相同时跳出循环 { printf("|%5d ||%9d |\n",tmp->DataNode.ID,tmp->DataNode.val); //输出结点元素 tmp = tmp->next; //指向下一元素 } printf("--------------------------------\n"); printf("| size ||%d |\n",list->Size); printf("--------------------------------\n\n\n");}
8、判断链表是否为空:
boolean isEmpty(Double_Circular_List *list){ if(list->head == list->tail) return TRUE; return FALSE;}
9、测试
快速插入几个结点方便调试
void Test(Double_Circular_List *list,Data_Node *dataNode){ for(int i = 3;i < 8;i++) { dataNode->ID = i; dataNode->val = i * 10; Insert_Tail(list,dataNode); }}
10、获取链表结点数量:
void Get_Size(Double_Circular_List *list){ printf("链表结点数量为:\t%d\n",list->Size);}
11、链表逆序显示:
void Show_List_Reverse(Double_Circular_List *list){//从尾结点开始通过指向pre结点完成逆序遍历 if(isEmpty(list)) { printf("结点元素为空,无结点数据显示。。。\n"); return ; } List_Node *tmp = list->tail; //临时指针保存尾结点位置 printf("--------------------------------\n"); printf("| ID | Val |\n"); printf("--------------------------------\n"); while(tmp != list->head) //当临时结点指向的位置和头结点位置相同时跳出循环 { printf("|%5d ||%9d |\n",tmp->DataNode.ID,tmp->DataNode.val); //输出结点元素 tmp = tmp->pre; //指向前一元素 }}
12、链表逆置:
本程序采用将原链表结点从首结点开始的结点依次遍历,每遍历一个结点将此结点从头部插入,最终完成逆置
void Reverse_List(Double_Circular_List *list){ if(isEmpty(list)) { printf("结点元素为空,无法逆置。。。\n"); return ; } /* 思路: 遍历结点,每遍历一个结点头部插入; 逆置还可以通过双指针的方法实现,此方法在单链表中也已经实现 */ List_Node *tmp = list->head->next;//获取首结点位置 List_Node *delete = tmp; //断开头结点和首结点间的指向,将头结点恢复为初始化的状态 list->tail = list->head; list->head->next = list->head; list->head->pre = list->head; list->Size = 0; //遍历插入结点 while(tmp != list->head) { Insert_Head(list,&tmp->DataNode); //头部插入 tmp = tmp->next; //指向下一结点 free(delete);//释放空间 delete = tmp;//更新删除结点 }}
13、按ID修改结点元素:
void Id_Modify(Double_Circular_List *list,int ID){ int val; if(isEmpty(list)) { printf("结点元素为空,无法修改。。。\n"); return ; } List_Node *tmp = list->head->next; //保存首结点元素地址 //当结点id 和查找的 id不同时结点向下一结点查找 //当链表被遍历完或者找到id对应结点时结束查找 while(tmp->DataNode.ID != ID && tmp != list->head) { tmp = tmp->next; } if(tmp == list->head) { printf("未找到对应 id 结点\n"); return ; } printf("请输入要修改的 val :\n"); scanf("%d",&val); tmp->DataNode.val = val; //将修改后的 val 替换该 id 的 val}
14、按ID查找结点:
void Id_Find(Double_Circular_List *list,int ID){ if(isEmpty(list)) { printf("结点元素为空,无法查找。。。\n"); return ; } List_Node *tmp = list->head->next; //当结点id 和查找的 id不同时结点向下一结点查找 //当链表被遍历完或者找到id对应结点时结束查找 while(tmp->DataNode.ID != ID && tmp != list->head) { tmp = tmp->next; } //如果tmp == list->head 说明遍历了所有结点均未找到 if(tmp == list->head) { printf("未找到对应 id 结点\n"); return ; } printf("ID = %d 结点 val 为:\t%d\n",tmp->DataNode.ID,tmp->DataNode.val);}
15、按ID插入结点:
1、注意判断链表此时是否为空,若为空则直接插入结点
2、若插入结点ID均大于当前链表结点的ID,在尾部插入结点
void Id_Insert(Double_Circular_List *list,Data_Node *dataNode,int ID){ if(!isEmpty(list)) //链表不为空 { List_Node *tmp = list->head->next;//存储首结点元素 //链表的结点ID 均小于插入结点ID时在尾部插入 while(ID > tmp->DataNode.ID && tmp != list->head) { tmp = tmp->next; } //遍历完链表未找到大于插入结点ID的结点,在尾部插入结点 if(tmp == list->head) { List_Node *Node = __malloc_List_Node(dataNode); //获取申请到的结点 List_Node *nodePre = list->tail; //nodePre指向链表尾部结点 List_Node *nodeNext = list->head; //nodeNext指向链表头结点 Node->next = nodePre->next; //新结点的next指向尾结点的next指向(即头结点) Node->pre = nodePre; //新结点的pre指向尾结点 nodePre->next = Node; //尾结点的next指向新结点 nodeNext->pre = Node; //头结点的pre指向新结点 list->tail = Node; //更新尾结点为新插入结点 list->Size ++; //结点数量加 1 } else //在中间结点插入的情况 { List_Node *Node = __malloc_List_Node(dataNode); //获取申请到的结点 Node->next = tmp; //新结点的next指向ID较大的结点 Node->pre = tmp->pre;//新结点的pre指向ID较大结点的前一个结点 tmp->pre->next = Node; //较大结点的前一个结点指向新结点 tmp->pre = Node; //较大结点的pre指向新结点 list->Size ++; } } if(isEmpty(list)) //链表结点元素为空时直接插入 { List_Node *Node = __malloc_List_Node(dataNode); //获取申请到的结点 List_Node *nodeNext = list->head; //nodeNext指向链表头结点 Node->next = nodeNext; //新结点的next指向头结点 Node->pre = nodeNext; //新结点的pre指向头结点 nodeNext->next = Node; //头结点next指向新结点 nodeNext->pre = Node; //头结点的pre指向新结点 list->tail = Node; //修改尾指针指向 list->Size ++; //结点数量加 1 }}
16、按ID删除结点:
void Id_Delete(Double_Circular_List *list,int ID){ if(isEmpty(list)) { printf("结点元素为空,无法删除。。。\n"); return ; } List_Node *tmp = list->head->next;//存储首结点元素 //遍历查找 while(ID != tmp->DataNode.ID && tmp != list->head) { tmp = tmp->next; } //如果遍历完所有结点未找到对应ID输出该结点不存在 if(tmp == list->head) { printf("ID = %d 的结点不存在\n",ID); return; } tmp->next->pre = tmp->pre; tmp->pre->next = tmp->next; free(tmp); list->Size --;}
16、排序:
void Sort(Double_Circular_List *list){ /* 思路: 获取首结点的位置,将链表头结点到首结点之间断开,头结点置为初始化的指向, 从首结点开始遍历结点,将遍历到的结点依次按ID插入结点,同时将遍历结点的内存空间释放 */ if(isEmpty(list)) { printf("结点元素为空,无法排序。。。\n"); return ; } List_Node *tmp = list->head->next; //获取首结点 List_Node *delete = tmp; //删除结点位置 //断开头结点和首结点间的指向,初始化头结点 list->tail = list->head; list->head->next = list->head; list->head->pre = list->head; list->Size = 0; //遍历插入结点 while(tmp != list->head) { Id_Insert(list,&tmp->DataNode,tmp->DataNode.ID); //按ID插入 tmp = tmp->next; //指向下一结点 free(delete);//释放空间 delete = tmp;//更新删除结点 }}
18、清空链表:
void clear(Double_Circular_List *list){ /* 思路: 遍历结点,每访问一个结点从头部删除一个结点 */ if(isEmpty(list)) { printf("结点元素为空。。。\n"); return ; } List_Node *tmp = list->head->next; //获取首结点位置 //遍历删除结点,当临时指针和头结点指向相同时遍历结束 while(tmp != list->head) { tmp = tmp->next; //指向下一结点 Delete_Head(list); //头部删除 }}
19、销毁链表:
void Destory(Double_Circular_List *list){ //先将链表清空 clear(list); //释放头结点空间 free(list->head);}
完整程序:
.c文件:
#include "linked_list.h"void main(){ Data_Node Datanode; Double_Circular_List List; int ID; Init_Double_Circular_List(&List); int operation = 1; while(operation) { printf("-----------------------------------------------\n");printf("|双向循环链表 |\n");printf("-----------------------------------------------\n");printf("| [1] 尾部插入结点 [2] 头部插入结点 |\n");printf("| [3] 尾部删除结点 [4] 头部删除结点 |\n");printf("| [5] 按ID插入结点 [6] 显示链表内容 |\n");printf("| [7] 按ID删除结点 [8] 按ID修改结点元素|\n");printf("| [9] 按ID查找结点 [10] 获取结点数量 |\n");printf("| [11] 排序 [12] 链表逆序显示 |\n");printf("| [13] 清空链表 [14] 销毁链表|\n");printf("| [15] 测试 [16] 链表逆置|\n");printf("| [0] 退出程序 |\n");printf("-----------------------------------------------\n");printf("请输入操作序号 :\n");scanf("%d",&operation); switch(operation) { case 0: printf("退出程序\n"); Sleep(1000); exit(-1); break; case 1: printf("尾部插入结点:\n"); printf("请输入结点ID 、存储数据 val :\n"); scanf("%d %d",&Datanode.ID,&Datanode.val); Insert_Tail(&List,&Datanode); break; case 2: printf("头部插入结点:\n"); printf("请输入结点ID 、存储数据 val :\n"); scanf("%d %d",&Datanode.ID,&Datanode.val); Insert_Head(&List,&Datanode); break; case 3: printf("尾部删除结点:\n"); Delete_Tail(&List); break; case 4: printf("头部删除结点:\n"); Delete_Head(&List); break; case 5: printf("按ID插入结点:\n"); printf("请输入结点ID 、存储数据 val :\n"); scanf("%d %d",&Datanode.ID,&Datanode.val); Id_Insert(&List,&Datanode,Datanode.ID); break; case 6: printf("显示链表元素:\n"); Show_List(&List); break; case 7: printf("按ID删除节点:\n"); printf("请输入要删除结点ID:\n"); scanf("%d",&ID); Id_Delete(&List,ID); break; case 8: printf("按ID修改结点元素:\n"); printf("请输入修改结点ID:\n"); scanf("%d",&ID); Id_Modify(&List,ID); break; case 9: printf("按ID查找结点元素:\n"); printf("请输入查找结点ID:\n"); scanf("%d",&ID); Id_Find(&List,ID); break; case 10: printf("显示结点数量:\n"); Get_Size(&List); break; case 11: printf("链表排序:\n"); Sort(&List); break; case 12: printf("逆序显示链表元素:\n"); Show_List_Reverse(&List); break; case 13: printf("清空链表\n"); clear(&List); break; case 14: printf("销毁链表:\n"); Destory(&List); break; case 15: Test(&List,&Datanode); break; case 16: printf("链表逆置\n"); Reverse_List(&List); break; default: printf("请输入 0-15之间的数字:\n "); break; } } system("pause"); return ;}void Init_Double_Circular_List(Double_Circular_List *list){ List_Node *Node = (List_Node *)malloc(sizeof(List_Node)); if(Node == NULL) { printf("内存申请失败...\n"); exit(-1); } //初始化结点指向自身 --- 头结点不存储元素,作为辅助结点方便操作 Node->next = Node; Node->pre = Node; //初始化头尾结点指向Node结点并初始化结点大小为 0 list->head = Node; list->tail = Node; list->Size = 0;}List_Node *__malloc_List_Node(Data_Node *dataNode){ List_Node *Node = (List_Node *)malloc(sizeof(List_Node)); //为插入节点申请内存 if(Node == NULL) { printf("内存申请失败...\n"); return NULL; } Node->DataNode.ID = dataNode->ID;//新结点的ID 存储插入结点的ID Node->DataNode.val = dataNode->val; //新结点的val 存储插入结点的val Node->next = NULL; //结点指向为空 Node->pre = NULL; return Node;//将申请到的结点返回}void Insert_Tail(Double_Circular_List *list,Data_Node *dataNode){ List_Node *Node = __malloc_List_Node(dataNode); //获取申请到的结点 List_Node *nodePre = list->tail; //nodePre指向链表尾部结点 List_Node *nodeNext = list->head; //nodeNext指向链表头结点 Node->next = nodePre->next; //新结点的next指向尾结点的next指向(即头结点) Node->pre = nodePre; //新结点的pre指向尾结点 nodePre->next = Node; //尾结点的next指向新结点 nodeNext->pre = Node; //头结点的pre指向新结点 list->tail = Node; //更新尾结点为新插入结点 list->Size ++; //结点数量加 1 }void Insert_Head(Double_Circular_List *list,Data_Node *dataNode){ List_Node *Node = __malloc_List_Node(dataNode); //获取申请到的结点 List_Node *nodeNext = list->head; //nodeNext指向链表头结点 Node->next = nodeNext->next; //新结点的next指向头结点的next指向 Node->pre = nodeNext; //新结点的pre指向头结点或者头结点的next结点的pre指向(两种指向位置相同)亦可用 Node-> pre = nodeNext->next->pre nodeNext->next->pre = Node; //首结点pre指向新结点 nodeNext->next = Node; //头结点的next指向新结点 /* 在头部插入时有两种情况: 已经存在结点元素和无结点元素两种 一、如果已经存在结点元素以上步骤已经实现插入结点, 二、如果无结点元素,此结点是第一个结点则需要改变尾指针指向 */ if(list->Size == 0) { list->tail = Node; } list->Size ++; //结点数量加 1}void Show_List(Double_Circular_List *list){ if(isEmpty(list)) { printf("结点元素为空,无结点数据显示。。。\n"); return ; } List_Node *tmp = list->head->next; //临时指针保存首结点位置 printf("--------------------------------\n"); printf("| ID | Val |\n"); printf("--------------------------------\n"); while(tmp != list->head) //当临时结点指向的位置和头结点位置相同时跳出循环 { printf("|%5d ||%9d |\n",tmp->DataNode.ID,tmp->DataNode.val); //输出结点元素 tmp = tmp->next; //指向下一元素 } printf("--------------------------------\n"); printf("| size ||%d |\n",list->Size); printf("--------------------------------\n\n\n");}void Delete_Tail(Double_Circular_List *list) { if(isEmpty(list)) { printf("结点元素为空,无法删除。。。\n"); return ; } List_Node * tmp = list->head; //tmp临时指针存储头结点位置 List_Node *delete = list->tail; //delete临时指针存储尾结点位置 delete->pre->next = delete->next;//尾结点的前一个结点的next指向头结点(或者说是尾结点的next指向) tmp->pre = delete->pre; //头结点的pre指向尾结点的前一个结点(或者说删除节点的前一个结点) list->tail = delete->pre; //更新尾结点为删除结点的前一个结点 free(delete); //释放尾结点空间 list->Size --; //结点元素减 1}void Delete_Head(Double_Circular_List *list){ if(isEmpty(list)) { printf("结点元素为空,无法删除。。。\n"); return ; } List_Node * tmp = list->head; //tmp临时指针存储头结点位置 List_Node *delete = list->head->next; //delete临时指针存储首结点位置 delete->next->pre = delete->pre; //首结点的下一结点的pre指向头结点(或删除节点的pre指向) tmp->next = delete->next; //头结点的next指向首结点的next指向(或删除结点的next指向) free(delete); //释放首结点空间 list->Size --; //结点元素减 1}boolean isEmpty(Double_Circular_List *list){ if(list->head == list->tail) return TRUE; return FALSE;}void Test(Double_Circular_List *list,Data_Node *dataNode){ for(int i = 3;i < 8;i++) { dataNode->ID = i; dataNode->val = i * 10; Insert_Tail(list,dataNode); }}void Get_Size(Double_Circular_List *list){ printf("链表结点数量为:\t%d\n",list->Size);}void Show_List_Reverse(Double_Circular_List *list){ if(isEmpty(list)) { printf("结点元素为空,无结点数据显示。。。\n"); return ; } List_Node *tmp = list->tail; //临时指针保存尾结点位置 printf("--------------------------------\n"); printf("| ID | Val |\n"); printf("--------------------------------\n"); while(tmp != list->head) //当临时结点指向的位置和头结点位置相同时跳出循环 { printf("|%5d ||%9d |\n",tmp->DataNode.ID,tmp->DataNode.val); //输出结点元素 tmp = tmp->pre; //指向前一元素 }}void Id_Modify(Double_Circular_List *list,int ID){ int val; if(isEmpty(list)) { printf("结点元素为空,无法修改。。。\n"); return ; } List_Node *tmp = list->head->next; //保存首结点元素地址 //当结点id 和查找的 id不同时结点向下一结点查找 //当链表被遍历完或者找到id对应结点时结束查找 while(tmp->DataNode.ID != ID && tmp != list->head) { tmp = tmp->next; } if(tmp == list->head) { printf("未找到对应 id 结点\n"); return ; } printf("请输入要修改的 val :\n"); scanf("%d",&val); tmp->DataNode.val = val; //将修改后的 val 替换该 id 的 val}void Id_Find(Double_Circular_List *list,int ID){ if(isEmpty(list)) { printf("结点元素为空,无法查找。。。\n"); return ; } List_Node *tmp = list->head->next; //当结点id 和查找的 id不同时结点向下一结点查找 //当链表被遍历完或者找到id对应结点时结束查找 while(tmp->DataNode.ID != ID && tmp != list->head) { tmp = tmp->next; } if(tmp == list->head) { printf("未找到对应 id 结点\n"); return ; } printf("ID = %d 结点 val 为:\t%d\n",tmp->DataNode.ID,tmp->DataNode.val);}void Id_Insert(Double_Circular_List *list,Data_Node *dataNode,int ID){ if(!isEmpty(list)) //链表不为空 { List_Node *tmp = list->head->next;//存储首结点元素 //链表的结点ID 均小于插入结点ID时在尾部插入 while(ID > tmp->DataNode.ID && tmp != list->head) { tmp = tmp->next; } if(tmp == list->head) { List_Node *Node = __malloc_List_Node(dataNode); //获取申请到的结点 List_Node *nodePre = list->tail; //nodePre指向链表尾部结点 List_Node *nodeNext = list->head; //nodeNext指向链表头结点 Node->next = nodePre->next; //新结点的next指向尾结点的next指向(即头结点) Node->pre = nodePre; //新结点的pre指向尾结点 nodePre->next = Node; //尾结点的next指向新结点 nodeNext->pre = Node; //头结点的pre指向新结点 list->tail = Node; //更新尾结点为新插入结点 list->Size ++; //结点数量加 1 } else //在中间结点插入的情况 { List_Node *Node = __malloc_List_Node(dataNode); //获取申请到的结点 Node->next = tmp; //新结点的next指向ID较大的结点 Node->pre = tmp->pre;//新结点的pre指向ID较大结点的前一个结点 tmp->pre->next = Node; //较大结点的前一个结点指向新结点 tmp->pre = Node; //较大结点的pre指向新结点 list->Size ++; } } if(isEmpty(list)) //链表结点元素为空时直接插入 { List_Node *Node = __malloc_List_Node(dataNode); //获取申请到的结点 List_Node *nodeNext = list->head; //nodeNext指向链表头结点 Node->next = nodeNext; //新结点的next指向头结点 Node->pre = nodeNext; //新结点的pre指向头结点 nodeNext->next = Node; //头结点next指向新结点 nodeNext->pre = Node; //头结点的pre指向新结点 list->tail = Node; //修改尾指针指向 list->Size ++; //结点数量加 1 }}void Id_Delete(Double_Circular_List *list,int ID){ if(isEmpty(list)) { printf("结点元素为空,无法删除。。。\n"); return ; } List_Node *tmp = list->head->next;//存储首结点元素 //遍历查找 while(ID != tmp->DataNode.ID && tmp != list->head) { tmp = tmp->next; } //如果遍历完所有结点未找到对应ID输出该结点不存在 if(tmp == list->head) { printf("ID = %d 的结点不存在\n",ID); return; } tmp->next->pre = tmp->pre; tmp->pre->next = tmp->next; free(tmp); list->Size --;}void Sort(Double_Circular_List *list){ /* 思路: 获取首结点的位置,将链表头结点到首结点之间断开,头结点置为初始化的指向, 从首结点开始遍历结点,将遍历到的结点依次按ID插入结点,同时将遍历结点的内存空间释放 */ if(isEmpty(list)) { printf("结点元素为空,无法排序。。。\n"); return ; } List_Node *tmp = list->head->next; //获取首结点 List_Node *delete = tmp; //删除结点位置 //断开头结点和首结点间的指向,初始化头结点 list->tail = list->head; list->head->next = list->head; list->head->pre = list->head; list->Size = 0; //遍历插入结点 while(tmp != list->head) { Id_Insert(list,&tmp->DataNode,tmp->DataNode.ID); //按ID插入 tmp = tmp->next; //指向下一结点 free(delete);//释放空间 delete = tmp;//更新删除结点 }}void clear(Double_Circular_List *list){ /* 思路: 遍历结点,每访问一个结点从头部删除一个结点 */ if(isEmpty(list)) { printf("结点元素为空。。。\n"); return ; } List_Node *tmp = list->head->next; //获取首结点位置 //遍历删除结点,当临时指针和头结点指向相同时遍历结束 while(tmp != list->head) { tmp = tmp->next; //指向下一结点 Delete_Head(list); //头部删除 }}void Destory(Double_Circular_List *list){ //先将链表清空 clear(list); //释放头结点空间 free(list->head);}void Reverse_List(Double_Circular_List *list){ if(isEmpty(list)) { printf("结点元素为空,无法逆置。。。\n"); return ; } /* 思路: 遍历结点,每遍历一个结点头部插入; 逆置还可以通过双指针的方法实现,此方法在单链表中也已经实现 */ List_Node *tmp = list->head->next;//获取首结点位置 List_Node *delete = tmp; //断开头结点和首结点间的指向,初始化头结点 list->tail = list->head; list->head->next = list->head; list->head->pre = list->head; list->Size = 0; //遍历插入结点 while(tmp != list->head) { Insert_Head(list,&tmp->DataNode); //头部插入 tmp = tmp->next; //指向下一结点 free(delete);//释放空间 delete = tmp;//更新删除结点 }}
.h文件:
#include #include typedef struct {int ID; //存储元素id int val; //此结构体可以存储需要存储的数据元素}Data_Node;typedef struct ListNode{ Data_Node DataNode; //保存数据结点 struct ListNode *pre;//指向前一个结点 struct ListNode *next; //指向后一个结点}List_Node;typedef struct { List_Node *head; //头结点 List_Node *tail; //尾结点 int Size; //存储结点数量}Double_Circular_List;void Init_Double_Circular_List(Double_Circular_List *list); //初始化双向循环链表List_Node *__malloc_List_Node(Data_Node *dataNode); //为插入元素申请节点--方便操作,将内存申请定义为函数void Insert_Tail(Double_Circular_List *list,Data_Node *dataNode); //尾部插入结点void Insert_Head(Double_Circular_List *list,Data_Node *dataNode); //头部插入结点void Delete_Tail(Double_Circular_List *list); //尾部删除结点void Delete_Head(Double_Circular_List *list); //头部删除结点void Show_List(Double_Circular_List *list); //显示结点元素void Reverse_List(Double_Circular_List *list); //链表逆置void Show_List_Reverse(Double_Circular_List *list); //逆序显示结点元素boolean isEmpty(Double_Circular_List *list); //判断链表结点是否为空void Get_Size(Double_Circular_List *list); //获取链表数量void Id_Modify(Double_Circular_List *list,int ID); //按ID修改结点元素void Id_Find(Double_Circular_List *list,int ID); //按ID查找结点void Id_Insert(Double_Circular_List *list,Data_Node *dataNode,int ID);//按ID插入结点void Id_Delete(Double_Circular_List *list,int ID); //按ID删除结点void Sort(Double_Circular_List *list); //按ID从小到大排序void clear(Double_Circular_List *list); //清空链表void Destory(Double_Circular_List *list); //销毁链表void Test(Double_Circular_List *list,Data_Node *dataNode); //测试案例
参考:B站—IT扫地僧
声明:此文章为学习笔记,如有侵权请联系删除。
创作挑战赛 新人创作奖励来咯,坚持创作打卡瓜分现金大奖