《[毕业设计精品]迷宫问题》由会员分享，可在线阅读，更多相关《[毕业设计精品]迷宫问题（27页珍藏版）》请在金锄头文库上搜索。
1、数据结构课程设计课 程 设 计题 目迷宫问题学 院计算机科学与技术学院专 业计算机科学与技术班 级计算机科学与技术0909班姓 名指导教师2011年7月2日课程设计任务书题 目: 迷宫问题 初始条件： 以一个mn的长方阵表示迷宫，0和1分别表示迷宫中的通路和障碍。设计一个程序，对任意设定的迷宫，求出一条从入口到出口的通路，或得出没有通路的结论。 首先实现一个以链表作存储结构的栈类型，然后编写一个求解迷宫的非递归程序。求得的通路以三元组（i,j,d）的形式输出，其中：（i,j）指示迷宫中的一个坐标，d表示走到下一坐标的方向。如：对于下列数据的迷宫，输出的一条通路为：（1,1,1），（1,2,2）
2、，（2,2,2），（3,2,3），（3,1,2），。 测试用例见题集p105。要求完成的主要任务: （包括课程设计工作量及其技术要求，以及说明书撰写等具体要求）课程设计报告按学校规定格式用A4纸打印（书写），并应包含如下内容： 1、 问题描述简述题目要解决的问题是什么。2、 设计存储结构设计、主要算法设计（用类C语言或用框图描述）、测试用例设计；3、 调试报告调试过程中遇到的问题是如何解决的；对设计和编码的讨论和分析。4、 经验和体会（包括对算法改进的设想）5、 附源程序清单和运行结果。源程序要加注释。如果题目规定了测试数据，则运行结果要包含这些测试数据和运行输出，6、 设计报告、程序不得相互
3、抄袭和拷贝；若有雷同，则所有雷同者成绩均为0分。时间安排：1、第19周完成。2、7月1 日14：00到计算中心检查程序、交课程设计报告、源程序（CD盘）。指导教师签名： 年 月 日系主任（或责任教师）签名： 年 月 日目录1、问题描述与需求分析31.1 问题描述312 需求分析32、设计32.1 设计原理32.2 储存结构设计42.2.1 设定栈的抽象数据类型定义：42.2.2 设定迷宫的抽象数据类型为：62.3 详细设计72.3.2、栈模块：82.3.3 主程序模块：122.3.4 函数调用关系的层次结构框图：142.4 测试用例设计143、调试报告153.1 遇到的问题及解决办法153.2
4、 对设计和编码的讨论与分析154、经验和体会165、源程序和运行结果165.1 源程序165.2 运行结果216、参考文献23题目：迷宫问题1、问题描述与需求分析1.1 问题描述 以一个mn的长方阵表示迷宫，0和1分别表示迷宫中的通路和障碍。设计一个程序，对任意设定的迷宫，求出一条从入口到出口的通路，或得出没有通路的结论。 首先实现一个以链表作存储结构的栈类型，然后编写一个求解迷宫的非递归程序。求得的通路以三元组（i,j,d）的形式输出，其中：（i,j）指示迷宫中的一个坐标，d表示走到下一坐标的方向。如：对于下列数据的迷宫，输出的一条通路为：（1,1,1），（1,2,2），（2,2,2），（3
5、,2,3），（3,1,2），12 需求分析 （1）以二维数组Mazem+2n+2表示迷宫，其中：Maze0j和Mazem+1j(0=j=n+1)及Mazei0和Mazein+1 (0=i=n+1)为添加的一圈障碍。数组中一元素值为0表示通路，1表示障碍。（2）其中迷宫的入口位置和出口位置可由用户随时设定。（3）迷宫内墙的编写，用1表示内墙，0表示通路。（4）以链表作存储结构的栈类型，实现求解迷宫的非递归程序。（5）本程序只求出一条成功的通路，然而，只需要对迷宫求解的函数作小量修改，便可求得全部路径。2、设计2.1 设计原理主要采取三大模块：主程序模块、栈模块和迷宫模块栈模块：实现迷宫数据的抽象
6、化和对迷宫数据的处理； 迷宫模块：实现迷宫数据抽象类型；主程序模块：初始化迷宫模块。栈模块实现栈抽象数据类型迷宫模块实现迷宫抽象数据类型主程序模块：Void main() 初始化； do 接受命令； 处理命令； while(命令！=“退出”)；各模块之间的调用关系如下：主程序模块迷宫模块栈模块2.2 储存结构设计2.2.1 设定栈的抽象数据类型定义：ADT Stack 数据对象：D= ai|ai CharSet,i=1,2,n,n0 数据关系：R1=| ai-1 , ai D,i=2,n 基本操作： InitStack(&S) 操作结果：构造一个空栈S。 DestroyStack(&S) 初始
7、条件：栈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返回其值。 Stack
8、Traverse(S,visit() 初始条件：栈S已存在。 操作结果：从栈底到栈顶一次对S中的每个元素调用函数visit（）。ADT Stack2.2.2 设定迷宫的抽象数据类型为：ADT maze 数据对象：D=ai,j | ai,j 0,1,0im+1,0jn+1,m,n10 数据关系：R=ROW,COL ROW= | ai-1,j , ai-1D,i=1,m+1,j=0,n+1 COL= | ai,j-1 , ai-1D,i=1,m+1,j=0,n+1 InitMaze (&M ,a ,row , col )初始条件：二维数组arow+2col+2已经存在，其中自第一行至第row+1行
9、、每行中自第1列至第col+1列的元素已经有值，并且以值0表示通路，以值1表示障碍。操作结果：构成迷宫的字符型数组，并在迷宫四周加上一圈障碍。 MazePath (&M)初始条件：迷宫M已被赋值。操作结果：若迷宫M中存在一条通路，则按照所走的步骤，从小到大依次排列。 PrintMaze (M)初始条件：迷宫M已存在。操作结果：已字符形式输出迷宫。ADT maze;2.2.3 寻找公共路径的思想图如下：设定当前为出始值的入口：do 若当前位置可通， 则将当前位置插入栈顶； 若该位置是出口位置，则结束； 否则切换当前位置的东邻方块为新的当前位置； 否则 若栈不空且栈顶位置尚有其他方向未被探索， 则设定新的当前位置为沿顺时针方向旋转找到的栈顶位置的下一邻块； 若栈不为空且栈顶位置的四周均不可通， 则删除栈顶位置； 若栈不为空，则重新测试新的栈顶位置， 直至找到一个可通的相邻块或出栈至栈空； 2.3 详细设计2.3.1迷宫模块：以二维数组Mazem+2n+2表示迷宫，其中：Maze0j和Mazem+1j(0=j=n+1)及Mazei0和Mazein+1 (0=i=n+1)为添加的一圈障碍。数组中一元素值为0表示通路，1表示障碍，限定迷宫的大小m,n=(*S).stacksize) /*
