数据结构上机实验报告_结构力学上机实验报告
数据结构上机实验报告由刀豆文库小编整理，希望给你工作、学习、生活带来方便，猜你可能喜欢“结构力学上机实验报告”。
实习报告
题 目 : 实现一个约瑟夫环程序
班级：031021姓名：王帅学号：03102076
一、需求分析
1． 本演示程序中，利用单向循环链表存储结构存储约瑟夫环数据（即n个人的编号和密码）。
2． 演示程序以用户和计算机的对话方式执行，即在计算机终端上显示“提示信息”之后，由用户在键盘上输入演示程序中需要输入的数据，运算结果显示在其后。
3． 程序执行的命令包括：
1)构造单向循环链表；2）进行数值的输入，并作判断分析；3）约瑟夫算法的实现与结果输出；4）结束。
4． 测试数据
m 的初值为20；n=7，7个人的密码依次为：3，1，7，2，4，8，4，（正确的出列顺序为6，1，4，7，2，1，3，5）。
二、概要设计
1．单向循环链表的抽象数据类型定义为：
ADT List｛
数据对象：D=｛ai | ai↔正整数，I=1，2，......，n,n≥0｝数据关系：R1=｛ |，ai-1，ai↔D,I=1，2，......，n｝基本操作：
Init List(&L)
操作结果：构造一个空的线性表L。
List Insert(&L,i,e)
初始条件：线性表L已存在，1≤i≤List Length(L)+1.操作结果：在L中第i个位置之前插入新的数据元素e，L长度加1。List Delete(&L,i,&e)
初始条件：线性表L存在非空，1≤i≤List Length(L).操作结果：删除L的第i个元素，并用e返回其值，L长度减1。
2． 程序包含四个模块：
1）主程序模块：
void main()
{
初始化；
for（;;）
{}
while（命令=开始）
{
接受命令；
处理命令；
}
for（;;）
{ }
}
2）有序表单元模块——实现有序表的抽象数据类型；
3）节点结构单元模块——定义有序表的节点结构；
4）数据输入分析模块——判断输入数据正确有效；
各模块之间的调用关系如下：
主程序模块
↓
有序表结构模块
↓
节点结构单元模块
↓
数据输入分析模块
三、详细设计
1、结点类型，指针类型
TypedefstructLNode{
int code,date;//code 为人所在位置 date为人持有的密码 struct LNode *next;
};// 结点类型，指针类型
2、构造单向循环链表
struct LNode *p,*head,*q;//定义头节点，和指针
for(i=2;i
{
struct LNode *s=(struct LNode *)malloc(sizeof(struct LNode));//分配
新结点空间
s->code=i;
input(s->date);
p->next=s;
p=p->next;
}
p->next=head;//根据输入的人数，进行单项循环链表的创建，p指向最后一个结点，并与头节点链接，形成单项循环链表
3、约瑟夫环的程序实现部分
while(n!=1)//判断输入人数，如为1则直接输出结果，不循环
{
for(i=1，m=m%n;i
的前驱
{
p=p->next;
}
q=p->next;//找到要删除节点
p->next=q->next;//找到要删除节点的后继，并连接新环m=q->date;//找到下一个密码
printf(“%d”,q->code);
free(q);//释放已删除节点空间
n--;//链表长度减一
}
printf(“%d”,p->code);//约瑟夫环的结果输出
4、其他函数代码
数值的输入限制
int input()
{
int y,k,z=0;
char c;//元素类型
char a[4];//数组初始化
if(!z)//输入判断，确定位数字或控制字符且位置和密码不为零 {
for(y=0;y
{
c=getch();
if(c>=48&&c
{a[y]=c;
putch(c);
}
else
{
y--;
if(c=='r')//确定输入为控制字符 即回车或者删除
break;
else
if(c==8)
{a[y]='n';
y--;}
continue;
}
}
k=atoi(a);//确定最终输入数字的值
printf(“n”);
z=k;
if(z==0)
printf(“ERROR!The number couldn't be 0!n”);// 输入为零，重新输入 }
return(k);//数值的返回
5、函数的调用关系图反映程序层次结构
Main→input
四、调试分析
1、早期程序只写了约瑟夫环的实现部分，没有对输入数据进行筛选，调试的时候会经常出错。比如是输入字母，或者输入0，大于32767溢出；
2、早期的循环过程中没有进行优化，导致循环次数过多，浪费时间；
3、为了输出时美观，分别在input和main函数主体内做了两次，输入非零的判断，浪费了资源；
4、算法的时空分析
为了限制在输入过程中不会上溢，只在输入中限定为四个不全为零的数字，但是做的是do……while循环，复杂度为o（1）;
当n大于1时：
在数据输入中，链表的创建是for循环，时间复杂度为o（n-1）
在约瑟夫环实现程序中，为for循环。时间复杂度为o（m%n-1）
当n=1时，复杂度为o（1）。
五、用户手册
用户根据提示，先输入起始密码m，然后输入人数n，再根据人数，分别输入每个人的密码date，数值均不能为0，否则会提示重新输入，输入为字母则自动丢弃，输入错误可用删除键进行修改，输入完成后按回车键确定本次输入完毕（若输入数字大于9999，则第五位自动转换为下一个数字的起始位，依此类推）。
当n个数字全部输入完毕，则自动显示结果，按任意键则退出本程序。
六、测试结果
第一组：m 的初值为20；n=7，7个人的密码依次为：3，1，7，2，4，8，4，出列顺序为6，1，4，7，2，1，3，5。
第二组： m 的初值为30；n=8，7个人的密码依次为：5，1，6，9，4，7，2，3，出列顺序为6，5，2，3，7，1，4，8。
第三组 : m 的初值为15；n=6，7个人的密码依次为：5，3，4，7，6，9，出列顺序为3，1，2，6，4，5。
七、附录
源程序头文件名清单：
#include “malloc.h”//内存空间分配头文件
#include “stdio.h”//输入输出函数头文件
#include “stdlib.h”//input函数中字符串转短整形函数的头文件 #include “conio.h”//最后显示结果、清屏函数头文件
