迷宫问题课程设计
- 格式：docx
- 大小：29.82 KB
- 文档页数：12
迷宫问题课程设计
题目: 迷宫问题
初始条件：
以一个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），…。
测试用例见题集p105。
要求完成的主要任务:（包括课程设计工作量及其技术要求，以及说明书撰写
等具体要求）
课程设计报告按学校规定格式用A4纸打印（书写），并应包含如下内容：
1、问题描述
简述题目要解决的问题是什么。
2、设计
存储结构设计、主要算法设计（用类C语言或用框图描述）、测试用例设计；
3、调试报告
调试过程中遇到的问题是如何解决的；对设计和编码的讨论和分析。
4、经验和体会（包括对算法改进的设想）
5、附源程序清单和运行结果。源程序要加注释。如果题目规定了测试数据，则运行结果要包含这些测试数据和运行输出，
6、设计报告、程序不得相互抄袭和拷贝；若有雷同，则所有雷同者成绩均为0分。
时间安排：
1、第19周完成。
2、6月22 日14：00到计算中心检查程序、交课程设计报告、源程序（CD盘）。
指导教师签名：年月日
系主任（或责任教师）签名：年月日
目录
1、问题描述与需求分析 (1)
1.1 问题描述 (2)
1.2 需求分析 (2)
2、设计 (2)
2.1 设计原理 (2)
2.2储存结构设计 (3)
2.2.1 设定栈的抽象数据类型定义： (3)
2.2.2 设定迷宫的抽象数据类型为： (4)
2.3 详细设计 (6)
2.3.1 模块： (6)
2.3.2 主程序模块： (10)
2.3.3 函数调用关系的层次结构框图： (11)
2.4 测试用例设计 (12)
3、调试报告 (12)
3.1 遇到的问题及解决办法 (12)
3.2 对设计和编码的讨论与分析 (13)
4、经验和体会 (13)
5、源程序和运行结果 (14)
5.1 源程序 (14)
5.2 运行结果 (21)
6、参考文献 (24)
迷宫问题 1、问题描述与需求分析
1
1.1 问题描述
以一个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．2 需求分析
（1）以二维数组Maze[m+2][n+2]表示迷宫，其中：Maze[0][j]和Maze[m+1][j](0<=j<=n+1)及Maze[i][0]和Maze[i][n+1]
(0<=i<=n+1)为添加的一圈障碍。数组中一元素值为0表示通路，1表示障碍。
（2）其中迷宫的入口位置和出口位置可由用户随时设定。
（3）迷宫内墙的编写，用1表示内墙，0表示通路。
（4）以链表作存储结构的栈类型，实现求解迷宫的非递归程序。
（5）本程序只求出一条成功的通路，然而，只需要对迷宫求解的函数作小量修改，便可求得全部路径。
2、设计
2.1 设计原理
主要采取三大模块：主程序模块、栈模块和迷宫模块
栈模块：实现迷宫数据的抽象化和对迷宫数据的处理；
迷宫模块：实现迷宫数据抽象类型；
主程序模块：初始化迷宫模块。
栈模块——实现栈抽象数据类型
迷宫模块——实现迷宫抽象数据类型
主程序模块： 2
Void main()
{
初始化；
do{
接受命令；
处理命令；
｝while(命令！=“退出”)；
｝
各模块之间的调用关系如下：
2.2 储存结构设计
2.2.1 设定栈的抽象数据类型定义：ADT Stack{
数据对象：D=｛ a
i |a
i
∈CharSet,i=1,2,…,n,n≥0｝
数据关系：R1={
i-1, a
i
>| a
i-1
, a
i
∈D,i=2,…,n}
基本操作：
InitStack(&S)
操作结果：构造一个空栈S。 3
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
2.2.2 设定迷宫的抽象数据类型为：
ADT maze {
数据对象：D={a
i,j | a
i,j
∈{0,1},0≤i≤m+1,0≤j≤n+1,m,n≤10}
4
数据关系：R={ROW,COL}
ROW={
i-1,j , a
i,j
>| a
i-1,j
, a
i-1
∈D,i=1,…,m+1,j=0,…,n+1}
COL={
i,j-1, a
i,j
>| a
i,j-1
, a i-1
∈D,i=1,…,m+1,j=0,…,n+1}
InitMaze (&M ,a ,row , col )
初始条件：二维数组a[row+2][col+2]已经存在，其中自第一行至第row+1行、每行中自第1列至第col+1列的元素已经有值，并且以值
0表示通路，以值1表示障碍。
操作结果：构成迷宫的字符型数组，并在迷宫四周加上一圈障碍。
MazePath (&M)
初始条件：迷宫M已被赋值。
操作结果：若迷宫M中存在一条通路，则按照所走的步骤，从小到大依次排列。
PrintMaze (M)
初始条件：迷宫M已存在。
操作结果：已字符形式输出迷宫。
｝ADT maze;
设定当前为出始值的入口：
do{
若当前位置可通，
则{将当前位置插入栈顶；
若该位置是出口位置，则结束；
否则切换当前位置的东邻方块为新的当前位置；
}
否则{
若栈不空且栈顶位置尚有其他方向未被探索，
则设定新的当前位置为沿顺时针方向旋转找到的栈顶位置的下一邻块；
若栈不为空且栈顶位置的四周均不可通，
5
则{删除栈顶位置； 若栈不为空，则重新测试新的栈顶位置，
直至找到一个可通的相邻块或出栈至栈空；
}
}
2.3 详细设计
2.3.1模块：
迷宫模块
以二维数组Maze[m+2][n+2]表示迷宫，其中：Maze[0][j]和Maze[m+1][j](0<=j<=n+1)及Maze[i][0]和Maze[i][n+1]
(0<=i<=n+1)为添加的一圈障碍。数组中一元素值为0表示通路，1表示障碍，限定迷宫的大小m,n<=10。其中迷宫的入口位置和出口位置可由用户随时设定。
(1)坐标位置类型:
typedef struct{
int r,c; //迷宫中 r 行 c 列的位置
}PosType; //坐标位置类型
(2)迷宫类型：
typedef struct{
int m,n;
char arr[RANGE][RANGE]; //各位置取值' ','#','@'或'*'
}MazeType; //迷宫类型
栈模块
(1)栈类型SElemType:
typedef struct{
int step; //当前位置在路径上的“序号”
PosType seat; //当前的坐标位置
directiveType di; //往下一坐标位置的方向
}ElemType; //栈的元素类型
(2)构造一个栈SElmType:
struct SqStack //SqStack
