实验报告 题目：设计一个程序，对任意设定的迷宫，求出一条从入口到出口的通路，或得出没有通路的结论。 一、需求分析 1. 以二维数组 maze[N][N]表示迷宫，数组中以元素值 0表示通路，1表示障碍，限定迷宫大小 N<100。 2. 第一行的数据为迷宫的行数 m和列数 n；从第 2行到第 m+1为迷宫值，同一行两个数字之间用空格表示。 3. 实现一个以链表作存储结构的栈类型。 4. 编写一个求解迷宫的非递归程序。 5. 迷宫的入口位置和出口位置可由用户自己设定 6. 本程序只求出一条成功的通路求得的通路以三元组（i,j,d）的形式输出，其中：(i,j)指示迷宫中的一个坐标，d表示走到下一坐标的方向。 7. 测试数据：迷宫的测试数据如下：左上角(1,1)为入口，右下角(9,8)为出口 0 0 1 0 0 0 1 0 0 0 1 0 0 0 1 0 0 0 0 0 1 1 0 1 0 1 1 1 0 0 1 0 0 0 0 1 0 0 0 0 0 1 0 0 0 1 0 1 0 1 1 1 1 0 0 1 1 1 0 0 0 1 0 1 1 1 0 0 0 0 0 0 8．程序执行的命令为： 1）创建迷宫；2）求解迷宫；3）输出迷宫的解。 二、概要设计 拟采用栈来保存从入口到当前位置的路径，并采用“穷举求解”的方法进行求解。程序中将涉及到以下抽象数据类型： 1. 设定栈的抽象数据类型定义： ADT Stack{ 数据对象：D={|,1,2,, ,0iia aCharSet in n } 数据关系：R1={11,|,,2,,iiiiaaaaD in} 基本操作： InitStack (StackSq* S) 操作结果：构造一个空栈 S。 StackEmpty(StackSq* S) 初始条件：栈 S 已存在。 操作结果：若 S 为空栈，则返回 TRUE，否则返回 FALSE。 Push(StackSq* S,SElemType e) 初始条件：栈S 已存在。 操作结果：在栈S 的栈顶插入新的栈顶元素e。 Pop(StackSq* S,SElemType &e) 初始条件：栈S 已存在。 操作结果：删除S 的栈顶元素，并以e 返回其值。 } ADT Stack 2.设定迷宫的抽象数据类型为： ADT maze{ 数据对象：,,{|{0,1,2,3} ,01,01}i ji jDaaimjn 数据关系：1,,1,,1,,1,,{,}{,|,,1,...,,0,..., }{,|,,1,...,,0,..., }iji jiji jiji jiji jRROW COLROLaaaaD im jnCOLaaaaD im jn 基本操作： InitMaze(&Maze,row,col) 初始条件：用数组Maze[M][N]表示迷宫，迷宫的数据由用户自己定义，其中自第1 行至第M 行、...
