用栈方法、队列方法求解迷宫问题

用栈方法、队列方法求解迷宫问题

ID:47450164

大小:91.00 KB

页数:18页

时间:2020-01-11

用栈方法、队列方法求解迷宫问题_第页
预览图正在加载中,预计需要20秒,请耐心等待
资源描述:

《用栈方法、队列方法求解迷宫问题》由会员上传分享,免费在线阅读,更多相关内容在行业资料-天天文库

1、........目录1前言12需求分析12.1课程设计目的12.2课程设计任务12.3设计环境13概要设计13.1数据结构设计13.2模块设计24详细设计34.1数据类型的定义34.2主要模块的算法描述35测试分析66课程设计总结7参考文献8致谢8附录(程序代码实现)9.专业学习资料.........1前言设计一个简单迷宫程序,从入口出发,按某一方向向前探索,若能走通(未走过的),即某处可以到达,则到达新点,否则试探下一方向;若所有方向均没有通路,则沿原点返回前一点,换下一个方向在继续试探,直到所有可能的通路都探索到,或找到一条通路,或无路可走又返回到入口点。并利用两种方法实现:一种用栈实现,

2、另一种用队列实现。2需求分析2.1课程设计目的学生在教师指导下运用所学课程的知识来研究、解决一些具有一定综合性问题的专业课题。通过课程设计(论文),提高学生综合运用所学知识来解决实际问题、使用文献资料、及进行科学实验或技术设计的初步能力,为毕业设计(论文)打基础。2.2课程设计任务给出一个任意大小的迷宫数据,求出一条走出迷宫的路径,输出迷宫并将所求路径输出。要求用两种方法实现:一种用栈实现,另一种用队列实现。,我主要负责队列方面2.3设计环境(1)WINDOWS2000/2003/XP/7/Vista系统(2)VisualC++或TC集成开发环境3概要设计3.1数据结构设计(1)迷宫类型设迷宫

3、为M行N列,利用maze[M][N]来表示一个迷宫,maze=0或1,其中0表示通路,1表示不通。当从某点试探是,中间点有8个不同点可以试探,而四个角有3个方向,其他边缘点有5个方向,为使问题更容易分析我们用maze[M+2].专业学习资料.........[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中的下标。除此之外,还需设定头、尾指针,分别指向队头,队尾。类型定义如下:typedefstruct//队的相关类型定义{intx,y;intpre;}Elemtype;typedefstruct//队列的类型定义{Elemtypeelem[MAXSIZE];intfron

5、t,rear;intlen;}SqQueue;3.2模块设计定义函数DLmazepath(),利用队列实现迷宫求。定义函数DLmazepath(),实现队列的迷宫路径输出。定义函数InitQueue(),实现队列的初始化。定义函数QueueEmpty(),判断队列是否为空,为空返回1,否则返回0.定义函数GetHead(SqQueueq,Elemtype*e),实现队头元素的读取。定义函数EnQueue(SqQueue*q,Elemtypee),实现入队操作。定义函数DeQueue(SqQueue*q,Elemtype*e),实现出队操作。定义函数Sprint(inta[M+2][N+2]),

6、实现,迷宫的输出。.专业学习资料.........4详细设计(1)主函数voidmain(){inta,i,j,maze2[M+2][N+2];/*构造一个迷宫*/intmaze[M+2][N+2]={{1,1,1,1,1,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,

7、1},{1,0},{1,-1},{0,-1},{-1,-1},{-1,0},{-1,1}};/*坐标增量数组move的初始化*/为使得程序更加人性化,更加友好,因此可将系统输出界面设置如下:printf("

8、*****************迷宫求解系统*****************

9、");printf("

10、1、栈方法求解迷宫的路径

11、");printf("

12、2、队列求解的迷宫路径

13、

当前文档最多预览五页,下载文档查看全文

此文档下载收益归作者所有

当前文档最多预览五页,下载文档查看全文
温馨提示:
1. 部分包含数学公式或PPT动画的文件,查看预览时可能会显示错乱或异常,文件下载后无此问题,请放心下载。
2. 本文档由用户上传,版权归属用户,天天文库负责整理代发布。如果您对本文档版权有争议请及时联系客服。
3. 下载前请仔细阅读文档内容,确认文档内容符合您的需求后进行下载,若出现内容与标题不符可向本站投诉处理。
4. 下载文档时可能由于网络波动等原因无法下载或下载错误,付费完成后未能成功下载的用户请联系客服处理。