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

线性表及其应用班级：软件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):线性链表存储结构的定义structJosephNode{intnumber;//编号intpassword;//密码structJosephNode*next;};（2）：数据结构类型的定义typedefstructJosephNode*JosephCircle;JosephCircleInit(void);JosephCircleCountOff(JosephCirclejoseph,int&number,int&password);typedefstructJosephNode*PJoseph;三：详细设计//结构在程序设计语言中的表示；各函数的完整说明；所需函数的概要代码；函数调用关系等。○1：//Josep.h.structJosephNode{intnumber;//编号intpassword;//密码structJosephNode*next;};typedefstructJosephNode*JosephCircle;JosephCircleInit(void);JosephCircleCountOff(JosephCirclejoseph,int&number,int&password);typedefstructJosephNode*PJoseph;○2//Joseph..cpp：#includestdafx.h#includestdio.h#includeJoseph.hJosephCircleInit(void)//返回指向表尾的指针（考虑方便删除及报数可能为1的情况）{PJosephrear=NULL,p=NULL;intpass=0;intnumber=0;do{printf(请输入编号为%d成员的密码：(输入0终止),++number);scanf(%d,&pass);if(pass)//输入为0则不处理，dowhile循环将结束{p=newJosephNode;//分配内存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);returnrear;}JosephCircleCountOff(JosephCirclejoseph,int&number,int&password){//返回出列成员的前一个报数成员，理由同前，number存储出列成员编号，//password带入报数数以及存储出列成员密码。PJosephp=joseph,q=NULL;intcount=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;deleteq;}else//如果表中只有一个节点，出列的肯定为改节点表示的成员，同时表空。{number=p-number;password=p-password;deletep;p=NULL;}returnp;}○3：//main.cppintmain(intargc,char*argv[]){JosephCirclejoseph;intnumber,pass=20;printf(请输入初始密码：);scanf(%d,&pass);joseph=Init();while(joseph){joseph=CountOff(joseph,number,pass);printf(%d\n,number);}return0;}四、调试分析//调试过程中发现的问题以及解决方法；对于结构的调整以及原因；设计调试中所获得的经验等。（1）：通过对本实验的算法调试和分析，实现了实验要求；（2）本实验分为三个程序段，即Joseph.h头文件、Joseph.cpp和main.cpp执行部分。五、测试结果//在需求分析中给定的输入数据输入；以及所得到的实际结果（要求有运行截图）等。输入初始密码2，各成员密码分别为：2、7、1、8、、2、8、5；结束条件：输入0。运行结果如下所示：六、附录源程序清单等。运行环境：MicrosoftVisualStudio2010.Joseph.h{元素结点的定义部分}；Joseph.cpp{链表的实现部分}；main.cpp{主程序段}；//报告保存为Word2003格式；//件名为：060806110001-张阗阗-线性表及其应用.doc