程序设计与算法综合训练》设计报告1 学号： E11514064 姓名：汪泓章年级： 大一专 业：计科项目名称：迷宫问题的求解完成日期： 2016 年 6 月 28 日1、需求分析(1)问题描述： 以一个 m*n 的长方阵表示迷宫，0 和 1 分别表示迷宫中的通路和障碍。设计一个程序，对任意设定的迷宫，求出一条从入口到出口的通路，或得出没有通路的结论。（2）基本要求：1）首先实现一个以链表作存储结构的栈类型，然后编写一个求解迷宫的非递归程序。求得的通路以三元组（i，j，d）的形式输出。其中： （ i，j）指示迷宫中的一个坐标，d表示走到下一坐标的方向。如，对于教材第50 页图 3.4 所示的迷宫，输出一条通路为：（1， 1，1），（1，2， 2），（2，2，2），（3，2，3），（3，1， 2），⋯。2）编写递归形式的算法，求得迷宫中所有可能的通路。3）以方阵形式输出迷宫及其通路。4）按照题意要求独立进行设计，设计结束后按要求写出设计报告。①输入输出的要求：②(i) 求得的通路以三元组（i，j，d）的形式输出，其中： （ i，j）指示迷宫中的一个坐标， d 表示走到下一个坐标的方向。（ii ）输出迷宫示意图③程序所能达到的功能：(i) 实现一个以链表作存储结构的栈类型，以非递归算法求取所有通路和最短路径(ii) 以一个递归算法，对任意输入的迷宫矩阵（1 代表不通， 0 代表通路）求出所有通路2、概要设计i ）设计中非递归程序的模块结构图图中方框表示函数， 方框中指出函数名， 箭头方向表示函数间的调用关系，虚线方框表示文件的组成mgpath（）：求解迷宫问题，即输出从（1，1）到（ M，N）的全部路径和最短路径（包含最短路径长度） 。当找到一条路径时，不使用return语句退出，而是出栈一次，重新回溯走另一条路径，并用minlen 记录最短路径长度， Path 数组记录最短路径。ii ）程序的数据结构和数据库结构分析设迷宫为 m行 n 列，利用 maze[m][n] 来表示一个迷宫，maze[i][j]=0或 1; 其中： 0 表示通路， 1 表示不通，当从某点向下试探时，中间点有4 个方向可以试探，（见图）而四个角点有2 个方向，其它边缘点有3 个方向，为使问题简单化我们用 maze[m+2][n+2] 来表示迷宫， 而迷宫的四周的值全部为1。这样做使问题简单了，每个点的试探方向全部为4，不用再判断当前点的试探方向有几个，同时与迷宫周围是墙壁这一实际问题相一致。iii、栈的设计当到达了某点而无路可走时需返回前一点，再从...
