【文件属性】：
文件名称：迷宫寻路数据结构栈实现
文件大小：8KB
文件格式：TXT
更新时间：2012-06-11 07:10:53
迷宫寻路
#include
using std::cout;
using std::cin;
#include
#include
#include
#define OVERFLOW -2
#define INIT_SIZE 100 //存储空间初始分配量
#define INCREMENT 10 //存储空间分配增量
typedef struct{
int r;
int c;
}PostType;//迷宫中r行c列的位置
typedef struct{
int ord; //当前位置在路径上的序号
PostType seat;//当前坐标
int di; //往下一坐标的方向
}SElemType; //栈元素类型
typedef struct{
SElemType* base;//栈基址,构造前销毁后为空
SElemType* top;//栈顶
int stackSize; //栈容量
}Stack; //栈类型
int InitStack(Stack &S){ //构造空栈s
S.base=(SElemType*)malloc(INIT_SIZE *sizeof(SElemType));
if(!S.base)
exit(OVERFLOW);//存储分配失败
S.top=S.base;
S.stackSize=INIT_SIZE;
return 0;
}
int StackEmpty(Stack S)//若s为空返回TRUE,否则返回FALSE
{
if(S.top==S.base)
return 1;
return 0;
}
int Push(Stack &S,SElemType e){
//插入元素e为新的栈顶元素
if(S.top-S.base >=S.stackSize){//栈满，加空间
S.base=(SElemType *)realloc(S.base,(S.stackSize+INCREMENT)*sizeof(SElemType));
if(!S.base)
exit(OVERFLOW); //存储分配失败
S.top=S.base+S.stackSize;
S.stackSize+=INCREMENT;
}
*S.top++=e;
return 1;
}
int Pop(Stack &S,SElemType &e){//若栈不空删除栈，顶元素用e返回
if(S.top==S.base)
return 0;
e=*--S.top;
return 1;
}
int DestroyStack(Stack &S){//销毁栈S,
free(S.base);
S.top=S.base;
return 1;
}
#define MAXLEN 16//迷宫包括外墙最大行列数目
typedef struct{
int r;
int c;
char adr[MAXLEN][MAXLEN];
}MazeType; //迷宫类型
int InitMaze(MazeType &maze){
//初始化迷宫若成功返回TRUE,否则返回FALSE
int i,j;
cout<<"输入迷宫尺寸（长和宽）: ";
cin>>maze.r>>maze.c; //迷宫行和列数
for(i=0;i<=maze.c+1;i++){//迷宫行外墙
maze.adr[0][i]='#';
maze.adr[maze.r+1][i]='#';
}
for(i=0;i<=maze.r+1;i++){//迷宫列外墙
maze.adr[i][0]='#';
maze.adr[i][maze.c+1]='#';
}
for(i=1;i<=maze.r;i++)
for(j=1;j<=maze.c;j++)
maze.adr[i][j]=' ';//初始化迷宫
int m=1,n=maze.c;
for(m;m<8;m++)
maze.adr[2][m]='#';
for(n;n>1;n--)
maze.adr[6][n]='#';
maze.adr[4][5]='#';
maze.adr[4][6]='#';
maze.adr[3][3]='#';
maze.adr[3][2]='#';
maze.adr[5][7]='#';
maze.adr[5][6]='#';
maze.adr[8][3]='#';
maze.adr[7][2]='#';
maze.adr[7][5]='#';
return 1;
}//InitMaze
int Pass(MazeType maze,PostType curpos){
if(maze.adr[curpos.r][curpos.c]==' ')
return 1;
else
return 0;
}//Pass
int FootPrint(MazeType &maze,PostType curpos){
//若走过并且可通返回TRUE,否则返回FALSE
//在返回之前销毁栈S
maze.adr[curpos.r][curpos.c]='!';//"*"表示可通
return 1;
}//FootPrint
PostType NextPos(PostType &curpos,int i){
//指示并返回下一位置的坐标
PostType cpos;
cpos=curpos;
switch(i){
case 1 : cpos.c+=1; break;
case 2 : cpos.r+=1; break;
case 3 : cpos.c-=1; break;
case 4 : cpos.r-=1; break;
default: exit(0);
}
return cpos;
}//Nextpos
int MarkPrint(MazeType &maze,PostType curpos){
maze.adr[curpos.r][curpos.c]='@';//"@"表示曾走过但不通
return 1;
}
int MazePath(MazeType &maze,PostType start,PostType end){
//若迷宫maze存在从入口start到end的通道则求得一条存放在栈中
Stack S;
PostType curpos;
int curstep;//当前序号,1.2.3.4分别表示东,南,西,北方向
SElemType e;
InitStack(S);
curpos=start; //设置"当前位置"为"入口位置"
curstep=1; //探索第一步
do{
if(Pass(maze,curpos)){//当前位置可以通过,即是未曾走到过的通道
FootPrint(maze,curpos);//留下足迹
e.ord=curstep;
e.seat=curpos;
e.di=1;
Push(S,e); //加入路径
if(curpos.r==end.r&& curpos.c==end.c)
if(!DestroyStack(S))//销毁失败
exit(OVERFLOW);
else
return 1; //到达出口
else{
curpos=NextPos(curpos,1); //下一位置是当前位置的东邻
curstep++; //探索下一步
}
}
else{ //当前位置不通
if(!StackEmpty(S)){
Pop(S,e);
while(e.di==4
&& !StackEmpty(S)){
MarkPrint(maze,e.seat);
Pop(S,e); //留下不能通过的标记,并退一步
}
if(e.di < 4){
e.di++;//换下一个方向探索
Push(S,e);
curpos=NextPos(e.seat,e.di);//设定当前位置是该新方向上的相邻位置
}
}
}
}while(!StackEmpty(S));
if(!DestroyStack(S))//销毁失败
exit(OVERFLOW);
else
return 0;
}//MazePath
void PrintMaze(MazeType &maze){
//将标记路径信息的迷宫输出
int i,j;
cout<<"\n——!为所求迷宫路线路线——:\n\n";
cout<<" ";
for(i=0;i<=maze.r+1;i++)//打印列数名
cout<<" "<>start.r>>start.c;
if(start.r>maze.r || start.c>maze.c){
cout<<"\n越界!!!\n";
continue;
}
}while(start.r>maze.r || start.c>maze.c);
do{
cout<<"\n输入结束点坐标: ";
cin>>end.r>>end.c;
if(end.r>maze.r || end.c>maze.c){
cout<<"\n越界!!!\n";
continue;
}
}while(end.r>maze.r || end.c>maze.c);
if(!MazePath(maze,start,end))
cout<<"\n不能求得路径!\n";
else
PrintMaze(maze);
cout<<"\n是否继续?(y/n): ";
cin>>cmd;
}while(cmd=='y' || cmd=='Y');
}
