迷宫设计实验报告.doc

天津商业大学 《数据结构》课程设计报告 题 目： 迷宫问题 学 院： 信息工程学院 专 业： 计算机科学与技术 班 级： 13-01班 姓 名： 王 同组人员： 谭 陈 指导教师： 黄 2014 年 12 月 26 日  目 录 1. 课程设计的内容 1 2. 需求分析 1 3. 概要设计 1 3.1抽象数据类型定义 1 3.2 模块划分 1 4. 详细设计 1 4.1 数据类型的定义 1 4.2 主要模块的算法描述 1 4.3 函数之间的调用关系 2 5. 程序运行说明与测试 2 5.1 用户手册 2 5.2 测试结果及分析 2 6. 课程设计总结 2 附 录（源程序清单） 2 课程设计的内容 【问题描述】 以一个m×n的长方阵表示迷宫，0和1表示迷宫中的通路和障碍。设计一个程序，对任意设定的迷宫，求出一条入口到出口的通路，或得出没有通路的结论。 【基本要求】 首先实现一个栈类型，然后编写一个求解迷宫的非递归程序。求得的通路以三元组(i,j,d)的形式输出，其中：(i,j)指示迷宫中的一个坐标，d表示走到下一坐标的方向。如：对于下列数据的迷宫，输出的一条通路为：(1,1,1)，（1,2,2）,（2,2,2）（3,2,3），（3,1,2）…… 需求分析 (1)以二维数组maze[M+2][N+2]表示迷宫，其中maze[i][0]和maze[i][N+1](0=i=N+1)以及maze[0][j]和maze[M+1][j](0=j=M+1)为外加的一圈围墙。数组中元素0表示障碍1表示可通过，迷宫的大小可不限； (2) 迷宫中的数据均由用户自由输入； (3) 迷宫的出口和入口可由用户自由设定； (4) 本程序只求出一条成功的通路； (5) 程序执行的命令为： ① 创建迷宫 ② 求解迷宫 ③ 输出迷宫的解 3. 概要设计 3.1 抽象数据类型定义 (1) 设定栈的抽象数据类型定义： ADT Stack{ 数据对象：D={ai | ai∈CharSet，i = 1,2，…,n，n=0} 数据关系：R1{a(i-1) | a(i-1),ai∈D,i = 2,3…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返回栈顶元素e。 Push(S,e) 初始条件：栈S已存在。 操作结果：在栈S的栈顶插入新的栈顶元素。 Pop(S,e) 初始条件：栈S已存在。 操作结果：删除S的栈顶元素，并以e返回其值。 StackTraverse(S,visit()) 初始条件：栈S已存在。 操作结果：从栈底到栈顶依次对S中的每个元素调用visit() }ADT Stack (2) 设定迷宫的抽象数据类型为： ADT maze{ 数据对象：D = {a(i,j) | a(i,j)∈{0,1}，0=i=m+1,0=j=n+1,m,n=10} 数据关系：R = {M，N} M = {a(i-1,j)，a(i,j)|a(i-1,j)，a(i,j)∈D,i=1,2,…,m+1,j=0,1,…n+1} N = {a(i,j-1),a(i,j) | a(i,j-1),a(i,j)∈D,I = 0,1,…m+1,j = 1,2,…n+1} 基本操作： InitMaze(M,maze,m,n) 初始条件：二维数组maze[m+1][n+1] 已存在，其中自第一行至第m+1行、每行中自第一列至第n+1列的元素已有值，并且以值0表示通路，以值1表示障碍。 操作结果：构成迷宫的字符型数组，以字符0表示通路，以字符1障碍，并在迷宫四周加上一圈障碍。 MazePath(M) 初始条件：迷宫M已被赋值。 操作结果：若迷宫M中存在一条通路，则按如下规定改变迷宫M的状态：以数字0代表可通过，数字1代表不可通过。 　　 模块划分 (1) 主程序