数据结构实验--约瑟夫环问题.doc

线性表及其应用
班级：软件101  姓名：xxx  学号：xxxxxxx 完成日期：2011-11-18
题目：编制一个求解约瑟夫环问题的程序
一、需求分析
//该题目的功能等需求、测试数据以及预期的输出结果等。
问题描述：编号为1，2，…，n的n个人按顺时针方向围坐一圈。每人持有一个密码(正整数)，一开始任选一个正整数作为报数上限值m，从第一个人开始按顺时针方向自1开始报数，报到m时停止报数。报m的人出列，将他的密码作为新的m值，从他顺时针方向的下一个人开始重新从1报数，直至所有人全部出列为止。试设计一个程序求出出列顺序。
（1）：在本实验中，要求利用单向循环链表存储结构来完成，以便有效地掌握线性表相关知识及其应用。
（2）：在程序运行后，首先指定一个初始报数的上限值m=20，然后输入各人的密码，假设n<=10；
（3）：编译执行后得到结果并进行检查核对。
（4）：测试数据为：初始密码2，各成员密码分别为：2、7、1、8、、2、8、5 ；结束条件：输入0
二、概要设计
//数据结构的大概设计；程序模块的设计以及大概算法等。
为了实现上述程序功能，应以循环链表存储结构来表示；需要抽象数据类型有：
(1):线性链表存储结构的定义
struct JosephNode{
int number;//编号
int password;//密码
struct JosephNode *next;
};
（2）：数据结构类型的定义
typedef struct JosephNode *JosephCircle;
JosephCircle Init(void);
JosephCircle CountOff(JosephCircle joseph , int& number , int& password);
typedef struct JosephNode *PJoseph;
三：详细设计
//结构在程序设计语言中的表示；各函数的完整说明；所需函数的概要代码；函数调用关系等。
：//.
struct JosephNode
{
int number;//编号
int password;//密码
struct JosephNode *next;
};
typedef struct JosephNode *JosephCircle;
JosephCircle Init(void);
JosephCircle CountOff(JosephCircle joseph , int& number , int& password);
typedef struct JosephNode *PJoseph;
//Joseph..cpp：
#include ""
#include <>
#include ""
JosephCircle Init(void)//返回指向表尾的指针（考虑方便删除及报数可能为1的情况）
{
PJoseph rear = NULL , p = NULL;
int pass = 0;
int number = 0;
do
{
printf("请输入编号为%d成员的密码：