数据结构课程实例报告范例.docx

《数据结构课程实例报告范例.docx》由会员分享，可在线阅读，更多相关《数据结构课程实例报告范例.docx（26页珍藏版）》请在第一文库网上搜索。

1、及4科板女粤GuangxiUniversityofScienceandTechno1ogy课程设计汇报课程名称：算法与编程综合实习课题名称：.姓名：_学号：院系：计算机科学与通信工程学院专业班级：递值指导教师：完毕日期：2023年1月15日第1部分课程设计汇报3第1章课程设计目的3第2章课程设计内容和规定41. 1问题描述42. 2设计规定4第3章课程设计总体方案和分析43.1问题分析43. 2概要设计71.1 3详细设计73.4 调试分析103.5 测试成果10123. 6参照文献第2部分课程设计总结13附录（源代码）14第1部分课程设计汇才第1章课程设计目的仅仅认识到队列是一种特殊的线性表

2、是远远不够的,本次实习的目的在于使学生深入理解队列的J特性，以便在实际问题背景下灵活运用它，同步还将巩固这种数据构造的构造第2章课程设计内容和规定2.1问题描述：迷宫问题是取自心理学0一种古典试验。在该试验中，把一只老鼠从一种无顶大盒子的门放入，在盒子中设置了许多墙，对行进方向形成了多处阻挡。盒子仅有一种出口，在出口处放置一块奶酪，吸引老鼠在迷宫中寻找道路以抵达出口。对同一只老鼠反复进行上述试验，一直到老鼠从入口走到出口，而不走错一步。老鼠通过多次试验最终学会走通迷宫的路线。设计一种计算机程序对任意设定的矩形迷1论。或得出没有通路的结出口,2.2设计规定：规定设计程序输出如下：（1）建立一种大

3、小为mXn的任意迷宫（迷宫数据可由顾客输入或由程序自动生成），并在屏幕上显示出来；（2）找出一条通路0二元组（i,j）数据序列，（i,j）表达通路上某一点的坐标。（3）用一种标志（如数字8）在迷宫中标出该条通路；（4）在屏幕上输出迷宫和通路;(5)上述功能可用菜单项选择择。第3章课程设计总体方案和分析3.1问题分析：1迷宫的建立：迷宫中存在通路和障碍，为了以便迷宫的创立，可用O表达通路，用1表达障碍，这样迷宫就可以用0、1矩阵来描述，2 .迷宫的存储：迷宫是一种矩形区域，可以使用二维数组表达迷宫，这样迷宫的每一种位置都可以用其行列号来唯一指定，不过二维数组不能动态定义其大小，我们可以考虑先定义

4、一种较大的二维数组mazeM+2N2,然后用它的前m行n列来寄存元素，即可得到一种mn的二维数组，这样(0,0)表达迷宫入口位置，(m-1,n-1)表达迷宫出口位置。注：其中M,N分别表达迷宫最大行、列数，本程序M、N的缺省值为39、39,当然，顾客也可根据需要，调整其大小。3 .迷宫途径的搜索：首先从迷宫H入口开始，假如该位置就是迷宫出口，则己经找到了一条途径，搜索工作结束。否则搜索其上、下、左、右位置与否是障碍，若不是障碍，就移动到该位置，然后再从该位置开始搜索通往出口的途径；若是障碍就选择另一种相邻的位置，并从它开始搜索途径。为防止搜索反复出现，则将已搜索过的位置标识为2,同步保留搜索痕

5、迹，在考虑进入下一种位置搜索之前，将目前位置保留在一种队列中，假如所有相邻的非障碍位置均被搜索过，且未找到通往出口的途径，则表明不存在从入口到出口的途径。这实现时是广度优先遍历B算法，假如找到途径，则为最短途径。以矩阵OoIoI为例，来示范一下100101000100100首先，将位置（0,0）（序号0）放入队列中，其前节点为空，从它开始搜索，其标识变为2,由于其只有一种非障碍位置，因此接下来移动到（0,1）（序号D,其前节点序号为0,标识变为2,然后从（0,1）移动到（1,1）（序号2）,放入队列中，其前节点序号为1,（1,1）存在（1,2）（序号3）、（2,1）（序号4）两个可移动位置，其

