约瑟夫环
问题描述：
编号为1，2，…，n的n个人按顺时针方向围坐一圈。每人持有一个密码(正整数)，一开始任选一个正整数作为报数上限值m，从第一个人开始按顺时针方向自1开始报数，报到m时停止报数。报m的人出列，将他的密码作为新的m值，从他顺时针方向的下一个人开始重新从1报数，直至所有人全部出列为止。试设计一个程序求出出列顺序。
基本要求：
利用单向循环链表存储结构模拟此过程。
下面我们将给出约瑟夫环在Microsoft Visual C++6.0中的实现步骤。
1、如下图，执行 Microsoft Visual C++6.0。
2、在 File 菜单， 点击 New。 将显示 New 对话框。
3、在 New 对话框， 点击 Projects 选项卡。 在列表中选择 Win32 Console Application。 4、输入或选择以下选项：
保持 Create new workspace 单选项被选择。 在Project Name 输入框输入Joseph。
在Location 输入框输入你存储项目的目录（可选）。 在Platforms 复选框保持Win32被选择。
5、点击 OK。
将显示 Win32 Console Application – Step 1 of 1 对话框
6、选择 A simple application. 单选项。
7、点击 Finish 按钮。
将显示 New Project Information 对话框。
8、点击 OK 按钮。
9、在 File 菜单， 点击 New。 显示 New 对话框
10、在 New 对话框， 点击 Files 选项卡。 在列表中选择 C/C++ Header File。 11、输入或选择以下选项：
确保Add to project: 复选框被选中。 在File 输入框中输入Joseph。
在Location 输入框输入你存储文件的目录（可选，不建议修改）。
12、点击OK按钮。
13、考虑到约瑟夫环中每人有自己的编号和密码，以及要求利用单向循环链表存储结构模拟此过程。结构中至少有两个数据分量以及一个指针分量。由题目要求可知，两个数据分量均可为整形。
在Joseph.h 文件中，输入以下文本： struct JosephNode {
int number;//编号 int password;//密码
struct JosephNode *next; };
typedef struct JosephNode *JosephCircle; typedef struct JosephNode *PJoseph;
14、在Joseph.h 文件中typedef struct JosephNode *JosephCircle;之后另起一行输入：
JosephCircle Init(void);
然后在ClassView选项卡中展开Globals分支，双击main函数，打开Joseph.cpp文件。 15、在 #include \"stdafx.h\"之后输入： #include #include \"Joseph.h\"16、在Joseph.cpp文件中加入函数Init的实现。具体在main函数之前输入：
JosephCircle Init(void)//返回指向表尾的指针（考虑方便删除及报数可能为1的情况） {
PJoseph rear = NULL , p = NULL; int pass = 0; int number = 0; do {
printf(\"请输入编号为%d成员的密码：(输入 0 终止)\ scanf(\"%d\
if (pass)//输入为0则不处理，do while循环将结束 {
p = new JosephNode;//分配内存 p->number = number; p->password = pass;
if (rear)//如果不是空表，将新节点插入到rear之后并修改rear为新节点。 {
p->next = rear->next; rear->next = p; rear = p; }
else//如果是空表，修改rear为新节点，将其next域指向自身，构成循环链表。 {
rear = p;
rear->next = rear; } }
} while (pass);
return rear; }
17、在ClassView选项卡中双击JosephNode（或通过Window菜单）。打开Joseph.h文件。在JosephCircle Init(void);之后输入：
JosephCircle CountOff(JosephCircle joseph , int& number , int& password);
18、在Joseph.cpp文件中添加JosephCircle CountOff(JosephCircle joseph , int& number , int& password)的实现：
JosephCircle CountOff(JosephCircle joseph , int& number , int& password) {//返回出列成员的前一个报数成员，理由同前，number存储出列成员编号， //password带入报数数以及存储出列成员密码。 PJoseph p = joseph , q = NULL; int count = 0;
if (p->next != p)//如果表中多于一个节点 {
while (count++ < password - 1)//为方便删除，计数到报数值-1。 p = p->next; q = p->next;
p->next = q->next; number = q->number; password = q->password; delete q; }
else//如果表中只有一个节点，出列的肯定为改节点表示的成员，同时表空。 {
number = p->number; password = p->password; delete p; p = NULL; }
return p; }
19、在main函数中行return 0; 之前输入： JosephCircle joseph; int number, pass = 20;
printf(\"请输入初始密码：\"); scanf(\"%d\ joseph = Init(); while (joseph) {
joseph = CountOff(joseph,number,pass); printf(\"%d\\n\ }
20、在 Build 菜单， 点击 Execute Joseph.exe或按Ctrl + F5执行。 如果出现Microsoft Visual C++对话框：
点击“是(Y)” 按钮。程序执行初始界面如下：
21、运行结果如下图：
22、约瑟夫环实验完成，撰写实验报告。
