《迷宫课程设计.doc》由会员分享，可在线阅读，更多相关《迷宫课程设计.doc（23页珍藏版）》请在金锄头文库上搜索。
1、西华大学数计学院课程设计说明书数学与计算机学院课程设计说明书【此页单独打印】课 程 名 称:数据结构与算法B综合课程设计课 程 代 码: 6013799 题 目:DFS生成迷宫与迷宫的BFS、DFS搜索 年级/专业/班: 2012/计算机科学与技术/04班学 生 姓 名: 学 号:312012080605426 开 始 时 间: 2012 年 12 月 20 日完 成 时 间: 2012 年 12 月 24 日课程设计成绩：学习态度及平时成绩（30）技术水平与实际能力（20）创新（5）说明书撰写质量（45）总 分（100）指导教师签名： 年 月 日III目 录 摘要1 前言11.1 问题的提出
2、11.2 任务与分析12.软件总体设计22.1 开发工具22.2 系统框图22.3 模块功能22.3.1 绘图模块22.3.2 DFS模块32.3.3 BFS模块33.人机界面设计.4 3.1 客户区原始界面.4 3.2 迷宫拆墙界面.4 3.3 DFS走迷宫界面. 4 3.4 BFS走迷宫界面.44. 功能详细设计54.1 绘墙54.2 拆墙54.3 迷宫信息文本存储54.4 走迷宫(DFS)54.5 走迷宫(BFS)55 软件测试6结 论7致 谢8参考文献9摘 要 迷宫是一种充满复杂通道的建筑物,很难找到从其内部到达入口或从入口到达中心的道路。比喻复杂艰深的问题或难以捉摸的局面。迷宫从古代
3、就有人在研究并加以运用，它拥有千百年的历史，迷宫问题向来经典，有很多人都在研究它，以至于有很多迷宫相关的算法，要走迷宫首先要形成迷宫，这里采用常见的DFS深度优先搜索算法生成迷宫这样生成的迷宫是迷宫各个点所组成图的一个生成树，所以可以保证迷宫中任意两点都有路径到达，并且迷宫中没有环路（完美迷宫），迷宫拆完墙以后就构成了一条通道，当然为了下一次生成同样的迷宫，迷宫的拆墙信息以及各个单元格的四面墙的信息都应该以文件的形式进行保存，以便下一次读取恢复原来迷宫的形态，走迷宫采用DFS、BFS两种搜索方法，DFS的特点：纵深进行到底，采用STL的stack存储数据。BFS的特点：宽度进行到底，采用STL
4、的queue储存数据。调用gui函数并且采用Sleep()的方式将程序挂起，计算机一边运算一边动态展现，最终到达出口。关键词： DFS BFS GUI stack queue1 前言 1.1 问题的提出 为了更深刻地理解DFS、BFS搜索算法的搜索原理，为了了解gui相关函数的调用，为了将所学算法运用于生活中实际中我们编写了这个走迷宫程序。1.2 任务与分析1. 基于图形用户界面GUI的标准“Windows” 应用程序。2. 贴图表现：迷宫（二维平面图案，包括墙壁和通道）。3. 动画表现：动态表现迷宫生成和求解的每一步变化过程。4. 迷宫大小：N和M（用户输入），允许范围：1030，缺省值：1
5、5和15。5. 迷宫格子：N*M大小的迷宫由N*M个格子构成，每个格子有东、南、西、北四堵墙，迷宫生成过程就是对所有格子进行一次遍历拆墙过程，遍历完成后迷宫就生成了。6. 迷宫入口和出口：分别在第 0行和第N-1行上随机选择。 7. 算法要求：（1）生成的迷宫有解；（2）禁用递归程序；（3）保证每次生成的迷宫不同，这要求生成时用随机函数（时间种子）。8. 迷宫类型：生成的是完美迷宫即单连通迷宫，迷宫中不存在环，且不存在不可访问区域，迷宫中任意两点之间有且仅有唯一的路径（参考：图的生成树）。9. 文件存储：（1）将生成的迷宫保存在文件中（用文本文件，迷宫数据的存储格式自定）；（2）迷宫求解时，从
6、相应的迷宫文件中读取迷宫数据，然后求解。10. 界面设计要求1） 操作流程简便合理，操作界面美观自然，符合用户一般操作习惯。2） 界面简洁美观，配色和谐，比例合适，符合大多数人的审美趣向。11. 菜单设置“使用说明”，介绍本软件的开发者、特色、各项功能及使用。2. 软件总体设计2.1 开发工具开发工具：visual C+ 6.0 （企业版）优点：模块加载速度快，界面简单易操作开发环境：windows 7 （旗舰版x64系统）运行环境windows 95以上2.2 系统框图（1）系统组成框图：WinMain（函数入口） DFS（拆墙） BFS走迷宫DFS走迷宫 图2-1（2） 系统流程图： 开始
7、 客户区绘满方格（DrawRect） DFS拆墙迷宫拆墙数据.txt每个单元格四面墙的数据.txt 四面墙数据 拆墙数据 拆墙数据 重绘客户区 读取 读取走迷宫（DFS） 读取 读取 重绘客户区 走迷宫（BFS） 结束 图2-22.3 模块功能软件开发方式：SDKGUI函数模块： 1)DrawWhiteGround (HDC hdc);/将整个客户区绘制为白色2)DrawRedBlock (HDC hdc, int l, int t, int r, int b);/绘制迷宫起始点与终止点3)DrawRect (HDC hdc, int l, int t, int r, int b);/绘制单元
8、方格4)DrawCell (HDC hdc, int l, int t, int r, int b);/绘制移动方块5)DrawGamePlace(HDC hdc, int col, int row); /在客户区绘满单元格6)Adj(int x, int y, bool* visited, int col);/判断该单元格是否有没有被访问的相邻单元格7)Adj_NoWall(int x, int y, bool* visited, Wall* wall, int col);/判断该单元格是否有没有被访问的相邻单元格并且周围没有墙可以访问8)Replace (HDC hdc, int x, i
9、nt y, int z, int k);/拆墙(用白色划线替换红色划线)文件操作模块：1)WriteDocument (MazeEdge* mazeedge, Wall* wall, int i);/将迷宫拆墙数据写入txt文件中2)ReadDocument (HDC hdc);/从txt文件中读取迷宫拆墙数据核心算法模块：1）DrawPath(HDC hdc, int w, int h);/迷宫拆墙2)DFS (HDC hdc);/深度优先搜索寻找迷宫路径3)BFS (HDC hdc);/广度优先搜索寻找迷宫路径动态效果关键函数：Sleep()3 人机界面设计 图3-1 客户区原始界面 图3
10、-2 迷宫拆墙界面 图3-3 DFS走迷宫界面 图3-4 BFS走迷宫界面4 功能详细设计GUI函数模块： 1)/将整个客户区绘制为白色void DrawWhiteGround (HDC hdc)int col, row;std:ifstream f (C:迷宫拆墙数据.txt);fcolrow;f.close();HBRUSH hbrush = CreateSolidBrush(RGB(255,255,255);SelectObject(hdc, hbrush);Rectangle(hdc, 0, 0, col*CELL, row*CELL);DeleteObject(hbrush);2)/绘制迷宫起始点与终止点void DrawRedBlock (HDC hdc, int l, int t, int r, int b)HBRUSH hbrush = CreateSolidBrush(RGB(255,0,0);SelectObject (hdc, hbrush);Rectangle(hd
