1 南昌航空大学实验报告 课程名称： 数据结构 实验名称：实验三、四：栈和队列应用— 迷宫问题 班 级： 学生姓名： 学号： 指导教师评定： 签 名 : 题目：假设迷宫由m 行 n 列构成，有一个入口和一个出口，入口坐标为(1， 1)，出口坐标为(m， n)， 试找出一条从入口通往出口的最短路径。设计算法并编程输出一条通过迷宫的最短路径或报告一个“无法通过”的信息。 要求：用栈和队列实现，不允许使用递归算法。 一、 需求分析 1. 用户可以根据自己的需求进行输入所需的迷宫，其中1 表示迷宫的墙壁，0 表示迷宫的通路，从而建立自己的迷宫；或则使用程序中提供的迷宫。其中用栈和队列的基本操作完成迷宫问题的求解； 2. 用户还可以自己设计迷宫的入口坐标，当然也可以设计出口了，但是应该在合法范围内； 3. 用户进入菜单页面选择输入迷宫的状态（0：表示用户根据自己的需求创建迷宫： 1：表示用户使用程序提供的迷宫； 2：表示退出程序状态） 4. 程序执行的命令包括： （ 1）构造栈sqmaze （ 2）构造抽象迷宫数组maze （ 3）选择自己要的迷宫 （ 4）输出迷宫 （ 5）在迷宫中寻找一条最短的通路 （ 6）打印出所找到的最短通路（输出搜索结果） 二、概要设计 ⒈ 为实现上述算法，需要线性表的抽象数据类型： ADT Stack { 数据对象：D={ai:|ai∈ ElemSet,i=1„ n,n≥ 0} 数据关系：R1={
|ai-1,ai∈ D,i=2,„ n≥ 0} 基本操作: initstack(& S) 操作结果：构造一个空的栈S。 StackLength(S) 初始条件：栈S 已经存在 操作结果：返回S 中数据元素的个数。 Stackempty(S) 初始条件：栈S 已经存在 操作结果：判断S 中是否为空，若为空，则返回TURE，否则FALSE。 GetTop(S,&e) 初始条件：栈S 已存在且不为空 2 操作结果：用e 返回S 的栈顶的元素。 Push(&S ,e) 初始条件：栈S 已存在 操作结果：插入元素e 为新的栈顶元素。 Pop(&S， &e) 初始条件：栈S 已存在且不为空 操作结果：删除S 的栈顶元素，并用e 返回其值。 }ADT List 2. 本程序有三个模块： ⑴ 主程序模块 main(){ 初始化； Switch（参数）{ Case 0 ： 接受命令； Case 1 ： 接受命令； Case 2： 接受命令； ｝ ｝ ⑵ 栈单元模块：实现栈抽象数据类型； ⑶ 迷宫数组单元模块：设计迷宫，实现迷宫抽象数据类型。 各模块之间的调用关系是：主程序模块——迷宫模块...
