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

南昌航空实验报告课程名称：数据结构 实验名称：班级：姓名：：指导教师评定：签名:假设迷宫由m行n列构成，有一个入口和一个出口，入口坐标为(1，1)，出口坐标为(m，n)试找出一条从入口通往出口的路径。 一、需求分析 ⒈ 用栈的基本操作完成迷宫问题的求解，其中栈的基本操作作为一个独立的模块存在。 ⒉ 以二维数组b[m][n]表示迷宫，b[i][j] 表示迷宫中相应（i,j）位置的通行状态（0:表示可以通行，1：表示有墙，不可通行），完成迷宫的抽象数据类型，包括出口、入口位置等。 ⒊ 程序中完成对应迷宫的初始化。 ⒋ 迷宫的入口位置和出口位置在合法范围内由用户而定。 ⒌ 程序完成对迷宫路径的有哪些信誉好的足球投注网站，如果存在路径，则输出走出迷宫的路径。 ⒍ 程序执行的命令： ⑴ 创建初始化迷宫； ⑵ 有哪些信誉好的足球投注网站迷宫； ⑶ 输出有哪些信誉好的足球投注网站结果。 二、概要设计 ⒈ 设计栈的抽象数据类型定义： ADT Stack { 数据对象：D={ai:|ai∈PositionSet,i=1…n,n≥0} 数据关系：R1={ai-1,ai|ai-1,ai∈d,i=2,…n} 基本操作： 操作结果 InitStack(S) 构造一个空栈，完成栈的初始化S DestoryStack(S) 撤消一个已经存在的栈S ClearStack(S) 将栈S重新置空 StackLength(S) 返回栈的长度 GetTop(S,e) 用e返回栈S的栈顶元素 StackEmpty(S) 若S为空返回1，否则返回0 Push(S,e) 将新的元素e压入栈顶 Pop(S,e) 删除栈顶元素，并用e返回其值 StackTraverse(s) 将栈S的所有元素输出 }ADT Stack； ⒉ 迷宫的抽象数据类型定义： ADT Maze{ 数据对象：D：={aij,Start,end|aij,Start,end∈{} 0≤i≤m+2,0≤j≤n+2,m,n≥0} 数据关系：R={ROW.COL} Row={ai-1j,aij|ai-1,aij∈D i=1,…,m+2,j=1,…,n+2} Col={aij-1,aij|aijaij-1∈D} 基本操作: SetMaze(Maze) 初始条件：Maze已经定义，Maze的下属单元二维数组Maze.M[row+2][d+2]已存在，Maze.start,Maze.end也已作为下属存储单元存在 操作结果：构成数据迷宫，用数值标识迷宫的物理状态，以0表示通路，以1表示障碍，由终端读取迷宫空间大小，各点处的具体物理状态及Start和End点位置，完成迷宫构建 Pass(Mazem,Nposition,Position,di) 初始条件：已知目前迷宫状态及当前位置、下一步探索方向di 操作结果：完成相应的有哪些信誉好的足球投注网站任务，如果可行，则用Nposition返回 下一步位置，并将Maze状态改变为相应点已走过情况 PrintMaze(Maze) 操作结果：输出字符标示的迷宫 FindWay(Maze,way) 操作结果：利用Pass有哪些信誉好的足球投注网站迷宫，用way返回有哪些信誉好的足球投注网站所得路径。如不存在，返回０ PrintWay(Maze,way) 操作结果：将Maze及相应最短路径一起打印输出 }ADT MAZE, ⒊ 本程序模块结构 ⑴ 主函数模块 void main(){ 初始化； do{ 接受命令； 处理命令； ｝while（退出命令） ｝ ⑵ 栈模块——实现栈抽象数据类型； ⑶ 迷宫模块——实现迷宫抽象数据类型； 各模块之间的调用关系如下： 主程序模块　　　　　　 迷宫模块 栈模块 三、详细设计 ⒈ 基本数据类型操作 ⑴ 栈模块 ①struct sqstack{ int *base; // 在栈初始化之前和销毁之后为NULL int *top; // 栈顶指针，在栈顶元素上方一单元处 int stacksize; // 当前已分配存储空间，以元素为单位 }; // 线性存储结构 ② 参数设置： #define STACK_INIT_SIZE 20; #define STACKINIREMENT 10; //----------基本操作的算法描述-------------------- //建一个空栈 void initstack( sqstack s){ s.base=(int *)malloc(SIZE*sizeof(int)); if(!s.base){printf(\n内存不足\n);exit(0);} s.top=s.base; s.stacksize=SIZE; } //出栈 int pop( sqstack s,int *e){ if(