英豪比利 2023-03-29 14:39 采纳率: 60%
浏览 32
已结题

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


//基于单循环链表的约瑟夫环问题。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;
}

  • 写回答

2条回答 默认 最新

  • apples_kk 2023-03-29 15:12
    关注
    
    #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;
    }
    
    本回答被题主选为最佳回答 , 对您是否有帮助呢?
    评论
查看更多回答(1条)

报告相同问题?

问题事件

  • 系统已结题 4月6日
  • 已采纳回答 3月29日
  • 创建了问题 3月29日

悬赏问题

  • ¥15 win32如何自绘编辑框的背景图片(语言-c++|操作系统-windows)
  • ¥15 微信夜间被转走了1w对,当天手机剪切板里就出现了这个乱码,有铁子可以看看是啥吗可以
  • ¥50 跑通github上的代码 深度学习 pytorch
  • ¥50 求写,批处理调用分区助手分区脚本
  • ¥15 求购HI3519AV100开发板
  • ¥15 请问1553 RT怎么测试,没有BC有方法吗
  • ¥100 业务编程如何选择学习方向和内容?
  • ¥15 wamp3.3.5安装完成后图标正常显示绿色,鼠标左右键点击图标均无反应。求解决方法。
  • ¥15 鼠标点击的这条记录了什么?
  • ¥15 在写pid调速的程序时,电机始终维持最大速度