数据结构上机实验报告.docx

《数据结构上机实验报告.docx》由会员分享，可在线阅读，更多相关《数据结构上机实验报告.docx（11页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、数据结构上机实验报告 实习报告 题 目 : 实现一个约瑟夫环程序 班级：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，

2、4，7，2，1，3，5）。 二、概要设计 1单向循环链表的抽象数据类型定义为： ADT List 数据对象：D=ai | ai正整数，I=1，2，.，n,n0数据关系：R1= |，ai-1，aiD,I=1，2，.，n基本操作： Init List(&L) 操作结果：构造一个空的线性表L。 List Insert(&L,i,e) 初始条件：线性表L已存在，1iList Length(L)+1. 操作结果：在L中第i个位置之前插入新的数据元素e，L长度加1。List Delete(&L,i,&e) 初始条件：线性表L存在非空，1iList Length(L).操作结果：删除L的第i个元素，并用e返

3、回其值，L长度减1。 2 程序包含四个模块： 1）主程序模块： void main( ) 初始化； for（; ;） while（吩咐=起先） 接受吩咐； 处理吩咐； for（; ;） 2）有序表单元模块实现有序表的抽象数据类型； 3）节点结构单元模块定义有序表的节点结构； 4）数据输入分析模块推断输入数据正确有效； 各模块之间的调用关系如下： 主程序模块 有序表结构模块 节点结构单元模块 数据输入分析模块 三、具体设计 1、结点类型，指针类型 TypedefstructLNode int code,date;/code 为人所在位置 date为人持有的密码 struct LNode *nex

4、t; ; / 结点类型，指针类型 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则干脆输出结果，不循环

5、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 a4;/数组初始化 if(!z)/输入推断，确定位数字或限制字符且位置和密码不为零 for(y=0;y c=getch(); i

6、f(c=48&c ay=c; putch(c); else y-; if(c=r)/确定输入为限制字符 即回车或者删除 break; else if(c=8) ay=n; y-; continue; k=atoi(a);/确定最终输入数字的值 printf(n); z=k; if(z=0) printf(ERROR! The number couldnt be 0! n);/ 输入为零，重新输入 return(k);/数值的返回 5、函数的调用关系图反映程序层次结构 Maininput 四、调试分析 1、早期程序只写了约瑟夫环的实现部分，没有对输入数据进行筛选，调试的时候会常常出错。比如是输入

7、字母，或者输入0，大于32767溢出； 2、早期的循环过程中没有进行优化，导致循环次数过多，奢侈时间； 3、为了输出时美观，分别在input和main函数主体内做了两次，输入非零的推断，奢侈了资源； 4、算法的时空分析 为了限制在输入过程中不会上溢，只在输入中限定为四个不全为零的数字，但是做的是dowhile循环，困难度为o（1）; 当n大于1时： 在数据输入中，链表的创建是for循环，时间困难度为o（n-1） 在约瑟夫环实现程序中，为for循环。时间困难度为o（m%n -1） 当n=1时，困难度为o（1）。 五、用户手册 用户依据提示，先输入起始密码m，然后输入人数n，再依据人数，分别输入每

8、个人的密码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个人的

9、密码依次为：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/最终显示结果、清屏函数头文件 数据结构上机试验报告 数据结构上机试验报告 数据结构上机试验报告 链表 数据结构上机作业试验报告(六) 数据结构上机作业试验报告(五)举荐 数据结构试验报告 数据结构试验报告 数据结构试验报告 数据结构试验报告 数据结构试验报告 本文来源：网络收集与整理，如有侵权，请联系作者删除，谢谢！第11页 共11页第 11 页 共 11 页第 11 页 共 11 页第 11 页 共 11 页第 11 页 共 11 页第 11 页 共 11 页第 11 页 共 11 页第 11 页 共 11 页第 11 页 共 11 页第 11 页 共 11 页第 11 页 共 11 页