代码如下：
//头文件
#include<stdio.h>
#include<windows.h>//Sleep(500)函数调用此头文件
#include<conio.h>//getch()函数调用此头文件
#include<stdlib.h>//system("cls")函数调用此头文件 //函数状态码定义
/******************************/
#define TRUE 1
#define FALSE 0
#define OK 1
#define ERROR 0
#define INFEASIBLE -1
#define OVERFLOW -2
typedef int Status;
#define STACK_INIT_SIZE 100
#define STACKINCREMENT 10
#define Pass 0 //可通过
#define Wall 1 //墙
#define Start 6 //起点
#define End 7 //终点
#define Back 8 //返回
#define Exit 9 //出口：找到终点后标志出来
/******************************/ //自定义数据类型
/***************************************************/ //自定义枚举类型
enum direction{East=,South,West,North};//2,3,4,5分别代表东、南、西、北
/*+------------------------
使用枚举类型来表示方向
该枚举类型定义的变量只能取值 East,West,South,North
且East=2,South=3,West=4,North=5
本源码上面使用枚举类型,基本等效于下面
#define East 2
#define South 3
#define West 4
#define North 5
+------------------------*/ //自定义坐标结构体
typedef struct //迷宫x行，y列
{
int x;
int y;
}Position;//坐标结构体 //二维数组构造迷宫,1代表墙,0代表可通过。
int Map[][]={
{,,,,,,,,,},
{,,,,,,,,,},
{,,,,,,,,,},
{,,,,,,,,,},
{,,,,,,,,,},
{,,,,,,,,,},
{,,,,,,,,,},
{,,,,,,,,,},
{,,,,,,,,,},
{,,,,,,,,,}
}; //自定义结构体作为中间变量保存当前临时坐标信息
typedef struct
{
int number;//记录是第几步
Position seat;//通道块在迷宫中的"位置坐标"
enum direction direc;
//direction为枚举类型，用来表示从此通道走向下一通道的方向
//direc只能取值 East,West,South,North
//且East=2,South=3,West=4,North=5
}SElemType; //自定义栈结构便于将上面结构体的临时坐标信息放到栈内存储
typedef struct {
SElemType *base;
SElemType *top;
int stacksize;
}SqStack;//栈
/*********************************************/ //函数声明
/******************************************/ void Welcome();//欢迎界面函数
void printfMap();//打印迷宫函数
Status findPath(SqStack &S,Position start,Position end);//迷宫寻路径函数
Status InitStack(SqStack &S);//初始化栈
Status StackEmpty(SqStack S);//判断栈是否为空
Status Push(SqStack &S,SElemType e);//入栈
Status Pop(SqStack &S,SElemType &e);//出栈
enum direction Judge_direc(Position pos);//根据一个坐标探索周围坐标返回可通行的坐标
Position change_seat(Position &pos,enum direction direc);//根据方向移动到下一个可通行的坐标处
Status change_Map(int mapid); /****************主函数开始***********************/ //主函数
int main()
{
Position start,end;
int n;
SqStack S;
InitStack(S);//初始化栈
Welcome();//调用欢迎界面函数
start.x=;//
start.y=;//
printf("请选择地图:\n\n");
change_Map();
printf("\t\t默认地图0\n\n");
printfMap();
change_Map();
printf("\t\t备选地图1\n\n");
printfMap();
printf("选择默认地图请输入0,备选地图请输入1:\n");
printf("您的选择：");
scanf("%d",&n);
system("cls");
switch(n)
{
case :
{
change_Map();printf("初始迷宫如下所示:\n\n");
end.x=;end.y=;
printfMap();
printf("按任意键继续!");
getch();
system("cls");
break;
}
case :
{
change_Map();printf("初始迷宫如下所示:\n\n");
end.x=;
end.y=;
printfMap();
printf("按任意键继续!");
getch();
system("cls");
break;
}
}
findPath(S,start,end);
printf("\n\n按下任意键退出系统！\n");
getch(); return ;
}
/***************主函数结束***********************/
//打印迷宫
void printfMap()
{
int i,j;
for(i=;i<;i++)
{
printf("\t");
for(j=;j<;j++)
switch(Map[i][j]){
case Pass:printf("□");break;//可通过0
case Wall:printf("■");break;//墙1
case East:printf("→");break;//东2
case South:printf("↓"); break;//南3
case West:printf("←");break;//西4
case North:printf("↑");break;//北5
case Start:printf("⊙");break;//起点6
case End:printf("◎");break;//终点7
case Back:printf("Θ");break;//返回8
case Exit:printf("To");break;//出口9
}
printf("\n");
}
printf("\n");
} //走迷宫
Status findPath(SqStack &S,Position start,Position end){
Position curpos;//当前坐标
SElemType elem;//路径相关信息结构体
int step=;//记录步骤数
curpos=start;//开始坐标
while(){
if(curpos.x==start.x&&curpos.y==start.y)//此段代码只执行一次
{
elem.number=;
elem.direc=Judge_direc(curpos);//判断下一个位置是什么方向
elem.seat=curpos;
step++;
Push(S,elem);//第一个起点无条件入栈
} Map[curpos.x][curpos.y]=(int)elem.direc;//锁定当前位置
curpos=change_seat(curpos,elem.direc);//移动到下一个位置，根据方向改变坐标位置
if(Map[curpos.x][curpos.y]==End)//找到终点，退出循环
{
elem.seat=curpos;
elem.number=step;
Push(S,elem);
Map[curpos.x][curpos.y]=Exit;
system("cls");
printf("\n");
printfMap();
printf("\n\t恭喜您，迷宫路径已经找到！\n\n");
printf("路径坐标为：\n\n");
while(!StackEmpty(S))
{
Pop(S,elem);//出栈
curpos=elem.seat;
printf("(%d,%d)\t",curpos.x,curpos.y);
}
break;
}
if(Map[curpos.x][curpos.y]==Pass)//如果当前路可通
{
elem.number=step;
elem.seat=curpos;
elem.direc=Judge_direc(curpos);
Push(S,elem);//将当前坐标入栈
step++;
}
else//如果当前位置不通
{
Pop(S,elem);
curpos=elem.seat;
step=elem.number-;
Map[curpos.x][curpos.y]=Back;//表示四个都不通，标记走过了
do
{
Pop(S,elem);//出栈
curpos=elem.seat;
/************while循环开始*****************/
while(elem.direc<=)
{
elem.direc=(enum direction)(elem.direc+);
curpos=change_seat(curpos,elem.direc);//移动到下一个位置，根据方向改变坐标位置
if(Map[curpos.x][curpos.y]==Pass)
{
break;
}
};
/************while循环结束*****************/
if(Map[curpos.x][curpos.y]==Pass)
{
curpos=elem.seat;
elem.number=step;
elem.seat=curpos;
Push(S,elem);
step++;
break;
}
else
{
curpos=elem.seat;
Map[curpos.x][curpos.y]=Back;
}
printf("正在遍历查找...\n\n");
printfMap();
Sleep();
system("cls");
}while(!StackEmpty(S));//直到栈为空跳出循环
}
printf("正在遍历查找...\n\n");
printfMap();
Sleep();
system("cls");
}
return OK;
} //改变坐标
Position change_seat(Position &pos,enum direction direc){
switch(direc)
{
case East: pos.y=pos.y+;break;//
case South: pos.x=pos.x+;break;//
case West: pos.y=pos.y-;break;//
case North: pos.x=pos.x-;break;//
}
return pos;
}
//判断下一个位置方向
enum direction Judge_direc(Position pos)
{
enum direction judge;
if(Map[pos.x][pos.y+]==Pass||Map[pos.x][pos.y+]==End)
judge=East;
else
{
if(Map[pos.x+][pos.y]==Pass||Map[pos.x+][pos.y]==End)
judge=South;
else
{
if(Map[pos.x][pos.y-]==Pass||Map[pos.x][pos.y-]==End)
judge=West;
else
{
if(Map[pos.x-][pos.y]==Pass||Map[pos.x-][pos.y]==End)
judge=North;
}
}
}
return judge;
} Status change_Map(int mapid)
{
if(mapid==)//默认地图
{
Map[][]=Wall;
Map[][]=End;
}
if(mapid==)//其他地图
{
Map[][]=Wall;
Map[][]=End;
}
return OK;
} //初始化栈
Status InitStack(SqStack &S){
S.base=(SElemType *)malloc(STACK_INIT_SIZE*sizeof(SElemType));
if(!S.base)exit(OVERFLOW);
S.top=S.base;
S.stacksize=STACK_INIT_SIZE;
return OK;
} //判断栈是否为空
Status StackEmpty(SqStack S){
if(S.top==S.base)
return TRUE;
else
return FALSE;
}
//入栈
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.base+=STACKINCREMENT;
}
*S.top++=e;
return OK;
} //出栈
Status Pop(SqStack &S,SElemType &e){
if(S.top==S.base)return ERROR;
e=*--S.top;
return OK;
}
//去栈顶元素
Status GetTop(SqStack S,SElemType &e){ if(S.top==S.base)return ERROR; e=*(S.top-); //注意top指向待插入位置 return OK; } //欢迎界面函数
void Welcome(){
system("title 迷宫求解程序");//设置窗口标题
system("mode con cols=80 lines=40"); //窗口宽度高度
system("color a");//设置文本颜色，所在头文件
printf("★**************************************************************★\n");
printf("★ ★\n");
printf("★ 欢迎使用迷宫求解程序 ★\n");
printf("★ ★\n");
printf("★ 文件名称：数据结构期末实验 ★\n");
printf("★ ★\n");
printf("★ 项目名称：迷宫求解程序 ★\n");
printf("★ ★\n");
printf("★ 创建时间：2014-11-28 ★\n");
printf("★ ★\n");
printf("★ 最后修改时间：2014-12-2 ★\n");
printf("★ ★\n");
printf("★**************************************************************★\n");
printf("按任意键继续！\n");
getch();//暂停函数，所在头文件<conio.h>
system("cls");//清屏函数
}
