标签：依次   RoCE   空间   col   插入   har   10个   入栈   目的   

链接地址：【C/C++】迷宫问题详情分析--栈的应用

引言

这是一个简单的顺序栈的应用求解迷宫问题，主要分享的是在求解这个问题的之前的准备，
分析所需的数据，获得正确的数据结构，分析所需要的功能，划分模块，再分析各模块中，需要的具体功能，以确定功能函数。
这样也书写代码时，就可以事半功倍。

一，问题描述

迷宫求解问题
提出以一个m*n的长方阵表示迷宫，0和1分别表示迷宫中的通路和障碍。迷宮问题要求，求出从入口(x，y)到出口(x，y)的一条通路，或得出没有通路的结论。
基本要求：首先实现一个以链表作存储结构的栈类型，然后编写一个求迷宫问题的非递归程序，求得的通路。
要求用栈实现迷宫问题的求解

将要构建的迷宫：向下为x正方向；向右为y正方向

二，分析所用数据结构

迷宫结构体用于存储构建的迷宫数据。
坐标结构体和栈元素结构体都是服务于栈结构体。

三、所需函数及其功能

这幅图可以很清晰的，了解都有哪些函数，这些函数的功能又是什么。
图中很多函数都是为了一个函数服务的，即求解迷宫的函数。
蓝色底的函数，实现了但是没有测试，大家可以自行测试

四、程序执行详细框图

这是整个迷宫问题项目的详细执行过程。大家可以先看看，到时候阅读代码也会更加清洗直观。
不同的颜色，是一个不同的模块，实现相应的功能

五、代码实现-详细注释

代码相应的地方都有注释，也体现了我思考的过程，如有错误或者更优解，欢迎在指正讨论。

1、maze.h

#ifndef __MAZE_H__    
#define __MAZE_H__

#include 
#include 
#include 

#define TRUE 1
#define FALSE 0

#define STACK_INIT_SIZE 100
#define STACKINCREMENT 10

#define COLUMN 10  //列
#define ROW 10	   //行

typedef struct{
	char** maze;		//迷宫二维数组
	int** footprint;	//足迹二维数组
	int row;
	int column;
}MazeType;

typedef struct{
	int x;
	int y;
}PosType;

typedef struct{
	int ord;			//通道块在路径上的序号
	PosType seat;		//通道块在迷宫中的“坐标位置”
	int di;				//从此通道块走向下一个通道块的“方向”
}SElemType;

typedef struct{
	SElemType* base;
	SElemType* top;
	int stacksize;
}SqStack;

//构造一个空栈
bool InitStack(SqStack* S);
//初始化迷宫数据
bool InitMaze(MazeType* M);
//判断是否为空栈
bool IsStackEmpty(SqStack S);
//入栈，元素e为新的栈顶元素，传入e形参拷贝值，返回改变的栈S，及是否入栈成功
bool Push(SqStack* S, SElemType e);
//出栈,指针传入地址，直接改变e变量，即返回改变的e和栈S，及是否出栈成功
bool Pop(SqStack* S, SElemType* e);
//输出迷宫
bool PrintfMaze(MazeType* M);
//输出迷宫的路径
bool PrintfFoot(MazeType* M, SqStack* S);
//将迷宫的当前位置Pos设置为“走过”，即footprint该位置为1
bool FootPrint(MazeType* M, PosType pos);
//判断当前位置是否走过
bool Pass(MazeType* M, PosType pos);
//创建新的节点，用step,pos,d初始化该点
SElemType NewSElemType(int step, PosType pos, int d);
//将位置pos的方向设为d
PosType NextPos(PosType pos, int d);
//若迷宫maze中存在从入口start到出口end的通道，则求得一条存放在栈中（从栈底到栈顶）
bool MazePath(SqStack* S, MazeType maze, PosType start, PosType end);


