栈实现迷宫求解
实现的伪代码：
设定当前位置的初始值为入口位置
do{
若当前位置可通
则 {
若当前位置插入栈顶； //纳入路径
若该位置是出口位置，则结束； //求得路径存放在栈中
否则切换当初位置的东邻方块为新的当前位置；
}
否则,
若栈不空且栈顶位置尚有其他方向未经探索，
则设定新的当前位置为沿顺时针找到的栈顶位置的下一相邻块；
若栈不空但栈顶位置与四周均不可同，
则 { 删去栈顶位置，
若栈不空,则重新测试新的栈顶位置，
直至找到一个可通的相邻块或出栈至栈空；
}
}while(栈不空);
代码实现
关于栈的stack.h
//=======Stack 的表示与实现
//=====栈的顺序存贮结构
#define STACK_INIT_SIZE 100 // 存储空间的初始分配量
#define STACKINCREMENT 10 //存储空间分配增量
//-------------栈的顺序存储表示----------------
typedef struct
{
SElemType *base; //栈底指针
SElemType *top; //栈顶指针
int stacksize; //当前可使用的最大容量
} SqStack;
//------------基本操作--------------------
//构建一个空栈S
Status InitStack(SqStack &S)
{
S.base = (SElemType *)malloc(STACK_INIT_SIZE * sizeof(SElemType));
if(!S.base) //判断是否空间分配成功
exit(OVERFLOW);
S.top = S.base; //栈顶与栈底指向同一个位置，表示空栈
S.stacksize = STACK_INIT_SIZE;
return OK;
}//InitStack_Sq
//销毁栈S
Status DestroyStack(SqStack &S)
{
if(S.base)
{
free(S.base);
S.stacksize = 0;
return OK;
}
else
return ERROR;
}//DestroyStack_Sq
//初始条件：栈S存在
//操作结果：清空栈
Status CleanStack(SqStack &S)
{
S.top = S.base;
return OK;
}//CleanStack_Sq
//初始条件：栈S存在
//操作结果：若为空栈，返回TRUE，否则FALSE
Status StackEmpty(SqStack S)
{
if(S.top == S.base)
return TRUE;
else
return FALSE;
}//StackEmpty_Sq
//初始条件：栈S存在
//操作结果：返回栈内元素个数，即栈的长度
int StackLength(SqStack S)
{
int len;
len = (S.top - S.base);
return len;
}//StackLength_Sq
//初始条件：栈S存在
//操作结果：用e返回S的栈顶元素
Status GetTop(SqStack S, SElemType &e)
{
if(S.top == S.base)//判空
return ERROR;
else
{
e = *(S.top - 1);
return OK;
}
}//GetTop_Sq
//初始条件：栈S存在
//操作结果：插入元素e为新的栈顶元素
Status Push(SqStack &S, SElemType e)
{
//判满，追加存储空间
if(S.top - S.base >= S.stacksize)
{
S.base = (SElemType *)realloc(S.base,(S.stacksize + STACKINCREMENT) * sizeof(SElemType));
if(!S.base)//存储分配失败
exit(OVERFLOW);
S.top = S.base + S.stacksize;
S.stacksize += STACKINCREMENT;
}
*S.top++ = e; //插入元素
return OK;
}//Push_Sq
//初始条件：栈S存在
//操作结果：删除S的栈顶元素，并用e返回其值
Status Pop(SqStack &S, SElemType &e)
{
if(S.top == S.base) //判空
return ERROR;
e = *--S.top; //返回删除元素的值
return OK;
}//Pop_Sq
//初始条件：栈S存在
//操作结果：遍历栈元素并显示
Status StackTraverse(SqStack S)
{
if(S.base) //判断栈是否存在
{
if(S.top == S.base); //判空
else
{
SElemType *p;
p = S.base;
while(p <S.top)
{
Print_Selem(*p);
p++;
}
printf("\b\b ");
printf("\n");
}
return OK;
}
else
{
return ERROR;
}
}//StackTraverse_Sq
关于迷宫的maze.h
//判断当前位置是否可以通过（是否有墙）
void IntMaze(MazeType &maze)
{
int i,j;
char a[10][10] =
{
{'#','#','#','#','#','#','#','#','#','#'},
{'#',' ',' ','#',' ',' ',' ','#',' ','#'},
{'#',' ',' ','#',' ','#','#','#',' ','#'},
{'#',' ',' ',' ',' ','#','#','#',' ','#'},
{'#',' ','#','#','#','#','#','#',' ','#'},
{'#',' ',' ',' ','#','#','#','#',' ','#'},
{'#',' ','#',' ',' ',' ','#','#',' ','#'},
{'#',' ','#','#','#',' ','#','#',' ','#'},
{'#','#',' ',' ',' ',' ',' ',' ',' ','#'},
{'#','#','#','#','#','#','#','#','#','#'}
};
maze=new char *[10];
for(i=0; i<10; i++)
maze[i]=new char[10];
for(i=0; i<10; i++)
for(j=0; j<10; j++)
maze[i][j]=a[i][j];
}
void CreatMaze(MazeType &maze,int m,int n)
{
int i;
maze=new char *[m];
for(i=0; i<m; i++)
maze[i]=new char[n];
}
void print_maze(MazeType maze,int m=10,int n=10)
{
int i,j;
printf(" ");
for(i=0;i<n;i++) printf("%d",i);
printf("\n");
for(i=0; i<m; i++)
{
printf("%d",i);
for(j=0; j<n; j++)
printf("%c",maze[i][j]);
printf("\n");
}
}
Status Pass(PosType curpos,MazeType maze)
{
if(maze[curpos.x][curpos.y]==' ') return OK;
else return ERROR;
}
void FootPrint(PosType curpos,MazeType &maze)
{
maze[curpos.x][curpos.y]='@';
}
PosType NextPos(PosType curpos,int di)
{
if(di==1) curposy++;
else if(di==2) curpos.x++;
else if(di==3) curpos.y--;
else if(di==4) curpos.x--;
return curpos;
}
void MarkPrint(PosType curpos,MazeType &maze)
{
maze[curpos.x][curpos.y]=',';
}
Status MazePath(MazeType &maze,PosType start,PosType end)
{
SqStack S;
SElemType e;
InitStack(S);
PosType curpos = start; //设定"当前位置" 为 "入口位置"
int curstep = 1; //探索第一步
do
{
if(Pass(curpos,maze)) //当前位置可以通过，即是未曾走到过的通道块
{
FootPrint(curpos,maze); //留下足迹
e = {curstep,curpos,1};
Push(S,e); //加入路径
if(curpos == end )
{
printf("迷宫有通路,通路为：\n");
StackTraverse(S);
return(TRUE); //到达出口
}
curpos = NextPos(curpos,1); //下一位置是当前位置的东邻
curstep++; //探索下一步
}
else
{
if(!StackEmpty(S))
{
Pop(S,e);
while(e.di==4 && !StackEmpty(S))
{
MarkPrint(e.seat,maze); //留下不能通过的标记，
Pop(S,e); //退回一步
}
}
if(e.di<4)
{
e.di++;
Push(S,e); //换下一个方向探索
curpos = NextPos(e.seat,e.di); //设定当前位置是该方向上的相邻块
}
}
}
while(!StackEmpty(S));
printf("迷宫没有通路");
return FALSE;
}
Base.h
#include<stdio.h>
#include <stdlib.h> //malloc
//函数结果状态代码
#define TRUE 1
#define FALSE 0
#define OK 1
#define ERROR 0
#define OVERFLOW -2
//Status是函数的类型，其值是函数结果状态代码
typedef int Status;
typedef char** MazeType;
//----坐标的数据元素------
typedef struct PosType
{
int x;
int y;
bool operator==(const PosType p)const
{
return(this->x == p.x&&this->y == p.y);
}
} PosType;
//输出点坐标
void Print_Pos(PosType Pos)
{
printf("(%d,%d)",Pos.x,Pos.y);
}
//------迷宫中栈的元素类型
typedef struct
{
int ord; //通道块在路径上的"序号"
PosType seat; //通道块在迷宫中的“坐标位置”
int di; //在此通道块走向下一通道块的“方向”
} SElemType;
//输出SlemType
void Print_Selem(SElemType s)
{
printf("(%d,%d)->",s.seat.x,s.seat.y);
}
//----迷宫的元素类型
Print.h
void start_print()
{
printf("***********************************************************************************************************************\n");
printf(" 数据结构实验二 \n");
printf(" 迷宫求解----深度优先搜索（栈实现） \n");
printf(" 中国海洋大学 \n");
printf("***********************************************************************************************************************\n");
}
void Creathelp_print(int & m,int & n,MazeType &maze,PosType &start,PosType &end)
{
int i,j;
printf("**请输入迷宫的长和宽*\n");
scanf("%d %d",&m,&n);
getchar();
char a[m][n];
printf("**请输入迷宫(#为墙，空白符为路):**\n");
for(i=0; i<m; i++)
{
for(j=0;j<n;j++)
scanf("%c",&a[i][j]);
getchar();
}
CreatMaze(maze,m,n);
for(i=0;i<m;i++)
for(j=0;j<n;j++)
maze[i][j]=a[i][j];
printf("起点(x,y)=(");
scanf("%d,%d)",&start.x,&start.y);
printf("终点(x,y)=(");
scanf("%d,%d)",&end.x,&end.y);
}
void menu1_print()
{
printf("***********************************************************************************************************************\n");
printf(" 请选择 1.默认迷宫 2.新建迷宫 0.退出 \n");
printf("***********************************************************************************************************************\n");
}
void menu2_print()
{
printf("***********************************************************************************************************************\n");
printf(" 请选择 1.打印 A+B 2.打印 AXB 3.对多项式进行操作 0.退出 \n");
printf("***********************************************************************************************************************\n");
}
void output_tip_print(char a)
{
printf("多项式%c: ",a);
}
void over_print()
{
system("CLS");
printf(" ******* * * \n");
printf(" * * * \n");
printf(" * *** *** *** * * ** \n");
printf(" * * * * * * * ** * \n");
printf(" * * * **** * * * * ** \n");
}``
main.cpp
#include"Base.h"
#include"stack.h"
#include"maze.h"
#include"Print.h"
int main()
{
system("color F4"); //改变背景色和前景色
start_print();
system("pause"); //冻结屏幕
system("CLS"); //清屏操作
MazeType maze;
PosType start,end;
int a;// a进行输入控制
do
{
system("CLS");
do
{
menu1_print();
scanf("%d",&a);
if(a==1)
{
IntMaze(maze);
printf("迷宫如下:(#代表墙 空白代表路)\n");
print_maze(maze);
start= {1,1};
end= {8,8};
printf("按任意键求解");
system("pause");
MazePath(maze,start,end);
printf("图如下:\n");
print_maze(maze);
printf("(@代表通路 ,代表算法中探索过得路径)\n");
}
else if(a==2)
{
int m,n;
Creathelp_print(m,n,maze,start,end);
print_maze(maze,m,n);
printf("按任意键求解");
system("pause");
MazePath(maze,start,end);
printf("图如下:\n");
print_maze(maze,m,n);
printf("(@代表通路 ,代表算法中探索过得路径)\n");
}
else if(a==0)
{
over_print();
return 0;
}
}
while(1);
}while(a!=0);
}
效果展示