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


//基于单循环链表的约瑟夫环问题。n个人围成一圈，从第一个人开始报数1、2、3, 凡报到3者退出圈子, 
// 找出最后留在圈子中的人的序号。请实现下列解决约瑟夫环问题的单循环链表类Joseph，使程序正确运行。
// 当单向链表中的尾结点指向头结点即构成单循环链表。
//如果输入为0，输出 No one!
#include
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;
}



#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;
}