桂林理工大学-软件综合实习何天从

软件综合实习报告

课题名称 迷宫问题 姓 名 何天从 学 号 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 #include #include using namespace std;

//╞╪╪╪╪╪╪╪╪【定义迷宫数据结构】╪╪╪╪╪╪╪╪╪╪╪╪╪╪╪╡ 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班

软件综合实习

//╞╪╪╪╪╪╪╪【定义栈数据结构】╪╪╪╪╪╪╪╪╪╪╪╪╪╪╪╪╪╡ class Stack { private:

LinkNode *top; //指向第一个结点的栈顶指针 public:

Stack(); //构造函数，置空栈 ~Stack(); //析构函数

void Push(T e); //把元素data压入栈中 T Pop(); //使栈顶元素出栈 T GetPop(); //取出栈顶元素 void Clear(); //把栈清空 bool empty(); //判断栈是否为空，空返回1，否则返回0 };

//╞╪╪╪╪╪╪╪╪【初始化Stack()】╪╪╪╪╪╪╪╪╪╪╪╪╪╪╪╪╡ Stack::Stack() //构造函数，置空栈 {

top=NULL; }

//╞╪╪╪╪╪╪╪╪╪【初始化~Stack()】╪╪╪╪╪╪╪╪╪╪╪╪╪╪╪╡ Stack::~Stack() //析构函数 { }

//╞╪╪╪╪╪╪╪╪╪【压栈函数】╪╪╪╪╪╪╪╪╪╪╪╪╪╪╪╪╪╪╡ void Stack::Push(T e) //把元素e压入栈中 { LinkNode *P; P=new LinkNode;

P->data=e; //链栈【头插法】，把e插到链头 P->next=top; top=P; }

//╞╪╪╪╪╪╪╪╪╪【出栈函数】╪╪╪╪╪╪╪╪╪╪╪╪╪╪╪╪╪╡

T Stack::Pop() //使栈顶元素出栈 { T Temp;

LinkNode *P; P=top;

top=top->next; //链栈【头取法】，把top所指data赋给Temp Temp=P->data; delete P; return Temp;

信息科学与工程学院 - 5- 网络工程11-1班

软件综合实习

}

//╞╪╪╪╪╪╪╪╪╪【取栈顶元素函数】╪╪╪╪╪╪╪╪╪╪╪╪╪╪╪╡ T Stack::GetPop() {

return top->data; }

//╞╪╪╪╪╪╪╪╪╪╪【清空栈函数】╪╪╪╪╪╪╪╪╪╪╪╪╪╪╪╡ void Stack::Clear() { top=NULL; }

//╞╪╪╪╪╪╪╪╪【判断栈空函数】╪╪╪╪╪╪╪╪╪╪╪╪╪╪╪╪╡ bool Stack::empty() //判断栈是否为空，如果为空则返回1，否则返回0 { if(top==NULL) return 1; else

return 0; }

//╞╪╪╪╪╪╪╪╪╪【函数声名】╪╪╪╪╪╪╪╪╪╪╪╪╪╪╪╪╪╡ int move[4][2]={{0,1},{1,0},{0,-1},{-1,0}};

//定义当前位置移动的4个方向.【分别先向东、南、西、北】

bool Mazepath(string **maze,int m,int n);

//寻找迷宫maze中从（0，0）到（m,n）的路径， //如果到则返回true,否则返回false

void PrintPath(Stack p,int m,int n,string **maze); //输出迷宫的路径 void Restore(string **maze,int m,int n); //恢复迷宫 string ** GetMaze(int &m,int &n);

//获取迷宫，返回存取迷宫的二维指针

int a1,b1; //a1、b1分别为入口的行和列坐标 int c1,d1; //c1、d1分别为出口的行和列坐标

//╞╪╪╪╪╪╪╪╪【主函数】╪╪╪╪╪╪╪╪╪╪╪╪╪╪╪╪╪╪╪╡ int main(){

int m=0,n=0; //定义迷宫的长和宽

string **maze; //定义二维指针存取迷宫

