数据结构报告约瑟夫环由刀豆文库小编整理，希望给你工作、学习、生活带来方便，猜你可能喜欢“数据结构实验约瑟夫环”。
实习报告
题目:约瑟夫环
班级：08052712学号: 08052211姓名: 葛俊峰
一、需求分析
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.线性表的抽象数据类型为：
ADT List{
数据对象：D={ai|ai∈ElemSet,i=1,2,„，n,n≥0}
数据关系：R1={|ai-1,ai∈D,i=2,3,„,n}
基本操作：
InitList(&L)
操作结果：构造一个空的线性表L。
}ADT List
2.本程序包括三个模块:
1）主程序模块：
void main（）{
初始化；
输入数据；
函数调用；
}
2）构造链表并输入每个人信息的模块-----实现线性表的抽象数据类型；
3）运行模块-----模拟约瑟夫环依次出列；
各模块之间调用关系如下：
主程序模块
↓
构造链表并输入每个人信息的模块
↓
运行模块
三、详细设计
1.结点类型和指针类型
typedef struct Node{
int num;
int paword;
struct Node *next;
}LNode,*LinkList;//结点类型,指针类型
Status MakeNode（LinkList &p，Elem Type e）
{
//分配由p指向的数据元素为e、后继为“空”的特点，并返回TRUE，//若分配失败，则返回FALSE
P=(LinkType)malloc（sizeof（NodeType））；
If（！p）return FALSE；
p->data=e；p->next=null；return TRUE；
}
viod Free Node（Link Type &p）
{
//释放p所指结点
}
2.主函数和其他函数
int main()
{
//主函数
LinkList L = NULL;
LinkList s ,r;
int n,i,j,m;//初始化
printf(“请输入人数nn”);
scanf(“%d”,&n);
printf(“请输入mn”);
scanf(“%d”,&m);
printf(“请依次输入每个人的密码n”);//输入数据
CreatList(L,s,r,n);//创建链表run(L,n,m);//模拟约瑟夫环并输出
return 0;
}//main
void CreatList(LinkList &L,LinkList &s,LinkList &r,int n)
{
//创建链表
int i=1;
s=(LNode*)malloc(sizeof(LNode));//分配空间
scanf(“%d”,&s->paword);//输入密码
s->num = i;//序号为i
if(L==NULL)
L=s;
else
r->next=s;
r=s;//为下次连接做准备
for(i=2;i
{
s=(LNode*)malloc(sizeof(LNode));//分配空间
scanf(“%d”,&s->paword);
s->num = i;
r->next=s;//连接到下个结点
r=s;//为下次连接做准备
}
r->next = L;//闭合L = r;
} // void CreatList
void run(LinkList &L,int n,int m)
{
//模拟约瑟夫环并输出
LinkList s,r;
int i,j;
for(i = 0;i
{
for(j = 1;j
L = L->next;//报数
s = L->next;
r = s->next;
printf(“%dn”,s->num);//输出序号
m = s->paword;
L->next = r;
free(s);//删除结点
}
}//run
3.函数的调用关系图反映了演示程序的层次结构:
main
↓↓
CreatListrun
↓↓
Make NodeFree Node
四、调试分析
1.刚开始由于使用头结点,使得程序不符合要求。
2.在写程序时忽略了一些变量参数的标识“&”,使调试程序费时不少。今后应重视确定参数的变量和赋值属性的区分和标识。
3.本程序模块划分比较简单且容易看懂，但头指针赋空不太合理。
4.本实习作业采用数据抽象的设计方法，将程序划分为3个层次，使得设计时思路清晰，实现调试顺利
五、用户手册
1.本程序运行环境为DOS操作系统，执行文件为约瑟夫环.exe。
2． 进入演示程序后出现提示信息：
“请输入人数n”
输入后，出现提示信息：
“请输入m”
输入后，出现提示信息：
“请依次输入每个人的密码”
输入后，显示相应的结果。
《数据结构》课程设计报告课程名称：课程设计题目：姓名： 院系： 专业： 年级： 学号： 指导教师： 《数据结构》课程设计joseph环计算机学院2011年12月18日 目 录1 课程设计的目的…………......
数据结构上机实验报告02090401 12 雒文杰 题目：约瑟夫环问题 一．问题描述设有n个人围做一圈，现从某个人开始报数，数到m的人出列，接着从出列的下一个人开始重新报数，数到m的人又出......
数据结构实验二求解约瑟夫问题问题描述：使用代表头节点的循环单链表解决此问题。设有n个人围坐在一张圆桌周围，现从某个人开始从1报数，数到m的人离开。接着从出列的下一个人开......
关于理解约瑟夫环应用题代码题目：有二十九个女生（分别用1－29号来称呼）围成一圈玩报数游戏，规则是这样的：从1开始数数，当数到3的这个人就退出游戏，而她后面的人接着从1数。。。如此一......
《数据结构》 课程设计报告课程名称： 课程设计题目：姓名：院系： 专业： 年级： 学号： 指导教师： 《数据结构》课程设计joseph环 计算机学院 计算机科学与技术大二 王立波2012年5月17日......
