一、结果如图所示

二、代码 

#include<stdio.h>
#include<stdlib.h>
#define line 10
typedef struct
{
	int a[line][line];
}maze;
typedef struct
{
	int abs;//横向坐标
	int ord;//纵向坐标
	int direct;//方向
}coordinate;
typedef struct
{
	coordinate* base;
	coordinate* top;
	int stacksize;
}SqStack;
void initstack(SqStack& S)
{
	S.base = new coordinate[line * line];
	if (!S.base)
		exit(1);
	S.top = S.base;
	S.stacksize = line * line;
}
void push(SqStack& S, coordinate e)
{
	if (S.top - S.base == S.stacksize)
		printf("Error!");
	else
		*S.top++ = e;
}
void pop(SqStack& S, coordinate& e)
{
	if (S.top == S.base)
		printf("Error!!");
	else {
		e=*--S.top;
	}
}
coordinate Gettop(SqStack& S)
{
	if (S.top != S.base)
		return *(S.top - 1);
}
int StackEmpty(SqStack S)
{
	if (S.top == S.base)
		return 1;
	else
		return 0;
}

void MazeBuild(maze& M,int count)
{
	int i, j;
	int c[line][line] = {
		{1,1,1,1,1,1,1,1,1,1},
		{1,0,1,0,0,1,0,0,0,1},
		{1,0,0,1,0,1,0,1,1,1},
		{1,0,0,0,0,1,0,1,0,1},
		{1,0,0,1,1,1,0,1,1,1},
		{1,0,0,0,0,0,0,0,0,1},
		{1,1,1,1,0,0,1,1,0,1},
		{1,0,0,1,1,0,1,0,0,1},
		{1,0,0,0,0,0,1,0,0,1},
		{1,1,1,1,1,1,1,1,1,1}
	};
	printf("\n---------------------第%d次初始化迷宫--------------------\n", count);
	printf("原始迷宫（1为墙，0为通道）：\n");
	for (i = 0; i < line; i++) {
		for (j = 0; j < line; j++) {
			M.a[i][j] = c[i][j];
			printf(" %d", c[i][j]);
		}
		printf("\n");
	}
}
void InitBegin(coordinate& begin)
{
	int h, z;//横向和纵向坐标
	printf("输入起始坐标(先纵后横）：");
	scanf_s("%d%d", &z, &h);
	begin.ord = z;
	begin.abs = h;
}
void InitEnd(coordinate& end)
{
	int h, z;//横向和纵向坐标
	printf("输入起始坐标(先纵后横）：");
	scanf_s("%d%d", &z, &h);
	end.ord = z;
	end.abs = h;
}

void NextStep(coordinate& human)
{
	switch (human.direct)
	{
	case 1:
		human.abs++;
		break;
	case 2:
		human.ord++;
		break;
	case 3:
		human.abs--;
		break;
	case 4:
		human.ord--;
		break;
	}
}
int judge(maze& M, coordinate& human)
{
	if (M.a[human.ord][human.abs] == 0)//可通过
	{
		M.a[human.ord][human.abs] = 2;
		return 1;
	}
	else
		return 0;
}
void Printmaze(maze M)
{
	int i, j;
	for (i = 0; i < line; i++) {
		for (j = 0; j < line; j++) {
			switch (M.a[i][j])
			{
			case 0:
				printf("  ");
				break;
			case 1:
				printf("■");
				break;
			case 2:
				printf(" *");
				break;
			case 3:
				printf(" @");
				break;
			default:
				break;
			}
		}
		printf("\n");
	}
}
int mazepath(SqStack& S, maze& M, coordinate& human)
{
	InitBegin(human);
	coordinate end;
	InitEnd(end);
	coordinate e;
	printf("\n");
	if (judge(M, human))
		printf(" *");
	else
		return 0;
	do 
	{
		for (human.direct = 1; human.direct <= 4; human.direct++) 
		{
				push(S, human);
				e = human;
				NextStep(human);
				if (judge(M, human)) 
				{
					human.direct = 0;
					if (end.ord == human.ord && end.abs == human.abs) 
						return 1;
				}
				else 
				{
					pop(S, human);
					while (human.direct == 4 && !StackEmpty(S))
					{
						M.a[human.ord][human.abs] = 3;
						pop(S, human);
					}
				}
		}
	} while (!StackEmpty(S));
	return 0;
}
void printpath(SqStack& S,maze& M)
{
	int num, i;
	int flag = 1, count = 0;
	SqStack L;
	coordinate human, m;
	initstack(S);
	initstack(L);
	while (flag == 1) {
		count++;
		MazeBuild(M, count);
		num = 0;
		if (mazepath(S, M, human))
		{
			printf("---------------------------------------------------\n");
			printf("迷宫求解路径（■表示墙，@表示死胡同，*表示路径）：\n");
			Printmaze(M);
			while (!StackEmpty(S))
			{
				pop(S, m);
				push(L, m);
				num++;
			}
			printf("\n路径坐标（纵，横，方向）为：\n");
			for (i = 1; i <= num; i++)
			{
				pop(L, m);
				printf("(%d,%d,%d)->", m.ord, m.abs, m.direct);
			}
			printf("(%d,%d)\n\n", human.ord, human.abs);
			printf("---------------------------------------------------\n");
		}
		else
			printf("\n\n---------------------没有通路----------------------\n\n");
		printf("是否重新进行？是按1，否按2.\n请选择：");
		scanf_s("%d", &flag);
		if (flag != 1)
			printf("\n---------------------程序已结束--------------------\n");
	}
}
int main()
{
	SqStack S, L;
	maze M;
	printpath(S, M);
}

