约瑟夫问题-循环链表解法

pwnmelife

1. #include <stdio.h>
   
2. #include <stdlib.h>
   
3. 
   
4. #define ElementType int
   
5. 
   
6. typedef struct Node {
   
7.         ElementType data;
   
8.         struct Node* next;
   
9. } Node, *LinkList;
   
10. 
    
11. void InitCreateLinkLoopList(LinkList* L);
    
12. void CreateLinkLoopList(LinkList* L, int n);
    
13. void Josephus(LinkList* L);
    
14. 
    
15. /*
    
16. * 3->6->9->12->15->18->21->24->27->30->33->36->39->1->5->10->14->19->23->28->32->37
    
17. * ->41->7->13->20->26->34->40->8->17->29->38->11->25->2->22->4->16->35->31
    
18. */
    
19. 
    
20. int main() {
    
21.         LinkList* L = (LinkList*)malloc(sizeof(LinkList));
    
22.         InitCreateLinkLoopList(L);
    
23.         CreateLinkLoopList(L, 41);
    
24.         Josephus(L);
    
25.         return 0;
    
26. }
    
27. void InitCreateLinkLoopList(LinkList* L) {
    
28.         (*L) = (LinkList)malloc(sizeof(Node));
    
29.         (*L)->data = 41;
    
30.         (*L)->next = (*L);
    
31. }
    
32. void CreateLinkLoopList(LinkList* L, int n) {
    
33.         LinkList p, r;
    
34.         p = (*L);
    
35. 
    
36.         for (int i = 1; i <= n; i++) {
    
37.                 r = (LinkList)malloc(sizeof(Node));
    
38.                 r->next = p->next;
    
39.                 r->data = i;
    
40.                 p->next = r;
    
41.                 p = r;
    
42.         }
    
43. }
    
44. void Josephus(LinkList* L) {
    
45.         LinkList p, r, q;
    
46.         r = p = (*L);
    
47.         int times = 1;
    
48.         int number = 1;
    
49.         while (1) {
    
50.                 for (times = 1; times <= 3; times++) {
    
51.                         p = p->next;
    
52.                         if ((r == p)||!p->data) {
    
53.                                 times--;
    
54.                         }
    
55.                 }
    
56.                 printf("%d ", p->data);
    
57.                 p->data = 0;
    
58.                 number++;
    
59.                 if (number == 42) {
    
60.                         break;
    
61.                 }
    
62.         }
    
63. }

复制代码