约瑟夫问题链表实现

list.h (链表函数接口）

 1 typedef struct node* link;
 2 struct node 
 3 {
 4     int item;
 5     link next;
 6 };
 7 typedef link Node;
 8 
 9 void initNodes(int);
10 void freeNode(link);
11 link newNode(int);
12 void insertNext(link,link);
13 link deleteNext(link);
14 link Next(link);
15 int Item(link);

list.c (链表函数接口实现）

 1 #include<stdlib.h>
 2 #include "list.h"
 3 
 4 link freelist;
 5 
 6 void initNodes(int N)
 7 {
 8     freelist=malloc((N+1)*(sizeof *freelist));
 9     for(int i=0; i<N+1; i++)
10         freelist[i].next=&freelist[i+1];
11     freelist[N].next=NULL;
12 }
13 link newNode(int i)
14 {
15     link x=deleteNext(freelist);
16     x->item=i; x->next=x;
17     return x;
18 }
19 void freeNode(link x)
20 {
21     insertNext(freelist, x);
22 }
23 void insertNext(link x, link t)
24 {
25     t->next=x->next;
26     x->next=t;
27 }
28 link deleteNext(link x)
29 {
30     link t=x->next;
31     x->next=t->next;
32     return t;
33 }
34 link Next(link x)
35 {
36     return x->next;
37 }
38 int Item(link x)
39 {
40     return x->item;
41 }

main.c (约瑟夫问题程序)

 1 #include <stdio.h>
 2 #include "list.h"
 3 
 4 int main(void)
 5 {
 6     int N=10,M=5;
 7     Node t, x;
 8     
 9     initNodes(N);
10     x=newNode(1);
11    // x->next=x;
12     insertNext(x,x);
13     for(int i=2; i<=N; i++)
14     {
15         t=newNode(i);
16         insertNext(x,t); 
17         x=t;
18     }
19     while(x!=Next(x))
20     {
21         for(int i=1; i<M; i++)
22             x=Next(x);
23         freeNode(deleteNext(x));
24     }
25     printf("%d",Item(x));
26     
27     return 0;
28 }

约瑟夫问题 链表实现

约瑟夫问题链表实现