基于单循环链表的约瑟夫环问题

Question

//基于单循环链表的约瑟夫环问题。n个人围成一圈，从第一个人开始报数1、2、3, 凡报到3者退出圈子, 
// 找出最后留在圈子中的人的序号。请实现下列解决约瑟夫环问题的单循环链表类Joseph，使程序正确运行。
// 当单向链表中的尾结点指向头结点即构成单循环链表。
//如果输入为0，输出 No one!
#include<iostream>
using namespace std;
struct  node
{
    int  data;
    node* next;
    node(int  d, node* n = NULL) :data(d), next(n) {}
};
class  Joseph
{
private:
    node* head;
public:
    Joseph(int  n);
    ~Joseph();
    void  simulate();
};








int  main()
{
    int  n;
    cin>> n;          //若输入5，表5人
    Joseph  jos(n);//生成有5个结点的链表，5个结点的data为1、2、3、4、5，表各人的序号
    jos.simulate();
    //输出两行。第一行输出被淘汰人的序号（序号间一个空格隔开）：3  1  5  2
    //第二行输出剩下人的序号：4

    return  0;
}

Answer 1

#include <iostream>
using namespace std;

struct Node
{
    int data;
    Node *pNext;
};

class Joseph
{
private:
    Node *head;
public:
    Joseph()
    {
        head = NULL;
    }
    // 创建单链表
    void creatList(int n)
    {
        if(n == 0)
        {
            cout << "No one!" << endl;
        }
        else
        {
            // 创建头结点
            head = new Node;
            head->pNext = head;
            head->data = 1;

            Node *p = head;
            // 创建节点
            for(int i = 2; i <= n ; i++)
            {
                Node *s = new Node;
                s->data = i;
                p->pNext = s;
                p = s;
            }
            // 重新回到头结点
            p->pNext = head;
        }
    }
    // 出圈
    void JosephRing()
    {
        if(head != NULL)
        {
            int count = 0;
            Node *pPre = head;
            Node *pCur = head->pNext;
            while(pPre->pNext != pPre)
            {
                    count++; 
                    if(count == 3)
                    {
                    // 删除pCur
                    pPre->pNext = pCur->pNext;
                    cout << pCur->data << "出圈"<< endl;
                    // 将当前指针移动至下一位
                    pCur = pPre->pNext;
                    // counter 归零
                    count = 0;
                    }
                    else
                    {
                        // 将pPre 指针移动至下一位
                        pPre = pCur;
                        // 将当前指针移动至下一位
                        pCur = pPre->pNext;
                    }
            }
            cout << "最后留在圈中的是：" << pPre->data << endl;
        } 
    }
    ~Joseph(){}
};

int main()
{
    int n = 0;
    cin >> n;

    Joseph joseph;
    joseph.creatList(n);
    joseph.JosephRing();

    return 0;
}

Answer 2

• 你可以参考下这个问题的回答, 看看是否对你有帮助, 链接: https://ask.csdn.net/questions/744176
• 这篇博客你也可以参考下：单向循环链表解决约瑟夫问题
• 除此之外, 这篇博客: 数据结构考研总结中的 哈夫曼树的构造 部分也许能够解决你的问题, 你可以仔细阅读以下内容或跳转源博客中阅读:
  

• 1. 将n个结点分别作为n棵仅含有一个结点的二叉树，构成森林F

  2. 构造一个新结点，从F中选取两棵根结点权值最小的树作为新结点的左、右子树，并且将新结点的权值置为左、右子树上根结点的权值之和

  3. 从F中删除刚才选出的两棵树，同时将新得到的树加入F中

  4. 重复2-3步骤

• 您还可以看一下 AI100讲师老师的朋友圈爆款背后的计算机视觉技术与应用课程中的 朋友圈爆款背后的计算机视觉技术与应用小节, 巩固相关知识点