《迷宫问题数据结构课程设计报告》由会员分享，可在线阅读，更多相关《迷宫问题数据结构课程设计报告（6页珍藏版）》请在金锄头文库上搜索。
1、上海应用技术学院理学院数据结构与算法分析实验报告姓名：朱可玉班级：09122111学号：0912211133指导老师：何莉莉完成时间：2012-6-252012-7-06、绪言：1.1、课题背景：数据结构在计算机科学中是一门综合性的专业基础课。数据结构的研究不仅涉及到计算机硬件（特别是编码理论、存储装置和存取方法等）的研究范围，而且和计算机软件的研究有着更密切的关系，无论是编译程序还是操作系统，都涉及到数据元素在存储器中的分配问题。在研究信息检索时也必须考虑如何组织数据，以便查找和存取数据元素更为方便。因此，可以认为数据结构是介丁数学、计算机硬件和计算机软件三者之间的一门核心课程，在计算机科学
2、中，数据结构不仅是一般程序设计（特别是非数值计算的程序设计）的基础，而且是设计和实现编译程序、操作系统、数据系统及其它系统程序和大型应用程序的重要基础。迷宫问题是取自心理学的一个古典实验。在该实验中，让一只老鼠从一个无顶大盒子门进入，在盒子中设置了许多墙，对行进方向形成了多处阻挡。盒子仅有一个出口，在出口处置一块奶酪，吸引老鼠在迷宫中寻找道路以到达出口。对同一只老鼠重复进行上述实验，直到老鼠从入口走到出口，而不走错一步，老鼠经过多次试验最终学会走通迷宫的路线。1.2、课题研究的目的和意义：通过对此次数据结构大型作业内容的实际操作及分析，加深对数据结构丰富功能的理解及增强实际动手能力，在实践中不
3、断提高对汇编语言的运用能力。锻炼学生分析与编写大型软件代码的能力。1.3、主要研究内容这次课程设计我选择迷宫问题、二义树遍历、插入法排序、选择法排序、起泡法改进算法排序等三个课程为主要研究对象。:、需求设计:以一个m*m的方阵表示迷宫，0和1分别表示迷宫中的通路和障碍。设计一个程序，对任意设定的迷宫，求出一条从入口的通道，或得出没有通路的结论。三、概要设计:3.1:存储结构：采用了数组以及结构体来存储数据，在探索迷宫的过程中用到的栈，属于顺序存储结构。/*八个方向的数组表示形式*/intmove82=0,1,1,1,1,0,1,-1,0,-1,-1,-1,-1,0,-1,1；/*用结构体表示位
4、置*/structpositionintx,y,ok;positionstackm*m+1;3.2:基本算法:走迷宫的过程可以模拟为一个搜索的过程：每到一处，总让它按东、东南、南、西南、西、西北、北、东北8个方向顺序试探下一个位置；如果某方向可以通过，并且不曾到达，则前进一步，在新位置上继续进行搜索；如果8个方向都走不通或曾经到达过，则退回一步，在原来的位置上继续试探下一位置。每前进或后退一步，都要进行判断：若前进到了出口处，则说明找到了一条通路；若退回到了入口处，则说明不存在通路。用一个字符类型的二维数组表示迷宫，数组中每个元素取值“0”（表示通路）或“1,（表示墙壁）。迷宫的入口点在位置（
5、1,1）处，出口点在位置（m,m）处。设计一个模拟走迷宫的算法，为其寻找一条从入口点到出口点的通路。二维数组的第0行、第m+1行、第0列、第m+1列元素全置成“1”,表示迷宫的边界；第1行第1列元素和第m行第m列元素置成“0”，表示迷宫的入口和出口；其余元素值用随机函数产生。假设当前所在位置是（x,y）。沿某个方向前进一步，它可能到达的位置最多有8个。如果用二维数组move记录8个方向上行下标增量和列下标增量，则沿第i个方向前进y_一步，可能到达的新位置坐标可利用move数组确定：x=x+movei0y=y+movei1从迷宫的入口位置开始，沿图示方向顺序依次进行搜索。在搜索过程中，每前进一步
6、，在所到位置处做标记“.”（表示这个位置在通路上），并将该位置的坐标压入栈中。每次后退的时候，先将当前所在位置处的通路标记“:改成死路标记“x”（表示这个位置曾到达过但走不通，以后不要重复进入），然后将该位置的坐标从栈顶弹出。搜索到出口位置时，数组中那些值为“.”的元素形成一条通路。四、详细设计:源程序：迷宫问题走迷宫的过程可以模拟为一个搜索的过程：每到一处，总让它按东、东南、南、西南、西、西北、北、东北个方向顺序试探下一个位置；如果某方向可以通过，并且不曾到达，则前进一步，在新位置上继续进行搜索；如果某个方向都走不通或曾经到达过，则退回一步，在原来的位置上继续试探下一位置。每前进或后退一步，
7、都要进行判断：若前进到了出口处，则说明找到了一条通路；若退回到了入口处，则说明不存在通路。用一个字符类型的二维数组表示迷宫，数组中每个元素取值0”(表示通路)或1(表示墙壁)。迷宫的入口点在位置(1,1)处，出口点在位置(m,m)处，需要为其寻找一条从入口点到出口点的通路。这个算法为：#include#include#include#include#defineM20intmain()intm=1;while(m!=0)printf(输入m,使得为m*m的方阵迷宫(m0输入0时退出：)n);scanf(%d”,&m);/*设定n*n的方阵迷宫*/*数组的形式表示八个方向*/intmove82=
8、0,1,1,1,1,0,1,-1,0,-1,-1,-1,-1,0,-1,1;/*用结构体表示位置*/structpositionintx,y,ok;/*用于记录和输出迷宫探路中相关符号(当前方块的行号、列号以及下一可走相邻方位的方位号)charmazeM+2M+2;/*用栈来存储探路过程中的数据*/positionstackM*M+1;inttop;/*栈顶*/inti,x,y,ok;positionp;/*二维数组的第0行、第m+1行、第0列、第m+1列兀素全置成”1”,表示迷宫的边界；第1行第1列元素和第m行第m列元素置成”0”，表示迷宫的入口和出口；其余元素值用随机函数产生。*/sran
9、d(time(0);for(x=1;x=m;x+)for(y=1;y=m;y+)mazexy=48+rand()%2;maze11=0;mazemm=0;for(x=0;x=m+1;x+)mazex0=1;mazexm+1=1;for(y=0;y=m+1;y+)maze0y=1;mazem+1y=1;p.x=1;p.y=1;top=1;stacktop=p;maze11=.;/*开始探路dop=stacktop;ok=0;i=0;while(ok=0)&(i0)&(p.x!=m)|(p.y!=m);/*输出探路结果*/if(top=0)printf(没有路径n);elseprintf(有路径n
10、);/*输出探路迷宫留下的踪迹*/for(x=1;x=m;x+)printf(n);for(y=1;y=m;y+)printf(%c,mazexy);)printf(n);system(pause);)五、调试分析:5.1:测试数据和结果:5.2:算法时间复杂度:O(m2)5.3、主要研究内容这个迷宫问题的算法中，迷宫是m*m的方阵，入口为（1,1）,出口为（m,m），而其实可以找一个任意的m*n的矩阵（即不一定是方阵迷宫），入口不一定是坐标（1,1）,可以是任意的（a,b），出口也不一定是（m,m），可以是任意的（c,d）。房次遍历序列涌BCDEFGHIJKLHH先序遍用应列=递归建法诵BDEHJKLMNCFGI非递归算法油BDEHJKLMNCFGI中序遍历庆列：递归K：DBJHLXHHEAFCGI非递归算荏5BJHLKMNEAFCG1后序遍历度列=递归夏皆DJLNMKHEBFIGCA非递的真军DJLNrtKHEBPTGCAiPressanytocontinue9输出二结点左孩子为J右孩子为K二支树b的深度汗5二叉二叉6）二叉树h的叶手结点个数:6Pressanykeytocentinue
