数据结构实验--约瑟夫环问题(共5页).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;三：详细设计 //结构在程序设计语言中的表示；各函数的完整说明；所需函数的概要代码；函数调用关系等。

//Josep.h.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 "stdafx.h"#include #include "Joseph.h"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;}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)//为方便删除，计数到报数值-1p = 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;}：//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("%d\n",number);} return 0;}四、调试分析 //调试过程中发现的问题以及解决方法；对于结构的调整以及原因；设计调试中所获得的经验等1）：通过对本实验的算法调试和分析，实现了实验要求；（2）本实验分为三个程序段，即Joseph.h头文件、Joseph.cpp和main.cpp执行部分五、测试结果 //在需求分析中给定的输入数据输入；以及所得到的实际结果（要求有运行截图）等输入初始密码2，各成员密码分别为：2、7、1、8、、2、8、5 ；结束条件：输入0。

运行结果如下所示：六、附录源程序清单等运行环境：Microsoft Visual Studio 2010.Joseph.h {元素结点的定义部分}；Joseph.cpp{链表的实现部分}；main.cpp {主程序段}；//报告保存为Word2003格式；//件名为：1-张阗阗-线性表及其应用.doc专心---专注---专业。