南昌航空大学实验报告
课程名称：班级：签
数据结构
实验名称：实验三、四：栈和队列应用迷宫问题学生姓名：名学号：
指导教师评定：
题目：假设迷宫由m行
列构成，有一个入口和一个出口，入口坐标为1，1，出口坐标为m，
，试找出一条从入口通往出口的最短路径。设计算法并编程输出一条通过迷宫的最短路径或报告一个“无法通过”的信息。要求：用栈和队列实现，不允许使用递归算法。
一、需求分析
1用户可以根据自己的需求进行输入所需的迷宫，其中1表示迷宫的墙壁，0表示迷宫的通路，从而建立自己的迷宫；或则使用程序中提供的迷宫。其中用栈和队列的基本操作完成迷宫问题的求解；2用户还可以自己设计迷宫的入口坐标，当然也可以设计出口了，但是应该在合法范围内；3用户进入菜单页面选择输入迷宫的状态（0：表示用户根据自己的需求创建迷宫：1：表示用户使用程序提供的迷宫；2：表示退出程序状态）4程序执行的命令包括：（1）构造栈sqmaze（2）构造抽象迷宫数组maze（3）选择自己要的迷宫（4）输出迷宫（5）在迷宫中寻找一条最短的通路（6）打印出所找到的最短通路（输出搜索结果）
二、概要设计
⒈为实现上述算法，需要线性表的抽象数据类型：ADTStack数据对象：Daiai∈ElemSeti1
≥0数据关系：R1ai1aiai1ai∈Di2
≥0基本操作i
itstackS操作结果：构造一个空的栈S。StackLe
gthS初始条件：栈S已经存在操作结果：返回S中数据元素的个数。StackemptyS初始条件：栈S已经存在操作结果：判断S中是否为空，若为空，则返回TURE，否则FALSE。GetTopSe初始条件：栈S已存在且不为空
1
f操作结果：用e返回S的栈顶的元素。PushSe初始条件：栈S已存在操作结果：插入元素e为新的栈顶元素。PopS，e初始条件：栈S已存在且不为空操作结果：删除S的栈顶元素，并用e返回其值。ADTList2本程序有三个模块：⑴主程序模块mai
初始化；Switch（参数）Case0：接受命令；Case1：接受命令；Case2：接受命令；｝｝⑵栈单元模块：实现栈抽象数据类型；⑶迷宫数组单元模块：设计迷宫，实现迷宫抽象数据类型。各模块之间的调用关系是：主程序模块迷宫模块栈模块
三、详细设计
⒈元素类型定义typedefstructi
txi
tyi
tpresqmaze100i
tmazeMMsqmazemazepathi
tm
2对抽象数据类型中的部分基本操作的伪码算法如下：由于我定义的栈是用数组来实现的，因此与栈的基本操作的名称及操作有点不一样。数组r