《数据结构课程设计》迷宫实习报告

《《数据结构课程设计》迷宫实习报告》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、实习报告二迷宫班级:08052311姓名:钱子霞学号:08051103一、需求分析迷宫问题要解决的是给你一个起点和终点，一幅迷宫地图，然后输出起点到终点的一条路径。我的代码中路径的输出有两种方式，一是育•接输出该路径上的一个位置，和路径下一个位置的在该位置的方向，二是用还是一幅地图的形式输出，在地图上表明最终路径和曾经走过的但未在路径上的足迹。所以说我们需要一个二维数组maze[n+l][m+l]来记录地图，分别为迷宫的长和宽。还要用一个二维数组hash[n+l][m+l]来记录起点到终点的一条路径和曾经走过的足迹，分别用表示最终路径上

2、的位置，和曾经走过但未在路径上的足迹。在寻找路径的过程中，我们需要一个栈来实现位置的选择。二、概要设计1.第一部分是关于栈的操作，由于我在建立链式栈的时候是每次往前面加节点，又由于栈是先进先出的，在删除节点吋我们要知道栈顶节点的前驱，所以我建的链表是的节点的指针域是前驱的地址。且我的栈是没有空白不存数据的栈底元素，因为觉得没有实现起来也不麻烦,就没有用。lnitStack(PLinkStack&S)初始条件：栈顶的指针S已存在操作结构：清空栈StackEmpty(PLinkStack&S)初始条件：栈S已存在操作结构：如果栈为空，则返冋

3、true,否则返冋false.Pop(PLinkStack&S,SNode&e)初始条件：栈S已存在，节点e已中请空间存在操作结构：删除栈顶元素Push(PLinkStack&S,SNode&e)初始条件：栈S已存在，节点e已存在操作结构：将节点e推入到栈顶2.lnitMaze(intn,intm,intmaze[100][100])初始条件：已输入地图的长和宽n,m,已有二维数组maze[][]操作结果：图的初始化，构成迷宫字符型数组，以空白字符表示通路，一字符'#'表示障碍。1.寻找路径：MathPath(intsx,intsy,i

4、ntex,intey,PLinkStack&S,intmaze[100][100])初始条件：已知起点终点位S,(sx,sy),(ex,ey),栈S已存在，地图已初始化完操作结果：找到一条起点到终点的路径，路径上的位置依次从起存在栈S屮把路径记录在hash[][]数组中，若位置(i,j)在路径上则标记为2.若该位置仅仅走过但最后并未在路径上则标记为3.最后如果成功找到一条路径返回true,否则返回false.2.Pass(intx,inty,intn,intm,intmaze[100][100])初始条件：已知位置(x,y),迷宫的长宽

5、n,m,迷宫地图maze[][]操作结果：判断该位置是否可以通过，可以则返IhItrue,否则返[Hlfalse・3.PrintPath(boolsucczPLinkStackS)初始条件：succ起点到终点路径是否存在的标志，栈S存在，如果有路径存在的话，栈里就是存放了路径。操作结果：直接输出该路径上的每个位置，和路径下一个位置的在该位置的方向，4.PrintMaze(boolsucc,PLinkStack&S,intn,intm,intmaze[100][100])初始条件：已知路径查找是否成功，迷宫的长宽n,m,迷宫地图maze[

6、][],记录路径情况的二维数组hash[][].操作结果：一幅地图的形式输出，在地图上表明最终路径和曾经走过的但未在路径上的足迹.三、详细设计栈内节点的形式：typedefstructnode{intposx,posy;intdir;//dir为下一步的方向1:向东走;2:向南走;3:向西走;4;向北走structnode*pre;//以为栈是先进后岀,top删除后我们需要知道top前面的节点，所以节点的指针域用来保存前驱地址更好}SNode;栈的形式：typedefstructfSNode*base;SNode*top;}LinkSt

7、ack,*PLinkStack;intdir[4][2]二{OJJQO—,0};//一个位置的周围的四个方向，一次为东南西北栈的具体操作1).voidlnitStack(PLinkStack&S){S->base=S->top=NULL;}因为没有栈底元素，所以当栈空时为topz指针和base指针都为NULL2)boolStackEmpty(PLinkStack&S){讦(S->base==NULL&&S->top==NULL)returntrue;returnfalse;}3)voidPop(PLinkStack&S,SNode&e)

8、{e=*S->top;if(S->base==S->top){free(S->top);S->base=S->top=NULL;}else{SNode*p=S->top;S->top二p->pre;free