软件综合实习报告
课题名称 迷宫问题 姓 名 何天从 学 号 3110757101 班 级 网络11-1班 院 （系） 信息科学与工程学院 指导教师 陈基漓 王宇 农坚 起止日期 2013.6.3~2013.6.21
软件综合实习
迷宫问题
1、需求分析
1.1 迷宫问题的功能
1.1.1 输入迷宫路径，包括迷宫的长、宽和内容；
【用0和1分别表示迷宫的通路和内墙，用■表示外墙】
1.1.2 自定义输入迷宫的入口和出口的行列坐标；【选作内容，已实现】： 1.1.3 输出迷宫的路径；
（以三元组（i，j，d）的形式输出，其中：（i，j）指示迷宫中的一个坐标，d
表示走到下一坐标的方向j：对于下列数据的迷宫，输出的一条通路为：（1，l，→），（1，2，↓），（2，2，→），（2，3，↓），?。）
1.1.4 输出迷宫的二维图；【选作内容，已实现】
1.1.5 用函数system(\，清空屏幕。【自加内容，已实现】 1.2 设计思路
1.2.1 首先定义一个链表作存储结构的栈类型； 1.2.2 建立二维存储结构，定义指针**maze；
1.2.3利用链表实现队列的构造。每次输入一项迷宫内容，可以存储当
前值的行和列的坐标x、y；
1.2.4 演示程序以用户和计算机的对话方式执行，即在计算机终站上显
示“提示信息”之后，由用户在键盘上输入演示程序中规定的运行命令；最后根据相应的输入数据（滤去输入中的错误选择）建立的迷宫路径以及迷宫的二维图在屏幕上显示。
迷宫的二维图形显示的格式为： 迷宫的路径为：
0 1 2 3 4 (1,1,→) 0 ■ ■ ■ ■ ■ (1,2,↓) 1 ■ 入 ↓ 1 ■ (2,2,↓) 2 ■ 1 ↓ 0 ■ (3,2,→) 3 ■ 0 → 出 ■ (3,3,) 4 ■ ■ ■ ■ ■
1.3 设计思路分析
求迷宫问题就是求出从入口到出口的所有路径。在求解时,即从入口出发,顺某一方向向前试探,若能走通,则继续往前走；否则沿原路退回,换一个方向再继续试探,直至所有可能的通路都试探完为止。如所有可能的通路都探索到而未能到达出口，则所设定的迷宫没有通路。
信息科学与工程学院 - 1- 网络工程11-1班
软件综合实习
【实现存储】
为了实现存储，定义二维数组指针(** [x][y]),利用两层循环存储输入的迷宫内容。
【实现搜索迷宫】
定义栈p、q ，分别存储探索迷宫的最终路径和待定路径，首先从入口开始搜索，先把q的x或y坐标加1或减1，实现向东、南、西、北移动，如果发现p、q的坐标不一样，则把q当前栈顶赋经p，并且给当前坐标设置一个标志maze[x][y]=\，然后搜索下一个，如果发现p、q相等，说明围墙，把p、q弹栈，回溯，然后搜索下一个方向，直到q的x、y坐标与出口的x、y坐标都相等，找到出口。
【实现输出迷宫路径】
利用最后搜索出来的通路。先利用出口坐标与前一个相邻的坐标比较。即后一个坐标的x、y分别与前一个坐标的x、y比较，如果x=1，则说明前一坐标在下一坐标的上方，即前一坐标是方向是向下的。定义int dir，把当前坐标的方向，用一个数字存储此方向。（0:无效,1:向东,2:向南,3:向西,4:向北）。
输出路径时，就是根据dir的值输出方向。
【实现输出迷宫二维图】
根据dir的值，如果dir分别为1、2、3、4，则把迷宫的内容maze[x][y]的值改为“→”“↓”“←”“↑”。从而实现输出二维图的路径显示为“→”“↓”“←”“↑”表示的通路。 最后利用两层循环输出迷宫maze[x][y]的内容，即得到二维图。 信息科学与工程学院
- 2- 网络工程11-1班
软件综合实习
2、概要设计
2.1.为了实现上述程序功能，需要定义链栈的抽象数据类型：
class Stack { private:
LinkNode *top; public:
Stack();
~Stack(); void Push(T e); T Pop(); T GetPop(); void Clear(); bool empty(); };
class T //定义描述迷宫中当前位置的结构类型 { public:
int x; //x代表行坐标 int y; //y代表列坐标 int dir; //路径的方向 };
class LinkNode //链表结点 {
friend class Stack;
//将外部class Stack声明为LinkNode类的友元函数
public:
T data;
LinkNode *next; };
2.2.本程序包含5个函数：
2.2.1、int main()【主函数】
2.2.2、string ** GetMaze(int &m,int &n) 【存储迷宫函数】 2.2.3、bool Mazepath(string **maze,int m,int n) 【搜索路径函数】 2.2.4、void PrintPath(Stack p,int m,int n,string **maze) 【输出函数】
2.2.5、void Restore(string **maze,int m,int n)【恢复函数】
信息科学与工程学院 - 3- 网络工程11-1班
软件综合实习
2.3.各函数间关系如下：
（注：虚线表示函数间调用，箭头所指向的为被调用函数）
3、详细设计
源代码：
#include
//╞╪╪╪╪╪╪╪╪【定义迷宫数据结构】╪╪╪╪╪╪╪╪╪╪╪╪╪╪╪╡ class T {
public:
int x; //x代表当前位置的行坐标 int y; //y代表当前位置的列坐标
int dir; //0:无效,1:东,2:南,3:西,4:北 };
//╞╪╪╪╪╪╪╪╪╪【定义链表结点】╪╪╪╪╪╪╪╪╪╪╪╪╪╪╪╪╪╡ class LinkNode {
friend class Stack; //将外部Stack类声明为LinkNode类的友元函数 public:
T data;
LinkNode *next; };
信息科学与工程学院 - 4- 网络工程11-1班