任务书1(迷宫问题)

课程设计报告课程名称数据结构课程设计课题名称迷宫问题专业信息与计算科学班级1002班学号08姓名田雯指导教师刘洞波×××2012年6月9日课程设计任务书课程名称数据结构课程设计课题迷宫问题专业班级信科1002班学生姓名田雯学号08指导老师刘洞波审批任务书下达日期：2012年6月9日任务完成日期：2012年6月16日目录1问题描述.....................错误!未定义书签。2需求分析.....................错误!未定义书签。3概要设计.....................错误!未定义书签。3．1抽象数据类型定义...........................53．2模块划分...........................................53.3各模块的调用关系………………….24详细设计....................................................24．1数据类型的定义...............................24．2主要模块的算法描述.......................95测试分析....................................................66课程设计总结............................................7参考文献.........................错误!未定义书签。附录（源程序清单）.....错误!未定义书签。一、设计内容与设计要求1．设计内容：1）问题描述以一个M*N的长方阵表示迷宫，0和1分别表示迷宫中的通路和墙壁。设计一个程序，对任意设定的迷宫，求出一条从入口到出口的通路，或得出米有通路的结论。2）基本要求a.实现一个以链表作存储结构的栈类型，然后编写一个求解迷宫的非递归程序。求得的通路以三元组（i，j，d）的形式输出，其中：（i，j）指示迷宫中的一个坐标，d表示走到下一个坐标的方向。b.编写递归形式的算法，求得迷宫中所有可能的通路。3）测试数据迷宫的测试数据如下：左上角（1,1）为入口，右下角（8,9）为出口。0010001000100010000011010111001000010000010001010111100111000101110000004）实现提示计算机解迷宫通常用的是“穷举求解”方法，即从入口出发，顺着某一个方向进行探索，若能走通，则继续往前进；否则，沿着原路退回，换一个方向继续探索，直至出口位置，求得一条通路。假如所有可能的通路都探索到而未能到达出口，则设定的迷宫没有通路。可以二维数组存储迷宫数据，通常设定入口点的下标为（1，1），出口点的下标为（m，n）。为处理方便起见，可在迷宫的四周加一圈障碍。对于迷宫中任一位置，均可约定有东、南、西、北四个方向可通。2．设计要求：课程设计报告规范1)需求分析（1）首先实现一个以链表作存储结构的栈类型，然后编写一个求解迷宫的非递归程序。求得的通路以三元组（i，j，d）的形式输出，其中：（i，j）指示迷宫中的一个坐标，d表示走到下一坐标的方向。否则报告一个无法通过的信息。（2）建立InitStack函数，用于构造一个空栈。（3）建立DestroyStack函数，用于销毁栈。（4）建立Pop函数，用于删除栈顶元素，返回栈顶元素的值。（5）建立Push函数，用于插入新的栈顶元素。（6）建立NextPos函数，用于定位下一个位置。2)概要设计3．1抽象数据类型定义（1）栈的抽象数据类型定义InitStack(LStack*S)操作结果：构造一个空栈S。DestroyStack(LStack*S)操作结果：栈S被销毁。Pop(LStack*S，ElemType*e)操作结果：删除S的栈顶元素。用e返回栈顶元素的值。若栈为空则返回0。Push(LStack*S，ElemTypee)操作结果：在栈顶之上插入元素e为新的栈顶元素。若栈S为空栈，则返回0。（2）迷宫的抽象数据类型定义NextPos(unsigned*x，unsigned*y，shortdi)操作结果：找到下一个位置。3．2模块划分本程序包括三个模块：（1）主程序模块voidmain(){初始化；构造迷宫；迷宫求解；迷宫输出；}（2）栈模块——实现栈的抽象数据类型（3）迷宫模块——实现迷宫的抽象数据类型各模块的调用关系如下：4）求解迷宫的通路的伪码算法：设定当前位置的处值为入口位置；DO{若当前的位置可通。则{将当前的位置插入栈顶；若该位置为出口位置，则结束；否则切换当前位置的东邻的为新的当前位置；}否则{若栈不为空且栈的顶位置尚有其他的方向没有被探索，则设定新的当前位置为沿顺时针方向旋转找到栈顶的位置的下一个相邻块；若栈不空但栈顶的四周均不可通过，则{删去栈顶位置；若栈不为空，则重新测试新的栈顶位置；只至找到一个可通过的块至栈空；}1坐标的位置的类型typedefstruct{intline;introw;}PosType;2迷宫类型voidCreatMaze(intr,intl)//定义迷宫的墙为*，通路为_，障碍为#{inti,j;for(i=0;ir;i++){maze[i][0]='*';//左面墙maze[i][l-1]='*';//右面墙}for(j=1;jl-1;j++){maze[0][j]='*';//上面墙maze[r-1][j]='*';//下面墙}for(i=1;ir-1;i++)for(j=1;jl-1;j++)maze[i][j]='_';cout请输入迷宫内障碍物的个数：;intnum;cinnum;cout请依次输入障碍物的坐标：endl;intx,y;for(i=1;i=num;i++){cinxy;maze[x][y]='#';}coutendl创建的迷宫的如下：endlendl;PrintMaze(r,l);coutendl;4迷宫的路径的算法intMazePath(PosTypestart,PosTypeend){InitStack(S);curpos=start;//设定当前位置为入口位置curstep=1;//第一步do{if(Pass(curpos)){//当前位置可以通过（未曾走过）FootPrint(curpos);//留下足迹e.ord=curstep;e.seat=curpos;e.di=1;Push(S,e);//加入路径if(curpos.row==end.row&&curpos.line==end.line)//到达终点returnTRUE;curpos=NextPos(curpos,1);//下一位置是当前位置的东邻curstep++;//探索下一步}//ifelse{//当前位置不能通过if(!StackEmpty(S)){Pop(S,e);while(e.di==4&&!StackEmpty(S)){MarkPrint(e.seat);//留下不能通过的标志Pop(S,e);//退回一步//curstep--;}//whileif(e.di4){e.di++;//换下一个方向探索Push(S,e);curpos=NextPos(e.seat,e.di);//设定当前位置是该新方向上的相邻块}//if}//if}//else}while(!StackEmpty(S));returnFALSE;3)详细设计4．1数据类型的定义（1）迷宫类型typedefstruct{unsignedord,x,y；shortdi；}ElemType；unsignedx,y,curstep,i=0；charmaze[10][10]；（2）栈类型typedefstructNode{ElemTypedata；structNode*next；}Node,*LinkList；typedefstruct{LinkListtop；unsignedlength；}LStack；LinkListq；LStackS,T；ElemTypee；4．2主要模块的算法描述4.1函数寻找下一个位置流程图此函数的功能是寻找下一个位置。首先判断di的值，如果di=1，指针x++，退出。如果di=2，指针y++，退出。如果di=3，指针x--，退出。如果di=4，指针y--，退出。如果di为其它值，则直接退出。见图4.1。YNYNYYNNdi=1di=2di=3di=4Break；指针x自增；Break；指针y自增；Break；指针x自减；Break；指针y自减；Break；开始结束图4.1函数寻找下一个位置流程图4.2函数销毁栈流程图此函数的功能是销毁栈，首先建立单链表q，判断top指针是否为空，若为空则释放s的空间，否则出栈，直到top指针为空，释放s的空间。见图4.2。图4.2函数销毁栈流程图4.3函数出栈流程图此函数的功能是出栈。首先建立单链表q，如果栈s为空则返回0，若栈s不为空，则出栈，修改指针。返回1。见图4.3。YNLinkListq；栈s为空出栈；Return1；Return0；开始结束YNLinkListq；判断栈的top释放栈s的空间；出栈；开始结束图4.3函数出栈流程图4.4函数入栈流程图此函数的功能是入栈。首先在链表中生成结点p，判断p是否为空。若为空则返回0，若非空，则入栈，修改指针，返回0。见图4.4。图4.4函数入栈流程图4.5主函数流程图主函数实现了求解迷宫，首先建立栈s和t，输出迷宫图形，然后探索路径，实现迷宫求解，最后输出出迷宫顺序。如果有完整路径则输出完整路径，如果没有完整路径则输出无法通过信息。见图4.5。YN生成结点p；!p入栈；Return1；Return0；开始结束建立栈S和T；输出迷宫图形；迷宫求解；输出出迷宫顺序；结束开始图4.5主函数流程4)调试分析（1）有一条完整路径通过迷宫的测试数据及结果。见图5.1。图5.1有一条完整路径通过迷宫的测试数据及结果从入口出发，顺着某一个方向进行探索，若能走通，则继续往前进；否则沿着原路退回，换一个方向继续探索，直至出口位置，求得一条通路。输出通路的坐标，即出迷宫的顺序。（2）没有路径能通过迷宫的测试数据及结果。见图5.2。图5.2没有路径能通过迷宫的测试数据及结果从入口出发，顺着某一个方向进行探索，若能走通，则继续往前进；否则沿着原路退回，换一个方向继续探索，直至前面没有路径。输出此时无法通过，没有能够通过迷宫的路径的信息！5)课程设计总结通过这次课程设计使我充分的理解了用栈实现迷宫问题的基本原理，知道了栈存储结构的定义和算法描述，同时也学会了编写简单的迷宫问题的程序。虽然此次的程序不是很完备，但是总体还是一个比较能体现数据结构知识点能力的程序了，当然只是相对于我这个初学者来说。在刚开始编程的时候，错误百出，不知道怎么样改正，但是通过自己的仔细的分析和老师的细心的指导，在认真分析了原程序后，终于认识并理解了自己错误的地方，使自己加以改正，汲取教训。为以后知识水平的提高，做了最好的准备。在此我非常要感谢的是我们的指导老师申寿云老师，同时也要感谢我们的成娅辉老师平时上课的教导，和编程时细心认真的辅导，教给我许多知识。这次课程设计能够顺利的完成，当然有我个人的努力，但同时更离不开指导老师的答疑解惑。6)使用说明先初始化栈，然后增加栈顶，撤销栈顶，再输出栈，想出迷宫路径，最后撤出栈s，制造迷宫7)书写格式见附带说明。8)附录a.参考书目[1]严蔚敏，吴伟民.数据结构（C语言版）[M].北京：清华大学出版社，2002[2]刘振鹏，张晓莉，郝杰．数据结构[M]．北京：中国铁道出版社，2003b.源程序清单（带注释）#includestdio.h#includestdlib.htypedefstruct{unsignedord,x,y;/*通道块在路径上的序号和在迷宫中的坐标位置*/shortdi;/*从此通道块