资源描述：
《用栈方法、队列方法求解迷宫问题》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。
1、目录1前言12需求分析12.1课程设计目的12.2课程设计任务12.3设计环境13概要设计13.1数据结构设计13.2模块设计24详细设计34．1数据类型的定义34．2主要模块的算法描述35测试分析66课程设计总结7参考文献8致谢8附录（程序代码实现）91前言设计一个简单迷宫程序，从入口出发，按某一方向向前探索，若能走通（未走过的），即某处可以到达，则到达新点，否则试探下一方向；若所有方向均没有通路，则沿原点返回前一点，换下一个方向在继续试探，直到所有可能的通路都探索到，或找到一条通路，或无路可走又返回到入口点。并
2、利用两种方法实现：一种用栈实现，另一种用队列实现。2需求分析2.1课程设计目的学生在教师指导下运用所学课程的知识来研究、解决一些具有一定综合性问题的专业课题。通过课程设计（论文），提高学生综合运用所学知识来解决实际问题、使用文献资料、及进行科学实验或技术设计的初步能力，为毕业设计（论文）打基础。2.2课程设计任务给出一个任意大小的迷宫数据，求出一条走出迷宫的路径，输出迷宫并将所求路径输出。要求用两种方法实现：一种用栈实现，另一种用队列实现。，我主要负责队列方面2.3设计环境（1）WINDOWS2000/2003/X
3、P/7/Vista系统（2）VisualC++或TC集成开发环境3概要设计3.1数据结构设计（1）迷宫类型设迷宫为M行N列，利用maze[M][N]来表示一个迷宫，maze=0或1，其中0表示通路，1表示不通。当从某点试探是，中间点有8个不同点可以试探，而四个角有3个方向，其他边缘点有5个方向，为使问题更容易分析我们用maze[M+2]15[N+2]来表示迷宫，而迷宫四周的值全部为1。定义如下：#defineM6/*迷宫的实际行*/#defineN8/*迷宫的实际列*/intmaze[M+2][N+2];（2）队列
4、的类型定义队列的有关数据结构、试探方向等和栈的求解方法处理基本相同。不同的是：如何存储搜索路径。在搜索过程中必须几下每一个可到达的坐标点，以便从这些点出发继续向四周搜索。到达迷宫的出口点（m,n）后，为能够从出口沿搜索路径回溯直至入口，对于每一点，记下坐标点的同时，还要记下到达该点的前驱点，因此用一个结构体数组ele[MAX]作为队列的存储空间，因为每一点至少被访问一次，所以MAX至多等于m*n。该结构体有三个域：x、y和pre。其中x、y分别为所到达点的坐标，pre为前驱点在elem中的下标。除此之外，还需设定头
5、、尾指针，分别指向队头，队尾。类型定义如下：typedefstruct//队的相关类型定义{intx,y;intpre;}Elemtype;typedefstruct//队列的类型定义{Elemtypeelem[MAXSIZE];intfront,rear;intlen;}SqQueue;3.2模块设计定义函数DLmazepath()，利用队列实现迷宫求。定义函数DLmazepath()，实现队列的迷宫路径输出。定义函数InitQueue（），实现队列的初始化。定义函数QueueEmpty()，判断队列是否为空，为
6、空返回1，否则返回0.定义函数GetHead(SqQueueq,Elemtype*e)，实现队头元素的读取。定义函数EnQueue(SqQueue*q,Elemtypee)，实现入队操作。定义函数DeQueue(SqQueue*q,Elemtype*e)，实现出队操作。定义函数Sprint(inta[M+2][N+2])，实现，迷宫的输出。154详细设计（1）主函数voidmain(){inta,i,j,maze2[M+2][N+2];/*构造一个迷宫*/intmaze[M+2][N+2]={{1,1,1,1,1,
7、1,1,1,1,1},{1,0,1,1,1,0,1,1,1,1},{1,1,0,1,0,1,1,1,1,1},{1,0,1,0,0,0,0,0,1,1},{1,0,1,1,1,0,1,1,1,1},{1,1,0,0,1,1,0,0,0,1},{1,0,1,1,0,0,1,1,0,1},{1,1,1,1,1,1,1,1,1,1}};itemmove[8]={{0,1},{1,1},{1,0},{1,-1},{0,-1},{-1,-1},{-1,0},{-1,1}};/*坐标增量数组move的初始化*/为使得程序更加人
8、性化，更加友好，因此可将系统输出界面设置如下：printf("
9、*****************迷宫求解系统*****************
10、");printf("
11、1、栈方法求解迷宫的路径
12、");printf("
13、2、队列求解的迷宫路径
14、");printf("
15、3、退出系统
16、");printf("
17、*******************
