实验报告——迷宫问题.doc

实习2 栈的应用 本次实习的主要目的在于帮助学生深入了解栈的特性，以便在实际问题背景下灵活运用他们；同时还将巩固对栈这种结构的构造方法的理解。实验课时 6课时程序1：迷宫问题问题描述 以一个mn的长方阵表示迷宫，0和1分别表示迷宫中的通路和障碍。设计一个程序，对任意设定的迷宫，求出一条从入口到出口的通路，或得出没有通路的结论。基本要求 首先实现一个以顺序表或链表做存储结构的栈类型，然后编写一个求解迷宫的非递归程序。求得的通路以三元组（i,j,d）的形式输出，其中：（i,j）指示迷宫中的一个坐标，d表示走到下一坐标的方向。如：对下列数据的迷宫，输出的一条通路为：（1，1，1），（1，2，2），（2，2，2），测试数据迷宫的测试数据如下：左上角（1，1）为入口，右下角（3，4）为出口。 实现提示 计算机解迷宫通常用的是“穷举求解”方法，即从入口出发，顺着某一个方向进行探索，若能走通，则继续往前进；否则沿原路退回，换一个方向再继续探索，直至所有可能的通路都探索到为止,如果所有可能的通路都试探过，还是不能走到终点，那就说明该迷宫不存在从起点到终点的通道，可以二维数组存储迷宫数据。程序实现#include #include /1.迷宫位置坐标类型typedef structint x;/行int y;/列PosType;#define MAXENGTH 25 /迷宫最大行列数位25typedef int MazeTypeMAXENGTHMAXENGTH;/迷宫数列typedef struct/定义栈int ord;/通道块在路径上的序号PosType seat;/通道块在迷宫中的位置int di;/走向下一块的方向（03表示东、南、西、北）SElemType;/2.全局变量MazeType m;/迷宫数组int curstep=1;/当前位置，初值为1#define STACK_INIT_SIZE 10/存储空间初始分配量#define STACKINCREMENT 2/存储空间分配增量/3.栈的顺序存储表示typedef struct SqStackSElemType *base;/尾指针SElemType *top;/头指针int stacksize;/栈大小SqStack;/顺序表/4.构造空栈int InitStack(SqStack &S)S.base=(SElemType *)malloc(STACK_INIT_SIZE*sizeof(SElemType);if(!(S.base)exit(0);S.top=S.base;S.stacksize=STACK_INIT_SIZE;return 1;/5.判断栈是否为空（用来判断迷宫是否不可达到出口）int StackEmpty(SqStack S)if(S.top=S.base)/栈底与栈顶相等为空栈return 1;elsereturn 0;/6.插入元素int 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(0);S.top=S.base+S.stacksize;S.stacksize+=STACKINCREMENT;*(S.top)+=e;return 1;/7.栈不为空时，删除栈顶元素，用e返回（用于当栈顶元素各方向均不通时，将其从路径中删除）int Pop(SqStack &S,SElemType &e)if(S.top=S.base)return 0;e=*-S.top;/先将S.top的值赋给e，再将S.top向下移一位return 1;/8.判断迷宫m中b点是否可通过（是1，否0），其中墙为0，可通过路径为1，不可通过路径为-1int Pass(PosType b)if(mb.xb.y=1)return 1;elsereturn 0;/9.是迷宫m中a的序号变为足迹（即该位置目前可通过）void FootPrint(PosType a)ma.xa.y=curstep;/10.根据当前位置方向，返回下一位置PosType NextPos(PosType c,int di)PosType direc4=0,1,1,0,0,-1,-1,0;c.x+=direcdi.x;c.y+=direcdi.y;return c;/11.道路不能通过时（即为死路），将其标记为-1void MarkPrint(PosType b)mb.xb.y=-1;/12.求迷宫出口int MazePath(PosType start,PosType end)SqStack S;PosType curpos;/当前位置SElemType e;InitStack(S);curpos=start;doif(Pass(curpos)FootPrint(curpos);e.ord=curstep;e.seat.x=curpos.x;e.seat.y=curpos.y;e.di=0;Push(S,e);curstep+;if(curpos.x=end.x&curpos.y=end.y)return 1;curpos=NextPos(curpos,e.di);elseif(!StackEmpty(S)Pop(S,e);curstep-;while(e.di=3&!StackEmpty(S)MarkPrint(e.seat);Pop(S,e);curstep-;if(e.di3)e.di+;Push(S,e);curstep+;curpos=NextPos(e.seat,e.di);while(!StackEmpty(S);return 0;/13.输出迷宫结构void Print(int x,int y)int i,j;for(i=0;ix;i+)for(j=0;jy;j+)printf(%3d,mij);printf(n);/14.主函数int main()PosType begin,end;int i,j,x,y,x1,y1;printf(请输入迷宫行列数（包括外墙）:（空格隔开）n);scanf(%d %d,&x,&y);for(i=0;ix;i+)/定义外墙m0i=0;mx-1i=0;for(j=0;jy-1;j+)mj0=0;mjy-1=0;for(i=1;ix-1;i+)for(j=1;jy-1;j+)mij=1;/墙内初始值均为1/输入迷宫中墙的个数printf(输入墙的个数：);scanf(%d,&j);/安排墙的位置printf(请输入墙的位置（坐标），用空格隔开:n);for(i=1;i=j;i+)scanf(%d %d,&x1,&y1);mx1y1=0;printf(迷宫结构如下n);Print(x,y);printf(请输入起点坐标：n);scanf(%d %d