Question

（C++）用循环单链表解决约瑟夫问题

用C++写一个循环链表模板类，且链表不带头节点

Answer 1

#include <iostream>
using namespace std;

class MyNode
{
public:

    MyNode(int a_data):data(a_data),link(NULL) {}


    int    data;
    MyNode *link;
};

class Josephus
{
public:
    Josephus(int a_N, int a_K, int a_M):N(a_N),K(a_K),M(a_M)
    {
        createList();
        outputList();
    }

protected:
    void createList();
    void outputList();

private:
    MyNode *m_pHead;//循环链表的头节点
    int    N;     //链表节点个数
    int    K;     //第一个报数人的序号
    int    M;     //报数出局的数
};

void Josephus::createList()
{
    MyNode *pre = NULL;
    MyNode *cur = NULL;
    MyNode *p = new MyNode(1);
    m_pHead = p;
    cur = p;
    for (int i=2; i<=N; i++)
    {
        p = new MyNode(i);
        pre = cur;
        cur = p;
        pre->link = cur;
    }
    cur->link = m_pHead;

    int n=N;
    p = m_pHead;
    cout<<"原来顺序：";
    while (n--)
    {
        cout << p->data << ",";
        p = p->link;
    }
    cout << endl;
}

void Josephus::outputList()
{
    MyNode *pre = NULL;
    MyNode *cur = m_pHead;
    K--;
    while (K--)            //寻找第K个人（开始报数的人）
    {
        pre = cur;
        cur = cur->link;
    }
    cout<<"依次出列的数字：";
    while (N--)            //输出链表中所有的节点值
    {
        int s = M-1;
        while (s--)            //寻找间隔M的人
        {
            pre = cur;
            cur = cur->link;
        }
        MyNode *p = cur;
        if(N>=1)
        cout << p->data << ",";
        if(N==0)
        {
            cout<<p->data<<endl;
           cout<<"最后剩下的数字:"<<p->data<<endl;
        }

        cur = cur->link;    //删除节点的过程
        pre->link = cur;
        delete p;
        p=NULL;
    }
}

int main()
{
    Josephus josephus(8,1,3);
    return 0;
}

网上找的代码，稍微改了一下。应该符合要求。