C++数据结构关于栈迷宫求解示例

一、实验目的

理解栈的抽象数据类型定义及操作特点。掌握顺序栈的存储结构的描述。掌握顺序栈的基本操作的实现方法。理解栈的广泛应用。

二、预备知识

阅读课程教材p44~45页内容，掌握栈的逻辑定义及“后进先出”的特点，理解抽象数据类型栈的定义。阅读课程教材p45~47页内容，理解顺序栈的存储特点及存储表示，掌握顺序栈各种基本操作（initstack、stackempty、gettop、push、pop等）的实现方法。阅读课程教材p50~52页内容，理解“迷宫求解”问题的含义，体会求解过程中栈的应用。仔细分析主要实现算法，理解求解步骤和方法。

三、实验内容

按如下要求编写程序，进行调试，写出调试正确的源代码，给出测试结果。
1．完成顺序栈的存储表示，实现顺序栈的各种基本操作，包括initstack、stackempty、gettop、push、pop等操作。
2．利用顺序栈求解迷宫中从入口到出口的一条路径，并输出结果。
说明：
（1）使用二维数组maze描述迷宫，迷宫的规模及初态自定。
（2）路径的输出形式可用文字描述，也可用图形描述。

定义一些代码：

#include<iostream>
#include<cstdlib>
#define stack_init_size 100
#define stackincrement 10
typedef struct {//栈元素类型
	int x;//坐标
	int y;//坐标
	int di;//方向
}position;
using namespace std;
typedef struct {//栈
	position *base;
	position *top;
	int stacksize;
}stack;
/*************************迷宫**********************************/
int maze[10][10] = {//迷宫 maze（妹子）原型如下图：1表示路不通0表示可以通过。
//   0 1 2 3 4 5 6 7 8 9 
	{1,1,1,1,1,1,1,1,1,1},//0
	{1,0,0,1,0,0,0,1,0,1},//1
	{1,0,0,1,0,0,0,1,0,1},//2
	{1,0,0,0,0,1,1,0,0,1},//3
	{1,0,1,1,1,0,0,0,0,1},//4
	{1,0,0,0,1,0,0,0,0,1},//5
	{1,0,1,0,0,0,1,0,0,1},//6
	{1,0,1,1,1,0,1,1,0,1},//7
	{1,1,0,0,0,0,0,0,0,1},//8
	{1,1,1,1,1,1,1,1,1,1} //9
};

定义类

