实验报告——迷宫问题

《实验报告——迷宫问题》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

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

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

3、clude//1.迷宫位置坐标类型typedefstruct{intx;//行inty;//列}PosType;#defineMAXENGTH25//迷宫最大行列数位25typedefintMazeType[MAXENGTH][MAXENGTH];//迷宫数列typedefstruct//定义栈{intord;//通道块在路径上的序号PosTypeseat;//通道块在迷宫中的位置intdi;//走向下一块的方向（0~3表示东、南、西、北）}SElemType;//2.全局变量MazeTypem;//迷

4、宫数组intcurstep=1;//当前位置，初值为1#defineSTACK_INIT_SIZE10//存储空间初始分配量#defineSTACKINCREMENT2//存储空间分配增量//3.栈的顺序存储表示typedefstructSqStack{SElemType*base;//尾指针SElemType*top;//头指针intstacksize;//栈大小}SqStack;//顺序表//4.构造空栈intInitStack(SqStack&S){S.base=(SElemType*)malloc(STACK_IN

5、IT_SIZE*sizeof(SElemType));if(!(S.base))exit(0);S.top=S.base;S.stacksize=STACK_INIT_SIZE;return1;}//5.判断栈是否为空（用来判断迷宫是否不可达到出口）intStackEmpty(SqStackS){if(S.top==S.base)//栈底与栈顶相等为空栈return1;elsereturn0;}//6.插入元素intPush(SqStack&S,SElemTypee){if(S.top-S.base>=S.stacksiz

6、e)//栈顶-栈底>=栈长，说明空间已满{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;return1;}//7.栈不为空时，删除栈顶元素，用e返回（用于当栈顶元素各方向均不通时，将其从路径中删除）intPop(SqStack&S,SEl

7、emType&e){if(S.top==S.base)return0;e=*--S.top;//先将S.top的值赋给e，再将S.top向下移一位return1;}//8.判断迷宫m中b点是否可通过（是1，否0），其中墙为0，可通过路径为1，不可通过路径为-1intPass(PosTypeb){if(m[b.x][b.y]==1)return1;elsereturn0;}//9.是迷宫m中a的序号变为足迹（即该位置目前可通过）voidFootPrint(PosTypea){m[a.x][a.y]=curstep;}//10

8、.根据当前位置方向，返回下一位置PosTypeNextPos(PosTypec,intdi){PosTypedirec[4]={{0,1},{1,0},{0,-1},{-1,0}};c.x+=direc[di].x;c.y+=direc[di].y;returnc;}//11.道路不能通过时（即为死路）