(完整word版)实验报告——迷宫问题

1、实习 2栈的应用本次实习的主要目的在于帮助学生深入了解栈的特性，以便在实际问题背景下灵活运用他们；同时还将巩固对栈这种结构的构造方法的理解。实验课时6 课时程序 1：迷宫问题问题描述以一个 m×n 的长方阵表示迷宫， 0和 1分别表示迷宫中的通路和障碍。设计一个程序，对任意设定的迷宫，求出一条从入口到出口的通路，或得出没有通路的结论。基本要求首先实现一个以顺序表或链表做存储结构的栈类型，然后编写一个求解迷宫的非递归程序。求得的通路以三元组（i,j,d）的形式输出，其中：（ i,j）指示迷宫中的一个坐标，d表示走到下一坐标的方向。如：对下列数据的迷宫，输出的一条通路为： （ 1，1，1

2、），（1，2，2），（ 2， 2， 2），测试数据迷宫的测试数据如下：左上角（1， 1）为入口，右下角（3， 4）为出口。0123451111111001111001111000!1111111 实现提示 计算机解迷宫通常用的是 “穷举求解” 方法，即从入口出发， 顺着某一个方向进行探索，若能走通， 则继续往前进；否则沿原路退回， 换一个方向再继续探索， 直至所有可能的通路都探索到为止 ,如果所有可能的通路都试探过，还是不能走到终点，那就说明该迷宫不存在从起点到终点的通道，可以二维数组存储迷宫数据。程序实现 #include <stdio.h>#include <stdlib

3、.h>/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

4、_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=

5、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(SElemT

6、ype);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，可

7、通过路径为 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 Ma

8、rkPrint(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.di=0;Push(S,e);curstep+;if(curpos.x=end.x&&curpos.y=end.y)return 1;curpos=NextPos(curpos,e.di);e

9、lseif(!StackEmpty(S)Pop(S,e);curstep-;while(e.di=3&&!StackEmpty(S)MarkPrint(e.seat);Pop(S,e);curstep-;if(e.di<3)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;i<x;i+)for(j=0;j<y;j+)printf("%3d&

10、quot;,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;i<x;i+)/定义外墙m0i=0;mx-1i=0;for(j=0;j<y-1;j+)mj0=0;mjy-1=0;for(i=1;i<x-1;i+)for(j=1;j<y-1;j+)mij=1;/墙内初始值均为1/输入迷

11、宫中墙的个数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(" 请输入终点坐标