printf(\◢■■◣◢■■◣ ◢■ ◢■■◣ ◢■■◣ ◢■■◣ ◢■ \\n\

printf(\ ■■ ■ ■ ■ ■ ■ ■ \\n\

printf(\◢■■◤■ ■ ■ ■■■■ 年 ■■■■ 月 ◢■■◤ ■ 号 \\n\

printf(\■ ■ ■ ■ ■ ■ ■ ■ ■ \\n\

printf(\◥■■■◥■■◤◥■■■◤◥■■◤ ◥■■◤ ◥■■■◥■■■◤ \\n\

信息科学与工程学院 - 6- 网络工程11-1班

软件综合实习

printf(\

printf(\━━━━━━━━━【作者】━━━━━━━━━━━━━━ \\n\

printf(\┃ ┃ \\n\

printf(\┃ ● 何天从 ┃ \\n\

printf(\┃ ● 网络工程专业 11-1班 ┃ \\n\

printf(\┃ ● 学号：3110757101 ┃ \\n\

printf(\┃ ● 信息科学与工程学院 ┃ \\n\

printf(\┃ ● 桂林理工大学 ┃ \\n\

printf(\┃ ┃ \\n\

printf(\━━━━━━━━━━━━━━━━━━━━━━━━━━━ \\n\ printf(\

printf(\┣━━━━━━━━━【迷宫路径探索】━━━━━━━━━┫ \\n\

printf(\┃ ┃ \\n\

printf(\┃ ⑴〖输入迷宫路径〗 ┃ \\n\

printf(\┃ ⑵〖清空屏幕〗 ┃ \\n\

printf(\┃ ⑶〖结束探索〗 ┃ \\n\

printf(\┃ ┃ \\n\

printf(\┣━━━━━━━━━━━━━━━━━━━━━━━━━━┫ \\n\

printf(\ while(1) { int j;

printf(\【请选择】操作：\ scanf(\ switch(j) {

case 1: { maze=GetMaze(m,n);

//调用GetMaze(int &m,int &n)函数，得到迷宫

信息科学与工程学院 - 7- 网络工程11-1班

软件综合实习

if(Mazepath(maze,m,n))

//调用Mazepath(int **maze,int m,int n)函数获取路径

{ } else {

cout<<\《抱歉》！此路径不通!\\n\\n\

printf(\┣━━━━━━━━━【迷宫路径探索】━━━━━━━━━┫ \\n\

printf(\┃ ┃ \\n\

printf(\┃ ⑴〖输入迷宫路径〗 ┃ \\n\

printf(\┃ ⑵〖清空屏幕〗 ┃ \\n\

printf(\┃ ⑶〖结束探索〗 ┃ \\n\

printf(\┃ ┃ \\n\

printf(\┣━━━━━━━━━━━━━━━━━━━━━━━━━━┫ \\n\

printf(\ }

printf(\ break; } case 2:

{ system(\//清屏函数

printf(\┣━━━━━━━━━【迷宫路径探索】━━━━━━━━━┫ \\n\

printf(\┃ ┃ \\n\

printf(\┃ ⑴〖输入迷宫路径〗 ┃ \\n\

printf(\┃ ⑵〖清空屏幕〗 ┃ \\n\

printf(\┃ ⑶〖结束探索〗 ┃ \\n\

printf(\┃ ┃ \\n\

printf(\┣━━━━━━━━━━━━━━━━━━━━━━━━━━┫ \\n\

printf(\ break; } case 3:

信息科学与工程学院 - 8- 网络工程11-1班

软件综合实习

return 0; default:

printf(\【输入有误】，请重新输入！\\n\ } } return 0; }

//╞╪╪╪╪╪╪╪【存储迷宫函数】╪╪╪╪╪╪╪╪╪╪╪╪╪╪╪╪╪╪╡ string ** GetMaze(int &m,int &n) //返回存取迷宫的二维指针 {

string **maze; //定义二维指针存取迷宫 int i=0,j=0;

cout<<\【请输入】迷宫的长和宽:\ int a,b;

cin>>a>>b; //输入迷宫的宽a和高b cout<<\【请输入】迷宫内容:\\n\

//m，n分别代表迷宫的行数m和列数n

n=a; m=b;

maze=new string *[m+2]; //申请长度等于行数加2的二级指针【这句就是给一个指向指针的指针动态分配m+2个存放int类型指针的数组，用于动态申请二维数组。】

for(i= 0;i

maze[i]=new string[n+2]; }

for(i=1;i<=m;i++) //输入迷宫的内容，0代表可通，1代表不通 {

for(j=1;j<=n;j++) {

cin>>maze[i][j]; } }

for(i=0;i

maze[i][0]=maze[i][n+1]=\■\//使纵向围墙为1，就是0列和6列纵向 }

for(i=0;i

maze[0][i]=maze[m+1][i]=\■\//使横向围墙为1，就是0行和6行横向 }

return maze; //返回存贮迷宫的二维指针maze };

//╞╪╪╪╪╪╪【寻找迷宫路径函数】╪╪╪╪╪╪╪╪╪╪╪╪╪╪╪╡ bool Mazepath(string **maze,int m,int n)

信息科学与工程学院 - 9- 网络工程11-1班

软件综合实习

{ Stack q,p; //定义栈p、q,分别存探索迷宫的过程和存储路径 T Temp1,Temp2; int x,y,loop;

printf(\【请输入】入口行坐标，列坐标：\ cin>>a1>>b1;

while(a1>m||b1>n) {

printf(\【输入坐标有误】\

printf(\【请重新输入】入口行坐标，列坐标：\ cin>>a1>>b1; }

printf(\

printf(\【请输入】出口行坐标，列坐标：\ cin>>c1>>d1;

while(c1>m||d1>n) {

printf(\【输入坐标有误】\

printf(\【请重新输入】出口行坐标，列坐标：\ cin>>c1>>d1; }

printf(\ Temp1.x=a1; Temp1.y=b1;

q.Push(Temp1); //将入口位置入栈 p.Push(Temp1);

maze[a1][b1]=\//标志入口位置已到达过 while(!q.empty()) //栈q非空，则反复探索 { Temp2=q.GetPop(); //获取栈顶元素

if(!(p.GetPop().x==q.GetPop().x&&p.GetPop().y==q.GetPop().y)) { p.Push(Temp2);

//如果有新位置入栈，则把上一个探索的位置存入栈p }

for(loop=0;loop<4;loop++) //探索当前位置的4个相邻位置 { x=Temp2.x+move[loop][0];

//计算出新位置行x位置值（move分别=0、1、0、-1）

y=Temp2.y+move[loop][1];

//计算出新位置列y位置值（move分别=1、0、-1、0）

if(maze[x][y]==\//判断新位置是否可达 { Temp1.x=x; //把可行路径的行x、列y坐标赋给Temp Temp1.y=y;

maze[x][y]=\//标志新位置已到达过 q.Push(Temp1); //新位置入栈【临时栈q】 }

if((x==c1)&&(y==d1)) //成功到达出口

信息科学与工程学院 - 10- 网络工程11-1班

软件综合实习

{ Temp1.x=c1; //把出口的行x、列y坐标赋给Temp Temp1.y=d1; Temp1.dir=0;

p.Push(Temp1); //把最后一个位置入栈p PrintPath(p,m,n,maze); //输出路径 Restore(maze,m,n); //恢复路径

return 1; //表示成功找到路径 } }

if(p.GetPop().x==q.GetPop().x&&p.GetPop().y==q.GetPop().y)

//如果没有新位置入栈，则返回到上一个位置

{

p.Pop(); q.Pop(); } }

return 0; //表示查找失败，即迷宫无路经 }

//╞╪╪╪╪╪╪╪╪╪【输出路径函数】╪╪╪╪╪╪╪╪╪╪╪╪╪╪╪╡ void PrintPath(Stack p,int m,int n,string **maze)

{ Stack t; //定义一个栈，按从入口到出口存储路径 int a,b; T data;

LinkNode *temp;

temp=new LinkNode; //申请空间

temp->data=p.Pop(); //取栈p的顶点元素，即第一个位置 t.Push(temp->data); //第一个位置入栈t delete temp; //释放空间

while(!p.empty()) //栈p非空，则反复回首转移 {

temp=new LinkNode;

temp->data=p.Pop(); //获取下一个位置，得到行走方向 a=t.GetPop().x-temp->data.x; //行坐标方向 b=t.GetPop().y-temp->data.y; //列坐标方向 if(a==1)

{ temp->data.dir=1; //方向向下，用1表示 }

else if(b==1)

{ temp->data.dir=2; //方向向右，用2表示 }

else if(a==-1)

{ temp->data.dir=3; //方向向上，用3表示 }

else if(b==-1)

信息科学与工程学院 - 11- 网络工程11-1班

软件综合实习

{ temp->data.dir=4; //方向向左，用4表示 }

t.Push(temp->data); //把新位置入栈 delete temp; }

/* *****************************************************************

以下15行代码的作用是，把t赋给x和y。 x的作用是：赋给z（下面定义），提出输出迷宫的路径信息的栈。 y的作用是：定义迷宫通路的指向，提出输出迷宫二维图的栈。

********************************************************************* */ Stack x,y; LinkNode *w,*k;

w=new LinkNode; //申请空间 k=new LinkNode; //申请空间 while(!t.empty())

{ w->data=t.Pop(); //取栈p的顶点元素，即第一个位置 k->data=w->data;

x.Push(w->data); //第一个位置入栈t y.Push(k->data); delete w; delete k;

w=new LinkNode; //重新申请空间 k=new LinkNode; //重新申请空间 }

//╞╪╪╪╪╪╪╪【给可达的通路赋与行走方向】╪╪╪╪╪╪╪╪╪╪╪╪╡ while(!y.empty()) { data=y.Pop();

if(data.dir==1) maze[data.x][data.y]=\↓\ else if(data.dir==2)

maze[data.x][data.y]=\→\ else if(data.dir==3)

maze[data.x][data.y]=\↑\ else if(data.dir==4)

maze[data.x][data.y]=\←\ }

Stack z; //把x反向赋给z。（从z的栈顶是入口坐标） LinkNode *u;

u=new LinkNode; //申请空间 while(!x.empty())

{ u->data=x.Pop(); //取栈p的顶点元素，即第一个位置 z.Push(u->data); //第一个位置入栈t delete u;

u=new LinkNode; //重新申请空间

信息科学与工程学院 - 12- 网络工程11-1班

软件综合实习

} cout<<\《恭喜》！迷宫路径探索成功!\\n\\n\

printf(\┣━━━━━━━━━【迷宫路径输出】━━━━━━━━━┫ \\n\

printf(\┃ ┃ \\n\

printf(\┃ ⑴〖输出迷宫的二维图〗 ┃ \\n\

printf(\┃ ⑵〖输出迷宫的路径〗 ┃ \\n\

printf(\┃ ⑶〖重新输入迷宫路径〗 ┃ \\n\

printf(\┃ ⑷〖退空屏幕〗 ┃ \\n\

printf(\┃ ⑸〖结束探索〗 ┃ \\n\

printf(\┃ ┃ \\n\

printf(\┣━━━━━━━━━━━━━━━━━━━━━━━━━━┫ \\n\

printf(\ while(1) { int j;

printf(\【请选择】操作：\ scanf(\ printf(\ switch(j) {

case 1:

{ int i=0,j=0,count=0;

cout<<\【输出】迷宫的方阵为： \\n\ cout<<\

for(int c=0;c

cout<

cout<

cout<

for(i=0;i

for(j=0;j

if(maze[i][j]==\

信息科学与工程学院 - 13- 网络工程11-1班

软件综合实习

maze[i][j]=48; maze[a1][b1]=\入\ maze[c1][d1]=\出\

if(maze[i][j]==\ cout<<\

cout<

if(count%(n+2)==0) { r++;

cout<

cout<

cout<<\【■：围墙，入：入口，→:向右走，↓：向下走，←：向左走，↑：向上走 】\\n\\n\ break; } case 2:

{ cout<<\【输出】迷宫的路径为：\\n\\n\ while(!z.empty())

//栈非空，循环输出路径，包括行坐标、列坐标、下一个位置方向

{

data=z.Pop();

cout<<\

//输出行x坐标，列y坐标

switch(data.dir) //用循环输出相应的方向 { case 1:

cout<<\↓)\\n\ break; case 2:

cout<<\→)\\n\ break; case 3:

cout<<\↑)\\n\ break; case 4:

cout<<\←)\\n\ break; case 0:

cout<<\ break; }

信息科学与工程学院 - 14- 网络工程11-1班

软件综合实习

} cout<<\【括号内容:(行坐标,列坐标,方向)】\\n\ break; } case 3:

{ int m=0,n=0; //定义迷宫的长和宽 string **maze; //定义二维指针存取迷宫 maze=GetMaze(m,n);

//调用GetMaze(int &m,int &n)函数，得到迷宫

if(Mazepath(maze,m,n))

//调用Mazepath(int **maze,int m,int n)函数获取路径

{

printf(\┣━━━━━━━━━【迷宫路径探索】━━━━━━━━━┫ \\n\

printf(\┃ ┃ \\n\

printf(\┃ ⑴〖输入迷宫路径〗 ┃ \\n\

printf(\┃ ⑵〖结束探索〗 ┃ \\n\

printf(\┃ ⑶〖清空屏幕〗 ┃ \\n\

printf(\┃ ┃ \\n\

printf(\┣━━━━━━━━━━━━━━━━━━━━━━━━━━┫ \\n\

printf(\ }

case 4:

{ system(\ //清屏函数

printf(\┣━━━━━━━━━【迷宫路径输出】━━━━━━━━━┫ \\n\

printf(\┃ ┃ \\n\

printf(\┃ ⑴〖输出迷宫的二维图〗 ┃ \\n\

printf(\┃ ⑵〖输出迷宫的路径〗 ┃ \\n\

printf(\┃ ⑶〖重新输入迷宫路径〗 ┃ \\n\

printf(\┃ ⑷〖退空屏幕〗 ┃ \\n\

printf(\┃ ⑸〖结束探索〗 ┃ \\n\

信息科学与工程学院 - 15- 网络工程11-1班

软件综合实习

printf(\┃ ┃ \\n\

printf(\┣━━━━━━━━━━━━━━━━━━━━━━━━━━┫ \\n\

printf(\ break; } case 5:

exit(0); default:

printf(\【输入有误】，请重新输入！\\n\ } } }

//╞╪╪╪╪╪╪╪╪╪╪╪【恢复函数】╪╪╪╪╪╪╪╪╪╪╪╪╪╪╡ void Restore(string **maze,int m,int n) {

int i,j;

for(i=0;i

if(maze[i][j]==\ //恢复探索过位置，即把-1恢复为0 maze[i][j]=\ } }

4、调试分析

在调试过程中，遇到很多问题，应该设置什么数据结构和类型，一直在纠结，经过反复思考和调试，最后都解决了。 4.1.用“1”“0”来表示迷宫的障碍和通路，便于用户操作，用“→”“↓”

“←”“↑”表示方向，“■”表示外墙，比较方便用户观察。

4.2.在设定入口和出口坐标时，定义了全局变量类型，方便函数间调用。 4.3.还有就是数据结构问题，实现输出时的二维通路，开始是想通过dir的值实现输出0、1的二维图，但是觉得不直观，所以定义了string **maze[x][y]，从而可以存储字符，把“→”“↓”“←”“↑”的通路存储起来，实现了直观的二维通路的想法。 信息科学与工程学院

- 16- 网络工程11-1班

软件综合实习

5、使用说明

5.1.程序名为 迷宫问题.exe，运行环境为DOS。 5.2.程序执行后显示主菜单：

5.2.1主菜单功能选择：

选择⑴〖输入迷宫路径〗 选择⑵〖结束探索〗 选择⑶〖清空屏幕〗 5.2.2子菜单功能选择：

选择⑴〖输出迷宫的二维图〗 选择⑵〖输出迷宫的路径〗 选择⑶〖重新输入迷宫路径〗 选择⑷〖退空屏幕〗 选择⑸〖结束探索〗

信息科学与工程学院 - 17- 网络工程11-1班

软件综合实习

6、测试结果

⑴〖输入迷宫路径〗

6.2输出子菜单：

⑴〖输出迷宫的二维图〗

信息科学与工程学院 - 18- 网络工程11-1班

软件综合实习

⑵〖输出迷宫的路径〗

⑶〖重新输入迷宫路径〗

信息科学与工程学院 - 19- 网络工程11-1班

软件综合实习

7、实习总结

通过迷宫问题的编程，认真回顾和重新思考数据结构的使用，比如对栈、指针、链表等的深入了解，让我感受到了数据结构及其算法的重要。此外还熟悉了各种方法的应用。

在编程过程中，我认识到程序员要有丰富的想象力，不拘泥于固定的思维方式，试试别人从没想过的方法。丰富的想象力是建立在丰富的知识的基础上，实习期间，我通过多个途径来帮助自己建立较丰富的知识结构，查阅了大量的书籍，并通过网上的资料学习到了很多。

在编程时我也看到了有良好的编程风格是十分重要的，特别是写注解，一些新的灵感还是需要立即记下的，或者反复阅读注解后，会有新的思想。在时间效率上也提高了。

在实习这三周里，我遇到了很多的困难，当自己认真思考后还在纠结时，我会跟同学们一起交流，或者向老师请教。在这里非常地感谢老师和同学们的帮助！

2013年6月27日星期四

信息科学与工程学院 - 20- 网络工程11-1班

软件综合实习

由于上面的原代码编排过，可以编译时出错,下面附没有编排的：

#include #include

#include //exit(0) 控制程序直接退出 using namespace std;

信息科学与工程学院 - 21- 网络工程11-1班

软件综合实习

//╞╪╪╪╪╪╪╪╪╪╪╪╪╪╪【定义迷宫数据结构】╪╪╪╪╪╪╪╪╪╪╪╪╪╪╪╪╪╪╡

class T //定义描述迷宫中当前位置的结构类型 {

public:

int x; //x代表当前位置的行坐标 int y; //y代表当前位置的列坐标 int dir; //0:无效,1:东,2:南,3:西,4:北 };

//╞╪╪╪╪╪╪╪╪╪╪╪╪╪╪【定义链表结点】╪╪╪╪╪╪╪╪╪╪╪╪╪╪╪╪╪╪╪╪╡

class LinkNode //链表结点 {

friend class Stack; //将外部class Stack声明为LinkNode类的友元函数 public:

T data;

LinkNode *next; };

信息科学与工程学院 - 22- 网络工程11-1班

软件综合实习

//╞╪╪╪╪╪╪╪╪╪╪╪╪╪╪【定义栈数据结构】╪╪╪╪╪╪╪╪╪╪╪╪╪╪╪╪╪╪╪╡

class Stack {

private:

LinkNode *top; //指向第一个结点的栈顶指针

public:

Stack(); //构造函数，置空栈 ~Stack(); //析构函数

void Push(T e); //把元素data压入栈中 T Pop(); //使栈顶元素出栈 T GetPop(); //取出栈顶元素 void Clear(); //把栈清空

bool empty(); //判断栈是否为空，如果为空则返回1，否则返回0 };

//╞╪╪╪╪╪╪╪╪╪╪╪╪╪╪【初始化Stack()】╪╪╪╪╪╪╪╪╪╪╪╪╪╪╪╪╪╪╪╡

Stack::Stack() //构造函数，置空栈

信息科学与工程学院 - 23- 网络工程11-1班

软件综合实习

{

top=NULL; }

//╞╪╪╪╪╪╪╪╪╪╪╪╪╪╪【初始化~Stack()】╪╪╪╪╪╪╪╪╪╪╪╪╪╪╪╪╪╪╡

Stack::~Stack() //析构函数 { }

//╞╪╪╪╪╪╪╪╪╪╪╪╪╪╪【压栈函数】╪╪╪╪╪╪╪╪╪╪╪╪╪╪╪╪╪╪╪╪╪╡

void Stack::Push(T e) //把元素e压入栈中 {

LinkNode *P; P=new LinkNode;

P->data=e; //链栈【头插法】，把e插到链头 P->next=top; top=P; }

信息科学与工程学院 - 24- 网络工程11-1班

软件综合实习

//╞╪╪╪╪╪╪╪╪╪╪╪╪╪╪【出栈函数】╪╪╪╪╪╪╪╪╪╪╪╪╪╪╪╪╪╪╪╪╪╡

T Stack::Pop() //使栈顶元素出栈 {

T Temp; LinkNode *P; P=top;

top=top->next; //链栈【头取法】，把top所指data赋给Temp

Temp=P->data; delete P; return Temp; }

//╞╪╪╪╪╪╪╪╪╪╪╪╪╪╪【取栈顶元素函数】╪╪╪╪╪╪╪╪╪╪╪╪╪╪╪╪╪╡

T Stack::GetPop() //取出栈顶元素 {

return top->data; }

信息科学与工程学院 - 25- 网络工程11-1班

软件综合实习

//╞╪╪╪╪╪╪╪╪╪╪╪╪╪╪【清空栈函数】╪╪╪╪╪╪╪╪╪╪╪╪╪╪╪╪╪╪╪╡

void Stack::Clear() //把栈清空 {

top=NULL; }

//╞╪╪╪╪╪╪╪╪╪╪╪╪╪╪【判断栈空函数】╪╪╪╪╪╪╪╪╪╪╪╪╪╪╪╪╪╪╡

bool Stack::empty() //判断栈是否为空，如果为空则返回1，否则返回0 {

if(top==NULL)

return 1;

else }

//╞╪╪╪╪╪╪╪╪╪╪╪╪╪╪【函数声名】╪╪╪╪╪╪╪╪╪╪╪╪╪╪╪╪╪╪╪╡

return 0;

信息科学与工程学院 - 26- 网络工程11-1班

软件综合实习

int move[4][2]={{0,1},{1,0},{0,-1},{-1,0}}; //定义当前位置移动的4个方向.【分别先向东、南、西、北】

bool Mazepath(string **maze,int m,int n); //寻找迷宫maze中从（0，0）到（m,n）的路径，

如果到则返回true,否则返回false

void PrintPath(Stack p,int m,int n,string **maze); //输出迷宫的路径

void Restore(string **maze,int m,int n); //恢复迷宫

string ** GetMaze(int &m,int &n); //获取迷宫，返回存取迷宫的二维指针

//╞╪╪╪╪╪╪╪╪╪╪╪╪╪╪【主函数】╪╪╪╪╪╪╪╪╪╪╪╪╪╪╪╪╪╪╪╪╡

int main() {

int m=0,n=0; //定义迷宫的长和宽 string **maze; //定义二维指针存取迷宫 printf(\◢■■◣◢■■◣ ◢■ ◢■■◣ ◢■■◣ ◢■■◣ ◢■ \\n\

int a1,b1;

int c1,d1;

信息科学与工程学院 - 27- 网络工程11-1班

软件综合实习

printf(\ ■■ ■ ■ ■ ■ ■ ■ \\n\

printf(\◢■■◤■ ■ ■ ■■■■ 年 ■■■■ 月 ◢■■◤ ■ 号 \\n\

printf(\■ ■ ■ ■ ■ ■ ■ ■ ■ \\n\

printf(\◥■■■◥■■◤◥■■■◤◥■■◤ ◥■■◤ ◥■■■◥■■■◤ \\n\

printf(\

printf(\━━━━━━━━━【作者】━━━━━━━━━━━━━━ \\n\

printf(\┃ ┃ \\n\

printf(\┃ ● 何天从 ┃ \\n\

printf(\┃ ● 网络工程专业 11-1班 ┃ \\n\

printf(\┃ ● 学号：3110757101 ┃ \\n\

printf(\┃ ● 信息科学与工程学院 ┃ \\n\

printf(\┃ ● 桂林理工大学 ┃ \\n\

printf(\┃ ┃ \\n\

printf(\━━━━━━━━━━━━━━━━━━━━━━━━━━━ \\n\

printf(\

信息科学与工程学院 - 28- 网络工程11-1班

软件综合实习

printf(\┣━━━━━━━━━【迷宫路径探索】━━━━━━━━━┫ \\n\

printf(\┃ ┃ \\n\

printf(\┃ ⑴〖输入迷宫路径〗 ┃ \\n\

printf(\┃ ⑵〖清空屏幕〗 ┃ \\n\

printf(\┃ ⑶〖结束探索〗 ┃ \\n\

printf(\┃ ┃ \\n\

printf(\┣━━━━━━━━━━━━━━━━━━━━━━━━━━┫ \\n\

printf(\

while(1) {

int j;

printf(\【请选择】操作：\scanf(\switch(j) {

case 1:

{

maze=GetMaze(m,n); //调用GetMaze(int &m,int &n)函数，

得到迷宫

信息科学与工程学院 - 29- 网络工程11-1班

软件综合实习

if(Mazepath(maze,m,n)) //调用Mazepath(int **maze,int

m,int n)函数获取路径 {

} else {

探索】━━━━

━━━━━┫ \\n\

┃ \\n\

径〗

┃ \\n\

┃ \\n\

┃ \\n\

信息科学与工程学院

cout<<\《抱歉》！此路径不通!\\n\\n\ printf(\┣━━━━━━━━━【迷宫路径

printf(\┃

printf(\┃ ⑴〖输入迷宫路

printf(\┃ ⑵〖清空屏幕〗 printf(\┃ ⑶〖结束探索〗

- 30- 网络工程11-1班

软件综合实习

printf(\┃

┃ \\n\ ━━━━━━━━

printf(\┣━━━━━━━━━━━━━

━━━━━┫ \\n\

printf(\ }

printf(\ break;

}

case 2:

{

system(\清屏函数

printf(\┣━━━━━━━━━【迷宫路径

探索】━━━━

━━━━━┫ \\n\

printf(\┃

┃ \\n\ 径〗

┃ \\n\

printf(\┃ ⑵〖清空屏幕〗

printf(\┃ ⑴〖输入迷宫路

信息科学与工程学院 - 31- 网络工程11-1班

软件综合实习

┃ \\n\

printf(\┃ ⑶〖结束探索〗

┃ \\n\

printf(\┃

┃ \\n\ ━━━━━━━━

printf(\┣━━━━━━━━━━━━━

━━━━━┫ \\n\

printf(\

break; }

case 3:

return 0;

default:

printf(\【输入有误】，请重新

输入！\\n\ }

}

}

return 0;

信息科学与工程学院 - 32- 网络工程11-1班

软件综合实习

//╞╪╪╪╪╪╪╪╪╪╪╪╪╪╪【存储迷宫函数】╪╪╪╪╪╪╪╪╪╪╪╪╪╪╪╪╪╪╡

string ** GetMaze(int &m,int &n) //返回存取迷宫的二维指针 {

string **maze; //定义二维指针存取迷宫

int i=0,j=0;

cout<<\【请输入】迷宫的长和宽:\int a,b;

cin>>a>>b; //输入迷宫的宽a和高b

cout<<\【请输入】迷宫内容:\\n\ //m，n分别代表迷宫的行数m和列数n

n=a; m=b;

maze=new string *[m+2]; //申请长度等于行数加2的二级指针【这句就是给一个指向指针的指

针动态分配m+2个存放int类型指针的数组，用于动态申请二维数组。】

for(i= 0;i

maze[i]=new string[n+2];

for(i=1;i<=m;i++) //输入迷宫的内容，0代表可通，1代表不通

信息科学与工程学院 - 33- 网络工程11-1班

软件综合实习

{

for(j=1;j<=n;j++)

{

cin>>maze[i][j];

} }

for(i=0;i

{

maze[i][0]=maze[i][n+1]=\■\使纵向围墙为1，就是0列和6列纵向

}

for(i=0;i

{

maze[0][i]=maze[m+1][i]=\■\使横向围墙为1，就是0行和6行横向

}

return maze; //返回存贮迷宫的二维指针maze };

//╞╪╪╪╪╪╪╪╪╪╪╪╪╪╪【寻找迷宫路径函数】╪╪╪╪╪╪╪╪╪╪╪╪╪╪╪╪╪╪╡

信息科学与工程学院 - 34- 网络工程11-1班

软件综合实习

bool Mazepath(string **maze,int m,int n) //寻找迷宫maze中从（1，1）到（m,n）的路径，如果到则返回true,

否则返回false {

Stack q,p; //定义栈p、q,分别存探索迷宫的过程和存储路径 T Temp1,Temp2; int x,y,loop;

printf(\【请输入】入口行坐标，列坐标：\ cin>>a1>>b1; while(a1>m||b1>n) {

printf(\【输入坐标有误】\

printf(\【请重新输入】入口行坐标，列坐标：\ cin>>a1>>b1; }

printf(\

printf(\【请输入】出口行坐标，列坐标：\ cin>>c1>>d1; while(c1>m||d1>n) {

printf(\【输入坐标有误】\

printf(\【请重新输入】出口行坐标，列坐标：\ cin>>c1>>d1;

信息科学与工程学院 - 35- 网络工程11-1班

软件综合实习

}

printf(\

Temp1.x=a1; Temp1.y=b1;

q.Push(Temp1); //将入口位置入栈

p.Push(Temp1);

maze[a1][b1]=\标志入口位置已到达过

while(!q.empty()) //栈q非空，则反复探索 {

Temp2=q.GetPop(); //获取栈顶元素

if(!(p.GetPop().x==q.GetPop().x&&p.GetPop().y==q.GetPop().y))

{

p.Push(Temp2); //如果有新位置入栈，则把上一个探索的位置存入栈p

}

for(loop=0;loop<4;loop++) //探索当前位置的4个相邻位置

{

x=Temp2.x+move[loop][0]; //计算出新位置行x位置值（move分别=0、1、0、-1）

y=Temp2.y+move[loop][1]; //计算出新位置列y位置值（move分别=1、0、-1、0）

if(maze[x][y]==\判断新位置是否可达

信息科学与工程学院 - 36- 网络工程11-1班

软件综合实习

{

Temp1.x=x; //把可行路径的行x、列y坐标赋给Temp

Temp1.y=y;

maze[x][y]=\标志新位置已到达过

q.Push(Temp1); //新位置入栈【临时栈q】

}

if((x==c1)&&(y==d1)) //成功到达出口

{

Temp1.x=c1; //把出口的行x、列y坐标赋给Temp

Temp1.y=d1; Temp1.dir=0; p.Push(Temp1);

//把最后一个位

置入栈p 出路径

PrintPath(p,m,n,maze); //输

Restore(maze,m,n); //恢复路径 return 1; //表示成功找

到路径

}

}

if(p.GetPop().x==q.GetPop().x&&p.GetPop().y==q.GetPop().y) //如果没有新位置入栈，则返回到上一个位置

信息科学与工程学院 - 37- 网络工程11-1班

软件综合实习

{

p.Pop(); q.Pop();

}

}

return 0; //表示查找失败，即迷宫无路经 }

//╞╪╪╪╪╪╪╪╪╪╪╪╪╪╪【输出路径函数】╪╪╪╪╪╪╪╪╪╪╪╪╪╪╪╪╪╪╡

void PrintPath(Stack p,int m,int n,string **maze) //输出路径 {

Stack t; //定义一个栈，按从入口到出口存取路径 int a,b; T data;

LinkNode *temp;

temp=new LinkNode; //申请空间 temp->data=p.Pop(); //取栈p的顶点元素，即第一个位置

信息科学与工程学院 - 38- 网络工程11-1班

软件综合实习

t.Push(temp->data); //第一个位置入栈t

delete temp; //释放空间

while(!p.empty()) //栈p非空，则反复回首转移 {

temp=new LinkNode;

temp->data=p.Pop(); //置，得到行走方向 a=t.GetPop().x-temp->data.x; // b=t.GetPop().y-temp->data.y; // if(a==1) {

temp->data.dir=1; //示

}

else if(b==1) {

temp->data.dir=2; //示 }

else if(a==-1) {

temp->data.dir=3; //示

}

信息科学与工程学院 - 39- 获取下一个位行坐标方向 列坐标方向 方向向下，用1表

方向向右，用2表

方向向上，用3表

网络工程11-1班

本文来源：https://www.bwwdw.com/article/g61.html