《计算机实践》 实验报告.docx

《计算机实践》实验报告

《计算机实践》实验报告I—数据结构班号：0316102学号：031650106姓名：郭砚璞Email：[e-mail]签名：南京航空航天大学2018年10月21日目录目录…………………………………………………………2实验一：约瑟夫斯问题求解………………………………3实验二：停车场管理问题…………………………………12实验三：管道铺设施工的最佳方案问题…………………25实验四：内部排序算法的实现与比较……………………35参考资料……………………………………………………44源程序清单…………………………………………………44实验一、约瑟夫斯问题求解一、问题描述1）问题描述约瑟夫斯（Josephus）问题的一种描述是：编号为1，2，…，n的n个人按顺时针方向围坐一圈，每人持有一个密码（正整数）。一开始任选一个正整数作为报数上限值m，从第一个人开始按顺时针方向自1开始报数，报到m时停止报数。报m的人出列，将他的密码作为新的m值，从他在顺时针方向下一个人开始重新从1报数，如此下去，直至所有的人全部出列为止。试设计一个程序，按出列顺序印出各人编号。2）实验目的与基本要求利用单向循环链表存储结构模拟此过程，按照出列的顺序印出各人的编号。3）测试数据n=7，7个人的密码依次为：3，1，7，2，4，8，4。m初值为6（正确的出列顺序应为6，1，4，7，2，3，5）。4）提示程序运行后，首先要求用户指定初始报数上限m，然后读取个人的密码。可设n≤30。注意链表中空表和非空表的界限。5）输入输出输入数据：建立输入处理，输入n输入以及每个人的密码；m的初值。输出形式：建立一个输出函数，输出正确的序列。6）选作内容添加采用顺序存储结构实现问题求解的模块。以上是本实验的题目要求，下面我将介绍我的实现算法，程序调试结果以及编程过程中遇到的具体问题，并且谈谈我的收获和感悟！二、需求分析1、本实验用于求出一组排列数的约瑟夫斯出列顺序。2、程序运行后显示提示信息，提示用户输入人数n和初始报数上限m，程序需判断m与n的大小，如果m>n，需提示用户重新输入n值和m值。3、m和n输入有效后，程序提示用户继续输入n个数据，作为n个人的密码。4、用户输入完毕后，程序需自动显示输入的数据，并且按照出列顺序将n个出列者的编号结果显示出来。三、概要设计为了实现上述功能，应以循环链表的数据结构存储n个人的编号、密码信息和顺序关系，因此需要一个循环链表的数据类型。1、循环链表抽象数据类型定义：ADTCircularLinkList{数据对象：一个循环链表，每个结点数据域是一个人的编号和密码。数据关系：一个结点的指针域指向按照编号下一个结点。基本操作：CREATE_SL(SLNODE*);//构建顺序链表ShowOutput(SLNODE*h,intm);//递归程序，按顺序依次输出出列者的编号}ADTCircularLinkList2、本程序保护模块主函数模块建立链表模块：将输入数据赋给结点数据域，并构建循环链表的数据关系核心算法模块：按照算法移动指针、删除节点，依次输出出列者的编号。调用关系：3、算法流程图四、详细设计1.元素类型、结点类型和结点指针类型：#defineElemTypeint#defineSLNODEstructsl_nodeSLNODE{ElemTypedata[2];SLNODE*next;};2、建立链表的伪码SLNODE*CREATE_SL(SLNODE*h,intn)//创建一个h为头指针的链表，h指向的结点数据域用不到{ElemTypedata;inti=1;SLNODE*p,*s;p=h;while(i{printf(“请输入第%d个元素:t”,i);scanf_s(“%d”,&data);s=(SLNODE*)malloc(sizeof(SLNODE));s->data[0]=i;s->data[1]=data;if(h->next==NULL){h->next=s;}else{p->next=s;}p=s;i++;}p->next=h;returnh;}3、主函数伪码intmain(){intm,n,mistake=1;SLNODE*Head;PrintInformation1();//输出程序信息和个人信息while(mistake){printf(“输入人数n:n”);scanf_s(“%d”,&n);printf(“请指定初始报数上限m(m应必须小于等于n):n”);scanf_s(“%d”,&m);if(m>n){printf(“输入数据有误，请重新输入n”);}elsemistake=0;}Head=(SLNODE*)malloc(sizeof(SLNODE));Head->next=NULL