问题描述：
有n个小孩围成一圈，将他们从1开始依次编号，从编号为1的小孩开始报数，数到m的小孩出列，然后从出列的下一个小孩重新开始报数，数到m的小孩又出列，如此反复，直到所有的小孩全部出列为止，求整个出列序列。例如，n=6，m=5，则出列序列是：5,4,6,2,3,1。
办法：使用一个循环单链表表示小孩围成一圈。然后从编号为1的节点开始计数，计数到m时，将对应的节点从单链表中移除，同时输出该节点的编号。
（1）节点的存储结构：
typedef struct _ListNode
{
size_t number;
_ListNode *next;
}ListNode;
（2）设计一个Joseph类，其中包括mTotal(对应n)，mStart(对应m)整型变量和首节点指针mHead，构造函数用于建立长度为mTotal的循环单链表。保护成员函数JosephSequence用于输出约瑟夫序列。析构函数不做任何工作。
具体代码如下：
#ifndef JOSEPH_H
#define JOSEPH_H
#include <stdio.h>
typedef struct _ListNode
{
size_t number;
_ListNode *next;
}ListNode;
class Joseph
{
private:
Joseph()
{
}
public:
Joseph(size_t total,size_t start);
virtual ~Joseph();
void printJsequence();
protected:
void JosephSequence();
private:
size_t mTotal;
size_t mStart;
ListNode* mHead;
};
Joseph::Joseph(size_t total,size_t start)
{
mTotal = total;
mStart = start;
ListNode *r,*p;
mHead = new ListNode();
mHead->next = nullptr;
mHead->number = 1;
r = mHead;
//建立单链表,包含mTotal个节点
for (size_t i=2; i <= mTotal; ++i)
{
p = new ListNode();
p->number = i;
r->next = p;
r = p;
}
r->next = mHead; //将链表连成循环链表
}
void Joseph::printJsequence()
{
JosephSequence();
}
//输出约瑟夫序列
void Joseph::JosephSequence()
{
ListNode *p,*q;
size_t j = 1;
for (size_t i=1; i <= mTotal; ++i)
{
j = 1;
p = mHead;
while (j < mStart-1)//从1数到mStart
{
p = p->next;
++j;
}
q = p->next; //q是第mStartge节点，将该节点从循环单链表中移除
p->next = q->next;
printf("%d ",q->number);
delete q;
q = nullptr;
mHead = p->next;
}
}
Joseph::~Joseph()
{
}
#endif // JOSEPH_H
测试：
#include "Joseph.h"
int main()
{
Joseph jo(6,5);
jo.printJsequence();
return 0;
}
输出：5 4 6 2 3 1 | 
楼主
标题置顶
标题高亮
