数据结构再战—约瑟夫环(循环链表)

学习思路

约瑟夫环是一个很经典的题目，有多种实现方法，为了练习链表我决定用三种方法实现：循环链表、数组标志位、数组模拟链表。

原题链接: AcWing

题目描述：

N 个人围成一圈顺序编号，从 1 号开始按 1、2、3 顺序报数，报 m 者退出圈外，其余的人再从 1、2、3 开始报数，报 m 的人再退出圈外，依次类推。 请输出最后那个剩下的人的编号。

输入格式

输入一行包含 2 个整数 n，m。 注意：程序有多组输入数据，当输入为0时退出

输出格式

对于每组输入数据，输出对应的答案（每组数据中最后剩余的人的编号）用换行隔开

数据范围

所有测试点满足 1 ≤ n ≤ 300，m ≤ n。

输入样例：

300 9
10 3
11 5
0 0

输出样例：

34
4
8

• 循环链表
• 数组标志位
• 数组模拟链表

循环链表实现代码:

#include <iostream>
using namespace std;
typedef struct node
{
    int data;
    struct node *next;
} NODE, *Link;
int main()
{
    int n, m; // n为人数，m为报数，每当报数到m就退出1人
    int i;
    int answer[100]; // answer保存每次的答案,最后统一输出
    int count = 0;   // count用来控制答案数组的下标
    Link head, tail, p, q;

    //创建头节点
    head = new NODE;
    head->data = -1;
    head->next = nullptr;

    //通过循环保存多组输入数据
    while (1)
    {
        scanf("%d %d", &n, &m);

        //如果n(人数)为0或者m(报数)为0则直接结束循环
        if (n == 0 || m == 0)
        {
            //释放头节点
            delete head;
            break;
        }
        else
        {
            //让另一个指针指向头节点
            tail = head;
            for (i = 0; i < n; ++i)
            {
                //按照人数构建链表
                p = new NODE;
                p->data = i + 1;      //保存每个人数的序号,从1开始
                tail->next = p;       //插到头节点的尾部
                p->next = head->next; //最后一个节点的next指向第一个节点，这样就构成了一个循环链表
                tail = p;             //另一个指针移动到新增的最后一个节点，为下一次插入做准备
            }

            //当循环链表构建完了之后
            p = head->next; // p指针指向第一个链表节点
            q = tail;       // q指针指向尾节点

            //报数,从1开始
            i = 1;

            // p和q是一个首,一个尾,永远是一前一后的关系,一旦他们相遇,则说明只剩一个节点了
            while (p != q)
            {
                //当 i 报数到 m
                if (i == m)
                {
                    //把当前节点从链表中删除
                    //这里的意思是,q永远在p的前一个节点，q->next->next表示的是p的下一个节点,而p指向的就是要删除的当前节点
                    //当q->next = q->next->next时,就把p的前一个节点和p指向的当前的节点的链接断掉了,重新去指向了p的后一个节点
                    //这样p所在的这个节点就被链表这个队伍抛弃了
                    q->next = q->next->next;

                    //然后就可以直接释放p所在的这个节点的内存
                    delete p;

                    //将p移动到下一个有效节点上,q->next这时指向的是p被释放的节点的下一个有效节点
                    p = q->next;

                    // i = 1重新开始报数
                    i = 1;
                }
                else
                {
                    // q指向p所在的节点,而p一开始指向的是第一个有效节点
                    q = p;

                    //然后p往后移动一位,这样q和p就构成了一前一后的关系,一直往后移动
                    p = p->next;

                    //报数器加1，一直报数到m就删除p所指向的节点
                    i++;
                }
            }

            //维持链表的完整性，就是说当循环退出时链表中除了头节点被删的只剩下一个节点了，这个节点由p和q指针共同指着，这时头节点原本指向的第一个有效节点已经被删除，头节点和链表之间联系已经被断开
            //如果还要对这个剩下的最后一个节点做其他操作那么可以用头节点重新链接这个最后的节点，如果题目没有要求可以不加这一句，只需要在程序最后把那最后一个节点删除就行了
            // head->next = q;

            //将最后一个剩余的人的序号保存起来，它就是我们要的答案
            answer[count] = p->data;

            //答案数组的计数器加一，进行新一轮的循环
            count++;

            //删除最后一个节点
            delete p;
            head->next = nullptr; //链表这时已为空，只剩下头节点了，可以将头节点的next置为空，这是一个好习惯
        }
    }

    //按照题目要求输出最后的答案
    for (int i = 0; i < count; ++i)
    {
        cout << answer[i] << endl;
    }

    return 0;
}

数组标志位实现代码:

