数据结构与算法18讲约瑟夫的作业

安吉

1. /*编号为1~N的N个人按顺时针方向坐一圈，每个人持有一个密码（正整数，可以自由输入），
   
2. 开始人选一个正整数作为报数上限值M，从第一个人按顺时针方向自1开始顺序报数，报到M时
   
3. 停止报数。报M的人出列，将他的密码作为新的M值，从他顺时针方向上的下一个人开始从1报数，
   
4. 如此下去，直至所有人出列*/
   
5. #include<stdio.h>
   
6. #include<stdlib.h>
   
7. 
   
8. typedef struct circular_linked_list{
   
9.         int password;
   
10.         int index;
    
11.         struct  circular_linked_list *next;
    
12. } Node;
    
13. 
    
14. Node * Creat (int n);
    
15. 
    
16. int main()
    
17. {
    
18.         int i,n,m;
    
19.         Node *p, *temp;
    
20.         printf("输入一个正整数n，代表有n个人围成一个圈。\n");
    
21.         scanf("%d",&n);
    
22.         p=Creat(n);
    
23.         printf("输入一个正整数M，代表第一个人报数的上限值。\n");
    
24.         scanf("%d",&m);
    
25. 
    
26.     m=m>n?m%n:m;
    
27.         while(p->next!=p)
    
28.         {
    
29.                 for(i=1;i<m-1;i++)
    
30.                         p=p->next;
    
31.                 printf("%d->",p->next->index);
    
32.                 m=p->next->password;
    
33.         m=m>n?m%n:m;
    
34.                 temp=p->next;
    
35.                 p->next=temp->next;
    
36.                 free(temp);
    
37.                 p=p->next;
    
38.         }
    
39.         return 0;
    
40. }
    
41. Node *Creat(int n)
    
42. {
    
43.         int i;
    
44.         Node *head, *p, *s;
    
45.         head = (Node *)malloc(sizeof(Node));
    
46.         p=head;
    
47.         printf("输入N个正整数，代表每个人手中的密码\n");
    
48.         for(i=0;i<n;i++)
    
49.         {
    
50.                 s=(Node *)malloc(sizeof(Node));
    
51.                 scanf("%d",&s->password);
    
52.                 s->index=i+1;
    
53.                 p->next=s;
    
54.                 p=s;
    
55.         }
    
56.         s->next=head->next;
    
57.         free(head);
    
58.         return s->next;
    
59. }
    

复制代码

ps：小甲鱼老师，我欠你一个会员。