約瑟夫問題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 }