数据结构实验--约瑟夫环问题(共5页)

1、线性表及其应用班级：软件101  姓名：xxx  学号：xxxxxxx 完成日期：2011-11-18题目：编制一个求解约瑟夫环问题的程序一、需求分析/该题目的功能等需求、测试数据以及预期的输出结果等。问题描述：编号为1，2，n的n个人按顺时针方向围坐一圈。每人持有一个密码(正整数)，一开始任选一个正整数作为报数上限值m，从第一个人开始按顺时针方向自1开始报数，报到m时停止报数。报m的人出列，将他的密码作为新的m值，从他顺时针方向的下一个人开始重新从1报数，直至所有人全部出列为止。试设计一个程序求出出列顺序。（1）：在本实验中，要求利用单向循环链表存储结构来完成，以便有效地

2、掌握线性表相关知识及其应用。（2）：在程序运行后，首先指定一个初始报数的上限值m=20，然后输入各人的密码，假设n<=10；（3）：编译执行后得到结果并进行检查核对。（4）：测试数据为：初始密码2，各成员密码分别为：2、7、1、8、2、8、5 ；结束条件：输入0二、概要设计/数据结构的大概设计；程序模块的设计以及大概算法等。为了实现上述程序功能，应以循环链表存储结构来表示；需要抽象数据类型有：(1):线性链表存储结构的定义struct JosephNodeint number;/编号int password;/密码struct JosephNode *next;（2）：数据结构类型的定义

3、typedef struct JosephNode *JosephCircle;JosephCircle Init(void);JosephCircle CountOff(JosephCircle joseph , int& number , int& password);typedef struct JosephNode *PJoseph;三：详细设计/结构在程序设计语言中的表示；各函数的完整说明；所需函数的概要代码；函数调用关系等。：/Josep.h.struct JosephNodeint number;/编号int password;/密码struct JosephNo

4、de *next;typedef struct JosephNode *JosephCircle;JosephCircle Init(void);JosephCircle CountOff(JosephCircle joseph , int& number , int& password);typedef struct JosephNode *PJoseph;/Joseph.cpp：#include "stdafx.h"#include <stdio.h>#include "Joseph.h"JosephCircle Init

5、(void)/返回指向表尾的指针（考虑方便删除及报数可能为1的情况）PJoseph rear = NULL , p = NULL;int pass = 0;int number = 0;doprintf("请输入编号为%d成员的密码：(输入 0 终止)",+number);scanf("%d",&pass);if (pass)/输入为0则不处理，do while循环将结束p = new JosephNode;/分配内存p->number = number;p->password = pass;if (rear)/如果不是空表，将新节点

6、插入到rear之后并修改rear为新节点。p->next = rear->next;rear->next = p;rear = p;else/如果是空表，修改rear为新节点，将其next域指向自身，构成循环链表。rear = p;rear->next = rear; while (pass);return rear;JosephCircle CountOff(JosephCircle joseph , int& number , int& password)/返回出列成员的前一个报数成员，理由同前，number存储出列成员编号，/password带入报

7、数数以及存储出列成员密码。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->nu

8、mber;password = p->password;delete p;p = NULL;return p;：/main.cppint main(int argc, char* argv)JosephCircle joseph;int number, pass = 20;printf("请输入初始密码：");scanf("%d",&pass);joseph = Init();while (joseph)joseph = CountOff(joseph,number,pass);printf("%dn",number);return 0;四、调试分析/调试过程中发现的问题以及解决方法；对于结构的调整以及原因；设计调试中所获得的经验等。（1）：通过对本实验的算法调试和分析，实现了实验要求；（2）本实验分为三个程序段，即Joseph.h头文件、Joseph.cpp和main.cpp执行部分。五、测试结果/在需求分析中给定的输入数据输入；以及所得到的实际结果（要求有运行截图）等。输入初始密码2，各成员密码分别为：2、7、1、8、2、8、5 ；结束条件：输入0。运行结果如下所示：六、附录源程序清