6、前节点序号均为2.对于每一种非障碍位置，它的相邻非障碍节点均入队列，且它们B前节点序号均为该位置的序号，因此假如存在途径，则从出口处节点的位置，逆序就可以找到其从出口到入口的通路。如下表所示：012345678910(0,0)(0,1)(1,D(1,2)(2,1)(2,2)(1,3)(2,3)(0,3)(3,3)(3,4)-10122345679由此可以看出,得到最短途径：(3,4)(3,3)(2,3)(2,2)(1,2)(1,1)(0,1)(0,0)搜索算法流程图如下所示:A循环结束无解迷宫3. 2概要设计1 .构建一种二维数组mazeM+2N+2用于存储迷宫矩阵自动或手动生成迷宫，即为二维

7、数组mazeM+2N+2赋值构建一种队列用于存储迷宫途径建立迷宫节点structPoint,用于存储迷宫中每个节点0访问状况实现搜索算法屏幕上显示操作菜单2 .本程序包括10个函数：(1)主函数main()(2)手动生成迷宫函数shoudongjnaze()(3)自动生成迷宫函数zidong_maze()(4)将迷宫打印成图形print_maze()(5)打印迷宫途径(若存在途径)resu1tmaze()(6)入队enqueue()(7)出队dequeue()(8)判断队列与否为空is_empty()(9)访问节点visit()(10)搜索迷宫途径mgpath()3. 3详细设计实现概要设计中

8、定义B所有数据类型和操作的伪代码算法1 .节点类型和指针类型迷宫矩阵类型：intmazeM+2N+2;为以便操作使其为全局变量迷宫中节点类型和队列类型:structpointintrow,co1,predecessorque5122 .迷宫0操作(1)手动生成迷宫voidshoudongmaze(intm,intn)定义i,j为循环变量for(i=m)for(j=n)输入mazeijB值(2)自动生成迷宫voidZidOngjnaZe(intm,intn)定义i,j为循环变量for(i=m)for(jrand()%2由于rand()产生欧J随机数是从O到RANDJfAX,RANDJfAX是定义

9、在std1ib.h中时,其值至少为32767),要产生从X到Y时数,只需要这样写：k=rand()%(Y-X+1)+X;(3)打印迷宫图形voidprint_maze(intm,intn)用i,j循环变量，将mazeij输出口、(4)打印迷宫途径voidresu1t_maze(intm,intn)用i,J循环变量，将mazeij输出口、迷宫中队列入队操作voidenqueue(structpointp)将P放入队尾,tai1+迷宫中队列出队操作structpointdequeue(structpointp)head+,返回quehead-1判断队列与否为空intis_empty()返回head

10、=tai1B值,当队列为空时,返回0访问迷宫矩阵中节点voidvisit(introw,intco1,intmaze4141)建立新J队列节点visit_point,将其值分别赋为row,co1,head-1,mazerowco1=2,表达该节点以被访问过；调用enqueue(visit_point),将该节点入队途径求解voidmgpath(intmaze4141,intm,intn)先定义入口节点为structpointp=0,0,-1,从maze00开始访问。假如入口处即为障碍，则此迷宫无解，返回0,程序结束。否则访问入口节点，将入口节点标识为访问过mazep.rowp.co1=2,调用

11、函数CnqUeUe(P)将该节点入队。判断队列与否为空，当队列不为空时，则运行如下操作：调用dequeue。函数，将队头元素返回给p,假如p.row=m-1且p.co1=-1,即抵达出口节点，即找到了途径，结束假如p.co1+10且mazep.rowp.co1-1=0,阐明未到迷宫左边界，且其左方有通路,则ViSit(p.row,p.co1-1,maze),将左方节点入队标识已访问假如p.row-10且mazep.row-1p.co1=0,阐明未到迷宫上边界,且其上方有通路,则ViSit(p.row,p.co1+1,maze),将上方节点入队标识已访问)访问到出口(找到途径)即p.row=m-

12、1且p.CoI=nT,则逆序将途径标识为3即mazep.rowp.co1=3;whi1e(p.predecessor!-1)p=queuep.predecessor;mazep.rowp.co1=3;最终将途径图形打印出来。3 .菜单项选择择whi1e(cyc1e!=(-1)自动生成迷宫请按：2退出请按：3scant(%c,&i);switch(i)case1：请输入行列数(假如超过预设范围则提醒重新输入)shoudong_maze(m,n);print_maze(m,n);mgpath(maze,m,n);if(X!=0)resu1tmaze(m,n);case2：请输入行列数(假如超过预设

13、范围则提醒重新输入)ZidongJnaZe(m,n);print_maze(m,n);mgpath(maze,m,n);if(X!=0)resu1t_maze(m,n);case3：cyc1e=(-1);break;)注：详细源代码见附录3. 4调试分析在调试过程中，首先是使用链表进行存储，不过产生的途径是多条或不是最短途径,因此通过算法比较，改用此算法4. 5测试成果1 .手动输入迷宫c*D:1yDocuentsGTAViceCityUserFi1es迷宫DebugCpp1exe欢迎进入迷宫求解系统设计者:马兆瑞（信息09-2班）宫宫迷迷成成生生动动出HHn退情选择你的操作:欢迎进入迷宫求解系统设计者:马兆瑞（信息、09-2班）技技技请请请123壬动生成迷宫音动生成迷宫退出请选择你的操作:请输入行数：6请输入列数：6迷宫生成中请按任意键继续.迷宫生成结果如下:迷宫入口口迷宫出口此迷宫无解PressEnterContiue?3.6参照文献1严蔚敏吴伟民数据构造（C语言版）清华大学出版社，2023年9月2谭浩强C程序设计（第三版）清华大学出版社2023年1月第2部分课程设计总结通过这段时间的课程设计，本人对计算机的应用，数据构造的作用以和C语言的使用均有了更深0理解。尤其是C语言的进步让我深刻0感受到