文章目录
- 【 1. 基本原理 】
- 【 2. 循环链表的创建 】
-
- 【 3. 循环链表的 插入 】
- 【 4. 循环单链表的 删除操作 】
- 【 5. 循环单链表的遍历 】
- 【 6. 实例 - 循环链表的 增删查改 】
- 【 7. 双向循环链表 】
【 1. 基本原理 】
- 对于单链表以及双向链表，其就像一个小巷，无论怎么样最终都能从一端走到另一端，然而循环链表则像一个有传送门的小巷，因为循环链表当你以为你走到结尾的时候，其实你又回到了开头。
- 循环链表和非循环链表其实创建的过程以及思路几乎完全一样，唯一不同的是，非循环链表的尾结点指向空（NULL），而 循环链表的尾指针指向的是链表的开头。通过将单链表的尾结点指向头结点的链表称之为 循环单链表（Circular linkedlist）。如下图所示：
【 2. 循环链表的创建 】
2.1 循环链表结点设计
- 以单循环链表为例，对于循环单链表的结点，可以完全参照于单链表的结点设计，如图：
- data表示数据，其可以是简单的类型（如int,double等等），也可以是复杂的结构体（struct类型）
- next表示指针，它永远指向自身的下一个结点， 对于 只有一个结点的存在，这个next指针则永远指向自身，对于一个 循环链表的尾部结点，next永远指向开头。
- 其代码可以表示为：
typedef struct list
{int data;struct list *next;
}list;
2.2 循环单链表初始化
- 如同单链表的创建，我们需要先创建一个头结点并且给其开辟内存空间，但与单链表不同的是，我们需要在开辟内存空间成功之后将头结点的next指向head自身。我们可以创建一个init函数来完成这件事情，为了以后的重复创建和插入，我们可以考虑 在init重创建的结点next指向空，而在主函数调用创建之后手动 将head头结点的next指针指向自身。这样的操作方式可以方便过后的创建单链表，直接利用多次调用的插入函数即可完成整体创建。
- C语言实现可以表示为：
list *initlist()
{list *head=(list*)malloc(sizeof(list));if(head==NULL){printf("创建失败，退出程序");exit(0);}else{head->next=NULL;return head;}
}
list *head=initlist();
head->next=head;
【 3. 循环链表的 插入 】
- 对于插入数据的操作，基本与单链表的插入操作相同，我们可以创建一个独立的结点，通过将需要插入的结点的上一个结点的next指针指向该节点，再由需要插入的结点的next指针指向下一个结点的方式完成插入操作。
- C 代码可以表示为：
list *insert_list(list *head,int pos,int data)
{list *node=initlist(); list *p=head; list *t;t=p;node->data=data;if(head!=NULL){for(int i=1;i<pos;i++){t=t->next; }node->next=t->next;t->next=node;return p;}return p;
}
【 4. 循环单链表的 删除操作 】
- 如图所示，循环单链表的删除操作可以参考单链表的删除操作，其都是 找到需要删除的结点，将其前一个结点的next指针直接指向删除结点的下一个结点 即可，但需要注意的是尾节点和头结点的特判，尤其是尾结点，因为删除尾节点后，尾节点前一个结点就成了新的尾节点，这个新的尾节点需要指向的是头结点而不是空，其重点可以记录为【删除节点的前一节点.next=删除结点.next】这样的操作可以省去头尾结点的特判：
- C 代码：
int delete_list(list *head)
{if(head == NULL) {printf("链表为空！\n");return 0;}list *temp = head; list *ptr = head->next;int del;printf("请输入你要删除的元素：");scanf("%d",&del);while(ptr != head) {if(ptr->data == del) {if(ptr->next == head) {temp->next = head;free(ptr);return 1;}temp->next = ptr->next; free(ptr);return 1;}temp = temp->next;ptr = ptr->next;}printf("没有找到要删除的元素\n");return 0;
}
【 5. 循环单链表的遍历 】
- 与普通的单链表和双向链表的遍历不同，循环链表需要进行结点的判断，找到尾节点的位置，由于尾节点的next指针是指向头结点的，所以不能使用链表本身是否为空（NULL）的方法进行简单的循环判断，我们需要通过判断结点的next指针是否等于头结点的方式进行是否完成循环的判断。
- 此外还有一种计数的方法，即建立一个计数器count=0，每一次next指针指向下一个结点时计数器加一，当count数字与链表的节点数相同的时候即完成循环，这样做有一个 问题就是获取到链表的节点数同时也需要完成一次遍历才可以达成目标。
- C代码：
int display(list *head)
{if(head != NULL) {list *p = head;while(p->next != head ) {printf("%d ",p->next->data);p = p->next;}printf("\n"); return 1;}else{printf("头结点为空!\n");return 0;}
}
【 6. 实例 - 循环链表的 增删查改 】
#include<stdio.h>
#include<stdlib.h>
typedef struct list{int data;struct list *next;
}list;
list *initlist(){list *head=(list*)malloc(sizeof(list));if(head==NULL){printf("创建失败，退出程序");exit(0);}else{head->next=NULL;return head;}
}
int create_list(list *head){int data; printf("请输入要插入的元素：");scanf("%d",&data);list *node=initlist();node->data=data;if(head!=NULL){list *p=head;while(p->next!=head){p=p->next;}p->next=node;node->next=head;return 1;}else{printf("头结点已无元素\n");return 0;}}
list *insert_list(list *head,int pos,int data){list *node=initlist(); list *p=head; list *t;t=p;node->data=data;if(head!=NULL){for(int i=1;i<=pos;i++){t=t->next;}node->next=t->next;t->next=node;return p;}return p;
}
int delete_list(list *head) {if(head == NULL) {printf("链表为空！\n");return 0;}list *temp = head; list *ptr = head->next;int del;printf("请输入你要删除的元素：");scanf("%d",&del);while(ptr != head) {if(ptr->data == del) {if(ptr->next == head) { temp->next = head;free(ptr);return 1;}temp->next = ptr->next;free(ptr);return 1;}temp = temp->next;ptr = ptr->next;}printf("没有找到要删除的元素\n");return 0;
}
int display(list *head) {if(head != NULL) {list *p = head;while(p->next != head ) {printf("%d ",p->next->data);p = p->next;}printf("\n"); return 1;} else {printf("头结点为空!\n");return 0;}
}int main(){list *head=initlist();head->next=head;for(int i=0;i<5;i++){ create_list(head);}display(head);head=insert_list(head,1,10);display(head);delete_list(head);display(head);return 0;
}
【 7. 双向循环链表 】
- 循环链表还有一个进阶的概念练习，同双向链表与单链表的关系一样，循环单链表也有一个孪生兄弟——双向循环链表，其设计思路与单链表和双向链表的设计思路一样，就是 在原有的双向链表的基础上，将尾部结点和头部结点进行互相连接。
