Posted on 2007-10-05 20:17
山泉弯延 阅读(7778)
评论(7) 编辑 收藏 引用 所属分类:
数据结构实验集
1 #include <stdio.h>
2 #include <stdlib.h>
3 //约瑟夫环的实现：一群人围成一圈，这群人共有 n个人，每个人身上都一个key，依次给这圈人编号：
4 //1，2，
n 一开始报数的上限值为m从第一个人（编号：1）自一开始报数报到m时停止报数，报到m的人出列，
5 //将他的密码做为新的m值，从他的顺时针方向开始的下个人开始从新从一报数，如此下去，直至所有的人出列为止
6 typedef struct Node
7 {
8 int key;//每个人身上带的key
9 int NUM;//每个人的编号
10 struct Node *next;
11 }Node;
12 //=========================
13 int n;//总共的人数
14 Node *L=NULL;//循环链表指针
15 //=========================
16 void InitList(int x)//初始化第一个节点，这个节点有实际的意义
17 {
18
19 L = (Node*)malloc(sizeof(Node));
20 if(!L)
21 {
22 printf("malloc fail\n");
23 system("PAUSE");
24 exit(1);
25 }
26 L->NUM=1;
27 L->key=x;
28 L->next=L;
29 }
30 //===========================================
31 void DelNode(Node *p_front)//p_front指向的是p的前一个节点，删除的却是p
32
33 {
34 Node *tmp=p_front->next;
35 p_front->next = tmp->next;
36 free(tmp);
37 }
38 //============================================
39 void CreateList(void)//创建循环链表
40 {
41 printf("Players n=");
42 scanf("%d",&n);
43 while(n<1||n>30)
44 {
45 printf("n must >=1 && <=30\n");
46 printf("Players n=");
47 scanf("%d",&n);
48 }
49 int key_tmp;
50 printf("NUM=1 key=");
51 scanf("%d",&key_tmp);
52 while(key_tmp<1||key_tmp>300)
53 {
54 printf("key must >0&&<=300\n");
55 printf("NUM=1 key=");
56 scanf("%d",&key_tmp);
57 }
58 InitList(key_tmp);
59 int i;
60 Node *s,*p=L;
61 for( i=2;i<=n;i++)
62 {
63 s=(Node*)malloc(sizeof(Node));
64 if(!s)
65 {
66 printf("malloc error\n");
67 system("PAUSE");
68 exit(1);
69 }
70 printf("NUM=%d key=",i);
71 scanf("%d",&key_tmp);
72 while(key_tmp<1||key_tmp>300)
73 {
74 printf("key must >0 && <=300");
75 printf("\nNUM=%d key=",i);
76 scanf("%d",&key_tmp);
77 }
78 s->key=key_tmp;
79 s->next=L;//构成循环链表的next指针赋值
80 p->next=s;
81 s->NUM=i;
82 p=s;//指针p往前移动
83 }
84 }
85 //=============================================
86 void PlayGame(void)//开始游戏！报数
87 {
88 Node *p=L;
89 Node *p_front=L;
90 int m;
91 printf("start game !\n");
92 printf("m=");
93 scanf("%d",&m);
94 while(m<1||m>300)
95 {
96 printf("m must >0 && <=300\n m=");
97 scanf("%d",&m);
98 }
99 int i;
100 int count = n;
101 for(i=1;i<=m;i++)
102 {
103 // printf("num =%d key=%d\n",p->NUM,p->key);
104
105 if(m==i)
106 {
107
108 m=p->key;
109 i=0;
110 printf(" %d",p->NUM);
111 DelNode(p_front);
112 p=p_front;
113 count--;
114 if(count==1)
115 {
116 printf(" %d",p->NUM);
117 //printf("num =%d key=%d\n",p->NUM,p->key);
118 printf(" all out !\n");
119 system("PAUSE");
120 exit(0);
121 }
122
123 }
124 p_front=p;
125 p=p->next;
126
127 }
128 }
129 //==================================================
130 int main(int argc, char *argv[])//运行游戏！
131 {
132 CreateList();
133 PlayGame();
134 system("PAUSE");
135 return 0;
136 }
137