By yusijia

Updated:

Contents
  1. 1. 循环链表
  2. 2. 题目：

循环链表

  • 用一道经典例题来理解吧！
  • 约瑟夫环问题
  • 补：约瑟夫环问题其实还可以用数论的知识解。

题目：

有n个人(n不是特别大的数),排成一个圈，从第一个人开始数1，数到m的人出队，然后第m+1个人数1… 一直这样循环下去，求最后的一个幸存的人是谁

图片

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
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98


//从1开始：
#include<stdio.h>
#include<stdlib.h>
struct node{
    int v;
    struct node *next;
}*head;
void insert_node(int val)                        //头插法
{
    struct node *p=(struct node*)malloc(sizeof(struct node));
    p->v=val;
    p->next=head;
    head=p;
}
void delete_node(struct node *p)
{                                               //注意是把下一个节点删除
    struct node *q=p->next;                     //把下一个节点记住
    p->v=p->next->v;                            //让当前节点等于下一个节点里的值,(重点)然后从当前节点开始数1
    p->next=q->next;
    free(q);
}
int main()
{
    int n,m,i;
    struct node *p;
    while(scanf("%d%d",&n,&m)==2 && n)//scanf（）函数识别了正确输入的两个数，且n不等于0，n等于0说明为空链表
    {
        head=NULL;
        for(i=n;i>0;i--)              //建链表   ，顺序是从1开始的，例如n=5，则为1，2，3，4，5
            insert_node(i);
        p=head;                       //从头找
        while(p->next!=NULL)          //找最后一个不等于NULL的节点
            p=p->next;
        p->next=head;                 //首尾相接，（head=第一个节点，所以第一个节点也是作为头节点）此时p还在最后一个节点上
        p=p->next;                    //p到1的位置上
        while(--n)                    //删掉n-1个        循环n-1次  //如果是while（n--）就是循环n次
        {
            for(i=1;i<=m-1;i++)
                p=p->next;
            delete_node(p);           //删除当前节点，让下一个节点代替它
        }
        printf("%d\n",p->v);
        free(p);                      //注意养成习惯：用完了就删了他
    }
    return 0;
}




//从0开始：
#include<stdio.h>
#include<stdlib.h>
struct node{
    int v;
    struct node *next;
}*head;
void insert_node(int val)           //头插法
{
    struct node *p=(struct node*)malloc(sizeof(struct node));
    p->v=val;
    p->next=head;
    head=p;
}
void delete_node(struct node *p)
{
    struct node *q=p->next;         //把下一个节点记住
    p->v=p->next->v;
    p->next=q->next;
    free(q);
}
int main()
{
    int n,m,i;
    struct node *p;
    while(scanf("%d%d",&n,&m)==2&&n)
    {
        head=NULL;
        for(i=n;i>=0;i--)           //建链表   ,顺序是从0开始的例如n=5，则为0，1，2，3，4，5
            insert_node(i);
        p=head;                     //从头找
        while(p->next!=NULL)        //找最后一个不等于NULL的节点
            p=p->next;
        p->next=head;               //首尾相接
        p=p->next;
        while(n--)                  //删掉n-1个  ,从0开始，例如n为5，但因为从0开始所以右6个，删除5个，while（n--）
        {
            for(i=1;i<=m-1;i++)
                p=p->next;
            delete_node(p);
        }
        printf("%d\n",p->v);
        free(p);                    //注意养成习惯：用完了就删了他
    }
    return 0;
}
Contents
  1. 1. 循环链表
  2. 2. 题目：