数据结构约瑟夫环问题

《数据结构约瑟夫环问题》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、数据结构实验报告题目：约瑟夫环问题一．设计内容[问题描述]约瑟夫环问题的一种描述是：编号为1，2，3，…，n的n个人按顺时针方向围坐一圈，每人手持一个密码（正整数）。一开始任选一个整数作为报数上限值，从第一人开始顺时针自1开始顺序报数，报到m时停止报数。报m的人出列，将它的密码作为新的m值，从他在顺时针方向上的下一个人开始重新从1报数，如此下去直到所有人全部出列为止。试设计程序实现之。[基本要求]利用循环链表存储结构模拟此过程，按照出列的顺序打印各人的编号。[实验提示]程序运行后首先要求用户指定

2、初始报数上限值。然后读取各人的密码。设n<=30。程序执行后，要求用户在计算机终端上显示“提示信息”后，用键盘输入“提示信息”中规定的命令，以“回车符”为结束标志。相应的输入数据和运算结果显示在其后。二、设计目的1.达到熟练掌握C++语言的基本知识和技能；2.能够利用所学的基本知识和技能，解决简单的面向对象程序设计问题。3.把课本上的知识应用到实际生活中，达到学以致用的目的。三、系统分析与设计（确定程序功能模块）1、为实现上述程序的功能，应以有序链表表示集合。基本操作：InitList(&L)操

3、作结果：构造一个空的有序表L。DestroyList(&L)初始条件：有序表L已存在。操作结果：销毁有序表L。ListEmpty(L)初始条件：有序表L已存在。操作结果：若L为空表，则返回TRUE，否则返回FALSE。ListLength(L)初始条件：有序表L已存在。操作结果：返回L中数据元素个数。GetElem(L,i)初始条件：有序表L已存在，并且1≤i≤ListLength(L)。操作结果：返回L中第i个数据元素。LocatePos(L,e)初始条件：有序表L已存在，e和有序表中元素同类

4、型的值。操作结果：若L中存在和e相同的元素，则返回位置；否则返回0。InsertElem(&L,e)初始条件：有序表L已存在操作结果：在L中，按有序关系插入值和e相同的数据元素。DeleteElem(&L,i)初始条件：有序表L已存在。操作结果：删除L中第i个数据元素。ListTraverse(L,visit())初始条件：有序表L已存在。操作结果：依次对L的每个数据元素调用函数visit()。一旦visit()失败，则操作失败。}ADTOrderedList2、本程序包含两个模块：（1）主程序

5、模块：voidmain(){初始化；调用函数（接受命令，处理命令）}（2）有序表单元模块——实现有序表的抽象数据类型。（3）输出函数模块——有序表的输出。四、源程序代码#include"stdio.h"#include"malloc.h"//1.元素类型，结点类型和指针类型typedefstructLNode//定义结构体，{intnum,pwd;//num用来存储人的序号，pwd用来存储人的密码structLNode*next;};structLNode*head,*p,*pt;//定义结点/

6、/2、创建循环链表函数intcreatLinkList(intn)//参数n传递人数，{inti;head=(structLNode*)malloc(sizeof(structLNode));//创建一个带头结点的链表if(!head){return0;}//创建不成功，返回0p=head;for(i=1;inext=pt;p=pt;}p->next=

7、head;//构成循环链表pt=head;return0;}//3.创建输入密码函数intenterPwd(intn)//参数n传递人数{inti,j;printf("请输入密码:");for(i=1;i<=n;i++){scanf("%d",&j);pt->num=i;//num存储人的序号pt->pwd=j;//pwd存储人的密码pt=pt->next;}pt=p;returnj;}//4、创建输出函数intoutList(intm,intn)//参数m、n传递报数上限值和人数{in

8、ti,a;for(i=1;i<=n;i++)//用一个for循环搜索循环链表{for(a=1;anext;}p=pt->next;m=p->pwd;printf("%d",p->num);//输出人的序号pt->next=p->next;free(p);//释放动态申请的结点空间}return0;}//主函数voidmain(){intm,n;//m为报数上限值，n为人数printf("参数m、n传递报数上限值和人数;");printf("请