数据结构上机实验报告.docx
数据结构上机实验报告 实习报告 题 目 : 实现一个约瑟夫环程序 班级：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,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返回其值，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 a4;/数组初始化 if(!z)/输入推断，确定位数字或限制字符且位置和密码不为零 for(y=0;y c=getch(); if(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 couldn't be 0! n");/ 输入为零，重新输入 return(k);/数值的返回 5、函数的调用关系图反映程序层次结构 Maininput 四、调试分析 1、早期程序只写了约瑟夫环的实现部分，没有对输入数据进行筛选，调试的时候会常常出错。比如是输入字母，或者输入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，再依据人数，分别输入每个人的密码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"/最终显示结果、清屏函数头文件 数据结构上机试验报告 数据结构上机试验报告 数据结构上机试验报告 链表 数据结构上机作业试验报告(六) 数据结构上机作业试验报告(五)举荐 数据结构试验报告 数据结构试验报告 数据结构试验报告 数据结构试验报告 数据结构试验报告 本文来源：网络收集与整理，如有侵权，请联系作者删除，谢谢！第11页 共11页第 11 页 共 11 页第 11 页 共 11 页第 11 页 共 11 页第 11 页 共 11 页第 11 页 共 11 页第 11 页 共 11 页第 11 页 共 11 页第 11 页 共 11 页第 11 页 共 11 页第 11 页 共 11 页
