约瑟夫生死者游戏（c语言版）_约瑟夫生死游戏c语言

题目描述：
        约瑟夫（Joeph）问题的一种描述是：
        编号为1,2,…,n的n个人按顺时针方向围坐一圈，每人持有一个密码（正整数）。
        一开始任选一个正整数作为报数上限值m，从第一个人开始按顺时针方向自1开始顺序报数，报到m时停止报数。
        报m的人出列，将他的密码作为新的m值，从他在顺时针方向上的下一个人开始重新从1报数，如此下去，直至所有人全部出列为止。
题目分析：
        分析题目可以知道，约瑟夫生死环游戏本质上可以理解为循环单链表的应用。每个人就相当于链表的一个结点。杀人的实现：删除链表结点。重复操作，直到最后一个人出列。
功能代码：
void Initialise() //初始化链表
void Traversal() //遍历链表
void Delete() //删除结点（实现杀人）
完整代码：

#include<stdio.h>
#include<malloc.h>
#include<stdlib.h>
#include<string.h>

//定义结点
typedef struct LinkList
{
	int data;
	struct LinkList *next;
}node;
//初始化链表
 void Initialise(node **pNode,int item)//**pNode 指向指针的指针   指向的对象pNode还是指针
 {
	 node *tmp;
	 node *target;
	 int i=1;         
	 while(i <= item)
	 {
		 if(* pNode == NULL)
		 {
			 *pNode = (node *)malloc(sizeof(LinkList));
			 if(!(* pNode))
			 {
				 exit(0);//退出
			 }
			 (*pNode)->data = i;
			 (*pNode)->next = *pNode ;
			 i++;
		 }
		 else
		 {
			 target = *pNode;
			 while(target->next != *pNode)
			 {
				 target = target->next ;
			 }
			 tmp = (node*)malloc(sizeof(LinkList ));
			 if(! tmp)
			 {
				 exit(0);
			 }
			 tmp->data = i;
			 i++;
			 tmp->next  = *pNode ;
			 target->next  = tmp;
		 }
	 }
 }
 //遍历链表
 void Traversal(node *pNode)
 {
	 node *tmp;
	 tmp = pNode;
	 printf("\n\t\t*****************************链表元素*********************************\n\n");
	 do
	 {
		 printf("\t%d",tmp->data );
		 tmp = tmp->next ;
	 }while(tmp->next != pNode);
	 printf("\t%d",tmp->data );
	 puts("");
 }
 //删除结点(杀人)
 void DeleteNode(node **pNode,int x,int y)
 {
	 int people = 1;
	 int Key[80];
	 printf("请依次输入每人的密码(使用空格隔开)：\n\n");
	 for(int i=1;i<=y;++i)
	 {
		 scanf("%d",&Key[i]);

	 }
	 printf("出列顺序：\n\n");
	 node *target;
	 target = *pNode ;
	 while(people <= y)
	 {
		 node *tmp;
		 if(people != 1)
		 {
			 target = target->next ;
		 }
		 if(x != 1)
		 {
			 for(int i=1;i<x-1;++i)
			 {
				 target = target->next ;
			 }
			 tmp = target->next ;
			 printf("%d\t",tmp->data );//打印删除结点标号
			 x = Key[tmp->data ];
			 target->next  = tmp ->next ;
			 free(tmp);
		 }
		 else
		 {
			 printf("%d\t",target->data );
		 }
		 people++;
	 }
 }


 int main()
 {
	 printf("Designer by MaLong\n");
	 printf("\n\t\t**********************************************************************\n");
	 printf("\t\t*                                                                    *\n");
	 printf("\t\t*                                                                    *\n");
	 printf("\t\t********************欢迎来到约瑟夫杀人游戏****************************\n"); 
	 printf("\t\t*                                                                    *\n");
	 printf("\t\t*                                                                    *\n");
	 printf("\t\t**********************************************************************\n\n\n\n");
	 int x,y;
	 printf("请输入参与游戏的人数:\n");
	 scanf("%d",&y);
	 printf("请输入初始密码:\n");
	 scanf("%d",&x);
	 node *head = NULL;
	 Initialise (&head,y);
	 Traversal (head);
	 DeleteNode (&head,x,y);
	 return 0;
 }

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
114
115
116
117
118
119
120
121
122
123
124
125
126
127

运行结果：

希望对您有所帮助！
不足之处还请多多指教！