欢迎光临苍狼电竞金属配件有限公司!公司简介 | 苍狼电竞

某某工厂-专业生产加工、定做各种金属工艺品

国内金属工艺品加工专业厂家
全国服务电话 全国服务电话 400-123-4567
产品展示
联系我们
全国服务电话:400-123-4567

传真:+86-123-4567

手机:138 0142 069

邮箱:

地址:山东省滕州市中央城

当前位置:主页 > 新闻资讯 > 常见问题 >
轮回链表(约瑟夫环)的成立及C语言实现
发布时间:2021-02-13 09:59 来源:网络整理

无论是静态链表照旧动态链表,有时在办理详细问题时,需要我们对其布局举办稍微地调解。好比,可以把链表的两端毗连,使其成为了一个环状链表,凡是称为轮回链表

和它名字的表意一样,只需要将表中最后一个结点的指针指向头结点,苍狼电竞首页 ,链表就能成环儿,如图 1 所示。


图1 轮回链表

 

需要留意的是,固然轮回链表成环状,但本质上照旧链表,因此在轮回链表中,依然可以或许找到头指针和首元节点等。轮回链表和普通链表对比,独一的差异就是轮回链表首尾相连,其他都完全一样。

轮回链表实现约瑟夫环 约瑟夫环问题,是一个经典的轮回链表问题,题意是:已知 n 小我私家(别离用编号 1,2,3,…,n 暗示)围坐在一张圆桌周围,从编号为 k 的人开始顺时针报数,数到 m 的那小我私家出列;他的下一小我私家又从 1 开始,照旧顺时针开始报数,数到 m 的那小我私家又出列;依次反复下去,直到圆桌上剩余一小我私家。

如图 2 所示,假设此时圆周周围有 5 小我私家,要求从编号为 3 的人开始顺时针数数,数到 2 的那小我私家出列:


轮回链表实现约瑟夫环


图 2 轮回链表实现约瑟夫环


出列顺序依次为:

编号为 3 的人开始数 1,然后 4 数 2,所以 4 先出列;

4 出列后,从 5 开始数 1,1 数 2,所以 1 出列;

1 出列后,从 2 开始数 1,3 数 2,所以 3 出列;

3 出列后,从 5 开始数 1,2 数 2,所以 2 出列;

最后只剩下 5 本身,所以 5 胜出。

约瑟夫环问题有多种变形,好比顺时针转改为逆时针等,固然问题的细节有多种变数,但办理问题的中心思想是一样的,纵然用轮回链表。

通过以上的阐明,我们可以实验编写 C 语言代码,完整代码如下所示: #include <stdio.h> #include <stdlib.h> typedef struct node { int number; struct node * next; }person; person * initLink(int n) { int i = 0; person * head = NULL, *cyclic = NULL; head = (person*)malloc(sizeof(person)); head->number = 1; head->next = NULL; cyclic = head; for (i = 2; i <= n; i++) { person * body = (person*)malloc(sizeof(person)); body->number = i; body->next = NULL; cyclic->next = body; cyclic = cyclic->next; } cyclic->next = head;//首尾相连 return head; } void findAndKillK(person * head, int k, int m) { person * p = NULL; person * tail = head; //找到链表第一个结点的上一个结点,为删除操纵做筹备 while (tail->next != head) { tail = tail->next; } p = head; //找到编号为k的人 while (p->number != k) { tail = p; p = p->next; } //从编号为k的人开始,只有切合p->next==p时,说明链表中除了p结点,所有编号都出列了, while (p->next != p) { int i = 0; //找到从p报数1开始,报m的人,而且还要知道数m-1de人的位置tail,利便做删除操纵。 for (i = 1; i < m; i++) { tail = p; p = p->next; } tail->next = p->next;//从链表大将p结点摘下来 printf("出列人的编号为:%d\n", p->number); free(p); p = tail->next;//继承利用p指针指向出列编号的下一个编号,游戏继承 } printf("出列人的编号为:%d\n", p->number); free(p); } int main() { int n = 0, k = 0, m = 0; person * head = NULL; printf("输入圆桌上的人数:"); scanf("%d", &n); head = initLink(n); printf("从第几小我私家开始报数(k>1且k<%d):", n); scanf("%d", &k); printf("数到几的人出列:"); scanf("%d", &m); findAndKillK(head, k, m); return 0; } 输出功效:

输入圆桌上的人数:5
从第几小我私家开始报数(k>1且k<5):3
数到几的人出列:2
出列人的编号为:4
出列人的编号为:1
出列人的编号为:3
出列人的编号为:2
出列人的编号为:5

最后出列的人,即为胜利者。虽然,你也可以改造措施,令查找出最后一小我私家时,输出此人胜利的信息。 总结 轮回链表和动态链表独一差异在于它的首尾毗连,这也注定了在利用轮回链表时,附带最多的操纵就是遍历链表。

在遍历的进程中,尤其要留意轮回链表固然首尾相连,但并不暗示该链表没有第一个节点和最后一个结点。所以,不要随意改变头指针的指向。