循环链表Josephus问题（c,cpp)

问题描述：

设有n个人围坐在一个圆桌周围，现从第s个人开始报数，数到第m个的人出列，然后从出列的下一个人重新开始报数，数到第m个的人又出列，.......，如此反复直到所有的人出列为止。

Josephus.c

 1 #include <stdio.h>
 2 #include <stdlib.h>
 3 typedef struct LNode
 4 {
 5     int data;
 6     struct LNode *next;
 7 }LNode,*LinkList;
 8 
 9 void CreateList(LinkList *l,int n)
10 {
11     int i;
12     LinkList p,tail;
13     for(i = 1;i <= n;i++)
14     {
15         p = (LinkList)malloc(sizeof(LNode));
16         p->data = i;
17         
18         if(i == 1)
19         {
20             *l = p;
21             tail = *l;
22         }
23         else
24         {
25             tail->next = p;
26         }
27         tail = p;
28     }
29     tail->next = *l;
30 }
31 
32 void PrintList(LinkList l)
33 {
34     LinkList p;
35     p=l;
36     printf("初始化：");
37     while(p->next != l)
38     {
39         printf("%d ",p->data);
40         p = p->next;
41     }
42     printf("%d
",p->data);
43 }
44 
45 void DelElem(LinkList l)
46 {
47     LinkList p;
48     p = l->next;
49     l->next = p->next;
50     printf("%d",p->data);
51     free(p);
52 }
53 
54 LinkList LocatePos(LinkList l,int m)
55 {
56     LinkList p = l;
57     int i;
58     for(i = 1;i < m;i++)
59     {
60         p = p->next;
61     }
62     return p;
63 }
64 
65 void Josephus(LinkList l,int n,int s,int m)
66 {
67     LinkList p,q;
68     p = LocatePos(l,s);
69     while(p->next != p)
70     {
71         if(m == 1)
72         {
73             q = LocatePos(p,n--);
74         }
75         else
76         {
77             q =LocatePos(p,m-1);
78         }
79         DelElem(q);
80         p = q->next;
81     }
82     printf("%d",p->data);
83 }
84 int main()
85 {
86     int n,s,m;
87     LinkList l;
88     printf("总人数：");
89     scanf("%d",&n);
90     CreateList(&l,n);
91     PrintList(l);
92     printf("第几个人开始报数：");
93     scanf("%d",&s);
94     printf("数到第几个人出列：");
95     scanf("%d",&m);
96     Josephus(l,n,s,m);
97     return 0;
98 }

Josephus.cpp

 1 #include <iostream>
 2 #include <cstdlib>
 3 using namespace std;
 4 typedef struct LNode
 5 {
 6     int data;
 7     struct LNode *next;
 8 }LNode,*LinkList;
 9 
10 LinkList CreateList(LinkList &l,int n)
11 {
12     LinkList tail,p;
13     int i;
14     for(i = 1;i <= n;i++)
15     {
16         p = (LinkList)malloc(sizeof(LNode));
17         p->data = i;
18         if(i == 1)
19         {
20             l = p;
21             tail = l;
22         }
23         else
24         {
25             tail->next = p;
26         }
27         tail = p;
28     }
29     tail->next = l;
30 }
31 
32 void PrintList(LinkList l)
33 {
34     LinkList p = l;
35     while(p->next != l)
36     {
37         cout<<p->data<<" ";
38         p = p->next;
39     }
40     cout<<p->data<<endl;
41 }
42 
43 void DelElem(LinkList p)
44 {
45     
46     LinkList q;
47     q = p->next;
48     p->next = q->next;
49     cout<<q->data<<" ";
50     free(q);
51 }
52 
53 LinkList LocatePos(LinkList l,int k)
54 {
55     int i;
56     LinkList p = l;
57     for(i = 1;i < k;i++)
58     {
59         p = p->next;
60     }
61     return p;
62 }
63 
64 void Josephus(LinkList l,int n,int s,int m)
65 {
66     LinkList p,q;
67     p = LocatePos(l,s);
68     cout<<"输出顺序：";
69     while(p != p->next)
70     {
71         if(m == 1)
72             q = LocatePos(p,n--);
73         else
74             q = LocatePos(p,m-1);
75         DelElem(q);
76         p = q->next;
77         
78     }
79     cout<<p->data<<endl;
80     free(p);
81 }
82 int main()
83 {
84     LinkList l;
85     int n,s,m;
86     cout<<"总人数：";
87     cin>>n;
88     CreateList(l,n);
89     cout<<"初始化：";
90     PrintList(l);
91     cout<<"第几个人开始报数：";
92     cin>>s;
93     cout<<"数到第几个人出列：";
94     cin>>m;
95     Josephus(l,n,s,m); 
96     return 0;
97 }