2022年约瑟夫环 2.pdf

实习报告题 目:实现一个约瑟夫环程序班级：05 计（1）姓名：学号：完成日期：2007.10.12 一、需求分析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 已存在，1i List Length(L)+1.操作结果：在 L 中第 i 个位置之前插入新的数据元素e，L 长度加 1。List Delete(&L,i,&e)初始条件：线性表L 存在非空，1i List Length(L).操作结果：删除 L 的第 i 个元素，并用 e 返回其值，L 长度减 1。2 程序包含四个模块：1）主程序模块：void main()初始化；for（;）while（命令=开始）名师资料总结-精品资料欢迎下载-名师精心整理-第 1 页，共 4 页 -接受命令；处理命令；for（;）2）有序表单元模块实现有序表的抽象数据类型；3）节点结构单元模块定义有序表的节点结构；4）数据输入分析模块判断输入数据正确有效；各模块之间的调用关系如下：主程序模块有序表结构模块节点结构单元模块数据输入分析模块三、详细设计1、结点类型，指针类型Typedef struct LNode int code,date;/code 为人所在位置 date 为人持有的密码struct LNode*next;/结点类型，指针类型2、构造单向循环链表struct LNode*p,*head,*q;/定义头节点，和指针for(i=2;icode=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;inext;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=48&c=57)/确定为输入数字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);/输入为零，重新输入名师资料总结-精品资料欢迎下载-名师精心整理-第 3 页，共 4 页 -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 /最后显示结果、清屏函数头文件名师资料总结-精品资料欢迎下载-名师精心整理-第 4 页，共 4 页 -