《 数 据 结 构 与 算 法 设 计 》 迷 宫 问 题 实 验 报 告 ——实验二 专业：物联网工程 班级：物联网 1 班 学号：******** 姓名：*** 一、 实验目的 本程序是利用非递归的方法求出一条走出迷宫的路径，并将路径输出。首先由用户输入一组二维数组来组成迷宫，确认后程序自动运行，当迷宫有完整路径可以通过时，以 0 和 1 所组成的迷宫形式输出，标记所走过的路径结束程序；当迷宫无路径时，提示输入错误结束程序。 二、实验内容 用一个 m*m 长方阵表示迷宫，0 和 1 分别表示迷宫中的通路和障碍。设计一个程序对于任意设定的迷宫，求出一条从入口到出口的通路，或得出没有通路的结论。 三、程序设计 1 、概要设计 （1 ） 设定栈的抽象数据类型定义 ADT Stack{ 数据对象：D={ai|ai 属于 CharSet，i=1、2… n，n>=0} 数据关系：R={
|ai-1,ai属于 D，i=2,3,… n} 基本操作： InitStack(&S) 操作结果：构造一个空栈 Push（&S，e） 初始条件：栈已经存在 操作结果：将 e 所指向的数据加入到栈 s 中 Pop（&S,&e） 初始条件：栈已经存在 操作结果：若栈不为空，用 e 返回栈顶元素，并删除栈顶元素 Getpop（&S，&e） 初始条件：栈已经存在 操作结果：若栈不为空，用 e 返回栈顶元 StackEmpty(&S) 初始条件：栈已经存在 操作结果：判断栈是否为空。若栈为空，返回1，否则返回0 Destroy(&S) 初始条件：栈已经存在 操作结果：销毁栈s }ADT Stack （2）设定迷宫的抽象数据类型定义 ADT yanshu{ 数据对象：D={ai,j|ai,j 属于{‘ ’、‘*’、‘@’、‘#’},0<=i<=M,0<=j<=N} 数据关系：R={ROW,COL} ROW={|ai-1,j,ai,j 属于D，i=1,2,… M,j=0,1,… N} COL={|ai,j-1,ai,j 属于D,i=0,1,… M，j=1,2,… N} 基本操作： InitMaze(MazeType &maze, int a[][COL], int row, int col){ 初始条件：二维数组int a[][COL],已经存在，其中第1 至第m-1 行，每行自第1 到第n-1 列的元素已经值，并以值0 表示障碍，值1 表示通路。 操作结果：构造迷宫的整形数组，以空白表示通路，字符‘0’表示障碍 在迷宫四周加上一圈障碍 MazePath（&maze）{ 初始条件：迷宫maze 已被赋值 操作结果：若迷宫maze 中存在一条通路，则按如下规定改变maze 的状态；以字符‘*’表示路径上的位置。字符‘@’表示‘死胡同’；否则迷...
