约瑟夫环(C循环链表)

约瑟夫环(约瑟夫问题)是一个数学的应用问题: 已知n个人(以编号1,2,3…n分别表示)围坐在一张圆桌周围。从编号为k的人开始报数,数到m的那个人出列;他的下一个人又从1开始报数,数到m的那个人又出列;依此规律重复下去,直到圆桌周围的人全部出列。 一个挺简单的循环的题,拿来初学者学链表时练手很适合 talk is cheap, show me the code 下面是代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
#include <stdio.h>

#include <stdlib.h>


#define maxn 100 //最多100个人同时处于环中


typedef int DataType;
typedef struct Node{
DataType data;
struct Node *next;
}Node;


Node *CreatList(DataType a[],int n){
Node *first = (Node*)malloc(sizeof(Node));
first->next = NULL;
Node *r = NULL,*p = NULL;
r = first;


for(int i = 0;i < n;i++){
p = (Node*)malloc(sizeof(Node));
p->data = a[i];
p->next = NULL;
r->next = p;
r = p;
}
p->next = first->next; // 建立循环链表


return first;


}


void DeleteData(Node *first,int n,int x){
Node *p = first->next;
Node *r;
int ptr;
for(int i = 1;i < n;i++)
p = p->next; //确定第一个退出的人的位置
while(p->next != p){ //一直循环到链表中只剩下一个人为止,则这个人就为最后存活的那一个
for( int i = 1;i <= x - 1;i++){
p = p->next; //循环找第X位淘汰的人
}


ptr = (p->next)->data;
r = p->next;
p->next = r->next;
free(r); //淘汰出局
}
printf("%d",p->data); //荒野逃生,绝地吃鸡(逃)
}






int main()
{
Node* first = NULL;
int n;
int i,k,x = 1;
k = 3;
//每隔K个人便淘汰一个
DataType Data[maxn];


scanf("%d",&n);
for(i = 0;i < n;i++){
Data[i] = i + 1;
}
first = CreatList(Data,n); //创建循环链表
DeleteData(first,n,k); //Game Begining,开始淘汰出局


return 0;
}

觉得文章不错的话可以请我喝一杯茶哟~
  • 本文作者: bestsort
  • 本文链接: https://bestsort.cn/2019/04/21/61/
  • 版权声明: 本博客所有文章除特别声明外,均采用 BY-SA 许可协议。转载请注明出处!并保留本声明。感谢您的阅读和支持!
-------------本文结束感谢您的阅读-------------