约瑟夫环

约瑟夫环
问题描述：
编号为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 终止)",++number);
scanf("%d",&pass);
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",&pass);
joseph = Init();
while (joseph)
{
joseph = CountOff(joseph,number,pass);
printf("%d\n",number);
}
20、在 Build 菜单， 点击 Execute Joseph.exe或按Ctrl + F5执行。
如果出现Microsoft Visual C++对话框：

点击“是(Y)” 按钮。程序执行初始界面如下：
21、运行结果如下图：

22、约瑟夫环实验完成，撰写实验报告。