数据结构课程设计——迷宫求解.docVIP

指导教师对课程设计的评语 指导教师签字： 年 月 日 设计2 迷宫问题 一、需求分析 1、问题描述 迷宫是一些互相连通的交叉路口的集合，给定一个迷宫入口，一个迷宫出口，当从入口到出口存在通路时输出其中的一条通路，当从入口到出口不存在通路时输出无通路存在。 要求: 随机产生一个mXn的迷宫，0和1分别表示迷宫中的通路和障碍。存在回路时能记住已经走过的路口，不重复已经走过的路口。 2、需要用户自己设置入口和出口。 3、本程序只求出一条成功的通路。 二、概要设计 1、计算机解迷宫通常用的是“穷举求解”方法，即从入口出发，顺着某一个方向进行探索，若能走通，则继续往前进；否则沿着原路退回，换一个方向继续探索，直至出口位置，求得一条通路。假如所有可能的通路都探索到则未能到达出口，则所设定的迷宫没有通解。 可以二维数组存储迷宫数据，通常设定入口点的下标为（1，1），出口点的下标为（n,n）。为处理方便起见，可以迷宫的四周加一圈障碍。对于迷宫任一位置，均可约定有东、南、西、北四个方向可通。 ADT Stack{ 数据对象：D={ai| ai∈CharSet，i=1,2,3.....，n，n=0} 数据关系：R1={ ai-1, ai | ai-1, ai∈D,i=2, .....，n } 基本操作： StackSize( S ) 操作结果：构造一个空栈S。 DestoryStack( S ) Push( S, e ) 初始条件：栈S已存在。操作结果：在栈S的栈顶插入新的栈顶元素e。 Pop( S, e ) 初始条件：栈S已存在。操作结果：删除S的栈顶元素，并以e返回其值。 StackEmpty( S ) 初始条件：栈S已存在。操作结果：若栈S为空栈，则返回TRUE，否则返回FALSE。 } ADT Stack 2.设定迷宫的抽象数据类型为： ADT maze{ 数据对象：D={ ai，j ∈{‘ ’ ,‘#’、’@’、’*’}，0=i=m+1,0=j=n+1,m,n=10} 数据关系：R={ ROW，COL } ROW={ai-1, j , ai，j | ai-1, j, ai，j∈D,i=1,……,m+1,j=0,……n+1 } COL={ ai，j-1 , ai，j | ai，j-1 ,ai，j ∈D,i=1,……,m+1,j=0,……n+1} 基本操作： InitMaze( maze, a, row, col ) 初始条件：二维数组a[row+2][col+2]已存在，其中自第1行至第row+1行、每行中自第1 列至第col+1列的元素已有值，并且以值0表示通路，以值1表示障碍。 操作结果：构造迷宫的字符数组，以空白字符表示通路，以字符‘#‘表示障碍，并在迷宫四周加上一圈障碍。 MazePath( maze, start, end ) 初始条件：迷宫maze已被赋值。 操作结果：若迷宫maze中存在一条通路，则按照如下规定改变迷宫maze的状态；以字符“*”表示路径上的位置，字符“@”表示”死胡同”；否则迷宫的状态不变。 PrintMaze( maze ) 初始条件：迷宫maze已存在。 操作结果：以字符形式输出迷宫。 } ADT maze 3、为了实现上述操作，以栈为存储结构。 1）主程序模块： Void main() { 初始化； do{ 接受命令； 处理命令； }while（命令！=“退出”）；} 2）栈模块——实现栈抽象数据类型 3）迷宫模块——实习迷宫抽象数据类型 4.求解迷宫中一条通路的伪代码： do{ 若当前位置可通， 则{ 将当前位置插入栈顶； 若该位置是出口位置，则结束； 否则切换当前位置的东临方块为新的当前位置； } 否则{ 若栈不空且栈顶位置尚有其他方向未被探索， 则设定新的的当前位置为沿顺时针方向旋转找到的栈顶位置的下一相邻块 若栈不空但栈顶位置的四周均不可通， 则{ 删去栈顶位置； 若栈不空，则重新测试新的栈顶位置，直至找到一个可通的相邻块或出栈至栈空。 }}} while(栈不空) 三、详细设计 1,位置设置 typedef struct{ int r,c; }PosType;//位置类型 2) 栈类型： typedef struct{ int step; //当前位置在路径上的序号