队列的应用――迷宫问题_实验样本

《队列的应用――迷宫问题_实验样本》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、队列的应用――迷宫问题_实验样本导读：就爱阅读网友为您分享以下“队列的应用――迷宫问题_实验样本”资讯，希望对您有所帮助，感谢您对92to.com的支持!南昌航空大学实验报告二Ｏ年课程名称：月日数据结构实验名称：实验四：队列的应用班级：12203125学生姓名：李平同组人：指导教师评定：签名:题目：假设迷宫由m行n列构成，有一个入口和一个出口，入口坐标为(1，1)，出口坐标为(m，n)，试找出一条从入口通往出口的最短路径。设计算法并编程输出一条通过迷宫的最短路径或报告一个“无法通过”的信息。要求：用栈和队列实现，不允许使用递归算

2、法。一、需求分析⒈用栈的基本操作完成迷宫问题的求解，其中栈的基本操作作为一个独立的模块存在。⒉以二维数组b[m][n]表示迷宫，b[i][j]表示迷宫中相应（i,j）位置的通行状态（0:表示可以通行，1：表示有墙，不可通行）14，完成迷宫的抽象数据类型，包括出口、入口位置等。⒊程序中完成对应迷宫的初始化。⒋迷宫的入口位置和出口位置在合法范围内由用户而定。⒌程序完成对迷宫路径的搜索，如果存在路径，则输出走出迷宫的路径。⒍程序执行的命令：⑴创建初始化迷宫；⑵搜索迷宫；⑶输出搜索结果。二、概要设计⒈设计栈的抽象数据类型定义：ADTSt

3、ack{数据对象：D={ai:

4、ai∈PositionSet,i=1„n,n≥0}数据关系：R1={ai-1,ai

5、ai-1,ai∈d,i=2,„n}基本操作：InitStack(&S)DestoryStack(&S)ClearStack(&S)StackLength(S)GetTop(S,&e)StackEmpty(S)Push(&S,e)Pop(&S,e)StackTraverse(s)}ADTStack；1操作结果构造一个空栈，完成栈的初始化S撤消一个已经存在的栈S将栈S重新置空返回栈的长度用e返回栈S的栈顶元素若S为空返

6、回1，否则返回0将新的元素e压入栈顶删除栈顶元素，并用e返回其值将栈S的所有元素输出14⒉迷宫的抽象数据类型定义：ADTMaze{数据对象：D：={aij,Start,end

7、aij,Start,end∈{}0≤i≤m+2,0≤j≤n+2,m,n≥0}数据关系：R={ROW.COL}Row={ai-1j,aij

8、ai-1,aij∈Di=1,„,m+2,j=1,„,n+2}Col={aij-1,aij

9、aijaij-1∈D}基本操作:SetMaze(&Maze)初始条件：Maze已经定义，Maze的下属单元二维数组Maze.M[r

10、ow+2][d+2]已存在，Maze.start,Maze.end也已作为下属存储单元存在操作结果：构成数据迷宫，用数值标识迷宫的物理状态，以0表示通路，以1表示障碍，由终端读取迷宫空间大小，各点处的具体物理状态及Start和End点位置，完成迷宫构建Pass(&Mazem,&Nposition,Position,di)初始条件：已知目前迷宫状态及当前位置、下一步探索方向di操作结果：完成相应的搜索任务，如果可行，则用Nposition返回下一步位置，并将Maze状态改变为相应点已走过情况PrintMaze(Maze)操作结果：

11、输出字符标示的迷宫FindWay(Maze,&way)操作结果：利用Pass搜索迷宫，用way返回搜索所得路径。如不存在，返回０PrintWay(Maze,way)操作结果：将Maze及相应最短路径一起打印输出}ADTMAZE,⒊本程序模块结构⑴主函数模块voidmain(){初始化；do{接受命令；处理命令；｝while（退出命令）｝14⑵栈模块——实现栈抽象数据类型；⑶14迷宫模块——实现迷宫抽象数据类型；2各模块之间的调用关系如下：主程序模块迷宫模块栈模块三、详细设计⒈基本数据类型操作⑴栈模块①structsqstack{

12、int*base;//在栈初始化之前和销毁之后为NULLint*top;//栈顶指针，在栈顶元素上方一单元处intstacksize;//当前已分配存储空间，以元素为单位};//线性存储结构②参数设置：#defineSTACK_INIT_SIZE20;#defineSTACKINIREMENT10;//----------基本操作的算法描述-------------------//建一个空栈voidinitstack(sqstack&s){s.base=(int*)malloc(SIZE*sizeof(int));if(!s.b

13、ase){printf(“内存不足”);exit(0);}s.top=s.base;s.stacksize=SIZE;}//出栈intpop(sqstack&s,int*e){if(s.top==s.base)return0;*e=*(--s.top);