传真:+86-123-4567
手机:138 0142 069
邮箱:
地址:山东省滕州市中央城
无论是静态链表照旧动态链表,有时在办理详细问题时,需要我们对其布局举办稍微地调解。好比,可以把链表的两端毗连,使其成为了一个环状链表,凡是称为轮回链表。
和它名字的表意一样,只需要将表中最后一个结点的指针指向头结点,链表就能成环儿,如图 1 所示。
图1 轮回链表
需要留意的是,固然轮回链表成环状,但本质上照旧链表,因此在轮回链表中,依然可以或许找到头指针和首元节点等。轮回链表和普通链表对比,独一的差异就是轮回链表首尾相连,其他都完全一样。
轮回链表实现约瑟夫环 约瑟夫环问题,是一个经典的轮回链表问题,题意是:已知 n 小我私家(别离用编号 1,2,3,…,n 暗示)围坐在一张圆桌周围,从编号为 k 的人开始顺时针报数,数到 m 的那小我私家出列;他的下一小我私家又从 1 开始,照旧顺时针开始报数,数到 m 的那小我私家又出列;依次反复下去,直到圆桌上剩余一小我私家。
编号为 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