问题描述

以一个m╳n的长方阵表示迷宫，0和1分别表示迷宫中的通路和障碍。设计一个程序，对任意设定的迷宫，求出一条从入口到出口的通路，或得出没有通路的结论。

基本要求

（1）实现一个以链表作为存储结构的栈类型，然后编写一个求解迷宫的非递归程序；
（2）程序中以二维数组表达迷宫数据，迷宫数据由文件读入，文件的格式如下：第1行数据为迷宫的行数m和列数n；第2行至第m+1行（每行n个数）为迷宫值，同一行中的两个数字以空格隔开。如图1所示，为一个9╳8的迷宫的测试数据：

图1 迷宫数据文件格式
（2）迷宫的入口位置和出口位置有用户随时设定，当用户输入非法信息时，提示错误；
（3）若设定的迷宫存在通路，则以长方阵形式将迷宫及其通路输出到屏幕上，如图2所示，以字符“#”表示障碍，字符“*”表示路径上的位置，字符“@”表示“死胡同”，即曾途经然而不能到达出口的那些位置，其余用空格符印出。若迷宫不存在通路，则报告相应的信息。

详细设计

#include<stdio.h>
#include<stdlib.h>
#define length 8
#define width 10
#define start_hang 1 //从0行开始计算row
#define start_lie 1//从0列开始column
#define end_hang 8
#define end_lie 6
#define OVERFLOW -1
#define OK 1
#define ERROR -1
#define TRUE 1
#define FALSE -1
#define STACK_INIT_SIZE	100
char maze[width][length];
#define WALL 1   //代表当前格子是墙
#define PATH 0  //代表是通路且未走过
#define RIGHT -1 //代表是通路且从其向右走
#define DOWN -2  //代表是通路且从其向下走
#define LEFT -3  //代表是通路且从其向左走
#define UP -4    //代表是通路且从其向上走
#define BACK -5  //代表是通路且从其后退一步
#define DESTINATION -6//代表是通路且是目标位置
#define EXIT -7
#define STACKINCREMENT 10
typedef int MazeType[10][8];最外初始化成墙
typedef int Status;
typedef int ElemType;//
typedef struct
{
	int r;
	int c;
}postype;
typedef struct
{
	int ord;//通道块在路径上的序号
	postype seat;//通道块在迷宫中的坐标
	int di;//从此通道块走向下一通道块的方向 
}selemtype;
typedef struct
{
	selemtype* base;
	selemtype* top;
	int stacksize;
}sqstack;

