约瑟夫问题C代码

 1 /*Joseph Problem
 2  *利用单循环链表解决约瑟夫问题。
 3  *问题描述：将n个数链接成一个环，从第m个开始，每次从1计数到s时
 4  *          将s删除。从下一个开始再次从1计数至s时删除s。直到全
 5  *        部删除为止。
 6  * */
 7 #include<stdio.h>
 8 #include<stdlib.h>
 9 
10 typedef struct Node{
11     int data;
12     struct Node* next;
13 }Node;
14 typedef struct Node* LinkList;
15 
16 void CreateJosephLoop(LinkList *L,int number){
17 //创建Joseph环，在头结点中放入了元素1.
18     *L = (LinkList)malloc(sizeof(struct Node));
19     if(!(*L)){
20         printf("Error:malloc:0!\n");
21         exit(1);
22     }
23     (*L)->next = (*L);
24     (*L)->data = 1;
25     int i;
26     LinkList new;
27     LinkList tail = *L;
28     for(i = 1; i < number; i++){
29         new = (LinkList)malloc(sizeof(struct Node));
30         if(!new){
31             printf("Error:malloc:1+i");
32             exit(1);
33         }
34         new->data = i+1;
35         new->next = tail->next;
36         tail->next = new;
37         tail = new;
38     }
39 }
40 void JosephProblem(int loopSize,int from,int stepBy){
41 //loopSize：Joseph环的大小
42 //form：从from开始
43 //stepBy：每次计数到stepBy时删除stepBy所指向的元素
44     LinkList L;
45     CreateJosephLoop(&L,loopSize);
46     int seekStart = 1;
47     while(seekStart < from){
48         L = L->next;
49         seekStart += 1;
50     }
51     while(L->data != L->next->data){
52         int i = 1;
53         LinkList temp;
54         for(i = 1;i < stepBy - 1; ){
55             L = L->next;
56             i++;
57         }
58         temp = L->next;
59         printf("%d-->",temp->data);
60         L->next = L->next->next;
61         L = L->next;
62         free(temp);
63     }
64     printf("%d\n",L->data);
65 }
66 int main(){
67     JosephProblem(10,3,4);
68     JosephProblem(41,1,3);
69     return 0;
70 }