一、单向循环链表
将单链表的首尾节点相连就形成了单向循环链表。
1、单向循环链表的节点
2、单向循环链表的结构
单向循环链表只有一个节点时：
二、双向循环链表
1、双向循环链表示意图
2、双向循环链表节点设计
struct d_node{ int data; //数据域 struct d_node *next; struct d_node *prev; };
3、双向循环链表的一般性结构
1）只有头结点的情况
2）有多个节点的情况
4、双向循环链表头插法插入节点
步骤：
1）p->next = head->next
2）head->next = p;
3）p->next->prev = p;
4）p->prev = head;
若双向循环链表只有一个节点
步骤：
1）head->next = p;
2）p->prev = head;
5、双向循环链表尾插法
步骤：
1）处理前继指针
p->prev = head->prev;
head->prev = p;
2)处理后继指针
p->prev->next = p;
p->next = head;
6、双向循环链表节点的删除
删除指定节点p步骤：
1）从逻辑上在链表中把p节点删除
p->prev->next = p->next;
p->next->prev = p->prev;
2）从物理上删除节点p——free§
若p节点是链表的最后一个节点，那就：p->prev->next = NULL;
示例代码：
#include <stdio.h> #include <stdlib.h> #include <stdbool.h> //0,设计双向循环链表节点 typedef struct d_node{ int data; struct d_node *prev; //前继指针 struct d_node *next; //后继指针 }D_NODE; //1,创建双向循环链表 D_NODE *D_Loop_List_Create(void) { //1)申请链表头结点堆空间 D_NODE *d_list = (D_NODE *)malloc(sizeof(D_NODE)); if (NULL == d_list) { perror("malloc failed"); return NULL; } //2)对头结点进行赋值 d_list->prev = d_list; d_list->next = d_list; //3)返回头结点地址 return d_list; } //2,添加链表节点 -->头插法 bool D_Loop_List_Insert_Head(D_NODE *head, int data) { //1,新节点申请堆空间 D_NODE *newnode = (D_NODE *)malloc(sizeof(D_NODE)); if (NULL == newnode) { perror("malloc newnode failed"); return false; } //2,对新节点进行赋值 newnode->data = data; newnode->prev = newnode; newnode->next = newnode; //3,头插法插入链表 newnode->next = head->next; head->next = newnode; newnode->next->prev = newnode; newnode->prev = head; return true; } //尾插法 bool D_Loop_List_Insert_End(D_NODE *head, int data) { //1,新节点申请堆空间 D_NODE *newnode = (D_NODE *)malloc(sizeof(D_NODE)); if (NULL == newnode) { perror("malloc newnode failed"); return false; } //2,对新节点进行赋值 newnode->data = data; newnode->prev = newnode; newnode->next = newnode; //尾插法插入节点 //1)处理前继指针 newnode->prev = head->prev; head->prev = newnode; //2)处理后继指针 newnode->prev->next = newnode; newnode->next = head; return true; } //3,链表显示 void D_Loop_List_Display(D_NODE *head) { D_NODE *p = head->next; printf("链表数据："); while( p != head) { printf("%d ", p->data); p = p->next; } printf("\n"); } //4,链表节点查找 bool D_Lool_List_Search(D_NODE *head, int data) { int i = 1; D_NODE *p = head->next; while(p != head) { if (p->data == data) { printf("找到这个节点！,节点序号[%d]\n", i); return true; } p = p->next; i++; } printf("链表中没有这个节点！\n"); } //5,链表节点删除 bool D_Loop_List_Remove(D_NODE *head, int data) { int i = 1; D_NODE *p = head->next; while(p != head) { if (p->data == data) { printf("删除这个节点！,节点序号[%d]\n", i); p->prev->next = p->next; p->next->prev = p->prev; free(p); return true; } p = p->next; i++; } printf("链表中没有这个节点！\n"); } //6,链表的销毁 void D_Lool_List_Destroy(D_NODE *head) { int i = 0; D_NODE *p = head; while(p->next != head) { p = p->next; free(p->prev); i++; } free(p); printf("销毁链表成功，一共释放[%d]个节点！\n", i); } /*双向循环链表*/ int main(int argc, char const *argv[]) { int i, num; D_NODE *dl_list = D_Loop_List_Create(); for(i=0; i<5; i++) { scanf("%d", &num); D_Loop_List_Insert_End(dl_list, num); D_Loop_List_Display(dl_list); } printf("请输入需要查找的数据："); scanf("%d", &num); D_Lool_List_Search(dl_list, num); printf("请输入需要删除的数据："); scanf("%d", &num); D_Loop_List_Remove(dl_list, num); D_Lool_List_Destroy(dl_list); return 0; }
