文档介绍：实习2栈的应用本次实习的主要目的在于帮助学生深入了解栈的特性, 以便在实际问题背景下灵活运用他们;同时还将巩固对栈这种结构的构造方法的理解。实验课时 6课时程序1:迷宫问题[问题描述]以一个mxn的长方阵表示迷宫,‘0'和‘1'分别表示迷宫中的通路和障碍。设计一个程序,对任意设定的迷宫,求出一条从入口到出口的通路,或得出没有通路的结论。[基本要求]首先实现一个以顺序表或链表做存储结构的栈类型, 然后编写一个求解迷宫的非递归程序。求得的通路以三元组(i,j,d)的形式输出,其中:(i,j)指示迷宫中的一个坐标, d表示走到下一坐标的方向。如: 对下列数据的迷宫,输出的一条通路为:(1,1,1),(1,2,2),(2,2,2),…[测试数据]迷宫的测试数据如下:左上角(1,1)为入口,右下角(3,4)为出口。0 1 2 3 4 511111110011**********!1111111[实现提示]计算机解迷宫通常用的是 “穷举求解”方法,即从入口出发,顺着某一个方向进行探索,若能走通,则继续往前进;否则沿原路退回, 换一个方向再继续探索, 直至所有可能的通路都探索到为止,如果所有可能的通路都试探过,还是不能走到终点,那就说明该迷宫不存在从起点到终点的通道,可以二维数组存储迷宫数据。[程序实现]#include<>#include<>〃{intx;〃行inty;〃列}PosType;#defineMAXENGTH25//迷宫最大行列数位25typedefintMazeType[MAXENGTH][MAXENGTH];〃迷宫数列typedefstruct//定义栈{intord;//通道块在路径上的序号PosTypeseat;/通道块在迷宫中的位置intdi;//走向下一块的方向(0~3表示东、南、西、北)}SElemType;//;//迷宫数组intcurstep=1;//当前位置,初值为1#defineSTACK_INIT_SIZE10//存储空间初始分配量#defineSTACKINCREMENT2//存储空间分配增量//{SElemType*base;〃尾指针SElemType*top;//头指针intstacksize;//栈大小}SqStack;〃顺序表//(SqStack&S){=(SElemType*)malloc(STACK_INIT_SIZE*sizeof(SElemType));if(!())exit(0);=;=STACK_INIT_SIZE;return1;}//(用来判断迷宫是否不可达到出口)intStackEmpty(SqStackS){if(==)〃栈底与栈顶相等为空栈return1;elsereturn0;}//(SqStack&S,SElemTypee){if(->=)//栈顶-栈底>=栈长,说明空间已满{=(SElemType*)