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