void initstack(sqstack* s)
{
	s->base = (selemtype*)malloc(STACK_INIT_SIZE * sizeof(selemtype));
	if (!s->base)
	{
		printf("创建空间失败");
		exit(0);
	}
	s->top = s->base;
	s->stacksize = STACK_INIT_SIZE;
}
Status StackEmpty(sqstack S)
{
	if (S.top == S.base)
		return TRUE;
	else return FALSE;
}
ElemType GetTop(sqstack S, selemtype& e)
{
	if (S.base == S.top)
		return ERROR;
	e = *(S.top - 1);
	return OK;
}
Status Push(sqstack& S, selemtype e)
{
	if (S.top - S.base >= S.stacksize)
	{
		S.base = (selemtype*)realloc(S.base, (S.stacksize + STACKINCREMENT) * sizeof(selemtype));//增加空间
		if (!S.base)exit(OVERFLOW);//存储分配失败
		S.top = S.base + S.stacksize;
		S.stacksize += STACKINCREMENT;
	}
	*S.top++ = e;
	return OK;
}
Status Pop(sqstack& S, selemtype& e)
{
	if (S.top == S.base)
		return ERROR;
	e = *--S.top;
	return OK;
}
void FootPrint(MazeType& maze, postype curpos, Status s)
{
	//留下足迹
	maze[curpos.r][curpos.c] = s;
}
void readmaze(MazeType& maze)//从文件中读入迷宫 。 
{
	char ch, ch1;
	int i, j;
	FILE* fp;
	char tile[10];
	fp = fopen("maze.txt", "r");
	if (fp == NULL)
	{
		printf("打开迷宫文件失败");
		exit(0);
	}
	else

		fgets(tile, 10, fp);

	for (i = 0; i < 10; i++)
	{

		for (j = 0; j < 8; j++)
		{
			ch = fgetc(fp);
			ch1 = fgetc(fp);
			maze[i][j] = ch - 48;

		}

	}
	for (i = 0; i < width; i++)
	{
		for (j = 0; j < length; j++)
		{
			printf("%2d", maze[i][j]);
		}
		printf("\n");//输出换行 
	}
}
postype Nextpos(postype curpos, Status s)
{
	//返回下一个位置
	switch (s)
	{
	case RIGHT:
		curpos.c++;
		break;
	case DOWN:
		curpos.r++;
		break;
	case LEFT:
		curpos.c--;
		break;
	case UP:
		curpos.r--;
		break;
	}
	return curpos;
}

Status PassMaze(MazeType& maze, postype start, postype end, sqstack& S)
{
	//求迷宫中start到end的通路，有通路返回TRUE，没通路返回FALSE，栈S返回路径
	postype curpos = start;//当前位置为开始位置
	int curstep = 1;//探索第一步
	selemtype e;
	if (maze[curpos.r][curpos.c] != PATH)//入口不通则停
		return FALSE;
	while (1) //从当前位置处理，不断找cospos重复，直到栈空或者找到出口
	{
		if (maze[curpos.r][curpos.c] == PATH) //当前位置可通
		{
			e.di = RIGHT;//右邻马上被访问
			e.seat = curpos;
			e.ord = curstep;
			Push(S, e);//加入路径
			if (curpos.r == end.r && curpos.c == end.c) //到达终点
			{
				FootPrint(maze, curpos, DESTINATION);//留下足迹
				return OK;
			}
			else
			{
				FootPrint(maze, curpos, RIGHT);
				curpos = Nextpos(curpos, RIGHT);//下一位置是当前位置的东临
			}
		}
		else  //当前位置不通
		{
			if (!StackEmpty(S))
				return FALSE;
			GetTop(S, e);//取最近到过的位置查看信息
			while (e.di == -4) //四周都访问过
			{
				Pop(S, e);
				curstep--;
				FootPrint(maze, e.seat, BACK);//后退一步 留下不能通过的标记
				GetTop(S, e);
			}
			if (e.di > -4) //栈顶位置有其他方向可以选择
			{
				Pop(S, e);
				e.di--; //换一个方向
				Push(S, e);//修改栈顶位置信息
				FootPrint(maze, e.seat, e.di);
				curpos = Nextpos(e.seat, e.di);//设定当前位置是新方向上的相邻块
			}
		}
	}
	return OK;
}

void PrintMaze(MazeType maze)
{
	//输出迷宫
	int x, y;
	for (x = 0; x < 10; x++)
	{
		for (y = 0; y < 8; y++)
		{
			switch (maze[x][y])
			{
			case 1:
				printf(" # ");
				break;
			case PATH:
				printf("   ");
				break;
			case RIGHT:
				printf(" * ");
				break;
			case DOWN:
				printf(" * ");
				break;
			case LEFT:
				printf(" * ");
				break;
			case UP:
				printf(" * ");
				break;
			case BACK:
				printf(" @ ");
				break;
			case DESTINATION:
				printf("◎");
				break;
			default:
				printf("error");
			}
		}
		printf("\n");
	}
}

int main()
{
	int i, j;
	sqstack S;
	initstack(&S);
	MazeType maze;
	printf("迷宫如下：\n");
	readmaze(maze);
	postype start, end;
	start.r = start_hang;
	start.c = start_lie;
	end.r = end_hang;
	end.c = end_lie;
	printf("求解通路如下（*代表所求道路、@表示经过的死路、#表示墙）：\n");
	PassMaze(maze, start, end, S);
	PrintMaze(maze);

	system("pause");
}

