列表

链表是一组数据项的集合，其中每个数据项都是一个节点的一部分，每个节点都包含指向下一个节点的链接。

约瑟夫问题

循环链表范例

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
#include <stdio.h>
#include <stdlib.h>
typedef struct node* link;
struct node {int item; link next;};
main(int argc, char *argv[]){
    int i;
    int N = atol(argv[1]);
    int M = atol(argv[2]);
    link t = malloc(sizeof *t);
    t->item = 1;
    t->next = t;

    link x = t;
    for(i=2; i<=N; i++){
        x->next = malloc(sizeof *x);
        x = x->next;
        x->item = i;
    }
    x->next = t;

    while(x != x->next){
        for(i=1; i<M; i++) x = x->next;
        x->next = x->next->next;
    }

    printf("%d\n", x->item);
}

约瑟夫问题

链表的数组表示，初始状态，设第i+1个人的索引为next[i]，next[8]=0形成一个循环链表。如下：M（12）个人，N（5）出局

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
#include <stdio.h>
#include <stdlib.h>
main(int argc, char *argv[]){
    int i, j;
    int N = atol(argv[1]);
    int M = atol(argv[2]);
    int *next = malloc(N*sizeof(int));

    if(next == NULL){
        printf("Insufficient memory.\n");
        return;
    }

    for(i=0; i<N-1; i++){
        next[i] = i + 1;
    }
    next[i] = 0;

    while(next[i] != i){
        for(j=0; j<M-1; j++){
            i = next[i];
        }
        next[i] = next[next[i]];
    }

    printf("%i\n", i+1);
}

item	0	1	2	3	4	5	6	7	8	9	10	11