数据结构课程设计—迷宫问题.doc

《数据结构》 课 程 设 计 报 告 学院（系）： 班 级： 学生学号： 姓名： 指导教师： 2012 年 6 月 15 日 目 录 一、需求分析…………………………………………3 二、概要设计…………………………………………3 1、设计栈的抽象数据类型………………………………3 2、设计迷宫的抽象数据类型……………………………4 3、本程序包含四个模块…………………………………5 4、各模块之间的调用关系………………………………5 详细设计…………………………………………5 坐标位置类型………………………………………………6 栈类型………………………………………………………6 栈的基本操作设置…………………………………………6 求解迷宫路径的函数算法…………………………………7 创建迷宫……………………………………………………9 主函数………………………………………………………10 四、设计和调试分析…………………………………10 五、用户手册…………………………………………11 六、测试结果…………………………………………12 七、设计心得…………………………………………15 八、参考文献…………………………………………15 九、附录………………………………………………16 迷宫问题 需求分析： 1、以一个m* 的方阵表示迷宫，0和1分别表示迷宫中的通路和障碍。设计一个程序，对任意设定的迷宫，求出一条从入口的通道或得出没有通路的结论。 用户需用文件的形式输入迷宫的数据：文件中第一行的数据为迷宫的行数m和列数n；下面用0，1输入整个迷宫，每两个数字之间需加一个空格。 程序执行的命令为：1，创建迷宫；2，求解迷宫；3，输出迷宫的解。 栈的抽象数据类型ADT Stack { 数据对象：D={ai| aiCharSet,i=1,2…n,n=0} 数据关系：R1={ai-1, ai | ai-1, aiD,i=2,…n} 基本操作： InitStack(S) 操作结果：构造一个空栈S。 DestroyStack(S) 初始条件：栈S已存在。 操作结果：销毁栈S。 ClearStack(S) 初始条件：栈S已存在。 操作结果：将S清为空栈。 StackLength(S) 初始条件：栈S已存在。 操作结果：返回栈S的长度。 StackEmpty(S) 初始条件：栈S已存在。 操作结果：若S为空栈，则返回TRUE，否则返回FALSE。 GetTop(S，e) 初始条件：栈S已存在。 操作结果：若栈S不空，则以e返回栈顶元素。 Push(S， e) 初始条件：栈S已存在。 操作结果：在栈S的栈顶插入新的栈顶元素e。 Pop(S，e) 初始条件：栈S已存在。 操作结果：删除S的栈顶元素，并以e返回其值。 StackTraverse（S，visit（）） 初始条件：栈S已存在。 操作结果：从栈底到栈顶依次对S中的每个元素调用函数visit（）。 } ADT Stack迷宫的抽象数据类型 ADT maze{ 数据对象： {ai,j|ai,j{ ,‘0’，‘1’},0=i=m+1,0=j=n+1,m,n=15} 数据关系：R={ROW,COL} 基本操作： InitMaze(M,a,row,col) 初始条件：二维数组a[row+2][col+2]已存在，其中自第1行至第row+1行，每行中自第1列至第col+1列的元素已有值，并且以值0表示通路，以值1表示障碍。 操作结果：构成迷宫的字符型数组，以空白字符表示通路，以字符‘’ 表示障碍，并在迷宫四周加上一圈障碍。 MazePath(M) 初始条件：迷宫M已被赋值。 操作结果：若迷宫M中存在一条通路，则按以下规定改变迷宫M的状态：以字符’’表示路径上的位置，字符‘’表示“死胡同”，否则迷宫的状态不变。 PrintMaze（M） 初始条件：迷宫M已存在。 操作结果：以字符形式输出迷宫。 } ADT maze 3本程序包含三个模块 （1） 栈模块——实现栈抽象数据类型 （2） 迷宫模块——实现迷宫抽象数据类型 （3） 主程序模块： void mian() { } 各模块之间的调用关系 主模块程序→迷宫模块→栈模块 迷宫问题走迷宫的过程可以模拟为一个有哪些信誉好的足球投注网站的过程：每到一处，总让它按东、东南、南、西南、西、西北、北、东北个方向顺序试探下一个位置；如果某方向可以通过，并且不曾到达，则前进一步，在新位置上继续进行有哪些信誉好的足球投注网站；如果个方向都走不通或曾经到达过，则退回一步，在原来的位置上继续试探下