测试与结果
（1）测试文件

（2）测试结果

栈的应用–迷宫求解

思路: 从一个起点(1,1)坐标开始, 依次判断它的右,下,左,上, 方位能不能走 如果能就直接走, 每走一步将这个位置的坐标入栈,
并且标记为2, 若都不能走, 说明走到死路了, 要开始回溯,走过没有走过标记为3 回溯时就是把入栈的坐标出栈, 即可原路返回,
每返回一步就重新再判断它的 右,下,左,上, 能不能走,直到找到终点(8,8)坐标,否则没有通路

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <assert.h>
#include <malloc.h>			//动态存储分配函数头文件，用于栈的存储空间的分配


typedef int DirectiveType;		//下一个通道的方向
#define RANGE 100				//迷宫大小
#define STACK_INIT_SIZE 100		//定义栈的初始大小
#define STACKINCREMENT 10		//定义栈的存储增量，在栈长度越界时
#define OK 1
#define ERROR 0

#define ROW 10					//迷宫的行数
#define COL 10					//迷宫的列数
typedef int Status;

typedef struct{
	int m,n;
	int arr[RANGE][RANGE];		//迷宫数组
}MazeType;						//迷宫的类型

typedef struct{
	int row;					//迷宫的行
	int col;					//迷宫的列
}PosType;						//坐标（row,col）

typedef struct{
	int step;					//当前位置路径的序号
	PosType seat;				//当前位置坐标位置
	DirectiveType di;			//往下一个坐标位置的方向
}SElemType;

typedef struct{
	SElemType *base;			//栈底
	SElemType *top;				//栈顶
	int stacksize;				//栈的大小
}SqStack;						//定义栈



//初始化栈
Status InitStack(SqStack &s){
	s.base = (SElemType *)malloc (STACKINCREMENT * sizeof (SElemType ));
	if(!s.base ){
		exit(-2);
	}
	s.top = s.base ;
	s.stacksize = STACK_INIT_SIZE;
	return OK;
}


//当栈是不为空时，返回栈顶元素
Status GetTop(SqStack s,SElemType &e){
	if(s.top = s.base ){
		return ERROR;
	}
	e = *(s.top - 1);
	return OK;
}

//在栈是中插入元素e,入栈
Status PushStack(SqStack &s,SElemType e){
	if(s.top - s.base >= s.stacksize){					//若栈满，追加存储空间
		s.base = (SElemType *)realloc(s.base,(s.stacksize + STACKINCREMENT )*sizeof (SElemType ));

		if(!s.base){
			exit(-2);
		}
		s.top = s.base + s.stacksize;
		s.stacksize += STACKINCREMENT;
	}
	*s.top++ = e;
	return OK;
}

//在栈s中删除栈顶，出栈
Status PopStack(SqStack &s,SElemType &e){
	if(s.top == s.base){
		return ERROR;
	}
	e = *--s.top;
	return OK;
}

//判断栈是否为空
Status StackEmpty(SqStack s){
	if(s.base == s.top )
		return OK;
	return ERROR;
}

//销毁栈
Status DestorySatck(SqStack &s){
	free(&s);
	return OK;
}

//初始化迷宫
Status InitMaze(MazeType &maze,int a[ROW][COL],int row,int col){
	int i,j;
	//设置迷宫maze的初值,包括加上边缘一圈的值
	for(i = 1;i<row;i++){
		for(j=1;j<col;j++){
			maze.arr[i][j] = a[i][j];
		}
	}
	//加上围墙
	for(i= 0;i<row;i++){
		maze.arr[0][i] = maze.arr[row-1][i] = 1;		//第0行和第9行为1
	}
	for(j = 0;j<col;j++){
		maze.arr[j][0] = maze.arr[j][col-1] = 1;		//第0列和第9列为1
	}
	return OK;

}

//判断当前节点是否通过，（迷宫数组，当前位置坐标）
Status Pass(MazeType maze,PosType curpos){
	
	//当节点为0时，表示有路
	if(maze.arr[curpos .row][curpos .col] == 0){
		return OK;
	}else {
		return ERROR;
	}

}

//留下标记
Status FootPrint(MazeType &maze,PosType curpos){
	
	maze.arr[curpos.row][curpos .col] = 2;			//走过且走得通
	return OK;

}

//留下不能通过的标记
Status MarkPrint(MazeType &maze,PosType curpos){
	
	maze.arr[curpos .row][curpos .col] = 3;
	return OK;
}


