约瑟夫环-数据结构报告.源代码(源码) (2).docVIP

实习报告

题目:约瑟夫环

班级姓名:傅宁捷学号:完成日期:2010.1.4

一、需求分析

1.本演示程序中,编号为1,2,…,n的n个人按顺时针方向围坐一圈,

每个人持有一个密码,正整数,。一开始任选一个正整数作为报数上限值

m,从第一个人开始按顺时针方向自1开始顺序报数,报到m时停止报

数。报m的人出列,如此下去,直到所有人全部出列为止。

2.演示程序以用户和计算机的对话方式执行,即在计算机终端上显示“提示

信息”之后,由用户在键盘上输入相应数据,即总人数,m的值,每个人

所持的密码,,运算结果显示在其后。

3.程序执行的命令包括,

,1,构造链表,,2,输入数据,,3,执行报数,储存出列人的序号,删

除出列人的信息以及把出列人的密码赋给m,,4,结束。

4.测试数据,

m的初始值为20,n,7,7个人的密码依次为,3,1,7,2,4,8,4,

首先m值为6,则这正确的出列顺序为6,1,4,7,2,3,5。二、概要设计

为了实现上述操作,应以单向循环链表为存储结构。为此,需要1个抽象数据类型,线性表。

1.线性表的抽象数据类型为,

ADTList{

数据对象,D={ai|ai?ElemSet,i=1,2,…,n,n?0}

数据关系,R1={ai-1,ai|ai-1,ai?D,i=2,3,…,n}

基本操作,

InitList(L)

操作结果,构造一个空的线性表L。

}ADTList

2.本程序包括三个模块:

1,主程序模块,

voidmain,,{

初始化,

输入数据,

函数调用,

}

2,构造链表并输入每个人信息的模块-----实现线性表的抽象数据类型,

3,运行模块-----模拟约瑟夫环依次出列,

各模块之间调用关系如下,

主程序模块

?

构造链表并输入每个人信息的模块

?

运行模块

三、详细设计

1.结点类型和指针类型

typedefstructNode{

intnum;

intpassword;

structNode*next;

}LNode,*LinkList;//结点类型,指针类型

StatusMakeNode,LinkListp,ElemTypee,

{

//分配由p指向的数据元素为e、后继为“空”的特点,并返回TRUE,

//若分配失败,则返回FALSE

P=(LinkType)malloc,sizeof,NodeType,,,

If,，p,returnFALSE,

p-data=e,p-next=null,returnTRUE,

}

viodFreeNode,LinkTypep,

{

//释放p所指结点

}

2.主函数和其他函数

intmain()

{

//主函数

LinkListL=NULL;

LinkLists,r;

intn,i,j,m;//初始化

printf(请输入人数n\n);

scanf(%d,n);

printf(请输入m\n);

scanf(%d,m);

printf(请依次输入每个人的密码\n);//输入数据

CreatList(L,s,r,n);//创建链表

run(L,n,m);//模拟约瑟夫环并输出

return0;

}//main

voidCreatList(LinkListL,LinkLists,LinkListr,intn)

{

//创建链表

inti=1;

s=(LNode*)malloc(sizeof(LNode));//分配空间

scanf(%d,s-password);//输入密码

s-num=i;//序号为i

if(L==NULL)

L=s;

else

r-next=s;

r=s;//为下次连接做准备

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

{

s=(LNode*)malloc(sizeof(LNode));//分配空间

scanf(%d,s-password);

s-num=i;

r-next=s;//连接到下个结点

r=s;//为下次连接做准备

}

r-next=L;//闭合

L=r;

}//voidCreatList

voidrun(LinkListL,intn,intm)

{

//模拟约瑟夫环并输出

LinkLists,r;

inti,j;

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

{

for(j=1;jm;j++)

L=L-next;