首页 > 代码库 > 栈的应用-迷宫解题
栈的应用-迷宫解题
总结：这个是网上找的，下面一个是我在他基础上修改的。
/*
二. 栈的应用-迷宫解题
*/
#include<stdio.h>
#include<malloc.h>
#include<stdlib.h>
#define TRUE 1
#define FALSE 0
#define OK 1
#define ERROR 0
#define INFEASIBLE -1
#define OVERFLOW -2
//坐标类型
typedef struct
{
int x;
int y;
}Postype;
//栈的元素类型
typedef struct
{
int x;
int y;
}ElemType;
//二维数组，存储迷宫
int MAP[9][9] =
{
0,0,0,0,0,0,0,0,0,
0,1,0,0,1,1,1,1,0,
0,1,0,0,1,1,1,1,0,
0,1,1,1,1,0,1,1,0,
0,1,0,1,0,1,1,1,0,
0,1,0,1,0,1,1,1,0,
0,1,0,1,0,1,1,1,0,
0,0,0,1,1,1,1,1,0,
0,0,0,0,0,0,0,0,0,
};
/*-------------------------------------栈的元素类型定义完毕-------------------------*/
typedef int Status; //函数返回值
#define STACK_INIT_SIZE 5 // 栈的初始大小
#define STACK_INCREMENT 10 // 每次增加的空间大小
//下面给出栈的相关定义
typedef struct
{
ElemType *base; //在构造栈之前和销毁之后，base的值为NULL
ElemType *top; //栈顶指针
int stacksize; //当前已分配的存储空间，以元素为单位
}ZJC_Stack;
//--------------------------------------栈基本操作的算法部分--------------------------
//栈的初始化
Status InitStack(ZJC_Stack &S)
{
S.base = (ElemType *)malloc(STACK_INIT_SIZE * sizeof(ElemType)); //分配内存空间
if(!S.base){
exit(OVERFLOW);
}
else //否则分配成功
{
S.top = S.base;
S.stacksize = STACK_INIT_SIZE;
return OK;
}
}
//获得栈顶元素
ElemType GetTop(ZJC_Stack S)
{
if(S.top == S.base )
exit(ERROR);
return *(S.top - 1);
}
//压栈
Status Push(ZJC_Stack &S,ElemType e)
{
if(S.top - S.base >= S.stacksize)
{
S.base = (ElemType*)realloc(S.base,(S.stacksize + STACK_INCREMENT) * sizeof(ElemType));
if(!S.base)
exit(OVERFLOW);
S.top = S.base + S.stacksize;
S.stacksize += STACK_INCREMENT;
}
*S.top++ = e;
return OK;
}
void Print_Path(ZJC_Stack S) //打印出栈中的元素
{
printf("\n寻路完成..路径坐标值如下：......\n");
ElemType *p = S.base; //首先p指向栈底指针
ElemType temp;
while( p != S.top) //只要没有到顶端，指针就移动，然后输出元素值
{
temp = *p;
printf("\n路径 x = %d , y = %d",temp.x,temp.y);
p++;
}
}
//出栈函数
Status Pop(ZJC_Stack &S,ElemType &e)
{
if(S.top == S.base ) //空栈，返回错误
return ERROR;
else //不是空栈
{
e = * --S.top;
return OK;
}
}
void PathAddToStack(int i,int j,ElemType temp,ZJC_Stack &robot) //因为要修改值，所以取地址，开始没加取地址符号，栈顶元素一直是(1,1)
{
temp.x = i,temp.y = j;
Push(robot,temp);
MAP[i][j] = 2; //标记已经走过该格子了,当初想是否需要用其他标记，实际上不需要的，既然标记2，那么证明当然可以走过(不是墙)!
}
void MAZH_SOLVE(int endx,int endy) //解决迷宫问题函数,参数为终点的坐标
{
int i = 1,j = 1; //起点坐标
ZJC_Stack robot; //定义栈；
if(InitStack( robot ) ) //初始化栈
printf("\n栈的初始化完成....\n");
ElemType CurrentPos ; //当前位置
ElemType start; //初始位置的相关信息
ElemType temp; //暂时用的
start.x = i;
start.y = j;
temp = start;
MAP[i][j] = 2; //走过的标记为2
Push(robot,start); //初始位置入栈
printf("\n开始寻路....\n");
do //主要寻路算法：
{
CurrentPos = GetTop(robot);
i = CurrentPos.x;
j = CurrentPos.y;
printf(" \n寻路过程如下栈顶元素的 x = %d ,y = %d....\n",i,j);
if(MAP[i][j+1] == 1) //表明向下一格走得通
{
printf("\n向下能走动"); //向下前进一步，压栈，标记
j++;
PathAddToStack(i,j,temp,robot);
}
else if( MAP[i + 1][j] == 1)
{
printf("\n向右能走动");
i++;
PathAddToStack(i,j,temp,robot);
}
else if(MAP[i - 1][j] == 1)
{
printf("\n向左能走动");
i--;
PathAddToStack(i,j,temp,robot);
}
else if(MAP[i][j - 1] == 1)
{
printf("\n向上能走动");
j--;
PathAddToStack(i,j,temp,robot);
}
else //都走不动
{
printf("\n都走不动，退栈");
Pop(robot,temp);
}
}while( GetTop(robot).x != endx || GetTop(robot).y != endy); //只要栈顶元素的x,y不等于终点坐标的x,y,则一直循环找路径
printf("\n完成!\n");
Print_Path(robot); //打印出坐标值
}
int main() //入口函数
{
MAZH_SOLVE(7,7);
return 0;
}
/*
二. 栈的应用-迷宫解题
*/
#include<stdio.h>
#include<malloc.h>
#include<stdlib.h>
#define TRUE 1
#define FALSE 0
#define OK 1
#define ERROR 0
#define INFEASIBLE -1
#define OVERFLOW -2
//坐标类型
typedef struct
{
int x;
int y;
}Postype;
//栈的元素类型
typedef struct
{
int x;
int y;
}ElemType;
//二维数组，存储迷宫
int MAP[7][7] =
{
1,0,0,1,1,1,1,
1,0,0,1,1,1,1,
1,1,1,1,0,1,1,
1,0,1,0,1,1,1,
1,0,1,0,1,1,1,
1,0,1,0,1,1,1,
0,0,1,1,1,1,1,
};
/*-------------------------------------栈的元素类型定义完毕-------------------------*/
typedef int Status; //函数返回值
#define STACK_INIT_SIZE 5 // 栈的初始大小
#define STACK_INCREMENT 10 // 每次增加的空间大小
//下面给出栈的相关定义
typedef struct
{
ElemType *base; //在构造栈之前和销毁之后，base的值为NULL
ElemType *top; //栈顶指针
int stacksize; //当前已分配的存储空间，以元素为单位
}ZJC_Stack;
//--------------------------------------栈基本操作的算法部分--------------------------
//栈的初始化
Status InitStack(ZJC_Stack &S)
{
S.base = (ElemType *)malloc(STACK_INIT_SIZE * sizeof(ElemType)); //分配内存空间
if(!S.base){
exit(OVERFLOW);
}
else //否则分配成功
{
S.top = S.base;
S.stacksize = STACK_INIT_SIZE;
return OK;
}
}
//获得栈顶元素
ElemType GetTop(ZJC_Stack S)
{
if(S.top == S.base )
exit(ERROR);
return *(S.top - 1);
}
//压栈
Status Push(ZJC_Stack &S,ElemType e)
{
if(S.top - S.base >= S.stacksize)
{
S.base = (ElemType*)realloc(S.base,(S.stacksize + STACK_INCREMENT) * sizeof(ElemType));
if(!S.base)
exit(OVERFLOW);
S.top = S.base + S.stacksize;
S.stacksize += STACK_INCREMENT;
}
*S.top++ = e;
return OK;
}
void Print_Path(ZJC_Stack S) //打印出栈中的元素
{
printf("\n寻路完成..路径坐标值如下：......\n");
ElemType *p = S.base; //首先p指向栈底指针
ElemType temp;
while( p != S.top) //只要没有到顶端，指针就移动，然后输出元素值
{
temp = *p;
printf("\n路径 x = %d , y = %d",temp.x,temp.y);
p++;
}
}
//出栈函数
Status Pop(ZJC_Stack &S,ElemType &e)
{
if(S.top == S.base ) //空栈，返回错误
return ERROR;
else //不是空栈
{
e = * --S.top;
return OK;
}
}
void PathAddToStack(int i,int j,ElemType temp,ZJC_Stack &robot) //因为要修改值，所以取地址，开始没加取地址符号，栈顶元素一直是(1,1)
{
temp.x = i,temp.y = j;
Push(robot,temp);
MAP[i][j] = 2; //标记已经走过该格子了,当初想是否需要用其他标记，实际上不需要的，既然标记2，那么证明当然可以走过(不是墙)!
}
void MAZH_SOLVE(int endx,int endy) //解决迷宫问题函数,参数为终点的坐标
{
int i = 0,j = 0; //起点坐标
ZJC_Stack robot; //定义栈；
if(InitStack( robot ) ) //初始化栈
printf("\n栈的初始化完成....\n");
ElemType CurrentPos ; //当前位置
ElemType start; //初始位置的相关信息
ElemType temp; //暂时用的
start.x = i;
start.y = j;
temp = start;
MAP[i][j] = 2; //走过的标记为2
Push(robot,start); //初始位置入栈
printf("\n开始寻路....\n");
do //主要寻路算法：
{
CurrentPos = GetTop(robot);
i = CurrentPos.x;
j = CurrentPos.y;
printf(" \n寻路过程如下栈顶元素的 x = %d ,y = %d....\n",i,j);
if(MAP[i][j+1] && MAP[i][j+1] == 1) //表明向下一格走得通
{
printf("\n向下能走动"); //向下前进一步，压栈，标记
j++;
PathAddToStack(i,j,temp,robot);
}
else if( MAP[i + 1][j] && MAP[i + 1][j] == 1)
{
printf("\n向右能走动");
i++;
PathAddToStack(i,j,temp,robot);
}
else if(MAP[i - 1][j] && MAP[i - 1][j] == 1)
{
printf("\n向左能走动");
i--;
PathAddToStack(i,j,temp,robot);
}
else if(MAP[i][j - 1] && MAP[i][j - 1] == 1)
{
printf("\n向上能走动");
j--;
PathAddToStack(i,j,temp,robot);
}
else //都走不动
{
printf("\n都走不动，退栈");
Pop(robot,temp);
}
}while( GetTop(robot).x != endx || GetTop(robot).y != endy); //只要栈顶元素的x,y不等于终点坐标的x,y,则一直循环找路径
printf("\n完成!\n");
Print_Path(robot); //打印出坐标值
}
int main() //入口函数
{
MAZH_SOLVE(6,6);
return 0;
}
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。