资源描述：
《《数据结构》上机实验报告—利用栈实现迷宫求解》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。
1、福州大学数计学院《数据结构》上机实验报告专业和班级：信息计算科学与应用数学6班学号实验名称实验目的和要求姓名成绩栈、队列实验内容利用栈实现迷宫求解【实验目的】应用栈结构来解决应用问题，加深对栈结构特点的认识和应用。【基本要求】首先实现一个以链表作存储结构的栈类型，然后编写一个求解迷宫的非递归程序。求得的通路以三元组（i，j，d）的形式输出，其中：（i,j）指示迷宫中的一个坐标，d表示走到下一坐标的方向。如：对于下列数据的迷宫，输出的一条通路为；（1，1，1）,（1,2,2），（2,2,2），（3,2,3）,（3,1,2），....【问题描述】以一个mXn的长方阵表示迷宫，0和1
2、分别表示迷宫中的通路和障碍。设计一个程序，对任意设定的迷宫，求出一条从入口到出口的通路，或得出没有通路的结论【程序设计】问题描述和主要步骤^include^include〈stdlib.h>^include^defineTRUE1^defineFALSE0^defineOK1^defineERROR0^defineOVERFLOW-2^defineINIT_SIZE100//存储空间初始分配量^defineINCREMENT10//存储空间分配增量^defineMAXLEN10//迷宫包括外墙最大行列数0typedefintStatus;t
3、ypedefstruct（//迷宫屮r行c列的位置intr;intc;iPostType;typedefstruct{intord;//当前位置在路径上的序号PostTypeseat;//当前坐标intdi;//往下一坐标的方向}SElemType;//栈元素类型typedefstruct{SRlemType*base;//栈基址，构造前销毁后为空SRlemType*top;//桟顶intstackSize;//栈容量>Stack;//栈类型StatusTnitStack(Stack&S){//构造:空栈sS.base=(SElemType*)malloc(INIT_SIZE*
4、sizeof(SElemType));if(!S.base)exit(OVERFLOW);//存储分配失败S.top=S.base;S.stackSize=INIT_SIZE;returnOK;}//InitStackStatusStackEmpty(StackS){//若s为空返回TRUE,否则返回FALSEif(S.top~S.base)returnTRUE;returnFALSE;}//StackEmptyStatusPush(Stack&S,SElemTypee){//插入元素e为新的栈顶元素if(S.top-S.base〉=S.stackSize){//技满，加空间S
5、.base=(SElemType氺)realloc(S.base,(S.stackSize+INCRRMENT)*sizeof(SElemType));if(!S.base)exit(OVERFLOW);//存储分配失败S.top=S.base+S.stackSize;S.stacksize+=INCRRMENT;}氺S.top++=e;returnOK;}//pushStatusPop(Stack&S,SElemType&e){//若栈不空删除栈//顶元素用e返回并返回OK，否则返回ERRORif(S.top~S.base)returnERROR;e#—S.top;retur
6、nOK;}//PopStatusDestroyStack(Stack&S){//销毁栈S，free(S.base);S.top=S.base;returnOK;}//DestroyStacktypedefstruct{intr;intc;intadr[MAXLEN][MAXLEN];//可取0,1,2,3}MazeType;//迷宫类型StatusInitMaze(MazeType&maze){//初始化迷宫若成功返冋TRUE,否则返回FALSEinti,j;maze.r=9,maze.c=8;//迷宫行和列数for(i=0;i〈=maze.c+1;i++){//迷宫行外墙ma
7、ze,adr[0][i]=l;maze,adr[maze,r+1][i]=l;}//forfor(i=0;i<=mazo.r+1;i++){//迷宫列外墙maze,adr[i][0]=l;maze,adr[i][maze.c+l]=l;}for(i=l;i<=maze.r;i++)for(j=l;j<=maze.c;j++)maze.adr[i][j]=0;//初始化迷宫maze,adr[1][7]=maze.adr[1][3]=maze.adr[2][3]=1;maze,adr[2][7]