#include <iostream>
using namespace std;
int main()
{
    int n, m;      // n为人数，m为报数
    int number;    //记录剩余的人数
    int count = 1; // count代表当前的报数
    int i, pos;
    while (cin >> n >> m)
    {
        //如果人数为0或者报数为0则直接终止程序
        if (n == 0 || m == 0)
        {
            return 0;
        }
        number = n;

        // monkey数组存储人的编号和状态
        int monkey[301] = {0};
        //存储-1代表无效的数组部分，0代表退出的人，1至n+1代表还没退出的人序号
        for (i = 0; i < n; ++i)
        {
            monkey[i] = i + 1;
        }

        // pos控制当前处理的数组下标,指向数组的开始位置
        pos = 0;
        while (number > 1)
        {
            if (monkey[pos] > 0)
            {
                if (count != m)
                {
                    //报数+1
                    count++;

                    //当前处理的数组下标+1
                    pos = (pos + 1) % n;
                }
                else
                {
                    monkey[pos] = 0;     //标记为0,设置当前人出局
                    count = 1;           //报数重新开始
                    number--;            //人数-1
                    pos = (pos + 1) % n; //当前处理的数组下标+1
                }
            }
            else
            {
                //这条语句的妙处在于:当n的人数为10 时，pos为9,那么pos+1就变成了10,而10%10求余之后就变成了0,这样就构成了一个循环的情况
                //永远在0~9之间循环,当超过9就重新变为0
                pos = (pos + 1) % n; //当前处理的数组下标+1
            }
        }

        //输出最后的结果
        for (i = 0; i < n; ++i)
        {
            //此时数组中退出的人的编号都变成了0,只有唯一的那个剩下的人的编号不是0,所以只要找到最后那个不是0的输出就行了
            if (monkey[i] > 0)
            {
                cout << monkey[i] << endl;
            }
        }
    }
    return 0;
}

数组模拟链表实现代码:

#include <iostream>
using namespace std;
int main()
{
    int n, m;          // n为人数,m为报数
    int number;        //记录剩余的人数
    int count;         // count代表当前的报数
    int i, pos, prior; // pos指向数组首位,prior指向数组末尾
    while (cin >> n >> m)
    {
        //如果人数为0或者报数为0,则终止程序
        if (n == 0 || m == 0)
        {
            return 0;
        }

        //数组存储下一个人的位置，标识为-1的代表退出的人
        int monkey[301] = {0};

        //初始化数组,数组存储下一个人的下标
        for (i = 0; i < n - 1; ++i)
        {
            monkey[i] = i + 1;
        }

        //下标为n-1的元素的下个序号为0，形成循环链表
        monkey[i] = 0;

        // monkey[i+1] = -2; //将超过范围的元素标识为-2,方便跟踪的时候看数组内存

        number = n;
        pos = 0;
        prior = n - 1;
        count = 1;
        while (number > 1) //设置循环退出条件,也可以设置为:prior!=pos，prior永远指向pos的前一个节点
        {

            //如果没有报数到m
            if (count != m)
            {
                prior = pos; // prior保存pos的上一个节点的下标,也就是prior指针指向pos所在的下标

                // pos移动到下一个有效节点的下标,也就是pos指针指向下一个节点的下标，因为数组中存储的值刚好是下一个数组元素的下标
                //所以monkey[pos]里面存储的就是pos要指向的下一个节点的下标
                pos = monkey[pos];

                //报数加1
                count++;
            }
            else //当报数到了m
            {

                /*这里非常难理解，经过我一段时间的梳理，发现实际上就是：prior的下标在数组中对应的值是pos的下标,而pos的下标在数组中对应的值是pos的下一个数组元素的下标
                当monkey[prior] = monkey[pos]之后，也就是把pos的下标在数组中对应的值(也就是pos的下一个数组元素的下标)赋给monkey[prior]，原本monkey[prior]里面存储的是
                pos所在的数组元素的下标，现在就变成了pos的下一个数组元素的下标，这样monkey[prior]与pos所在的数组元素之间的联系就断开了
                */

                //更改链接关系
                monkey[prior] = monkey[pos];

                //出局的人,标识为-1,也就是将pos所在的数组元素标记为删除
                monkey[pos] = -1;

                // pos移动到下一个有效节点,因为经过上面的赋值之后,monkey[prior]里面的值已经变成了原先pos所在数组元素的下一个数组元素的下标
                //所以pos重新移动到了prior的下一个有效(不为-1)的数组元素
                pos = monkey[prior];

                //人的个数减一
                number--;

                //重新开始报数
                count = 1;
            }
        }

        //当循环结束后就只剩下最后那个没有被赋值为-1的人被pos和prior共同指着,那个人就是我们要的答案
        //输出最后一个有效的人,因为pos对应的最后那个人的数组元素的值是比pos下标多1的，所以最后要加1
        cout << pos + 1 << endl;
    }
    return 0;
}