链式栈结构的实现
 
思路：
 
使用链式栈存储可通过的路径；
 
若当前结点已经走过上下左右四个方向仍不可通行，则把这个点弹出；
 
具体迷宫实现是课本的函数例子。
 
 
 
代码部分
 
#include<string>
#include<iostream>

using namespace std;

#define OK 1
#define ERROR 0
typedef int SElemType;
typedef int Status;

typedef struct//迷宫
{
	int x;
	int y;
}PosType;

typedef struct {//使用结构体存储栈中元素
	int ord;//通道块在路径中的序号
	PosType seat;//通道块在迷宫中的“坐标位置”
	int di;//从此通道块走向下一通道块的“方向”
}MazeNode;

typedef struct SNode {//链式存储栈结点
	MazeNode data;
	struct SNode* next;
}StackNode;

typedef struct LStack//链式栈结构
{
	StackNode *top;
	StackNode *bottom;//定义栈底，却不对栈底进行操作
	int size;
}LinkStack;

int Maze[10][10] = {  //定义迷宫
{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,0,0,1},
{1,0,0,0,0,1,1,0,1,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}
};

LinkStack InitStack(LinkStack s)//栈初始化
{
	s.top = s.bottom = NULL;
	s.size = 0;
	return s;
}

int StackEmpty(LinkStack s)//判断栈是否为空
{
	if (s.top == NULL && s.bottom == NULL)
	{
		return ERROR;
	}
	else
	{
		return OK;
	}
}

LinkStack push(LinkStack s, MazeNode x)//进栈操作
{
	StackNode *t = (StackNode *)malloc(sizeof(StackNode));
	if (t == NULL)
		return s;
	if (StackEmpty(s) == ERROR)
	{
		s.top = s.bottom = t;
		t->next = NULL;
		s.top->data = x;
		printf("(%d,%d)\n", s.top->data.seat.x, s.top->data.seat.y);
		s.size++;
		printf("%d\n", s.size);
		return s;
	}
	else
	{
		t->next = s.top;//续上原来的栈顶
		s.top = t;
		s.top->data = x;
		s.size++;
		return s;

	}
}

LinkStack pop(LinkStack s)//出栈操作
{
	StackNode *t;
	MazeNode q;
	if (StackEmpty(s) == ERROR)
	{
		printf("栈为空，无法进行出栈操作\n");
		return s;
	}
	if (s.top == s.bottom)//出栈元素为栈底元素
	{
		q = s.top->data;
		printf("出栈元素为(%d,%d)\n", q.seat.x, q.seat.y);
		free(s.top);
		s.top = s.bottom = NULL;
		s.size--;
		return s;
	}
	else
	{
		q = s.top->data;
		printf("出栈元素为(%d,%d)\n", q.seat.x, q.seat.y);
		t = s.top->next;
		free(s.top);
		s.top = t;
		s.size--;
		return s;
	}
}

void PrintAll(LinkStack s)//输出所有栈中元素
{
	if (StackEmpty(s) == ERROR)
	{
		printf("此栈为空栈！\n");
	}
	printf("栈中元素为：");
	while (s.top != NULL)
	{
		printf("(%d,%d)\n", s.top->data.seat.x, s.top->data.seat.y);
		s.top = s.top->next;
	}
}

LinkStack DeleteStack(LinkStack s)//销毁栈
{
	StackNode *t;
	while (s.top != NULL)
	{
		t = s.top->next;
		free(s.top);
		s.top = t;
	}
	return s;
}



bool pass(PosType postion)//判断是否可以通过
{
	if (Maze[postion.x][postion.y] == 0)
	{
		return true;
	}
	else
	{
		return false;
	}
}

PosType NextPos(PosType now, int dirction)//转向函数
{
	PosType next;
	switch (dirction)
	{
	case 1:
	{
		next.x = now.x;
		next.y = now.y + 1;
		printf("向右走~\n");
		break;
	}
	case 2:
	{
		next.x = now.x + 1;
		next.y = now.y;
		printf("向下走~\n");
		break;
	}
	case 3:
	{
		next.x = now.x;
		next.y = now.y - 1;
		printf("向左走~\n");
		break;
	}
	case 4:
	{
		next.x = now.x - 1;
		next.y = now.y;
		printf("向上走~\n");
		break;
	}
	default:
		break;
	}
	return next;
}

