资源描述:
《《数据结构课程设计》迷宫实习报告》由会员上传分享,免费在线阅读,更多相关内容在工程资料-天天文库。
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