数据结构与算法（八）循环链表

目录

概述

一、循环链表的引入与定义

二、循环链表的操作

1、循环链表的初始化

2、循环链表的插入

3、循环链表的删除

4、循环链表返回结点所在位置

三、约瑟夫问题

1、什么是约瑟夫问题？

2、约瑟夫问题与循环链表

3、小练习

四、循环链表的特点

五、判断单链表中是否有环

1、有环的定义

2、判断方法

六、魔术师发牌问题

七、拉丁方阵问题

---

概述

        循环链表是线性表中一个重要的模块，本文将从理论出发，回归实践，通过约瑟夫问题、魔术师发牌问题以及拉丁方阵问题三个现实模型问题切入，给学习这一部分内容提供不一样的思路和角度。

        专栏地址：数据结构与算法（c语言实例）_Felix Du的博客-CSDN博客

        欢迎各位大佬批判指正！！

---

一、循环链表的引入与定义

        所谓的循环，简单来说就是绕了一圈。打个比方：从前有座山，山上有座庙，庙里有一个老和尚，老和尚对小和尚说：从前有座山，山上有座庙......

        对于我们单链表来说，由于每个结点只存储了向后的指针，到了尾部标识就停止了向后链的操作。也就是说，按照这样的方式，只能索引后继结点不能索引前驱结点。那么这会带来什么问题呢？

        例如我们如果不从头结点出发，就无法访问到全部结点。事实上要解决这个问题也并不麻烦，只需要将单链表中终端结点的指针由空指针改为指向头结点，这个问题就解决了。

        将单链表中终端结点的指针端由空指针改为指向头结点，就使整个单链表形成一个环，这种头尾相接的单链表称为但循环链表，简称循环链表。

        注意：一般我们提到的循环链表都是指的单循环链表。

        同时，这里并不是说循环链表就一定要有头结点。其实循环链表与单链表的主要差异就在于循环判断空链表的条件上，原来判断head->next是否为null，现在则是head->next是否等于head。回到刚才的问题，由于终端结点用尾指针rear指示，则查找终端结点是O(1)，而开始结点是rear ->next ->next，当然也是O(1)。下面我们就从几个基本操作的代码切入来讲解循环链表。

二、循环链表的操作

1、循环链表的初始化

