欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识！
您现在的位置是： 首页

迷宫（1）---利用顺序栈实现

程序员文章站 2022-05-20 20:25:30
...

头文件如下：

  • AfxStd.h
#ifndef AFXSTD_H
#define AFXSTD_H
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#include<malloc.h>
#include<assert.h>
#endif
  • SeqStack.h
#include"Maze.h"
#ifndef SEQSTACK_H
#define SEQSTACK_H
const int MaxSize = 100;
typedef SElemType ElemType;
typedef struct 
{
	ElemType *data;
	int maxsize;
	int top;
}SeqStack;
void InitStack(SeqStack *ps);
void DestroyStack(SeqStack *ps);
int StackSize(SeqStack *ps);
bool StackEmpty(SeqStack *ps);
void StackClear(SeqStack *ps);
bool StackFull(SeqStack *ps);
bool StackPush(SeqStack *ps, ElemType x);
bool StackPop(SeqStack *ps, ElemType &x);
#endif
  • Maze.h
#ifndef MAZE_H
#define MAZE_H
#define ROWSIZE 10
#define COLSIZE 10
#define Reachable 0		//可到达的节点
#define Bar	  1		//障碍物
#define Foot	  2		//足迹
#define Mark	  3		//不可通路标记
typedef int MapType[ROWSIZE][COLSIZE];
typedef struct
{
	int row;
	int col;
}PosType;        //坐标类型的结构体
typedef struct MElemType
{
	int ord;	
	PosType seat;
	int di;		
}SElemType;        //栈中将要存放的元素
bool MazePass(MapType maze, PosType pos);
void FootPrint();
PosType NexPos(PosType pos, int di);
void MarkPrint(MapType maze);
bool MarkPath(MapType maze, PosType start, PosType end);
void PrintMap(MapType maze);
#endif

源文件如下：

  • AfxStd.cpp
#include"AfxStd.h"
  • Maze.cpp
#include"AfxStd.h"
#include"SeqStack.h"
#include"Maze.h"

SeqStack st;//声明一个栈
bool MazePass(MapType maze, PosType pos)  //判断该位置是否可达
{
	return maze[pos.row][pos.col] == Reachable;
}

void FootPrint()        //打印输出足迹
{
	printf("迷宫路径如下:\n");
	for (int i = 0; i <st.data[st.top].ord; i++)
	{
		printf("\t(%d,%d)", st.data[i].seat.row, st.data[i].seat.col);
		if((i + 1) % 5 == 0)printf("\n");
	}
	printf("\n");
}

PosType NexPos(PosType pos, int di)//取下一个方块
{
	switch (di)
	{
	case 0:pos.row -= 1; break;
	case 1:pos.col += 1; break;
	case 2:pos.row += 1; break;
	case 3:pos.col -= 1; break;
	}
	return pos;
}

void MarkPrint(MapType maze)
{
	int count = 0;
	printf("阻塞的路径是：\n");
	for (int i = 1; i < ROWSIZE-1; ++i)
	{
		for (int j = 1; j < COLSIZE - 1; ++j)
		{
			if (maze[i][j] == Mark)
			{
				++count;
				printf("\t(%d,%d)", i, j);
				if (count % 5 == 0)printf("\n");
			}
		}
	}
}

bool MarkPath(MapType maze, PosType start, PosType end)
{
	int i, j,di;
	bool find;
	PosType nexpos;
	InitStack(&st);
	
	SElemType x;
	x.di = -1;		//最开始不指向任何方向
	x.ord = 1;
	x.seat = start;
	StackPush(&st, x);
	maze[st.data[st.top].seat.row][st.data[st.top].seat.col] = Foot;

	while (st.top > -1)
	{
		find = false;
		i = st.data[st.top].seat.row;
		j = st.data[st.top].seat.col;
		if (i == end.row&&j == end.col)
			return true;
		
		di = st.data[st.top].di;	//确定初始的方向
		while (di < 4&&!find)
		{
			if(di==-1)di++;

			nexpos = NexPos(st.data[st.top].seat,di);
			if (MazePass(maze, nexpos))
				find = true;

			di++;
		}

		if (find)
		{
			st.data[st.top].di = di-1;	//修改原栈顶元素的di值
			SElemType x;
			x.ord = st.data[st.top].ord + 1;
			x.seat = nexpos;
			x.di = -1;

			StackPush(&st, x);
			maze[nexpos.row][nexpos.col] = Foot;
		}
		else
		{
			maze[st.data[st.top].seat.row][st.data[st.top].seat.col] = Mark;
			StackPop(&st, st.data[st.top]);
		}
	}
	return false;
}

void PrintMap(MapType maze)
{
	for (int i = 0; i < ROWSIZE; ++i)
	{
		for (int j = 0; j < COLSIZE; ++j)
		{
			printf("\t%d", maze[i][j]);
		}
		printf("\n");
	}
}
  • SeqStack.cpp
#include"AfxStd.h"
#include"SeqStack.h"

