Posted on 2007-10-05 20:17
山泉彎延 閱讀(7796)
評論(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