C++循环链表解决约瑟夫环问题

约瑟夫环问题可以简单的使用数组的方式实现，但是现在我使用循环链表的方法来实现，因为上午看到一道面试题规定使用循环链表解决约瑟夫环问题。

　　什么是约瑟夫环？

　　“约瑟夫环是一个数学的应用问题：已知n个人（以编号1，2，3...n分别表示）围坐在一张圆桌周围。从编号为k的人开始报数，数到m的那个人出列；他的下一个人又从1开始报数，数到m的那个人又出列；依此规律重复下去，直到圆桌周围的人全部出列。”（百度百科中的解决办法列出了很多，可以看到循环链表并不是最简单的方法）

　　这道面试题考察了循环链表的“创建”，“遍历”和“删除”。

源代码如下：

#include<iostream>

using namespace std;

struct MyNode

{

    MyNode(int a_data):m_data(a_data),m_pNext(NULL){}

    int m_data;

    MyNode *m_pNext;

};

class Josephus

{

    public:

        Josephus(int a_N,int a_K,int a_M):m_N(a_N),m_K(a_K),m_M(a_M){

            createList();

            outputList();

        }

    protected:

        void createList();

        void outputList();

    private:

        MyNode *m_pHead;   //循环链表的头节点

        int m_N;  //链表节点个数

        int m_K;  // 第一个报数人的序号

        int m_M;  // 报数出局的数

};

void Josephus::createList()

{

    MyNode *pre = NULL;

    MyNode *cur = NULL;

    MyNode *p = new MyNode();

    m_pHead = p;

    cur = p;

    for(int i=; i<=m_N;i++)

    {

        p = new MyNode(i);

        pre = cur;

        cur = p;

        pre->m_pNext = p;

    }

    cur->m_pNext = m_pHead;

    int n = m_N;

    p = m_pHead;

    cout << "初始序列为:" << endl;

    while(n--){

        cout << p->m_data << ",";

        p = p->m_pNext;

    }

    cout << endl;

}

void Josephus::outputList()

{

    // 让pStart指向第一个报数人的序号

    MyNode *pStart = m_pHead;

    int count = ;

    while(count < m_K){

        pStart = pStart->m_pNext;

        count++;

    }

    MyNode *pTemp = pStart;

    MyNode *pPre = NULL;

    MyNode *tobeDeleted = NULL;

    cout << "依次出局的序列为:" << endl;

    while(pTemp->m_pNext!=pTemp) // when pTemp->m_pNext==pTemp only one node in the list

    {

        int count = ;

        while(count < m_M){

            pPre = pTemp;

            pTemp = pTemp->m_pNext;

            count++;

        }

        tobeDeleted = pTemp;

        pTemp = pTemp->m_pNext;

        pPre->m_pNext = pTemp;

        cout << tobeDeleted->m_data << ",";

    }

    cout << pTemp->m_data << endl;

}

int main()

{

    int total_people;

    int start;

    int step;

    cout << "请输入总人数:" << endl;

    cin >> total_people;

    cout << "请输入开始数的人:" << endl;

    cin >> start;

    cout << "请输入出局人数的数:" << endl;

    cin >> step;

    Josephus josephus(total_people,start,step);

    return ;

}                         

运行程序结果如下：