2022年实验报告——迷宫问题 .pdf
实习 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 struct int x;/ 行int y;/ 列PosType; #define MAXENGTH 25 /迷宫最大行列数位25 typedef int MazeTypeMAXENGTHMAXENGTH;/迷宫数列11111111111111111111110000000!012345名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 1 页，共 7 页 - - - - - - - - - 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 SqStack SElemType *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; else return 0; /6.插入元素int Push(SqStack &S,SElemType e) 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 2 页，共 7 页 - - - - - - - - - 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，不可通过路径为 -1 int Pass(PosType b) if(mb.xb.y=1) return 1; else return 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; 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 3 页，共 7 页 - - - - - - - - - c.y+=direcdi.y; return c; /11.道路不能通过时（即为死路），将其标记为-1 void MarkPrint(PosType b) mb.xb.y=-1; /12.求迷宫出口int MazePath(PosType start,PosType end) SqStack S; PosType curpos;/当前位置SElemType e; InitStack(S); curpos=start; do if(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); else if(!StackEmpty(S) Pop(S,e); curstep-; while(e.di=3&!StackEmpty(S) MarkPrint(e.seat); Pop(S,e); 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 4 页，共 7 页 - - - - - - - - - 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; 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 5 页，共 7 页 - - - - - - - - - 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,&begin.x,&begin.y); printf( 请输入终点坐标：n); scanf(%d %d,&end.x,&end.y); if(MazePath(begin,end) printf( 此迷宫的一条路径如下:n); Print(x,y); else printf( 此迷宫无法到达出口n); return 0; 实验结果 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 6 页，共 7 页 - - - - - - - - - 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 7 页，共 7 页 - - - - - - - - -