void footprint(PosType p,int step)
{
	Maze[p.x][p.y] =4;//走过且走通的点标记为4
	printf("走过~");
}

void Markprint(PosType p)
{
	Maze[p.x][p.y] = -1;//走过且走不通的点退栈，标记为0
}


int main()
{
	printf("输出预设迷宫矩阵：\n");
	for (int i = 0; i < 10; i++)
	{
		for (int j = 0; j < 10; j++)
		{
			if (Maze[i][j] == 0)
			{
				printf("O\t");//走通路径
			}
			else
			{
				printf("#\t");//墙壁
			}
		}
		printf("\n");
	}
	LinkStack path;
	path.size = 0;
	path = InitStack(path);//栈初始化
	PosType curpose;
	curpose.x = 1;
	curpose.y = 1;
	int curstep = 1;//步数
	do
	{
		if (pass(curpose))//模仿课本程序
		{
			footprint(curpose,curstep);
			MazeNode e;
			e.di = 1;
			e.ord = curstep;
			e.seat.x = curpose.x;
			e.seat.y = curpose.y;
			path = push(path, e);
			if (curpose.x == 8 && curpose.y == 8)break;
			curpose = NextPos(curpose,e.di);
			curstep++;
		}
		else
		{                                 //这里课本错误，不应该直接pop，因为这时候curpose根本没有入栈
			if (StackEmpty(path) == OK)
			{
				MazeNode e=path.top->data;
				while (StackEmpty(path) == OK && path.top->data.di == 4)
				{
					path = pop(path);
					Markprint(path.top->data.seat);
					printf("栈顶元素为：(%d,%d)", path.top->data.seat.x, path.top->data.seat.y);
					curstep--;
					//break;
				}
				footprint(path.top->data.seat, curstep);
				if (path.top->data.di < 4)
				{
					curpose = NextPos(path.top->data.seat, path.top->data.di + 1);
					path.top->data.di++;
					curstep++;
					path=push(path, path.top->data);
				}
			}
		}

	} while (StackEmpty(path) == OK);
	printf("\n");
	printf("输出迷宫可走通路径：\n");
	for (int i = 0; i < 10; i++)               //输出迷宫结果
	{
		for (int j = 0; j < 10; j++)
		{
			if (Maze[i][j] == 4)
			{
				printf("√\t");//走通路径
			}
			else if (Maze[i][j] == -1)
			{
				printf("×\t");//未走通路径
			}
			else
			{
				printf("#\t");//墙壁
			}
		}
		printf("\n");
	}
	system("PAUSE");
	return 0;
}
 
运行结果
 

 
 
 
 
问题与反思
 
定义栈结构时，由于data又是一个mazenode栈，可以说栈又嵌套了栈，为函数外部的赋值造成了困难。以后要尽量避免。如果需要栈嵌套，函数最好使用指针传参，否则函数内部的值传不出去。

出现实现图：
 

 
 

 
 
.h文件实现堆栈简易操作（此处没有将声明与实现分离，应注意！）
 

#pragma warning (disable : 4715)
#ifndef  STACK_H
#define STACK_H
struct Position//结构体位置，表示迷宫每一格的行号和 列号
{
	int row;//行号
	int col;//列号
};
class Stack
{
public:
	Stack(int MaxSize = 10);
	~Stack() { delete[] Element; };
	bool IsEmpty() const { return top == -1; }
	bool IsFull() const { return top == Maxtop; }
	Position Top() const;//返回栈顶元素
	Stack& Add(Position &x);//添加元素
	Stack& Delete(Position &x);//删除元素
private:
	int top;//栈顶，入栈和出栈的地方。
	int Maxtop;//栈顶元素位置。
	Position *Element;
};
Stack::Stack(int MaxSize)
{
	Maxtop = MaxSize - 1;
	Element = new Position[MaxSize];
	top = -1;
}
Position Stack::Top() const
{
	if (IsEmpty())
	{
	}
	else
		return Element[top];
}
Stack& Stack::Add(Position &x)
{
	if (IsFull())
	{
	}
	else
	{
		++ top;
		Element[top].row = x.row;
		Element[top].col = x.col;
	}
	return *this;
}
Stack& Stack::Delete(Position &x)
{
	if (IsEmpty())
	{
	}
	else
	{
	
		x.row = Element[top].row;
		x.col = Element[top].col;
		--top;
	}
	return *this;
}
#endif 

 源文件：
 

