课程设计说明书【此页单独打印】课程名称:数据结构与算法B综合课程设计课程代码：6013799题目：DFS生成迷宫与迷宫的BFS、DFS搜索年级/专业/班:2012/计算机科学与技术/04班学 生 姓 名学号312012080605426开始时间2012 年 12月 20 日完成时间2012 年 12月 24 日课程设计成绩：学习态度及平 时成绩（30）技术水平与实际 能力（20）创新（5）说明书撰写质量（45）总分 （100）指导教师签名： 年_月_日目录摘要1 前言 41.1 问题的提出 41.2 任务与分析 42.软件总体设计 52.1 开发工具 52.2 系统框图 52.3 模块功能 62.3.1 绘图模块 错误！未定义书签。2.3.2 DFS 模块错误！未定义书签。2.3.3 BFS模块错误！未定义书签。3.人机界面设计43.1客户区原始界面43.2迷宫拆墙界面43.3 DFS走迷宫界面43.4 BFS走迷宫界面44.功能详细设计74.1 绘墙 4.2 拆墙 4.3 迷宫信息文本存储4.4走迷宫(DFS)4.5走迷宫(BFS)错误！未定义书签。 错误！未定义书签 错误！未定义书签 错误！未定义书签 错误！未定义书签 错误！未定义书签结论205 软件测试 致 谢 20参考文献 错误！未定义书签。摘要迷宫是一种充满复杂通道的建筑物，很难找到从其内部到达入口或从入 口到达中心的道路。比喻复杂艰深的问题或难以捉摸的局面。迷宫从古代就 有人在研究并加以运用，它拥有千百年的历史，迷宫问题向来经典，有很多 人都在研究它，以至于有很多迷宫相关的算法，要走迷宫首先要形成迷宫， 这里采用常见的DFS深度优先搜索算法生成迷宫这样生成的迷宫是迷宫各 个点所组成图的一个生成树，所以可以保证迷宫中任意两点都有路径到达， 并且迷宫中没有环路(完美迷宫)，迷宫拆完墙以后就构成了一条通道，当然 为了下一次生成同样的迷宫，迷宫的拆墙信息以及各个单元格的四面墙的信 息都应该以文件的形式进行保存，以便下一次读取恢复原来迷宫的形态，走 迷宫采用DFS、BFS两种搜索方法，DFS的特点：纵深进行到底，采用STL 的stack存储数据。BFS的特点：宽度进行到底，采用STL的queue储存 数据。调用gui函数并且采用Sleep()的方式将程序挂起，计算机一边运算一 边动态展现，最终到达出口。关键词：DFS BFS GUI stack queue1 前言1.1 问题的提出为了更深刻地理解DFS、BFS搜索算法的搜索原理，为了了解gui相关 函数的调用，为了将所学算法运用于生活中实际中我们编写了这个走迷宫程 序。1.2 任务与分析1. 基于图形用户界面GUI的标准“Windows”应用程序。2. 贴图表现：迷宫(二维平面图案，包括墙壁和通道)。3. 动画表现：动态表现迷宫生成和求解的每一步变化过程。4. 迷宫大小：N和M (用户输入)，允许范围：1030,缺省值：15和15。5. 迷宫格子：N*M大小的迷宫由N*M个格子构成，每个格子有东、南、西、北四堵 墙，迷宫生成过程就是对所有格子进行一次遍历拆墙过程，遍历完成后迷 宫就生成了。6. 迷宫入口和出口：分别在第0行和第N-1行上随机选择。7. 算法要求：(1)生成的迷宫有解；(2)禁用递归程序；(3)保证每次生成的迷 宫不同，这要求生成时用随机函数(时间种子)。8. 迷宫类型：生成的是完美迷宫即单连通迷宫，迷宫中不存在环，且不存在不可访问区域，迷宫中任意两点之间有且仅有唯一的路径(参考：图的生成树)。9. 文件存储：(1) 将生成的迷宫保存在文件中(用文本文件，迷宫数据的存储格式自定)；(2) 迷宫求解时，从相应的迷宫文件中读取迷宫数据，然后求解。10. 界面设计要求1) 操作流程简便合理，操作界面美观自然，符合用户一般操作习惯。2) 界面简洁美观，配色和谐，比例合适，符合大多数人的审美趣向。11. 菜单设置“使用说明”，介绍本软件的开发者、特色、各项功能及使用。2.软件总体设计2.1 开发工具开发工具：visual C+ 6.0 （企业版） 优点：模块加载速度快，界面简单易操作 开发环境： windows 7 （旗舰版 x64 系统） 运行环境 windows 95 以上2.2 系统框图（ 1 ）系统组成框图WinMain （函数入口）DFS走迷宫BFS走迷宫DFS （拆墙）图 2-12）系统流程图：2.3 模块功能软件开发方式：SDKGUI 函数模块：1) DrawWhi teGround (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);/绘制单元方格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* visi ted, Wall * wall, int col);/ 判断该单元 格是否有没有被访问的相邻单元格并且周围没有墙可以访问8) Replace (HDC hdc, int x, int y, int z, int k);/ 拆墙(用白色划线替换红色划 线)文件操作模块：1) Wri teDocume nt (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-2 迷宫拆墙界面图 3-3 DFS 走迷宫界面图 3-4 BFS 走迷宫界面4 功能详细设计GUI 函数模块：1)/将整个客户区绘制为白色void DrawWhiteGround (HDC hdc)int col, row;st d:ifs tream 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(hdc, l, t, r, b); DeleteObject(hbrush);3) /画单元格，后面四个参数依次为左上坐标和右下坐标 void DrawRect (HDC hdc, int l, int t, int r, int b)MoveToEx (hdc, l, t, NULL); /将起始点移动到(l, t)LineTo (hdc, r, t);LineTo (hdc, r, b);LineTo (hdc, l, b);LineTo (hdc, l,t);4) /用绿色画刷画移动目标void DrawCell (HDC hdc, int l, int t, int r, int b) HBRUSH hbrush;hbrush=CreateSolidBrush(RGB(0,255,0); / 绿色画刷 SelectObject(hdc,hbrush);Rectangle(hdc,l, t, r, b); DeleteObject (hbrush);5) /在客户区绘满单元格void DrawGamePlace(HDC hdc, int col, int row) int i,j;HPEN hpen1; hpen1=CreatePen(PS_SOLID,1,RGB(255,0,0);/绘制游戏区域方格线(红色)SelectObject(hdc,hpen1);for (i=0; irow; i+)for(j=0; j-1)&!visitedy*col+x-1|(x+1-1&!visited(y-1)*col+x|y+1-1)&!visitedy*col+x-1&wally*col+x.wall_l=0|(x+1-1&!visited(y-1)*col+x&wally*col+x.wall_t=0|y+1H&!visited(y+ 1)*col+x&wally*col+x.wall_b=0)return true;return false;8) /拆墙(用白色划线替换红色划线)void Replace (HDC hdc, int x, int y, int z, int k)HPEN hpen;hpen = CreatePen(PS_SOLID, 1, RGB(255,255,