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

《数据结构实验--约瑟夫环问题.doc》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

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):线性链表存储结构的定义structJosephNode{intnumber;//编号intpassword;//密码structJosephNode*next;};（2）：数据结构类型的定义

3、typedefstructJosephNode*JosephCircle;JosephCircleInit(void);JosephCircleCountOff(JosephCirclejoseph,int&number,int&password);typedefstructJosephNode*PJoseph;三：详细设计//结构在程序设计语言中的表示；各函数的完整说明；所需函数的概要代码；函数调用关系等。：//Josep.h.structJosephNode{intnumber;//编号intpassword;//密码structJosephNode*next;};typede

4、fstructJosephNode*JosephCircle;JosephCircleInit(void);JosephCircleCountOff(JosephCirclejoseph,int&number,int&password);typedefstructJosephNode*PJoseph;//Joseph..cpp：#include"stdafx.h"#include#include"Joseph.h"JosephCircleInit(void)//返回指向表尾的指针（考虑方便删除及报数可能为1的情况）{PJosephrear=NULL,p=NULL;

5、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域指向自身，构成循环

6、链表。{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++next

7、;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;}：//main.cppintmain(intargc,char*argv[]){JosephCirclejoseph;in