1.概念
对于单链表，由于每个结点值存储了向后的指针，到了尾部标识就停止了向后链的操作。也就是说，按照这样的方式，只能索引后继结点不能索引前驱结点。
这样的话，假如不从头结点触发，就无法访问到全部结点。为了解决这个问题，我们将单链表中终端结点的指针由空指针改为指向头结点，问题就解决了。
定义
将单链表中终端结点的指针端由空指针改为指向头结点，就使整个单链表形成一个环，这种头尾相接的单链表称为单循环链表，简称循环链表。
注意：
并不是说循环链表一定要有头结点
循环链表和单链表的主要差异就在于循环的判断空链表的条件上，单 链表是判断head->next是否为NULL,现在则是head->next是否等于head
下方示例都以尾指针rear来指代循环链表而不是头指针,而且示例中的循环链表都没有头结点，也就是说，循环链中第一个结点，实际上是尾结点(这点需要发挥一点想象力)
由于终端结点用尾指针rear指示，则查找终端结点的复杂度为O(1)，而开始结点是rear->next->next,当然也是O(1)
2. 循环链表的定义
typedef struct Node{
ElemType data;
struct Node *next;
}Node;
typedef struct Node *CircleLinkList;
3. 循环链表的创建
void initCircleLinkList(CircleLinkList *L){
//表示输入的内容
int item;
CircleLinkList temp;
//target每次用来标记尾结点
CircleLinkList target = NULL;
printf("输入结点的值，输入0表示完成初始化\n");
while (1) {
scanf("%d",&item);
fflush(stdin);
if (item == 0) {
return;
}
if (*L == NULL) {
/*循环链表为空 则创建第一个结点 作为尾结点*/
*L = (CircleLinkList)malloc(sizeof(Node));
if (!(*L)) {
exit(0);
}
(*L)->data = item;
(*L)->next = *L;
} else {
//找到尾结点前面第一个结点
for (target = *L; target->next != *L; target = target->next);
temp = (CircleLinkList)malloc(sizeof(Node));
if (!temp) {
exit(0);
}
//在尾结点之前插入一个新的结点
temp->data = item;
temp->next = *L;
target->next = temp;
}
}
}
4. 循环链表的插入
/// 插入结点
/// @param L 链表的尾结点
/// @param i 插入的位置
void insertCircleLinkList(CircleLinkList *L,int i){
CircleLinkList temp,target;
int item,j = 1;
printf("请输入要插入结点的值:");
scanf("%d",&item);
if (i == 1) {
//i==1 表示要替换到之前的尾结点
temp = (CircleLinkList)malloc(sizeof(Node));
if (!temp) {
exit(0);
}
temp->data = item;
//循环得到尾结点前面一个结点
for (target = *L; target->next != *L; target = target->next);
temp->next = *L;
target->next = temp;
//将新结点放在尾结点位置
*L = temp;
} else {
target = *L;
//通过i-2次遍历，得到i位置前面一个结点
for (; j < (i-1); ++j) {
target = target->next;
}
temp = (CircleLinkList)malloc(sizeof(Node));
if (!temp) {
exit(0);
}
temp->data = item;
temp->next = target->next;
target->next = temp;
}
}
5.循环链表的删除
void deleteCircleLinkList(CircleLinkList *L,int i){
CircleLinkList target,temp;
if (i == 1) {
//删除尾指针的结点
//获取到尾结点前面的一个结点
for (target = *L; target->next != *L; target = target->next);
//重新指向
temp = *L;
*L = (*L)->next;
target->next = *L;
//释放结点
free(temp);
} else {
//获取到i-1位置的结点
target = *L;
for (int j = 1; j < i-1; j++) {
target = target->next;
}
temp = target->next;
target->next = target->next->next;
free(temp);
}
}
6.循环链表返回结点的位置
//通过数据的值，得到结点位置
int searchCircleLinkList(CircleLinkList L,int elem){
CircleLinkList target;
int i = 1;
for (target = L; target->data != elem && target->next != L; ++i) {
target = target->next;
}
if (target->next == L) {
//找了一圈还是没找到
return 0;
}
return i;
}
7、循环链表的特点
- 使用rear是否等于rear->next来判断循环链表是否为空表
一个例子：
题目：实现将两个线性表(a1,a2,...,an)和(b1,b2,...,bm)连接成一个线性表(a1,...an,b1,...bm)的运算
分析：
若在单链表或头指针表示的单循环表上左这种链接操作，都需要遍历第一个链表，找到结点an,然后将结点b1链到an的后面，其执行时间是O(n)
若在尾指针表示的单循环链表上实现，则只需要修改指针，无需遍历，其执行时间为O(1)
CircleLinkList connectLinkList(CircleLinkList L1,CircleLinkList L2){
CircleLinkList head = L1->next; //保存L1的头结点位置
L1->next = L2->next->next; //L1的尾结点指向L2的第一个结点
free(L2->next); //是否L2的头结点
L2->next = head; //让L2的尾结点指向L1的头结点
return L2;
}
8、约瑟夫问题
据说著名犹太历史学家 Josephus有过以下的故事：在罗马人占领乔塔帕特后，39 个犹太人与Josephus及他的朋友躲到一个洞中，39个犹太人决定宁愿死也不要被敌人抓到，于是决定了一个自杀方式，41个人排成一个圆圈，由第1个人开始报数，每报数到第3人该人就必须自杀，然后再由下一个重新报数，直到所有人都自杀身亡为止。然而Josephus 和他的朋友并不想遵从。首先从一个人开始，越过k-2个人（因为第一个人已经被越过），并杀掉第k个人。接着，再越过k-1个人，并杀掉第k个人。这个过程沿着圆圈一直进行，直到最终只剩下一个人留下，这个人就可以继续活着。问题是，给定了和，一开始要站在什么地方才能避免被处决？Josephus要他的朋友先假装遵从，他将朋友与自己安排在第16个与第31个位置，于是逃过了这场死亡游戏。
解题思路：
- 创建一个包含41个结点的循环链表（没有头结点）,每个节点的数据域都存放一个序号，分别为1-41
- 模拟计数过程，每次数到3则删除这个节点，并在下一个节点开始重新计数，最后得到免死的序号与人数
//创建一个不包含头结点的循环链表
Node *create(int n){
//head用于存储第一个结点的地址
Node *p = NULL,*s = NULL,*head = NULL;
for (int i = 1;i <= n; i++) {
p = (Node *)malloc(sizeof(Node));
p->data = i;
if (i == 1) {
//第一个结点
head = s = p;
} else {
s->next = p;
s = p;
}
}
//构成循环
s->next = head;
return head;
}
//解决约瑟夫问题，返回免死的人数
void soulutionProblem(int *args){
//n表示总人数，m表示数到几
int n = 41,m = 3;
// scanf("%d%d",&n,&m);
Node *L = create(n);
Node *p = L;
int counter = 1;
while (p != p->next) {
if (counter % m == 0) {
//数到了这个数字
/*
这个就是需要自杀的人 我们删除这个节点
然后再从下一个开始再排
*/
Node *temp = p->next;
p->next = temp->next;
free(temp);
p = p->next;
counter = 1;
n--;
if (n < m) {
//如果剩下总人数比计数的总人数还少的时候
//剩下的这些人就可以耍赖不自杀了
*args = n;
while (p != p->next) {
printf("%d\n",p->next->data);
Node *temp = p->next;
p->next = temp->next;
free(temp);
p = p->next;
}
printf("%d\n",p->data);
free(p);
break;
}
} else {
counter++;
if (counter % m != 0) {
p = p->next;
}
}
}
}
9.约瑟夫问题简易方法
大致思路就是逆推得到n人、m个数的问题，可以由(n-1)人推导到位置，依次类推,最后得到单次的公式为（ans + m）% n,其中ams为最后出列人的序号，m表示要数的数字，n表示单次总人数，下面给出代码
void simpleSolution(){
int n, m, i, s = 0;
n = 41;m = 3;
scanf("%d%d", &n, &m);
//经过n-1次的推导，单次的总人数为i
for (i = 2; i <= n; i++)
{
s = (s + m) % i;
printf("%d\n",s);
}
printf ("\nThe winner is %d\n", s+1);
}
这种方法的缺点是只能得到最终一个人，不能求得其它可以免于自杀的人的序号
