约瑟夫问题循环链表

 1 #include <stdio.h>
 2 #include <stdlib.h>
 3 
 4 #define N 8
 5 #define STEP 3
 6 
 7 typedef int datatype;
 8 
 9 typedef struct _node_
10 {
11     datatype data;
12     struct _node_ *next;
13 }linknode, *linklist;
14 #if 0
15 linklist p, q;
16 linklist h = (linklist)malloc(sizeof(linknode));
17 h->next = NULL;
18 
19 p = h;
20 for(i=0; i<10; i++)
21 {
22     q = (linklist)malloc(sizeof(linknode));
23     q->data = i;
24     q->next = NULL;
25     p->next = q;
26     p = p->next;
27 
28 }
29 #endif
30 int main(int argc, char *argv[])
31 {
32     int i;
33     linklist p, q;
34 
35     p = (linklist)malloc(sizeof(linknode));
36     p->data = 1;
37     q = p;
38 
39     for(i=2; i<=N; i++)
40     {
41         q->next = (linklist)malloc(sizeof(linknode));
42         q = q->next;
43         q->data = i;    
44     }
45     q->next = p;
46 #if 0
47     q = p;
48     for(i=0; i<=N; i++)
49     {
50         printf("%d ", q->data);
51         q = q->next;    
52     }
53 #endif
54 
55     while(p->next != p)
56     {
57         for(i=0; i<STEP-2; i++)
58             p = p->next;
59 
60         q = p->next;
61         p->next = q->next;
62         printf("%d ", q->data);
63         free(q);
64         p = p->next;
65     }
66     printf("%d \n", p->data);
67     return 0;
68 }

已知N个人围着一圈站（编号1、2、3、、、、、n），以编号为K 的人开始报数，数到m的那个人出列；他的下一个人又从k开始报数，数到m的那个出列；依次规律重复下去，直到全部出列。

思路：

一、建立一个具有n个节点的，无头节点的循环链表。

二、确定第一个报数人的位置。

三、不断地从链表中删除节点，直到链表位为空。