资源描述：
《数据结构迷宫问题实验报告》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。
1、数据结构迷宫问题实验报告篇一：数据结构•迷宫•实验报告与代码囹一.需求分析0本程序是利用非递归的方法求出一条走出迷宫的路径，并将路径输出。首先由用户输入一组二维数组来组成迷宫，确认后程序自动运行，当迷宫有完整路径可以通过时，以0和1所组成的迷宫形式输出，标记所走过的路径结束程序；当迷宫无路径时，提示输入错误结束程序。程序执行的命令：1创建迷宫;2求解迷宫;3输出迷宫求解;0二.算法设计0本程序中采用的数据模型，用到的抽象数据类型的定义，程序的主要算法流程及各模块之间的层次调用关系囹程序基本结构:E1设定
2、栈的抽象数据类型定义:0ADTStack{12数据对象：D={ai
3、ai丘CharSet,i=l/2/3/?-/n/n>=O;}(3数据关系:R={<ai?l,ai>
4、ai?l,ai^D/i=2/?/n}回设置迷宫的抽象类型囹ADTmaze{囹数据对象：D={ai
5、aiG'TJ=l/2/?/n/n>=0}数据关系：R={rzc}0r={<ai-l,ai>
6、aM,ai丘D*i=12?n}0c=<ai-l,ai>
7、ai-l,aiED,i=lZ?m}0结构体定义
8、：囹typedefstruct〃迷宫中x行y列的位置0{intx;0inty;0}PosType;0typedefstruct//栈类型intord;//通道块在路径上的“序号0PosTypeseat;//通道块在迷宫中的“坐标位置”0intdi;〃从此通道块走向下一通道块的“方向”0}MazeType;13typedefstruct0{MazeType*base;囹MazeType*top;0intstacksize;0}MazeStack;0基本函数:0StatusInitStackfMazeSta
9、ck&S)//新建一个栈0StatusPush(MazeStack&S,MazeType&e)〃入栈0StatusPop(MazeStack&S#MazeType&e)〃出栈0StatusStackEmpty(MazeStack&S)//判断是否为空0StatusMazePath(PosTypestart,PosTypeend)//迷宫路径求解0voidFootPrint(PosTypepos)[?1PosTypeNextPos(PosTypecurPos
10、,int&i)SvoidMakePrint(PosTypepos)刖三.程序设计0根据算法设计中给出的有关数据和算法，选定物理结构，详细设计需求分析中所要求的程序。包括：人机界面设计、主要功能的函数设计、函数之间调用关系描述等。囹1界面设计01）迷宫界面1212）迷宫路径显示忸2主要功能囹1)入栈操作0StatusPush(MazeStack&S,MazeType&e)〃入栈操作0if(S・top・S.base>=S.stacksize)13S.base=(MazeType
11、*)realloc(S.base,(S.stacksize+0STACKINCREMENT)*sizeof(MazeType));囹if(IS.base)0exit(OVERFLOW);0S.top=S.base+S.stacksize;刖S.stacksize+=STACKINCREMENT;町0*S.top++=e;SreturnOK;02)出栈操作囹StatusPop(MazeStack&S,MazeType&e)〃出栈囹｛Sif(S.top==S.base)囹returnERRO
12、R;0e=*-S.top;0returnOK;町囹3)判断栈是否为空SStatusStackEmpty(MazeStack&S)//判断是否为空[21if(S.base==S.top)忸returnOK;0returnERROR;04）迷宫路径求解0StatusMazePathfPosTypestart,PosTypeend)//迷宫路径求解｛0PosTypecurpos;0MazeStackS;0MazeTypee;Sintcurstep;0InitStack(S);scurpos=start
13、;//设定当前位置为入口位置curstep=1;//探索第一步0cout<<"起点："<<"(<<start.y<<",<<start.x<<")<<endl;do囹｛0if(Pass(curpos))〃当前位置可以通述即是未曾走到的通道块｛0FootPrint(curpos);//留下足迹13e.ord=c
