Example_4

任务：约瑟夫环

思路：

​ 使用一个不带头节点的循环单链表，设定一个变量为1，然后通过不断的遍历，来找到第n个节点，然后把这个节点删除。变量置1，重新循环，直到链表中只有一个节点即p->next = p;

代码实现

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
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
#include <stdio.h>
#include <stdlib.h>

//约瑟夫环问题：已知 n 个人（以编号1，2，3…n分别表示）围坐在一张圆桌周围。
// 从编号为 k 的人开始报数，数到 m 的那个人出圈；他的下一个人又从 1 开始报数，数到 m 的那个人又出圈；
//依此规律重复下去，直到剩余最后一个胜利者。



//解题思路：可以把这个环理解为一个循环单链表，然后通过一步步遍历来实现只剩下一个节点。
typedef struct Node {
	int data;
	struct Node* next;
}*LinkList;


void Init(LinkList first) {
	first = NULL;
}

void Insert(LinkList &first,int n)
{
	
	LinkList s;
	int i = 1,k;
	printf("请输入第%d个的标号：",i);
	scanf("%d", &k);
	s = (LinkList)malloc(sizeof(Node));
	s->data = k;
	s->next = NULL;
	first = s;
	LinkList p = first;
	for (i = 2; i <= n; i++)
	{
		printf("请输入第%d个的标号：",i);
		scanf("%d", &k);
		s = (LinkList)malloc(sizeof(Node));
		s->data = k;
		s->next = NULL;
		p->next = s;
		p = p->next;

	}
	
	p->next = first;
}


void Print(LinkList head)
{
	LinkList p = head;
	
	while (p->next != head)
	{
		printf("%d", p->data);
		p = p->next;
	}
	printf("%d\n", p->data);
}

void Del(LinkList &p)
{
	LinkList q = p;
	while (q->next != p)
	{
		q = q->next;
	}
	q->next = q->next->next;
	printf("%d-->", p->data);
	free(p);
}

void yue(LinkList first, int n)
{
	LinkList p = first;
	LinkList q;
	while (p->next != p)
	{
		for (int i = 1; i < n; i++)
		{
			p = p->next;
		}
		q = p;
		p = p->next;
		Del(q);
		
	}
	printf(" The winner: %d", p->data);

}



int main()
{
	LinkList first = NULL;
	//Init(first);
	int n;
	printf("-------------------------------\n");
	printf("请输入一共有多少个人参加：");
	scanf("%d",&n);
	printf("-------------------------------\n");
	Insert(first, n);
	//printf("\n");
	//Print(first);
	printf("-------------------------------\n");
	printf("请输入数到几的人淘汰：");
	scanf("%d",&n);
	printf("-------------------------------\n");
	printf("淘汰的顺序为：\n");
	yue(first, n);
}