数据结构--约瑟夫环问题--实习报告

中原工学院实验报告201100834105高雪娇1实验报告实验一线性表的基本操作及其应用一、实验目的1、复习C语言程序设计中的知识。2、熟悉线性表的逻辑结构。3、熟悉线性表的基本运算在两种存储结构上的实现，其中以熟悉链表的操作为侧重点。二、实验内容本次实验提供2个题目，如果实现第一个题目有困难，可做第二个题目题目一：约瑟夫环[问题描述]约瑟夫（Joseph）问题的一种描述是：编号为1,2,…,n的n个人按顺时针方向围坐一圈，每人可有代表本人的序号。一开始任选一个正整数m，从第一个人开始按顺时针方向自1开始顺序报数，报到m时停止报数。报m的人出列，从他在顺时针方向上的下一个人开始重新从1报数，如此下去，直至所有人全部出列为止。试设计一个程序求出出列顺序。[基本要求]利用单向链表存储结构模拟此过程，按照出列的顺序印出各人的编号。[测试数据]由学生任意指定。如：m的初值为5；n的值为7；序号：3，1，7，2，4，8，4；(报告上要求写出多批数据测试结果)[实现提示]程序运行后首先要求用户输入初始报数m，人数n,(设n≤30)。然后输入各人的序号。[选作内容]向上述程序中添加在顺序结构上实现的部分实验题目一：约瑟夫环一．需求分析1．利用单向循环链表存储结构模拟此过程，按照出列的顺序印出各人的编号。2．演示程序以用户和计算机的对话方式执行，即在计算机上显示“提示信息”之后，由用户在键盘上输入演示程序中规定的运算命令；相应的输入数据（滤去输入中的非法字符）和运算结构显示在其后。3.程序执行的命令包括：1）输入报数上限值；2）输入人数以及所持密码；3）输出出列顺序；4）结束2）测试数据4.由学生任意指定。如：m的初值为5；n的值为7；序号：3，1，7，2，4，8，4；二．概要设计为实现上述程序功能，需建立单向循环链表以存储此结构。为此，需要一个抽象数据结构类型。1.链表结点的抽象数据类型定义为：ADT中原工学院实验报告201100834105高雪娇22.本程序包含三个模块：3）主程序模块；4）循环链表的创建模块——实现创建循环链表；5）出列操作的模块——实现最终的出列操作；各模块之间的调用关系如下：出列操作的模块——主程序模块——循环链表的创建模块三.详细设计1.元素类型，结点类型和指针类型structLnode{intpassword;structLnode*next;};typedefstructLnode*LinkList;2.子函数1，创建循环链表intCreatlist_L(LinkList&head,intn)程序的实现：intCreatlist_L(LinkList&head,intn){//利用引用调用得到头指针head;inti;LinkListp,q;printf(请依次输入各位密码：);for(i=1;i=n;i++){if(i==1){//申请一个空间，将头指针head和指针p均指向第一个结点；head=p=(LinkList)malloc(sizeof(structLnode));if(p==0)return0;//分配存储空间失败}else{q=(LinkList)malloc(sizeof(structLnode));if(q==0)return0;p-next=q;//通过next将下一个结点和前一个结点连起来;p=q;}scanf(%d,&(p-password));//一次输入对应的密码；}p-next=head;//构成循环链表，并返回链表的头指针return0;}voidDeleteNode(LinkListhead,intm,intn){中原工学院实验报告201100834105高雪娇3LinkListp,q;intj,i;p=head;for(j=1;jn;j++){//先出列前n-1个人，并依次释放其结点的空间；for(i=1;im;i++,p=p-next);//寻找第m个人；printf(%d,p-password);p-password=p-next-password;//将后一个结点的数据全部赋值于当前p所指的结点q=p-next;p-next=p-next-next;//p指向其下一个的下个一结点，重新开始寻找；free(q);}printf(%d,p-password);//最后一个人出列，并释放其结点所占空间；free(p);}}scanf(%d,&(p-password));//一次输入对应的密码；}p-next=head;//构成循环链表，并返回链表的头指针return0;}3.主函数的实现，对两个子函数的调用voidmain(){intn,m;LinkListList;printf(输入人数:);scanf(%d,&n);printf(输入值m:);scanf(%d,&m);Creatlist_L(List,n);DeleteNode(List,m,n);printf(\n);}4.函数的调用关系图反映了演示程序的层次结构：main——Creatlist;main——DeleteNode;四调试分析1.由于对引用调用理解的不透侧，导致刚开始修改了很长时间。今后要注重这些细节方面。2.本程序的模块划分比较合理，共三个函数，且尽可能将指针的操作封装在结点和链表的模块中，并通过引用调用来返回头指针。并合理的释放了所申请的空间，变量也比较少，比较容易理解。3.算法的时空分析中原工学院实验报告201100834105高雪娇41）链表采用了带头结点的循环链表，各种操作的算法时间复杂度比较合理。函数1和函数2通过一个head指针连接。2）基于有序链表实现的有序集的各种运算和操作的时间复杂度分析如下：出列操作模块中，读入元素为n,循环n次，时间复杂度是O（n*n）.4.本实习作业采用数据抽象的程序设计方法，将程序划分为三个层次结构，使得设计时思路清晰，实现时调试顺利，确实得到了一次良好的程序设计训练。五．用户手册1.运行，按屏幕提示输入人数n;2.按屏幕提示输入报数上限的初值m；3.按屏幕提示依次输入第1个人到第n个人的password;4.回车显示n个人的出列顺序；5.Pressanykeytocontinue,退出。六．测试结果图表1图表2中原工学院实验报告201100834105高雪娇5图表3图表4