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

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


//基于单循环链表的约瑟夫环问题。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;
    }
    
    本回答被题主选为最佳回答 , 对您是否有帮助呢?
    评论
  • CSDN-Ada助手 CSDN-AI 官方账号 2023-03-29 16:55
    关注
    评论
查看更多回答(1条)

报告相同问题?

问题事件

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

悬赏问题

  • ¥40 找同学帮敲Python代码
  • ¥15 MYSQL 订单的商品明细重复计算问题
  • ¥15 微信实时共享位置修改
  • ¥100 TG的session协议号转成直登号号后客户端登录几分钟后自动退出设备
  • ¥50 共模反馈回路的小信号增益
  • ¥15 arduino ssd1306函数与tone函数放歌代码不兼容问题
  • ¥70 0.96版本hbase的row_key里含有双引号,无法deleteall
  • ¥15 诊断性META分析合并效能的检验
  • ¥15 请问abb根据色块判断奇偶数并根据批次号放入仓储
  • ¥66 开发PC客户端一定也要开发上位机吗?