《数据结构--约瑟夫环问题--实习报告(共7页).doc》由会员分享，可在线阅读，更多相关《数据结构--约瑟夫环问题--实习报告(共7页).doc（5页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、精选优质文档-倾情为你奉上 实验报告实验一 线性表的基本操作及其应用一、实验目的1、复习C语言程序设计中的知识。2、熟悉线性表的逻辑结构。3、熟悉线性表的基本运算在两种存储结构上的实现，其中以熟悉链表的操作为侧重点。二、实验内容本次实验提供2个题目，如果实现第一个题目有困难，可做第二个题目题目一：约瑟夫环问题描述约瑟夫（Joseph）问题的一种描述是：编号为1,2,n的n个人按顺时针方向围坐一圈，每人可有代表本人的序号。一开始任选一个正整数m，从第一个人开始按顺时针方向自1开始顺序报数，报到m时停止报数。报m的人出列，从他在顺时针方向上的下一个人开始重新从1报数，如此下去，直至所有人全部出列为
2、止。试设计一个程序求出出列顺序。基本要求利用单向链表存储结构模拟此过程，按照出列的顺序印出各人的编号。测试数据由学生任意指定。如：m的初值为5；n的值为7；序号：3，1，7，2，4，8，4； (报告上要求写出多批数据测试结果)实现提示程序运行后首先要求用户输入初始报数m，人数n,(设n30)。然后输入各人的序号。选作内容向上述程序中添加在顺序结构上实现的部分实验题目一：约瑟夫环一 需求分析1 利用单向循环链表存储结构模拟此过程，按照出列的顺序印出各人的编号。2演示程序以用户和计算机的对话方式执行，即在计算机上显示“提示信息”之后，由用户在键盘上输入演示程序中规定的运算命令；相应的输入数据（滤去
3、输入中的非法字符）和运算结构显示在其后。3.程序执行的命令包括：1） 输入报数上限值；2）输入人数以及所持密码；3）输出出列顺序；4）结束2） 测试数据4.由学生任意指定。如：m的初值为5；n的值为7；序号：3，1，7，2，4，8，4；二 概要设计为实现上述程序功能，需建立单向循环链表以存储此结构。为此，需要一个抽象数据结构类型。1. 链表结点的抽象数据类型定义为：ADT 2. 本程序包含三个模块：3） 主程序模块；4） 循环链表的创建模块实现创建循环链表；5） 出列操作的模块实现最终的出列操作；各模块之间的调用关系如下： 出列操作的模块循环链表的创建模块三. 详细设计1. 元素类型，结点类型
4、和指针类型struct Lnodeint password;struct Lnode *next;typedef struct Lnode *LinkList;2. 子函数1，创建循环链表int Creatlist_L(LinkList &head,int n)程序的实现：int Creatlist_L(LinkList &head,int n) /利用引用调用得到头指针head; int i; LinkList p,q; printf(请依次输入各位密码：); for(i=1;inext=q;/通过next将下一个结点和前一个结点连起来; p=q; scanf(%d,&(p-password
5、);/一次输入对应的密码； p-next=head;/构成循环链表，并返回链表的头指针 return 0;void DeleteNode(LinkList head,int m,int n) LinkList p,q;int j,i;p=head; for(j=1;jn;j+)/先出列前n-1个人，并依次释放其结点的空间；for(i=1;inext);/寻找第m个人；printf(%d ,p-password);p-password=p-next-password;/将后一个结点的数据全部赋值于当前p所指的结点q=p-next;p-next=p-next-next;/p指向其下一个的下个一结点
6、，重新开始寻找；free(q);printf(%d,p-password);/最后一个人出列，并释放其结点所占空间；free(p); scanf(%d,&(p-password);/一次输入对应的密码； p-next=head;/构成循环链表，并返回链表的头指针 return 0;3. 主函数的实现，对两个子函数的调用 void main() int n,m; LinkList List; printf(输入人数:); scanf(%d,&n); printf(输入值m:); scanf(%d,&m); Creatlist_L(List,n); DeleteNode(List,m,n); pr
7、intf(n);4. 函数的调用关系图反映了演示程序的层次结构： mainCreatlist; mainDeleteNode;四 调试分析1. 由于对引用调用理解的不透侧，导致刚开始修改了很长时间。今后要注重这些细节方面。2. 本程序的模块划分比较合理，共三个函数，且尽可能将指针的操作封装在结点和链表的模块中，并通过引用调用来返回头指针。并合理的释放了所申请的空间，变量也比较少，比较容易理解。3. 算法的时空分析1）链表采用了带头结点的循环链表，各种操作的算法时间复杂度比较合理。函数1和函数2通过一个head指针连接。2）基于有序链表实现的有序集的各种运算和操作的时间复杂度分析如下： 出列操作模块中，读入元素为n,循环n次，时间复杂度是O（n*n）.4. 本实习作业采用数据抽象的程序设计方法，将程序划分为三个层次结构，使得设计时思路清晰，实现时调试顺利，确实得到了一次良好的程序设计训练。五用户手册1. 运行，按屏幕提示输入人数n;2. 按屏幕提示输入报数上限的初值m；3. 按屏幕提示依次输入第1个人到第n个人的password;4. 回车显示n个人的出列顺序；5. Press any key to continue,退出。六测试结果 图表 1 图表 2 图表 3图表 4专心-专注-专业