数据结构约瑟夫环问题.docx

数据结构实验报告

完美WORD格式

题目：约瑟夫环问题

一、 设计内容

［问题描述］

为瑟夫环问题的一种描述是：编号为1，2，3，…，n的n个人按顺时针方向引坐一圈，每人手持一个密码（正整数）。一开始任选一个整数作为报数上限值，从第一人开始顺时针自1开始顺序报数，报到m时停止报数。报m的人出，将它的密码作为新的m值，从他在顺时针方向上的下一个人开始重新从1报数，如此下去直到所有人全部由为止。试设计程序实现之。

［基本要求］

用循环等表存储结构模拟此过程，按照出的顺序打印各人的编号。

［实验提示］

程序运后首先要求用户指定初始报数上限值。然后读取各人的密码。设n=30。程序执后，要求用户在计算机终端上显示“提示信息后，用键盘输入“提示信息中规定的命，以“回车符为结束标志。相应的输入数据和运算结果显示在其后。

二、 设计目的

达到熟练掌握C++语言的基本知识和技能；

能够用所学的基本知识和技能，解决简单的面向对象程序设计问题。

3.把课本上的知识应用到实际生活中，达到学以致用的目的。

三、系统分析与设计（确定程度功能模块）

1、为实现上述程序的功能，应以有序等表表示集合。

基本操作：

InitList(L)

操作结果：构造一个空的有序表L。

DestroyList(L)

初始条件：有序表L已存在。

操作结果：销毁有序表L。

ListEmpty(L)

初始条件：有序表L已存在。

操作结果：L为空表，则返回TRUE，否则返回FALSE。

ListLength(L)

初始条件：有序表L已存在。

操作结果：返回L中数据元素个数。

GetElem(L,i)

初始条件：有序表L已存在，并且1WiWListLength(L)。

操作结果：返回L中第i个数据元素。

LocatePos(L,e)

初始条件：有序表L已存在，e和有序表中元素同类型的值。

操作结果：L中存在和e相同的元素，则返回位置；否则返回0°

InsertElem(L,e)

初始条件：有序表L已存在

操作结果：在L中，按有序关系插入值和e相同的数据元素。

DeleteElem(L,i)

初始条件：有序表L已存在。

操作结果：删除L中第i个数据元素。

ListTraverse(L,visit())

初始条件：有序表L已存在。

操作结果：依次对L的每个数据元素调用函数visit()。一旦visit()失败，则操作失败。

}ADTOrderedList

2、本程序包含两个模块：

主程序模块：

voidmain(){

初始化；

调用函数(接受命，处命) }

有序表单元模块——实现有序表的抽象数据类型。

输出函数模块一一有序表的输出。

四、源程序代码

#includestdio.h

#includemalloc.h

//1.元素类型，结点类型和布针类型

//定义结构体，

//定义结构体，

//num用来存储人的序号，pwd用来存储人的

//定义结点

//参数n传递人数，

{

intnum,pwd;

密码

structLNode*next;

};

structLNode*head,*p,*pt;

//2、 创建循环链表函数

intcreatLinkList(intn)

inti;

head=(structLNode*)malloc(sizeof(structLNode));

//创建一个带头结点的链表

if(!head){return0;} //创建成功，返回0

p=head;

for(i=1;in;i++)

{

pt=(structLNode*)malloc(sizeof(structLNode));

if(!pt){return0;}p-next=pt;

p=pt;

p-next=head; //构成循环等表

pt=head;

return0;

}

//3.创建输入密码函数

intenterPwd(intn) //参数n传递人数

{

inti,j;

printf(\n请输入密码：\n);

for(i=1;i=n;i++){

scanf(%d,j);

pt-num=i; //num存储人的序号

pt-pwd=j; //pwd存储人的密码pt=pt-next;

}

pt=p;

returnj;

}

//4、创建输出函数

//参数m

//参数m、n传递报数上限值和人数

//用一个for循环搜循环等表

{

inti,a;

for(i=1;i=n;i++)

{

for(a=1;am;a++) //删除结点

{

pt=pt-next;

p=pt-next;

m=p-pwd;

printf(%d,p-num); //输出人的序号

pt-next=p-next;

free(p); //释放动态申请的结点