#include<iostream>
#include"STack.h"
using namespace std;
int main()
{
	cout << "老鼠迷宫！" << endl;
//构建迷宫。maze[1][1]表示入口， maze[10][10]表示出口。
	char **maze = new char *[12];
	for (int i = 0; i < 12; ++i)
		maze[i] = new char[12];

	//给迷宫加“墙”。
	for (int i = 0; i < 12; ++i)
	{
		maze[11][i] = '+';
		maze[0][i] = '+';
		maze[i][0] = '+';
		maze[i][11] = '+';
	}
	//构建迷宫，用符号+表示墙壁，空格表示通路，以使迷宫尽可能好看！
	for (int a = 1; a < 11; ++a)
		for (int b = 1; b < 11; ++b)
			maze[a][b] = ' ';
	for (int i = 2; i < 7; ++i)
		maze[1][i] = '+';
	maze[2][6] = maze[2][8] = maze[3][4] = maze[3][6] = maze[4][2] = maze[4][4] = maze[4][6] = maze[4][8] = maze[4][9] = '+';
	maze[5][2] = maze[5][4] = maze[5][6] = maze[5][8] = maze[6][2] = maze[6][3] = maze[6][4] = maze[6][6] = maze[6][8] = maze[6][10] = '+';
	maze[7][2] = maze[7][6] = maze[7][8] = maze[7][10] = maze[8][2] = maze[8][4] = maze[8][5] = maze[8][6] = maze[8][8] = '+';
	maze[9][1] = maze[9][8] = maze[10][5] = maze[10][6] = maze[10][7] = maze[10][8] = '+';
	//输出迷宫 布局。
	cout << "迷宫如下所示：" << endl;
	for (int a = 0; a < 12; ++a)
	{
		for (int b = 0; b < 12; ++b)
			cout << maze[a][b] << " ";
		cout << endl;
	}
	//构建迷宫完毕，开始寻找路径。
	Stack* Path = new Stack(10*10 - 1);//栈用来储存路径以及遇到障碍物时方标返回上一步。

	Position offset[4];//设置模拟移动方法。
	offset[0].row = 0; offset[0].col = 1;//右移
	offset[1].row = 1; offset[1].col = 0;//下移
	offset[2].row = 0; offset[2].col = -1;//左移
	offset[3].row = -1; offset[3].col = 0;//上移

	Position here;//代表当前位置。
	here.col = 1;
	here.row = 1;
	maze[1][1] = '#';//入口堵住，防止返回入口。
	int option = 0;//上、下、左、右四种走法。记录走的次数，一共四次，上下左右分布探索。
	int Lastoption = 3;
	//模拟移动，开始寻找出口。
	while (here.row != 10 || here.col != 10)
	{
		int x, y;
		while (option <= Lastoption)//最多循环4次，尝试每种走法。
		{
			x = here.row + offset[option].row;
			y = here.col + offset[option].col;
			if (maze[x][y] == ' ')//只要寻找得到通路，就退出循环。
				break;
			option++;
		}
		if (option <= Lastoption)
		{//移动一次，是通路，此处位置入栈，移动数option归0。
			Path->Add(here);
			here.row = x;
			here.col = y;

			maze[x][y] = '*';//将该处修改为墙壁，防止返回，做重复工作。
			option = 0;
		}
		else//不是通路，会退一步，路径记录栈栈顶元素出栈。
		{
			if (Path->IsEmpty())//出现空栈，表明该迷宫没有出口！
				cout << "这个迷宫没有出口！" << endl;
			Position next;
			next.col = next.row = 0;
			Path->Delete(next);//新的位置，表示here的前一步，用来回退。

			if (next.row == here.row)
			option = 2 + next.col - here.col;//通过计算得出回退后应该执行哪一种走法！
			else
				option = 3 + next.row - here.row;
			here = next;
		}
	}
	cout << "老鼠找到了迷宫的出口！！" << endl;//以图形的样式输出寻找得到的路径。
	for (int i = 0; i < 12; ++i)
	{
		for (int a = 0; a < 12; ++a)
			cout << maze[i][a] << " ";
		cout << endl;
	}
	system("pause");
}