class boos {//创建了一个角色类
private:
	stack sq_stack;//栈
	position temp;
public:
	/******************************栈的基本方法*******************/
	void initstack() {//创建栈
	bool stackempty()//判断是否空栈
	bool gettop(position &temp)//获得栈顶
	bool push(position &temp)//入
	bool pop(position &temp)//出栈
	void free_stack()//释放栈空间
	
/******************************走迷宫方法*******************/
	bool findmaze(int star_x, int star_y, int endr_x, int end_y) 
					//迷宫的入口和出口坐标
};

类的成员函数的一些说明：

这是一些基础方法 用于对栈的操作。

void initstack() {//创建空的栈
		sq_stack.base = (position *)malloc(sizeof(stack)*stack_init_size);
		if (!sq_stack.base) exit(-1);
		sq_stack.top = sq_stack.base;/*fhl*/
		sq_stack.stacksize = stack_init_size;
		cout << "栈创建成功" << endl;
	}
	bool stackempty() {判断是否空栈
		if (sq_stack.top == sq_stack.base)return 1;
		else 
			return 0;
	}
	bool gettop(position &temp) {//得到栈顶元素
		if (stackempty())return false;
		 temp= *(sq_stack.top-1);
		 return true;
	}
	bool push(position &temp){//入栈/*fhl*/
		if (sq_stack.top - sq_stack.base >= sq_stack.stacksize) {
			sq_stack.base = (position*)realloc(sq_stack.base

		 sizeof(position)*(sq_stack.stacksize + stackincrement));
			if(!sq_stack.base) exit(-1);/*fhl*/
			sq_stack.top = sq_stack.base + sq_stack.stacksize;
			sq_stack.stacksize += stackincrement;
		}
		
		*sq_stack.top = temp;
		sq_stack.top++;
		return true;
	}
	bool pop(position &temp) {//出栈
		if (stackempty())  return 0; 
		 sq_stack.top--;
		 temp = *sq_stack.top;
		return 1;
	}
	void free_stack() {
		free(sq_stack.base);
	}

找迷宫的方法（dfs算法）

bool findmaze(int star_x, int star_y, int endr_x, int end_y) {//迷宫的入口和出口坐标
		int i, j, k = 0;//i j表示目前的坐标
		int tep_di,next_x,tep_y;//下一步的坐标
		bool flag;
		position fan_maze[200];
		initstack();//先创建空栈
		temp.x = star_x, temp.y = star_y, temp.di - 1;//开始位置
		push(temp);//入栈操作。/*fhl*/
		maze[star_x][star_y]=-1;//-1表示走过；
		while (!stackempty()) {//栈不为空
			gettop(temp);/*fhl*/
			 i = temp.x, j = temp.y , tep_di=temp.di;
			if (i == endr_x && j == end_y) {
				cout << "找到走出迷宫的路" << endl;
				k = 0;
				while (!stackempty()) {
					pop(temp);
					fan_maze[k] = temp;
					k++;//k指向下一个被插入的位置；
				}
				cout <<"起点："<< "(" << fan_maze[k-1].x << ',' << fan_maze[k-1].y << ")->" << endl;
				int count = 1;
				for(k-=2;k>0;k--) {
					cout<<"(" << fan_maze[k].x <<','<< fan_maze[k].y<<")->";
					if (count % 3 == 0) cout << endl;
					count++;
				}
				cout  << "(" << fan_maze[0].x << ',' << fan_maze[0].y << ")" << "终点" << endl;//出口的位置
				free_stack();//释放申请的堆空间
				return true;
			}/*fhl*/
			flag = 0;
			while (tep_di < 4 && !flag) {
				tep_di++;
				if (tep_di == 0){ next_x = i;	tep_y = j + 1;}
				else if (tep_di == 1) { next_x = i + 1;tep_y = j; }
				else if (tep_di == 2) { next_x = i;tep_y = j - 1; }
				else { next_x = i - 1; tep_y = j; }
				
				if( maze[next_x][tep_y] == 0 ) flag = 1;
			}
				if(flag) {
					(sq_stack.top-1)->di = tep_di;//记录上次坐标走的方向。
					temp.x = next_x, temp.y = tep_y,temp.di=-1;
					push(temp);//这次坐标入栈
					maze[next_x][tep_y] = -1;//当前坐标标记为走过。
				}
				else {
					pop(temp);
					maze[temp.x][temp.y] = 0;
				}
			
		}/*fhl*/
		cout << "没有找到对应的出口" << endl;
		free_stack();//释放申请的堆空间
		return false;
	}

};

主函数(创建对象)

int main() {
	boos l1;
	l1.findmaze(1,1,8,8);
	system("pause");/*fhl*/
	return 0;
}

运行的一些截图：

1.当入口和终点一样时：

int main() {
	boos l1;
	l1.findmaze(1,1,1,1);
	system("pause");
	return 0;
}

2.终点是可以到达的路径

2.1（8,8）是终点

int main() {
	boos l1;
	l1.findmaze(1,1,8,8);
	system("pause");
	return 0;
}

2.2（8,2）是终点

int main() {
	boos l1;
	l1.findmaze(1,1,8,2);
	system("pause");
	return 0;
}

3.出口不通的情况

int main() {
	boos l1;
	l1.findmaze(1,1,9,9);
	system("pause");
	return 0;
}

以上就是c++数据结构关于栈迷宫求解示例的详细内容，更多关于c++数据结构栈迷宫的资料请关注其它相关文章！