/*****************************************************************
*函数名：InitStack
*函数参数：ps-指针
*函数功能描述：初始化栈
*函数返回值：无返回值
*作者：王赋睿
*函数创建日期：2018.6.5
*函数修改日期：尚未修改
*修改人：尚未修改
*修改原因：尚未修改
*版本：1.0
*历史版本：无
*****************************************************************/
void InitStack(SeqStack *ps)
{
	assert(ps != NULL);
	ps->data = (ElemType *)malloc(sizeof(ElemType)*MaxSize);
	if (ps->data == NULL)
	{
		exit(1);
	}
	ps->maxsize = MaxSize;
	ps->top = -1;
}
/*****************************************************************
*函数名：DestroyStack
*函数参数：ps-指针
*函数功能描述：摧毁栈
*函数返回值：无返回值
*作者：王赋睿
*函数创建日期：2018.6.5
*函数修改日期：尚未修改
*修改人：尚未修改
*修改原因：尚未修改
*版本：1.0
*历史版本：无
*****************************************************************/
void DestroyStack(SeqStack *ps)
{
	assert(ps != NULL);
	free(ps->data);
	ps->data = NULL;
	ps->maxsize = 0;
	ps->top = -1;
}

/*****************************************************************
*函数名：StackSize
*函数参数：ps-指针
*函数功能描述：统计栈中元素个数
*函数返回值：栈中元素个数；栈未初始化，返回-1
*作者：王赋睿
*函数创建日期：2018.6.5
*函数修改日期：尚未修改
*修改人：尚未修改
*修改原因：尚未修改
*版本：1.0
*历史版本：无
*****************************************************************/
int StackSize(SeqStack *ps)
{
	assert(ps != NULL);
	return ps->top + 1;
}

/*****************************************************************
*函数名：StackEmpty
*函数参数：ps-指针
*函数功能描述：判断栈是否为空
*函数返回值：栈空返回true，栈不空返回false
*作者：王赋睿
*函数创建日期：2018.6.5
*函数修改日期：尚未修改
*修改人：尚未修改
*修改原因：尚未修改
*版本：1.0
*历史版本：无
*****************************************************************/
bool StackEmpty(SeqStack *ps)
{
	assert(ps != NULL);
	return ps->top == -1;
}

/*****************************************************************
*函数名：StackClear
*函数参数：ps-指针
*函数功能描述：清空栈
*函数返回值：无返回值
*作者：王赋睿
*函数创建日期：2018.6.5
*函数修改日期：尚未修改
*修改人：尚未修改
*修改原因：尚未修改
*版本：1.0
*历史版本：无
*****************************************************************/
void StackClear(SeqStack *ps)
{
	assert(ps!= NULL);
	ps->top = -1;
}

/*****************************************************************
*函数名：StackFull
*函数参数：ps-指针
*函数功能描述：清空栈
*函数返回值：无返回值
*作者：王赋睿
*函数创建日期：2018.6.5
*函数修改日期：尚未修改
*修改人：尚未修改
*修改原因：尚未修改
*版本：1.0
*历史版本：无
*****************************************************************/
bool StackFull(SeqStack *ps)
{
	assert(ps != NULL);
	return(StackSize(ps) == ps->maxsize);
}

/*****************************************************************
*函数名：StackPush
*函数参数：ps-指针
*函数功能描述：入栈
*函数返回值：入栈成功，返回true；否则返回false
*作者：王赋睿
*函数创建日期：2018.6.5
*函数修改日期：尚未修改
*修改人：尚未修改
*修改原因：尚未修改
*版本：1.0
*历史版本：无
*****************************************************************/
bool StackPush(SeqStack *ps, ElemType x)
{
	assert(ps != NULL);
	if (StackFull(ps))
	{
		return false;
	}
	ps->top += 1;
	ps->data[ps->top] = x;
	return true;
}

/*****************************************************************
*函数名：StackPush
*函数参数：ps-指针， x-ElemType类型的变量 
*函数功能描述：出栈，由x带回栈顶元素，栈顶指针下移一位
*函数返回值：出栈成功，返回true；出栈失败，返回false
*作者：王赋睿
*函数创建日期：2018.6.5
*函数修改日期：尚未修改
*修改人：尚未修改
*修改原因：尚未修改
*版本：1.0
*历史版本：无
*****************************************************************/
bool StackPop(SeqStack *ps, ElemType &x)
{
	assert(ps != NULL);
	if (StackEmpty(ps))
	{
		return false;
	}
	else
	{
		x = ps->data[ps->top];
		ps->top -= 1;
		return true;
	}
}

测试文件：

  • test.cpp
#include"AfxStd.h"
#include"Maze.h"
#include"SeqStack.h"
int main() {
	MapType maze = {
	{ 1,1,1,1,1,1,1,1,1,1 },
	{ 1,0,0,1,0,0,0,1,0,1 },
	{ 1,0,0,1,0,0,0,1,0,1 },
	{ 1,0,0,0,0,1,1,0,0,1 },
	{ 1,0,1,1,1,0,0,0,0,1 },
	{ 1,0,0,0,1,0,0,0,0,1 },
	{ 1,0,1,0,0,0,1,0,0,1 },
	{ 1,0,1,1,1,0,1,1,0,1 },
	{ 1,1,0,0,0,0,0,0,0,1 },
	{ 1,1,1,1,1,1,1,1,1,1 },
	};
	PosType start, end;
	start.row = 1;
	start.col = 1;
	end.row = 8;
	end.col = 8;
	bool find = MarkPath(maze, start, end);
	if (find)
	{
		PrintMap(maze);
		FootPrint();
		MarkPrint(maze);
	}
	return 0;
}
迷宫（1）---利用顺序栈实现
本程序在VS2017下运行通过
相关标签： 迷宫

上一篇： json 数据之间的转换

下一篇： LeetCode 面试题55 - II. 平衡二叉树（树的高度的预处理、DFS）

推荐阅读