void ds_init(node **pNode)
{int item;node *temp;node *target;printf("请输入结点的值，输入0完成初始化\n")while(1){scanf("%d",&item);fflush(stdin);if(item == 0)return;if((*pNode) == NULL){//循环链表中只有一个结点*pNode = (node*)malloc(sizeof(struct CLinkList));if(!(*pNode))exit(0);(*pNode) -> data = item;(*pNode) -> next = *pNode;}else{//找到next指向第一个结点的结点for(target = (*pNode);target -> next != (*pNode); target = target -> next);//生成一个新的结点temp = (node*)malloc(sizeof(struct CLinkList));if(!temp)exit(0);temp ->data = item;temp -> next = *pNode;target -> next = temp;}}
}

2、循环链表的插入

//插入结点
//参数：链表的第一个结点，插入的位置void ds_insert(node **pNode,int i)
{node *temp;node *target;node *p;int item;int j = 1;printf("输入要插入结点的值:");scanf("%d",&item);if( i == 1){//新插入的结点作为第一个结点temp = （node*)malloc(sizeof(struct CLinkList));if(!temp)exit(0);temp ->data = item;//寻找到最后一个结点for(target = (*pNode); target -> next != (*pNode); target = target -> next);temp ->next = (*pNode);target -> next = temp;*pNode = temp;}else{target = *pNode;for(;j<(i-1);++j){target = target ->next;}//target指向第三个元素的temp = (node*)malloc(sizeof(struct CLinkList));if(!item)exit(0);temp -> data = item;p = target ->next;target -> next = temp;temp ->next = p;}
}

3、循环链表的删除

//删除结点
void ds_delete(node **pNode,int i)
{node *target;node *temp;int j = 1;if(i == 1){//删除的是第一个结点//找到最后一个结点for(target = *pNode;target->next != *pNode;target = target->next)temp = *pNode;*pNode = (*pNode)->next;target->next = *pNode;free(temp);}else{target = *pNode;for( ; j<i-1;++j){target = target -> next;}temp = target->next;target->next = temp->next;free(temp);}
}

4、循环链表返回结点所在位置

//返回结点所在位置
int ds_search(node *pNode,int elem)
{node *target;int i =1;for(target = pNode;target ->data !=elem && target->next != pNode;++i){target = target ->next;}if(target -> next ==pNode)//表中不存在该元素return 0;elsereturn i;
}

三、约瑟夫问题

1、什么是约瑟夫问题？

        据说著名犹太历史学家Josephus有过以下的故事：在罗马人占领桥塔帕特之后，39个犹太人与Josephus及他的朋友躲到一个洞中，39个犹太人决定宁愿死也不要被敌人抓到，于是决定了一个自杀方式，41个人排成一个圆圈，由第一个人开始报数，每报数到第三个人就必须自杀，然后再由下一个重新报数，指导所有人都自杀身亡为止。然后Josephus和他的朋友并不想遵从，于是他先假装遵从，然后将他和他的朋友安排在第16个和第31个位置，于是便逃过了这场死亡游戏。

2、约瑟夫问题与循环链表

        我们可以直观地感受到，约瑟夫问题中39个人的排序，不就是一个循环链表吗，所以我们就可以试着用循环链表模拟这个过程，让计算机告诉我们结果！

3、小练习

        问题：用循环链表模拟约瑟夫问题，把41个人自杀的顺序编号输出。

        代码如下：

//n个人围圈报数，报m出列，最后剩下的是几号？
#include<stdio.h>
#include<stdlib.h>typedef struct node
{int data;struct node *next;
}node;node *create(int n)
{node *p = NULL,*head;head = (node*)malloc(sizeof(node));p = head;node*s;int i = 1;if(0!=n){while(i<=n){    s = (node*)malloc(sizeof(node));s->data = i++;//为循环链表初始化，第一个结点为1，第二个结点为2p->next = s;p = s;}s->next = head->next;}free(head);return s->next;
}int main()
{int n = 41;int m = 3;int i;node*p =create(n);node *temp;m%n;while(p != p->next){for(i = 1;i < m-1;i++){p = p->next;}printf("%d->",p->next->data):temp = p->next;p->next = temp-next;free(temp);p = p->next;}printf("%d\n",p->data);return 0;
}

四、循环链表的特点

        回顾一下，在单链表中，我们有了头结点时，我们可以用O(1)的时间访问第一个结点，但对于要访问最后一个结点，我们必须要挨个向下索引，所以需要O(n)的时间。那我们有没有办法，只需要用O(1)的时间就能由链表指针访问到最后一个结点呢？当然可以！不过我们需要改造一下现有的循环链表，我们不用头指针，而是用指向终端结点的尾指针来表示循环链表，此时查找开始结点和终端结点都很方便了。如图：

        那么按照这个逻辑的话，判断是否为空链表，其实就是判断rear是否等于rear->next。

        循环链表的特点是无须增加存储量，仅对链接方式稍作改变，即可使得表处理更加灵活方便。

        【练习题】实现将两个线性表和连接成一个线性表的运算。

        分析如下：

        --若在单链表或头指针表示的单链表上做这种连接操作，都需要遍历第一个链表，找到结点，然后将结点链到的后面，其执行时间是O(n)

        --若在尾指针表示的单循环链表上实现，则只需修改指针，无须遍历，其执行时间是O(1)。

代码如下：

//假设A,B为非空循环链表的尾指针
LinkList Connect（LinkList A,LinkList B)
{LinkList p = A->next; //保存A表的头结点位置A->next = B->next ->next;//B表的开始结点链接到A表尾free(B->next);//释放B表的头结点，初学者容易忘记B->next = p；return B；//返回新循环链表的尾指针
}

五、判断单链表中是否有环

1、有环的定义

        有环的定义是，链表的尾结点指向了链表中的某个结点。

2、判断方法

        那么要判断单链表中是否有环，主要有以下两种方法。

        1）方法一：使用p、q两个指针，p总是向前走，但q每次都从头开始走，对于每个结点，看p走的步数是否和q一样。如上图，当p从6走到3时，用了6步，此时若q从head出发，则只需走两步就到3，因此步数不等，出现矛盾，因此存在环。

        2）方法二：使用p、q两个指针，p每次向前走一步，q每次向前走两步，若在某个时候p == q则存在环。

六、魔术师发牌问题

1、问题描述：魔术师利用一副牌中的13张黑牌，预先将他们排好后叠放在一起，牌面朝下。他先将最上面的那张牌数为1，翻过来正好是黑桃A，将黑桃A放在桌子上，第二次数1、2，将第一张牌放在这些牌的下面，将第二张牌翻过来，正好是黑桃2，然后将它手上的牌依次这样翻出来，牌的顺序正好是从A到K从大到小按顺序排列。问：牌的开始顺序是怎么样的，才能实现这种效果？

        解答代码如下：

//
//  main.c
//  Magician
//
//  Created by wangping on 2020/9/12.
//  Copyright © 2020 wangping. All rights reserved.
//#include <stdio.h>
#include <stdlib.h>
#define CardNumber 13typedef struct Node
{int data;struct Node *next;
}node, *LinkList;//  创建链表
node *CreateList()
{LinkList head = NULL;LinkList p;LinkList r = head;int i;for (i = 0; i < CardNumber; ++i){p = (node *)malloc(sizeof(node));p->data = 0;if (head == NULL)head = p;elser->next = p;r = p;}r->next = head;return head;
}//  发牌顺序计算
void Magician(LinkList head)
{LinkList p;p = head;p->data = 1;int i;int Countnumber = 2;while (1){for (i = 0; i < Countnumber; i++){p = p->next;if (p->data != 0)//  p = p->next;i = i - 1;}if (p->data == 0){p->data = Countnumber;Countnumber ++;if (Countnumber == 14)break;}}
}int main(int argc, const char * argv[])
{LinkList p;p = CreateList();Magician(p);int j;printf("以下是扑克牌的放置顺序： \n");for (j = 0; j < CardNumber; j++){printf(" 黑桃%d-> ", p->data);p = p->next;}/*for (q = p; q->next != p; q = q->next){printf("第 %d 张牌是黑桃 %d \n", j, q->data);j++;}*/return 0;
}

七、拉丁方阵问题

        拉丁方阵是一种n*n的方阵，方阵中恰有n种不同的元素，每种元素恰有n个，并且每种元素在一行和一列中恰好出现一次。著名数学家和物理学家欧拉使用拉丁字母来作为拉丁方阵里元素的符号，拉丁方阵因此得名。

        例如下图就是一个3*3的拉丁方阵：

        代码如下：

#include<stdio.h>
#include<stdlib.h>
#define len sizeof(list)
struct list
{int data;struct list *next;
};
int main()
{ int i=0 ;
int n;
printf("请输入你想要的n*n的拉丁方阵的n \n");
scanf("%d",&n);struct list *s,*p,*head;p=s=(struct list *) malloc(len);head=NULL;
while(i!=n)
{  if(i==1){head =s;}p=(struct list*)malloc(len);s->data=i;s->next =p;s=p;i++;
}s->next=head;
s->data=i;
s=head;//这行代码以上都是链表的初始化，与循环
//不懂的朋友可以看看我之前的博客关于链表的创建，插入，删除，循环等详细讲解 
i=0;
s=head;
int k=0;
while(k!=n*n&&k<n*n) //k<n*n 很重要！不然会陷入死循环
{ printf("%d",s->data);//主要是为了输出美观s=s->next;
while(i<n-1)// 加入这里N=4
{ i++;
printf("--%d",s->data);
s=s->next;
k++;   //那这里出来的K就是 N-1的倍数
}  //所以K的倍数依次为3 6 9 12 15 18  而 n*n= 16  调出来的15<16 而调出来的18又大于16  如果没有k<n*n 那么将会陷入死循环 
i=0;
printf("\n");s=s->next;//因为每次循环都会都会回到头结点的位置，所以呢，我们每次都移动一下头结点 就可以轻松实现拉丁方阵~
}
}

（本节完）

---

参考资料：

1、线性表12_哔哩哔哩_bilibili 鱼C小甲鱼

2、魔术师发牌问题：用循环链表解决魔术师发牌问题-CSDN博客

3、拉丁方阵问题：循环链表解决拉丁方阵问题-CSDN博客