//清空栈
bool ClearStack(SqStack* S);
//从栈底到栈顶依次对每个元素进行访问
bool StackTravel(const SqStack* S);
//返回栈的长度，即S元素的个数
int StackLength(SqStack S);
//若栈不为空，则用e返回S的栈顶元素
bool GetTop(SqStack S, SElemType* e);


#endif 

2、maze.c

#include "maze.h"

//构造一个空栈
bool InitStack(SqStack* S)
{
	//100*SElemType
	S->base = (SElemType*)malloc(STACK_INIT_SIZE*sizeof(SElemType));	
	if(!S->base)
	{	
		printf("申请空间失败，迷宫无法初始化.\n");
		return false;
	}

	S->top = S->base;
	S->stacksize = STACK_INIT_SIZE;
	return true;
}

//初始化迷宫数据
bool InitMaze(MazeType* M)
{
	char mz[ROW][COLUMN]={	
	{‘#‘,‘ ‘,‘#‘,‘#‘,‘#‘,‘#‘,‘#‘,‘#‘,‘#‘,‘#‘},
	{‘#‘,‘ ‘,‘ ‘,‘#‘,‘ ‘,‘ ‘,‘ ‘,‘#‘,‘ ‘,‘#‘},
	{‘#‘,‘ ‘,‘ ‘,‘#‘,‘ ‘,‘ ‘,‘ ‘,‘#‘,‘ ‘,‘#‘},
	{‘#‘,‘ ‘,‘ ‘,‘ ‘,‘ ‘,‘#‘,‘#‘,‘ ‘,‘ ‘,‘#‘},
	{‘#‘,‘ ‘,‘#‘,‘#‘,‘#‘,‘ ‘,‘ ‘,‘ ‘,‘ ‘,‘#‘},
	{‘#‘,‘ ‘,‘ ‘,‘ ‘,‘#‘,‘ ‘,‘#‘,‘ ‘,‘#‘,‘#‘},
	{‘#‘,‘ ‘,‘#‘,‘ ‘,‘ ‘,‘ ‘,‘#‘,‘ ‘,‘ ‘,‘#‘},
	{‘#‘,‘ ‘,‘#‘,‘#‘,‘#‘,‘ ‘,‘#‘,‘#‘,‘ ‘,‘#‘},
	{‘#‘,‘#‘,‘ ‘,‘ ‘,‘ ‘,‘ ‘,‘ ‘,‘ ‘,‘ ‘,‘ ‘},
	{‘#‘,‘#‘,‘#‘,‘#‘,‘#‘,‘#‘,‘#‘,‘#‘,‘#‘,‘#‘},
	};

	M->maze = (char **)malloc(sizeof(char*)*ROW);		//相当于分配一维数组空间，10个char*变量空间
	M->footprint = (int **)malloc(sizeof(int*)*ROW);	//相当于分配一维数组空间，10个int*变量空间
	
	if(!M->maze || !M->footprint)
	{
		printf("申请空间失败，迷宫无法初始化.\n");
		return false;
	}

	for(int i = 0; i maze[i]=(char*)malloc(sizeof(char)*COLUMN);		//相当于分配二维数组空间，每个个char*指向，10个char大小变量空间
		M->footprint[i]=(int*)malloc(sizeof(int)*COLUMN);	//相当于分配二维数组空间，每个个int*指向，10个int大小变量空间
		if(!M->maze[i] || !M->footprint[i])
		{
			printf("申请空间失败，迷宫无法初始化.\n");
			return false;
		}
	}
	for(int i = 0; i maze[i][j] = mz[i][j];
			M->footprint[i][j] = 0;
		}
	}
	M->row = ROW;
	M->column = COLUMN;
	return true;
}

//判断是否为空账
bool IsStackEmpty(SqStack S)
{
	if(S.top == S.base)
		return true;
	else
		return false;
}

//入栈，元素e为新的栈顶元素，传入e形参拷贝值，返回改变的栈S，及是否入栈成功
bool Push(SqStack* S, SElemType e)
{
	//结构体类型，按单位大小相减类比int型，每个int型为4byte，相减2-1也是按斯单位相减
	if(S->top - S->base >= S->stacksize)	//如果超出本来的长度，进行动态的添加，每一次添加10个SElemType大小空间,STACKINCREMENT=10
	{
		S->base = (SElemType*)realloc(S->base,(S->stacksize + STACKINCREMENT)*sizeof(SElemType));
		if(!S->base);
		{
			printf("重新申请空间失败.\n");
			return false;
		}
		S->top = S->base + S->stacksize;	//栈顶指针指向原先栈的尾部，栈底+栈长度
		S->stacksize +=STACKINCREMENT;		//栈的长度+10
	}
	*S->top++=e;	//栈顶指针+1前进，并且e赋值给解引用的指针，入栈
	//后置++/--为第一优先级，*和前置++/--为第二优先级
	return true;
}

//出栈,指针传入地址，直接改变e变量，即返回改变的e和栈S，及是否出栈成功
bool Pop(SqStack* S, SElemType* e)
{
	if(S->top == S->base)
	{
		printf("栈为空.\n");
		return false;
	}
	*e = *(--S->top);	//栈顶指针-1返回，并且解引用赋值给e
	return true;
}

//输出迷宫
bool PrintfMaze(MazeType* M)
{
	printf("%s","xy");
	for(int i=0;icolumn;i++)
	{
		printf("%d",i);
	}
	printf("\n");
	
	for(int i=0; irow; i++)
	{
		printf("%d ",i);
		for(int j=0; jcolumn; j++)
		{
			printf("%c",M->maze[i][j]);
		}
		printf("\n");
	}
	printf("\n");
	
	//footprintf
	printf("%s","xy");
	for(int i=0;icolumn;i++)
	{
		printf("%d",i);
	}
	printf("\n");
	for(int i=0; irow; i++)
	{
		printf("%d ",i);
		for(int j=0; jcolumn; j++)
		{
			printf("%d",M->footprint[i][j]);
		}
		printf("\n");
	}
	printf("\n");

	return true;
}

//输出迷宫路径
bool PrintfFoot(MazeType* M, SqStack* S)
{
	SElemType* p;
	for(int i=0; irow; i++)		//将footprint置0
	{
		for(int j=0; jcolumn; j++)
		{
			M->footprint[i][j]=0;
		}
	}

	p = S->base;
	if(S->base == S->top)
	{
		printf("栈为空.\n");
		return false;
	}
	while(p != S->top)	//根据栈中存有的节点的坐标，对footprint进行1路径赋值
	{
		M->footprint[p->seat.x][p->seat.y] = 1;
		*p++;
	}
	for(int i=0; irow; i++)	//输出路径
	{
		for(int j=0; jcolumn; j++)
		{
			printf("%d",M->footprint[i][j]);
		}
		printf("\n");
	}
	return true;
}

//将迷宫的当前位置Pos设置为“走过”，即footprint该位置为1
bool FootPrint(MazeType* M, PosType pos)	//FootPrint足迹
{
	if((pos.x>M->row) || (pos.y>M->column))	
	{
		printf("坐标越界.\n");
		return false;
	}
	M->footprint[pos.x][pos.y]=1;
	return true;
}

//判断当前位置是否走过
bool Pass(MazeType* M, PosType pos)
{
	if((pos.x > M->row) || (pos.y > M->column))	
	{
		printf("坐标越界.\n");
		return false;
	}
	
	if((0 == M->footprint[pos.x][pos.y])&&(M->maze[pos.x][pos.y]==‘ ‘))
		return true;	//通路没走过
	else
		return false;	//通路走过或者墙
}

//创建新的节点，用step,pos,d初始化该点
SElemType NewSElemType(int step, PosType pos, int d)
{
	SElemType e;
	e.ord = step;
	e.seat = pos;
	e.di = d;
	return e;

}

//将位置pos的方向设为d
PosType NextPos(PosType pos, int d)
{
	switch(d)
	{
		case 1:	//向下
			pos.x++;
			break;
		case 2: //向右
			pos.y++;
			break;
		case 3: //向上
			pos.x--;
			break;
		case 4: //向左
			pos.y--;
			break;
		default:
			printf("error.\n");
	}
	return pos;
}

//若迷宫maze中存在从入口start到出口end的通道，则求得一条存放在栈中（从栈底到栈顶）
bool MazePath(SqStack* S, MazeType maze, PosType start, PosType end)
{
	int curstep = 1;
	SElemType e;
	PosType curpos = start;
	InitStack(S);
	do
	{
		if(true == Pass(&maze, curpos)) //通路没走过
		{
			FootPrint(&maze,curpos);////将当前点标记为走过
			e=NewSElemType(curstep,curpos,1);//创建栈元素，将当前点的信息存储，便于出入栈及改变当前点的di信息
			Push(S,e);
			if((curpos.x==end.x)&&(curpos.y==end.y))//终点
			{
				printf("迷宫路径:\n");
				PrintfFoot(&maze,S);//打印通路路径
				return true;
			}
			curpos = NextPos(curpos,1);//向当前点的di方向偏移 ，即下一个点
			curstep++;//步数+1
		}
		else //通路走过或者墙
		{
			if(!IsStackEmpty(*S))
			{
				Pop(S,&e);
				while(e.di==4 && !IsStackEmpty(*S)) //四个方向遍历完，说明此点不是正确道路，，且且栈不为空，就一直出栈
				{
					Pop(S,&e);
				}
				if(e.ditop = S->base;
	return true;
}

//从栈底到栈顶依次对每个元素进行访问
bool StackTravel(const SqStack* S)
{
	SElemType* p = S->base;
	if(S->base == S->top)
	{
		printf("栈为空.\n");
		return false;
	}
	printf("栈中元素:\n");
	while(p != S->top)
	{
		printf("x=%d,y=%d\n",p->seat.x,p->seat.y);
		*p++;
	}
	printf("\n");
	return true;
}

//返回栈的长度，即S元素的个数
int StackLength(SqStack S)
{
	return S.stacksize;
}

//若栈不为空，则用e返回S的栈顶元素
bool GetTop(SqStack S, SElemType* e)
{
	if(S.top == S.base)
	{
		printf("栈为空.\n");
		return false;
	}
	else
	{
		*e = *(S.top - 1);
		//printf("栈顶元素:%c\n",*e);
		return true;
	}
}

3、maze.c

#include "maze.h"
int main()
{
	MazeType maze;
	SqStack *stack =(SqStack *)malloc(sizeof(SqStack));
	PosType start,end;
	start.x = 1;
	start.y = 6;
	end.x = 8;
	end.y = 9;

	InitMaze(&maze);
	
	printf("maze:\n");
	PrintfMaze(&maze);

	if(true == MazePath(stack,maze,start,end))
		printf("maze can out.\n");
	else
		printf("maze can not out.\n");
		
	StackTravel(stack);
	printf("栈的长度:%d\n",StackLength(*stack));
	
	SElemType ele;
	GetTop(*stack,&ele);
	printf("栈顶元素:ord=%d,x=%d,y=%d,di=%d\n",ele.ord,ele.seat.x,ele.seat.y,ele.di);

	ClearStack(stack);
	GetTop(*stack,&ele);
	
	//销毁栈——销毁free空间，需要在同一个内存空间销毁
	free(stack);
	stack=NULL;
	
	return 0;
}

六，效果展示

此测试起点（1，6），终点（8，9）

相信大家看到这个结果是会有疑问的，因为虽然得到一条正确的迷宫路径，但却不是最优解，这是为什么呢？

依旧存在缺陷的迷宫算法，无法获得最优路径解，因为遍历的方向固定，所以大家有什么办法可以优化它呢？

如有不足之处，还望指正 ^[1]。

【C/C++】迷宫问题详情分析--栈的应用

标签：依次   RoCE   空间   col   插入   har   10个   入栈   目的   

原文地址：https://www.cnblogs.com/CoutCodes/p/14147797.html