三，详细设计：
1.主程序文件1.cpp：
#include<stdlib.h>
#include <string.h>
#include <time.h>
#include<iostream.h>
#include"0.h"
#include"mg.h"
void main()
{
cout<<" ****************************************************************"<<endl;
cout<<" 2004数据结构课程设计之迷宫寻路"<<endl;
cout<<" 本程序根据你输入的行，列，复杂水平，生成一个矩阵图形迷宫。"<<endl;
cout<<" 0表示不可行走的障碍，1表示可以行走的路径。"<<endl;
cout<<" 程序自动寻路，用文字显示所有搜索的路径。"<<endl;
cout<<" 再用9标识最后走通的路径。"<<endl;
cout<<" ****************************************************************"<<endl;
Stack lj1;
stack1 s1;//存放走过的路径
zou z;
s1.InitStack(lj1,200);
int x(0),y(0),zz(0);
cout<<"行(1～10): ";
cin>>y;
cout<<"列(1～10): ";
cin>>x;
cout<<"障碍级别(1～+∞ 难度逐渐降低): ";
cin>>zz;
z.Initzou(x,y,zz);
do{
if(z.ifgoon(z))
{
s1.Push(lj1,z.xianz);
z.xingzou(z);
}
else
{
z.houtui();
}
}while(z.xianz.tbt!=4);
z.m[z.xianz.mx][z.xianz.my].tbt=9;//显示当前位置
Mg temp;
do{
temp=s1.Pop(lj1);
z.m[temp.mx][temp.my].tbt=9;
}while(!s1.StackEmpty(lj1));//给走过的路径表示成9
int i(0),j(0);
for(i=0;i<x;i++)
{
cout<<endl;
for(j=0;j<y;j++)
cout<<z.m[i][j].tbt<<" ";
}
cout<<endl<<endl;
}
} 2．栈类型：
1)文件o.h
struct Mg
{
int tbt;//通不通
int mx;//横坐标
int my;//纵坐标
int lks;//路口数目
int tgcs;//通过次数
};//迷宫的性质
struct Stack
{
Mg* stack;
short top;
short StackMaxSize;
};
class stack1
{
public:
void InitStack(Stack& S,int ms);
bool StackEmpty(Stack& S);
void Push(Stack& S,Mg& item);
Mg Pop(Stack& S);
};};
2)文件0.cpp
#include<stdlib.h>
#include<iostream.h>
#include"0.h"
void stack1::InitStack(Stack& S,int ms)
{
S.stack=new Mg [ms];
if(!S.stack)
{
cerr<<"Memory allocation failure!";
exit(1);
}
S.top=-1;
S.StackMaxSize=ms;
}
bool stack1::StackEmpty(Stack& S)
{
return S.top==-1;
}
void stack1::Push(Stack& S,Mg& item)
{
if(S.top==S.StackMaxSize-1)
{
cerr<<"Stack is full!"<<endl;
exit(1);
}
S.top++;
S.stack[S.top]=item;
}
Mg stack1::Pop(Stack& S)
{
if(S.top==-1)
{
cerr<<" Stack is empty!!"<<endl;
exit(1);
}
S.top--;
return S.stack[S.top+1];
}
3，迷宫文件
1)文件mg.h：
/*迷宫为Mg[10][10]的二维数组，通为1，不通为0。起点为3，终点为4;
走过的路径压入栈lj1;
在当前位置判断（在程序中是do{}while()语句部分）：
1：能否前进（遇到终点或是路的尽头都不能前进了。）任意一块地方不能
走他的Mg m.lks次以上
*/
class zou
{
public:
void Initzou(int i,int j,int k);//初始化迷宫，画出迷宫
bool ifgoon(zou& Z);//判断能否继续
void xingzou(zou& Z);//按反时针方向找新路 任意一块地方不能走两次以上
void houtui();//后退一步
int getlukoushu();//得到路口数目
Mg ganglk;
Mg xianz;
Mg m[10][10];
};
2)文件mg.cpp：
#include<stdlib.h>
#include<iostream.h>
#include"0.h"
#include"mg.h"
void zou::Initzou(int x,int y,int zz)
{
int i(0),j(0);
for(i=0;i<x;i++)
for(j=0;j<y;j++)
{
m[i][j].tbt=0;
m[i][j].mx=i;
m[i][j].my=j;
m[i][j].lks=0;
m[i][j].tgcs=0;
}
for(i=1;i<x-1;i++)
for(j=1;j<y-1;j++)
{
if(rand()%zz!=0)//根据随机数能不能被zz整除来生成障碍
m[i][j].tbt=1;
else
m[i][j].tbt=0;
}
m[1][1].tbt=4;
m[i-1][j-1].tbt=3;
for(i=0;i<x;i++)
{
cout<<endl;
for(j=0;j<y;j++)
cout<<m[i][j].tbt<<" ";
}
cout<<endl<<endl;
xianz=m[i-2][j-2];
ganglk=m[i-2][j-2];
m[i-2][j-2].tbt=1;
}
bool zou::ifgoon(zou& Z)
{
int x(0),y(0),xx(0),yy(0);
x=Z.xianz.mx;
y=Z.xianz.my;
xx=Z.ganglk.mx;
yy=Z.ganglk.my;
int temp(0);
temp=Z.m[xx][yy].tbt;
Z.m[xx][yy].tbt=0;
file://如果现在的位置的四个方向不可以通过或者找到终点
if(Z.m[x][y+1].tbt==0&&Z.m[x][y-1].tbt==0&&Z.m[x+1][y].tbt==0&&Z.m[x-1][y].tbt==0||Z.m[x][y].tbt==4)
{
Z.m[xx][yy].tbt=temp;
return false;
}
else
{
Z.m[xx][yy].tbt=temp;
return true;
}
}
void zou::xingzou(zou& Z)
{
int fangx(4);
int jg1=Z.xianz.my-Z.ganglk.my;
int jg2=Z.xianz.mx-Z.ganglk.mx;
if(jg1<0&&jg2==0)
{
fangx=0;//现在来时的左边
}
else if(jg1>0&&jg2==0)
{
fangx=1;//在右边
}
else if(jg1==0&&jg2<0)
{
fangx=2;//在上边
}
else if(jg1==0&&jg2>0)
{
fangx=3;//在下边
}
else if(jg1==0&&jg2==0)
{
fangx=4;//在原处
}
else
cout<<"ifgoon() has problem!"<<endl;
switch(fangx) {
case 0:
if(Z.m[Z.xianz.mx-1][Z.xianz.my].tbt!=0&&Z.m[Z.xianz.mx-1][Z.xianz.my].tgcs<Z.getlukoushu())
{//往上走
Z.ganglk=Z.xianz;
Z.xianz=Z.m[Z.xianz.mx-1][Z.xianz.my];
Z.xianz.tgcs=Z.xianz.tgcs+1;
cout<<"yes,sir,i go north"<<endl;
return;
}
else if(Z.m[Z.xianz.mx][Z.xianz.my-1].tbt!=0&&Z.m[Z.xianz.mx][Z.xianz.my-1].tgcs<Z.getlukoushu())
{//往左走
Z.ganglk=Z.xianz;
Z.xianz=Z.m[Z.xianz.mx][Z.xianz.my-1];
Z.xianz.tgcs=Z.xianz.tgcs+1;
cout<<"yes,sir,i go west"<<endl;
return;
}
else if(Z.m[Z.xianz.mx+1][Z.xianz.my].tbt!=0&&Z.m[Z.xianz.mx+1][Z.xianz.my].tgcs<Z.getlukoushu())
{//往下走
Z.ganglk=Z.xianz;
Z.xianz=Z.m[Z.xianz.mx+1][Z.xianz.my];
Z.xianz.tgcs=Z.xianz.tgcs+1;
cout<<"yes,sir,i go south"<<endl;
return;
}
else
{
xianz.tbt=4;
cout<<"sir,no way for search anymore!!"<<endl;
}
break;
case 1:
if(Z.m[Z.xianz.mx+1][Z.xianz.my].tbt!=0&&Z.m[Z.xianz.mx+1][Z.xianz.my].tgcs<Z.getlukoushu())
{//往下走
Z.ganglk=Z.xianz;
Z.xianz=Z.m[Z.xianz.mx+1][Z.xianz.my];
Z.xianz.tgcs=Z.xianz.tgcs+1;
cout<<"yes,sir,i go south"<<endl;
return;
}
else if(Z.m[Z.xianz.mx][Z.xianz.my+1].tbt!=0&&Z.m[Z.xianz.mx][Z.xianz.my+1].tgcs<Z.getlukoushu())
{//往右走
Z.ganglk=Z.xianz;
Z.xianz=Z.m[Z.xianz.mx][Z.xianz.my+1];
Z.xianz.tgcs=Z.xianz.tgcs+1;
cout<<"yes,sir,i go east"<<endl;
return;
}
else if(Z.m[Z.xianz.mx-1][Z.xianz.my].tbt!=0&&Z.m[Z.xianz.mx-1][Z.xianz.my].tgcs<Z.getlukoushu())
{//往上走
Z.ganglk=Z.xianz;
Z.xianz=Z.m[Z.xianz.mx-1][Z.xianz.my];
Z.xianz.tgcs=Z.xianz.tgcs+1;
cout<<"yes,sir,i go north"<<endl;
return;
}
else
{
xianz.tbt=4;
cout<<"sir,no way for search anymore!!"<<endl;
}
break;
case 2:
if(Z.m[Z.xianz.mx][Z.xianz.my+1].tbt!=0&&Z.m[Z.xianz.mx][Z.xianz.my+1].tgcs<Z.getlukoushu())
{//往右走
Z.ganglk=Z.xianz;
Z.xianz=Z.m[Z.xianz.mx][Z.xianz.my+1];
Z.xianz.tgcs=Z.xianz.tgcs+1;
cout<<"yes,sir,i go east"<<endl;
return;
}
else if(Z.m[Z.xianz.mx-1][Z.xianz.my].tbt!=0&&Z.m[Z.xianz.mx-1][Z.xianz.my].tgcs<Z.getlukoushu())
{//往上走
Z.ganglk=Z.xianz;
Z.xianz=Z.m[Z.xianz.mx-1][Z.xianz.my];
Z.xianz.tgcs=Z.xianz.tgcs+1;
cout<<"yes,sir,i go north"<<endl;
return;
}
else if(Z.m[Z.xianz.mx][Z.xianz.my-1].tbt!=0&&Z.m[Z.xianz.mx][Z.xianz.my-1].tgcs<Z.getlukoushu())
{//往左走
Z.ganglk=Z.xianz;
Z.xianz=Z.m[Z.xianz.mx][Z.xianz.my-1];
Z.xianz.tgcs=Z.xianz.tgcs+1;
cout<<"yes,sir,i go west"<<endl;
return;
}
else
{
xianz.tbt=4;
cout<<"sir,no way for search anymore!!"<<endl;
}
break;
case 3:
if(Z.m[Z.xianz.mx][Z.xianz.my-1].tbt!=0&&Z.m[Z.xianz.mx][Z.xianz.my-1].tgcs<Z.getlukoushu())
{//往左走
Z.ganglk=Z.xianz;
Z.xianz=Z.m[Z.xianz.mx][Z.xianz.my-1];
Z.xianz.tgcs=Z.xianz.tgcs+1;
cout<<"yes,sir,i go west"<<endl;
return;
}
else if(Z.m[Z.xianz.mx+1][Z.xianz.my].tbt!=0&&Z.m[Z.xianz.mx+1][Z.xianz.my].tgcs<Z.getlukoushu())
{//往下走
Z.ganglk=Z.xianz;
Z.xianz=Z.m[Z.xianz.mx+1][Z.xianz.my];
Z.xianz.tgcs=Z.xianz.tgcs+1;
cout<<"yes,sir,i go south"<<endl;
return;
}
else if(Z.m[Z.xianz.mx][Z.xianz.my+1].tbt!=0&&Z.m[Z.xianz.mx][Z.xianz.my+1].tgcs<Z.getlukoushu())
{//往右走
Z.ganglk=Z.xianz;
Z.xianz=Z.m[Z.xianz.mx][Z.xianz.my+1];
Z.xianz.tgcs=Z.xianz.tgcs+1;
cout<<"yes,sir,i go east"<<endl;
return;
}
else
{
xianz.tbt=4;
cout<<"sir,no way for search anymore!!"<<endl;
}
break;
case 4:
if(Z.m[Z.xianz.mx-1][Z.xianz.my].tbt!=0&&Z.m[Z.xianz.mx-1][Z.xianz.my].tgcs<Z.getlukoushu())
{//往上走
Z.ganglk=Z.xianz;
Z.xianz=Z.m[Z.xianz.mx-1][Z.xianz.my];
Z.xianz.tgcs=Z.xianz.tgcs+1;
cout<<"yes,sir,i go north"<<endl;
return;
}
else if(Z.m[Z.xianz.mx][Z.xianz.my-1].tbt!=0&&Z.m[Z.xianz.mx][Z.xianz.my-1].tgcs<Z.getlukoushu())
{//往左走
Z.ganglk=Z.xianz;
Z.xianz=Z.m[Z.xianz.mx][Z.xianz.my-1];
Z.xianz.tgcs=Z.xianz.tgcs+1;
cout<<"yes,sir,i go west"<<endl;
return;
}
else
{
xianz.tbt=4;
cout<<"sir,no way for search anymore!!"<<endl;
}
break;
default:
{
xianz.tbt=4;
cout<<"sir,no way for search anymore!!"<<endl;
return;
}
}
}
void zou::houtui()
{
Mg M;
int x(0),y(0),xx(0),yy(0);
x=xianz.mx;
y=xianz.my;
xx=ganglk.mx;
yy=ganglk.my;
int temp(0);
temp=m[xx][yy].tbt;
m[xx][yy].tbt=0;
if(m[x][y+1].tbt==0&&m[x][y-1].tbt==0&&m[x+1][y].tbt==0&&m[x-1][y].tbt==0&&ganglk.tgcs<2)
{
M=xianz;
xianz=ganglk;
ganglk=M;
xianz.tgcs=xianz.tgcs+1;
m[xx][yy].tbt=temp;
cout<<"sir,i go back"<<endl;
}
else
{
xianz.tbt=4;
m[xx][yy].tbt=temp;
cout<<"sir,no way for search anymore!!"<<endl;
}
}
int zou::getlukoushu()
{
int e(0),s(0),w(0),n(0);
if(m[xianz.mx][xianz.my+1].tbt==1)
e=1;
else
e=0;
if(m[xianz.mx][xianz.my-1].tbt==1)
w=1;
else
w=0;
if(m[xianz.mx-1][xianz.my].tbt==1)
n=1;
else
n=0;
if(m[xianz.mx+1][xianz.my].tbt==1)
s=1;
else
s=0;
return e+w+n+s;
}
四，调试分析：
由于是一个工程，由多个文件构成，头文件容易重复包含，可能引起连接错误。
五，用户手册：
执行文件MG.EXE。
进入演示程序，提示用户输入迷宫行数；提示用户输入迷宫列数,然后.提示用户输入迷宫复杂水平。
参数决定后随即以矩阵图形方式输出生成的迷宫，并且开始自动寻路。输出搜索路径的文字记录，以及用9标识走过路径的矩阵图形。
六，测试结果
****************************************************************
2004数据结构课程设计之迷宫寻路
本程序根据你输入的行，列，复杂水平，生成一个矩阵图形迷宫。
0表示不可行走的障碍，1表示可以行走的路径。
程序自动寻路，用文字显示所有搜索的路径。
再用9标识最后走通的路径。
****************************************************************
行(1～10): 10
列(1～10): 10
障碍级别(1～+∞ 难度逐渐降低): 3
0 0 0 0 0 0 0 0 0 0
0 4 1 1 1 1 1 0 0 0
0 1 1 1 1 1 0 1 1 0
0 1 1 0 0 0 0 1 0 0
0 1 1 0 1 1 1 1 0 0
0 1 0 0 1 1 1 1 0 0
0 1 0 1 0 0 1 0 1 0
0 1 1 1 1 1 0 0 1 0
0 1 0 1 1 1 1 1 3 0
0 0 0 0 0 0 0 0 0 0
yes,sir,i go north
yes,sir,i go north
sir,i go back
yes,sir,i go south
yes,sir,i go west
yes,sir,i go west
yes,sir,i go west
yes,sir,i go north
yes,sir,i go west
yes,sir,i go west
yes,sir,i go north
sir,i go back
yes,sir,i go west
yes,sir,i go west
yes,sir,i go north
yes,sir,i go north
yes,sir,i go north
yes,sir,i go east
yes,sir,i go north
yes,sir,i go north
yes,sir,i go east
yes,sir,i go east
yes,sir,i go east
yes,sir,i go north
yes,sir,i go east
sir,i go back
yes,sir,i go west
yes,sir,i go west
yes,sir,i go west
yes,sir,i go west
0 0 0 0 0 0 0 0 0 0
0 9 9 9 9 9 1 0 0 0
0 1 9 9 9 9 0 1 1 0
0 1 9 0 0 0 0 1 0 0
0 9 9 0 1 1 1 1 0 0
0 9 0 0 1 1 1 1 0 0
0 9 0 1 0 0 1 0 1 0
0 9 9 9 9 9 0 0 9 0
0 1 0 1 1 9 9 9 9 0
0 0 0 0 0 0 0 0 0 1
Press any key to continue
八，参考书籍：
《数据结构课程实验》 徐孝凯 著 清华大学出版社
九，说明；
1.栈的实现的代码取自《数据结构课程实验》 一书，在此表示感谢。
2.在mg.cpp文件中，移动的代码多次重复使用，应该独立出来作为成员函数的。考虑的不好。
3.有个别不通的迷宫不能停下来，出现很少两次：），要一直走到栈满了。不知道怎么的。请指教。[email protected]
本文地址：http://com.8s8s.com/it/it1198.htm