线性表的基本应用(四)：用循环链表模拟约瑟夫(Josephus)环问题

要求：

已知n个人（以编号1，2，3...n分别表示）围坐在一张圆桌周围。从编号为1的人开始报数，数到m的那个人出列；他的下一个人又从1开始报数，数到m的那个人又出列；依此规律重复下去，直到圆桌周围的人全部出列。要求输出出列的过程和最后一个人的编号。

思路：

该问题为古希腊著名史学家约瑟夫(Josephus)提出的问题演变而来，通常被称为约瑟夫环问题。若用循环链表来模拟，需要使用n个结点存储每个人的编号，由第一个结点开始循环遍历每个结点，且在遍历时同时计数。当计数到m时，打印访问结点的信息并将访问结点删除后继续循环遍历，直到链表仅剩余最后一个结点时结束。最后打印剩余结点信息。

#include <bits/stdc++.h>
using namespace std;

typedef struct Node
{
    int num; //num为约瑟夫环中每个人初始的编号
    struct Node * pNext;
}NODE,*PNODE;

class Josephus //Josephus类创建了一个不包含头结点的循环链表
{
public:
    Josephus(int n,int m); //构造函数中，n为约瑟夫环的初始长度，报到m的人出列
    void start();
private:
    PNODE pHead;
    PNODE pTail;
    int n; //在这里，n为约瑟夫环当前的长度，当n=1时，程序终止
    int m; //报到m的人出列
};

Josephus::Josephus(int n,int m)
{
    PNODE p;
    pHead = pTail = new Node();
    pHead->num = 1;
    pTail->pNext = pHead;
    for (int i = 2; i<=n; i++)
    {
        p = new Node();
        p->num = i;
        pTail->pNext = p;
        pTail = p;
        pTail->pNext = NULL;
    }
    pTail->pNext = pHead;
    this->n = n;
    this->m = m;
}

void Josephus::start()
{
    PNODE p = pTail;
    PNODE q = pHead;
    for (int i = 1; ; i++)
    {
        if (this->n == 1) //当n=1时，终止遍历
        {
            printf("\n最终留下的是%d号！\n",q->num);
            break;
        }
        if (i == this->m) //当计数到第m个结点时，删除该结点继续遍历
        {
            printf("%d",q->num);
            if(n>2)
                printf("-");
            p->pNext = q->pNext;
            delete q;
            q = p->pNext;
            i = 1;
            n--;
        }
        p=p->pNext;
        q=q->pNext;
    }
}

int main()
{
    Josephus j(41,3);
    j.start();
    return 0;
}

运行结果如下图所示：