用循環連結清單實作約瑟夫環

1 #include <stdio.h>
 2 #include <stdlib.h>
 3 typedef struct node{
 4     int number;
 5     struct node * next;
 6 }node;
 7 node * initLink(int n){
 8     node * head=(node*)malloc(sizeof(node));
 9     head->number=1;
10     head->next=NULL;
11     node * temp=head;
12     for (int i=2; i<=n; i++) {
13         node * p=(node*)malloc(sizeof(node));
14         p->number=i;
15         p->next=NULL; 
16         temp->next=p;
17         temp=temp->next;
18     }
19     temp->next=head;//首尾相連，組成循環連結清單 
20     return head;
21 }
22 
23 void find(node * head,int k,int m){
24 
25     node * temp=head;
26     //找到連結清單第一個結點的上一個結點，為删除操作做準備
27     while (temp->next!=head) {
28         temp=temp->next;
29     }
30    node * p=head;
31     while (p->number!=k) {
32         temp=p;
33         p=p->next;
34     }
35     //找到編号為k的人
36     while (p->next!=p) {
37         //找到從p報數1開始，報m的人，并且還要知道數m-1de人的位置tail，友善做删除操作。
38         for (int i=1; i<m; i++) {
39             temp=p;
40             p=p->next;
41         }
42         temp->next=p->next;//删除p結點
43         printf("出列人的編号為:%d\n",p->number);
44         free(p);
45         p=temp->next;//繼續使用p指針指向出列編号的下一個編号，遊戲繼續
46     }
47     printf("出列人的編号為:%d\n",p->number);
48     free(p);
49 }
50 
51 int main() {
52     int n,k,m; 
53     printf("輸入圓桌上的人數n:");
54     scanf("%d",&n);
55     node* head=initLink(n);
56     printf("從第k人開始報數(k>1且k<%d)：",n);
57     scanf("%d",&k);
58     printf("數到m的人出列：");
59     scanf("%d",&m);
60     find(head, k, m);
61     return 0;
62 }      

轉載于:https://www.cnblogs.com/AQhhhh/p/10659768.html