数据结构-迷宫-实验报告与代码.doc

《数据结构-迷宫-实验报告与代码.doc》由会员上传分享，免费在线阅读，更多相关内容在应用文档-天天文库。

1、一．需求分析本程序是利用非递归的方法求出一条走出迷宫的路径，并将路径输出。首先由用户输入一组二维数组来组成迷宫，确认后程序自动运行，当迷宫有完整路径可以通过时，以0和1所组成的迷宫形式输出，标记所走过的路径结束程序；当迷宫无路径时，提示输入错误结束程序。程序执行的命令：1创建迷宫；2求解迷宫；3输出迷宫求解；二．算法设计本程序中采用的数据模型，用到的抽象数据类型的定义，程序的主要算法流程及各模块之间的层次调用关系程序基本结构：设定栈的抽象数据类型定义：ADTStack{数据对象：D={

2、∈CharSet，i=1,2,3,…..,n,n>=0;}数据关系：R={<，>

3、，∈D,i=2,…,

4、n}设置迷宫的抽象类型ADTmaze{数据对象：D={ai

5、ai∈‘’，‘@’，‘#’，‘1’,i=1,2,…,n,n>=0}数据关系：R={r,c}r={

6、ai-1,ai∈D,i=1,2,…,n,}c=

7、ai-1,ai∈D,i=1,2,…,n,}结构体定义：typedefstruct//迷宫中x行y列的位置{intx;inty;}PosType;typedefstruct//栈类型{intord;//通道块在路径上的“序号”PosTypeseat;//通道块在迷宫中的“坐标位置”intdi;//从此通道块走向下一通道块的“方向”}MazeType;t

8、ypedefstruct{MazeType*base;MazeType*top;intstacksize;}MazeStack;基本函数：StatusInitStack(MazeStack&S)//新建一个栈StatusPush(MazeStack&S,MazeType&e)//入栈StatusPop(MazeStack&S,MazeType&e)//出栈StatusStackEmpty(MazeStack&S)//判断是否为空StatusMazePath(PosTypestart,PosTypeend)//迷宫路径求解voidFootPrint(PosTypepos)PosTypeNe

9、xtPos(PosTypecurPos,int&i)voidMakePrint(PosTypepos)三．程序设计根据算法设计中给出的有关数据和算法，选定物理结构，详细设计需求分析中所要求的程序。包括：人机界面设计、主要功能的函数设计、函数之间调用关系描述等。1界面设计1）迷宫界面2）迷宫路径显示2主要功能1)入栈操作StatusPush(MazeStack&S,MazeType&e)//入栈操作{if(S.top-S.base>=S.stacksize){S.base=(MazeType*)realloc(S.base,(S.stacksize+STACKINCREMENT)*size

10、of(MazeType));if(!S.base)exit(OVERFLOW);S.top=S.base+S.stacksize;S.stacksize+=STACKINCREMENT;}*S.top++=e;returnOK;}2）出栈操作StatusPop(MazeStack&S,MazeType&e)//出栈{if(S.top==S.base)returnERROR;e=*--S.top;returnOK;}3）判断栈是否为空StatusStackEmpty(MazeStack&S)//判断是否为空{if(S.base==S.top)returnOK;returnERROR;}4）

11、迷宫路径求解StatusMazePath(PosTypestart,PosTypeend)//迷宫路径求解{PosTypecurpos;MazeStackS;MazeTypee;intcurstep;InitStack(S);curpos=start;//设定当前位置为入口位置curstep=1;//探索第一步cout<<"起点:"<<"("<

12、os;e.di=1;Push(S,e);//加入路径if(curpos.x==end.x&&curpos.y==end.y){cout<<"终点("<