资源描述：
《范例：实验报告迷宫问题的研究》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。
1、范例：实验报告迷宫问题的研究迷宫问题的研究2004-2005（2）学期****班学号：**姓名：***指导老师：［问题描述］以一个mXn的长方阵表示迷宫，0和1分别表示迷宫中的通路和障碍。设计一个程序，对任意设定的迷宫，求出一条从入口到出口的通路，或得到没有通路的结论。［基木耍求］首先实现一个以链表作存储结构的栈类型，然后编写一个求解迷宫的非递归程序，求得的通路以三元组（i,j,d）的形式输出，其屮：（i,j）指示迷宫中的一个坐标，d表示走到下一坐标的方向。如：对于下列数据的迷宫，输出的一条通路为：（1,1,1）,（1,2,2）,（3,2,3)(
2、3,1,2)…［测试数据］迷宫的测试数据如下：左上角（1,1）为入口，右下角（&9）为出口。0()1P001f!0010001()000011010111001000010000010001010111100111()001011100000［实现提示］计算机解迷宫通常丿〕］的是“穷举求解”方法，即从入口岀发，顺着某一个方向进行探索，若能走通，则继续往前进；否则沿着原路退回，换一个方向继续探索，直至出口位路，求得一条通路。假如所有可能的通路都探索到而耒能到达出口，则所设定的迷宫没有通路。可以二维数组存储迷宫数据，通常设疋入口点的下标为（1,1）,
3、出口点的下标为（n,n）。为处理方便起见，可在迷宫的四周加一圈障碍。对于迷宫屮任一位銘，均可约定有东、南、西、北四个方向可通。[选作内容]1（1）编写递归形式的算法，求得迷宫中所有可能的通路；（2）以方阵形式输出迷宫及具通路。题FI：编制-•个求解迷宫通路的程序，对其机制进行研究。一、需求分析（1）以二维数组Maze[m+2][n+2]表示迷宫，其中:Maze[O][j]和Maze[m+1][j]（oWn+1）及Maze[i][0]和Maze[i][n+1]（oWm+1）为添加的一圈障碍。数组中以元素值为0表示通路，1表示障碍，限定迷宫的大小in
4、,nW10。（2）用户以文件的形式输入迷宫的数据；文件中笫一行的数据为迷宫的行数ni和列数n；从第2行至第m+1行（每行n个数）为迷宫值，同一行中的两个数字之间用空白字符相隔。（3）迷宫的入口位銘和出口位路可由用户随时设址。（4）若设定的迷宫存在通路，则以长方阵形式将迷宫及其通路输出到标准输出文件（即终端）上，其屮，字符表示障碍，字符“*”表示路径上的位铭，字符@表示“死胡同”，即曾途经然而不能到达出丨I的位路，余者用空格符印出。若设定的迷宫不存在通路，则报告相应信息。（5）本程序只求出一条成功的通路。然而，只需要对迷宫求解的函数作小量修改，便口
5、J求得全部路径。（6）测试数据见原题，当入口位路为（1,1）,出口位路为（9,8）时，输出数据应为：**#@@@#*#@@@#*@###*####@**#*@#*#############*（7）程序执行的命令为:1）创建迷宫；2）求解迷宫；3）输出迷宫的解。二、概要设计1.设定栈的抽象数据类型定义：2ADTStack{数据对象:D={ai
6、ai^CharSet,i=l,2,…，n,n2o}数据对象:Rl=«al-l,al>
7、aI-l,al€D,i=2,n}基木操作：InitStack(&S)操作结果：构造一个空栈S。DostroStack(&S
8、)初始条件：栈S已存在。操作结果：销毁栈S。ClcarStack(&S)初始条件：栈S已存在。操作结果：将s清为空栈。StackLength(S)初始条件：栈S已存在。操作结果：返回栈S的长度。StackEmpty(S)初始条件：栈S已存在。操作结果：若栈S为空栈,则返冋TRUE,否则返回FALSEoGetTop(S,&e)初始条件：栈SC存在。操作结果：若栈S不空，则以e返回栈顶元素。Push(&S,e)初始条件：栈SLA存在。操作结果：在栈S的栈顶插入新的栈顶元索。Pop(&S,&o)初始条件：栈SC存在。操作结果：删除S的栈顶元索，并以e返
9、冋其值。3StackTraverso(S,visit())初始条件：栈S已存在。操作结果：从栈底到栈顶依次对S屮的每个元索调用函数visit()0}ADTStack1.设左迷宫的抽象数据类型为：ADTStack{数据对象：D={aij
10、aT,jG{/zz#'、'©'},OWiWm+1,oWjWn+1,m,nW10}数据对象:R={ROW,COL}ROW={
11、al-l,j,al,jeD,i=l,・・・，m+l,j二0,・・・n+l}DOL二{〈ai,j-1,ai,j>
12、aT,j-1,al,jED,i二0,…，m+1,j二1
13、,…n+1}基木操作：InitMaze(&M,a,row,coI)初始条件：二维数组a[row+2][col+2]已存在,其中自第1行至