//创建元素e	
SElemType CreateSElem(int step,PosType pos,int di){
	
	SElemType e;
	e.step = step;
	e.seat = pos;
	e.di = di;

	return e;

}

//返回当前节点的下一个节点 （当前位置坐标，下一个位置方向）
PosType NextPos(PosType curpos ,DirectiveType di){

	PosType pos = curpos ;
	switch(di){
		case 1:pos.col++;break;			//右
		case 2:pos.row++;break;			//下
		case 3:pos.col--;break;			//左
		case 4:pos.row--;break;			//上
	}	

	return pos;
}

//判断是不是出口
Status PosEqual(PosType pos1,PosType pos2){
	
	if(pos1.row == pos2.row && pos1.col == pos2.col){
		return OK;
	}else
		return ERROR;

}
	
//打印路径
void PrintMaze(MazeType maze,int row,int col){
	int i,j;
	printf(" ");
    for (i = 0; i<col; i++)                    //打印列数名
       printf("%d ", i);
    printf("\n");
	for (i = 0; i<row; i++){
		 printf("%d",i);                      //打印行数名
       for (j = 0; j<col; j++){
		   //printf("%d ",maze.arr[i][j]);
           switch (maze.arr[i][j]){
				case 0:printf("  "); break;                //没走过，但是通路            
				case 1:printf("■");break;                //墙，障碍物
				case 2:printf("# ");break;              //走过且走得通             
				case 3:printf("* ");break;              //走过但走不通，死胡同               
				default:break;
           }   
       }
       printf("\n");
    }
}

//求解迷宫maze中,从入口start到出口end的一条路径
Status MazePath(MazeType &maze,PosType start,PosType end){
	
	SqStack s;					//定义栈
	SElemType e;
	InitStack (s);				//初始化栈
	PosType curpos = start;
	int curstep = 1;				//搜索第一步
	do{
		 //如果当前位置可以通过,即是未曾走到的路径
		if(Pass(maze,curpos)){
			FootPrint (maze,curpos);		//留下标记
			e = CreateSElem (curstep,curpos,1);		//创建元素
			PushStack(s,e);						//加入路径
			if(PosEqual(curpos,end)){       //判断是不是出口
				return OK;
			}
			curpos = NextPos(curpos,1);			//获取下一个节点,当前位置的右边
			curstep++;
			
		}else{									//当前位置不能通过
			if(!StackEmpty(s)){
				PopStack(s,e);
				while(e.di == 4 && !StackEmpty(s)){   //找寻了四个方向
					MarkPrint(maze,e.seat);
					PopStack(s,e);

				}
				if(e.di<4){
					e.di++;				//换下一个方向
					PushStack(s,e);
					curpos = NextPos (e.seat,e.di);     //设定当前位置是该方向上的相邻块
				}
			}
		}
	}while(!StackEmpty (s));
	
	return OK;
}


Status main(){
	
	int i,j;
	PosType start ,end;			//开始，终点坐标
	MazeType maze;
	int a[ROW][COL] = {
		{1,1,1,1,1,1,1,1,1,1},
		{1,0,0,0,1,0,0,1,0,1},
		{1,0,0,1,0,1,0,1,1,1},
		{1,1,0,0,0,1,0,0,0,1},
		{1,0,1,1,0,0,1,1,0,1},
		{1,1,0,0,1,0,0,0,1,1},
		{1,0,1,0,0,0,1,1,0,1},
		{1,0,1,0,1,1,1,1,0,1},
		{1,1,0,0,0,0,0,0,0,1},
		{1,1,1,1,1,1,1,1,1,1}
	};
	printf("\n原始迷宫如下：\n");
	printf("(其中‘1’表示墙，‘0’表示通道)\n");
    for(i = 0;i < 10;i++){
		for(j = 0;j < 10;j++){
			printf("%d ",a[i][j]);
		}
		printf("\n");
	}

	InitMaze(maze,a,ROW,COL);			//初始化迷宫
	start.row = 1;						//给定迷宫起点坐标(1,1)
	start.col = 1;
	end.row = 8;
	end.col = 8;						//给定迷宫终点坐标（8,8）
	

	if (MazePath(maze, start,end)){             //如果找到一条路径
       printf("\n~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~\n");
       printf("\n求解迷宫路径如下：\n");
	   printf("(其中'#'表示求解路径，'*'表示死胡同)\n");

       PrintMaze(maze, ROW,COL);               //输出迷宫路径

    }else 
		printf("\n从入口（1,1）到出口（8,8）没有通路!\n");

	return OK;
}