迷宫的生成与路由.doc

精品文档 I欢迎下载 数据结构课程设计报告撰写要求数据结构课程设计报告撰写要求 一 纸张与页面要求 1 采用国际标准 A4 型打印纸或复印纸 纵向打印 2 封页和页面按照下面模板书写 正文为 小四宋体 1 5 倍行距 3 图表及图表标题按照模板中的表示书写 二 课设报告书的内容应包括以下各个部分 按照以下顺序装订 1 封页 见课设模版 2 任务书 学生教师均要签字 信息填写完整 3 目录 4 正文一般应包括以下内容 1 题目介绍和功能要求 或描述 课程设计任务的详细描述 注意不能直接抄任务书 将内容做更详细的具体的分析与描述 2 系统功能模块结构图 绘制系统功能结构框图及主要模块的功能说明 3 使用的数据结构的描述 数据结构设计及用法说明 4 涉及到的函数的描述 5 主要算法描述 程序流程图 6 给出程序测试 运行的结果 设计多组数据加以描述 包括输入数据和输出结果 7 课程设计的总结及体会 8 参考文献 格式要求 1 作者 等 书名 出版地 出版社 出版年 5 附录 程序清单 应带有必要的注释 精品文档 II欢迎下载 沈阳航空航天大学 课课 程程 设设 计计 报报 告告 课程设计名称 数据结构课程设计数据结构课程设计 课程设计题目 迷宫的生成与路由 院 系 计算机学院 专 业 计算机科学与技术 班 级 学 号 姓 名 指导教师 精品文档 I欢迎下载I欢迎下载I欢迎下载I欢迎下载 目目 录录 1 1 题目介绍和功能要求题目介绍和功能要求 1 1 1 1 题目介绍 1 1 2 功能介绍 1 2 2 系统功能模块结构图系统功能模块结构图 2 2 2 1 系统功能结构框图 2 2 2 系统主要模块的功能说明 错误 未定义书签 错误 未定义书签 3 3 使用的数据结构的描述使用的数据结构的描述 3 3 3 1 数据结构设计 4 3 2 数据结构用法说明 4 4 4 函数的描述函数的描述 5 5 4 1 主要函数设计 6 4 2 主要函数流程图 6 5 5 程序测试和运行的结果程序测试和运行的结果 1111 5 1 程序测试 11 5 2 运行结果 13 参考文献参考文献 1 10 0 附附 录 关键部分程序清单 录 关键部分程序清单 1 11 1 精品文档 1欢迎下载1欢迎下载1欢迎下载1欢迎下载 1 题目介绍和功能要求 1 11 1 题目介绍题目介绍 设计算法生成一个 N M N 行 M 列 的迷宫 并完成迷宫的组织和存储 实现 两种不同的迷宫路由算法 广度搜索 深度优先搜索 要求 1 N 和 M 是用户可配置的 缺省值为 50 和 50 2 迷宫的入口和出口分别在第 0 行和第 N 1 行上 随机选择 3 生成的迷宫要求是连通的 4 实现图像化界面 选作 1 21 2 功能要求功能要求 1 迷宫用二维数组表示 2 rand 函数随机确定入口和出口 使用真随机数使得每次随机的结果 不同 3 入口和出口间的路径是连通的 使用数据结构的并查集来表示连通性 4 使用数据结构的两种搜索方式 深度和广度优先搜索来确定入口和出 口间的路径 精品文档 2欢迎下载2欢迎下载2欢迎下载2欢迎下载 2 系统功能模块结构图 2 12 1 系统功能结构框图系统功能结构框图 图图 2 12 1 系统功能结构框图系统功能结构框图 2 22 2 系统主要模块的功能说明系统主要模块的功能说明 1 初始化迷宫模块 Inint 函数用来初始化迷宫 使用二维数组来表示迷宫 假设迷宫 是用一个个封闭的小格子组成的 每个格子的四周是封闭的 首先随机生成入口 和出口的位置 2 随机化生成迷宫路径模块 并查集 数据结构 1 并查集可以用来表示元素之间的集合关系 即这些元素是 不是属于哪个集合 通俗理解是 若两个元素是属于统一集合 就将这两个元素并在一起 2 存储结构上 用树结构模拟 一开始 每个元素自己构成一个集合 所以自己构成一棵树 然后 若有两个元素并成一个集合 则将这两个元素所在的树 合并成一棵树 具体实现的 话 就是将一棵树的根看成是另一棵树根的新根 3 并查集的作用是可以统计并判定两个元 素是否属于统一集合 初始化迷宫模块 随机化生成迷 宫路径模块 广度优先搜索 模块 深度优先搜索模 块 形象化显示迷宫 模块 开始 结束 精品文档 3欢迎下载3欢迎下载3欢迎下载3欢迎下载 利用并查集实现入口和出口的连通 find 函数和 unite 函数 初始化迷宫的 每个元素都是一个独立的集合 随机化选择一个数组元素 再随机选择一个方向 使其与相邻的元素放入同一集合 直到入口和出口处于同一个集合 3 深度优先搜索模块 Bfs 函数利用队列从入口开始找到一条路径抵达出口 4 深度优先搜索模块 Dfs 函数利用递归从入口开始找到一条路径抵达出口 5 形象化显示迷宫模块 迷宫数组中任意相邻的元素如果属于同一集合 则之间是连通的 否则不连 通 并标注出入口和出口的位置 3 使用的数据结构的描述 3 13 1 数据结构设计数据结构设计 并查集 并查集可以用来表示元素之间的集合关系 即这些元素是不是属于哪个集合 通俗理解是 若两个元素是属于统一集合 就将这两个元素并在一起 存储结构上 用树结构模拟 一开始 每个元素自己构成一个集合 所以自己构成一棵树 然后 若有两个元素并成一个集合 则将这两个元素所在的树 合并成一棵树 具体实现的 话 就是将一棵树的根看成是另一棵树根的新根 并查集的作用是可以统计并判定两个元素是否属于统一集合 广度优先搜索 1 从队列头取出一个结点 检查它按照扩展规则是否能够 精品文档 4欢迎下载4欢迎下载4欢迎下载4欢迎下载 扩展 如果能则产生一个新节点 2 检查新生成的结点 看它是否已在队列中存在 如果新节点已在队列中 就 放弃此节点 然后回到第 1 步 否则 加入队尾 3 检查新节点是否为目标结点 如果是则搜索成功 程序结束 如果不是 回 到第 1 步 再从队列头取出结点进行扩展 4 当需要给出解的路径时 则要保存每个节点的来源 也就是它是从哪个结点 扩展来的 深度优先搜索 初始化所有顶点均未被访问过 选择初始点后 递归调用以 下步骤 1 访问搜索到的未被访问的邻接点 2 将此顶点的 visited 数组元素值置 1 3 搜索该顶点的违背访问的邻接点 若该邻接点存在 则从此邻接点开始进 行同样的访问和搜索 3 23 2 数据结构用法说明数据结构用法说明 并查集 首先将所有的迷宫元素处理成独立的集合 father i i 当选择将 两个元素连通时 即将两个元素处于同一集合下 具体做法是将一棵树的根看成 是另一棵树根的新根 假设元素 i 的树根是 b 元素 j 的树根是 h 则将 father b h 即将两个 元素放在 了同一集合里 也就是两个元素的树根相同 广度优先搜索 搜索时用到了队列 广度优先搜索的结果是最优的 也就是 从入口到出口的最短的路径 因为要知道具体的路径 所以需要标记每个入队列 的元素的来源 这样就能从出口返回到入口 深度优先搜索 搜索时用到了栈 递归操作是深度搜索的关键 标记的添加 与删除是非常重要的 我们需要存储遍历的路径 每当我们深入一层递归时 我 们需要将坐标入栈 每当递归回退时 表示这个位置不合适 我们将出栈 最后 当我们搜索到出口时 将栈输出即为遍历路径 精品文档 5欢迎下载5欢迎下载5欢迎下载5欢迎下载 4 函数的描述 4 14 1 主要函数设计主要函数设计 1 inint 函数 作用 按照规定尺寸申请二维数组表示迷宫 并将每个数组元素设置为独 立的集合 用并查集表示 规定每个元素与四周相邻的元素是不连通的 用 arry state 表示 当为 1 表示连通 0 时表示不连通 2 void maze 函数 作用 随机生成迷宫 构造路径从入口到出口是连通的 按并查集来说就 是将入口和出口以及二者间的路径元素都处于同一个集合 也就是有着相同的树 根 3 void bfs 函数 作用 广度优先搜索从入口遍历至出口 并记录具体路径 4 void dfs 函数 作用 深度优先搜索从入口遍历至出口 并记录具体路径 精品文档 6欢迎下载6欢迎下载6欢迎下载6欢迎下载 5 void finalprint 函数 作用 按照遍历路径扫描二维数组 形象化表示迷宫 4 2 主要函数流程图 Inint 图图 4 2 14 2 1 初始化迷宫函数流程初始化迷宫函数流程图图 开始 输入迷宫尺 寸 随机选择入口 和出口 申请二维数组 并将所有数组 元素设置为独 立的集合 将任意两个相邻的 数组元素设置为不 连通 结束 精品文档 7欢迎下载7欢迎下载7欢迎下载7欢迎下载 VoidVoid mazemaze 否 是 图图 4 2 24 2 2 随机生成连通函数流程图随机生成连通函数流程图 开始 入口和出口 是否连通 随机选择一 个数组元素 从上述元素的 四周随机选择 一个方向 将这两个元素连通 起来 结束 精品文档 8欢迎下载8欢迎下载8欢迎下载8欢迎下载 Void bfs 函数 是 否 图图 4 2 34 2 3 广度优先遍历迷宫函数流程图广度优先遍历迷宫函数流程图 开始 将入口坐标入队 列 取队头元素 将与队头元素相 邻的四个方向的 元素入队列 并 记录父节点坐标 判断是否 是出口 结束 精品文档 9欢迎下载9欢迎下载9欢迎下载9欢迎下载 Void dfs 函数 是 否 是 否 图图 4 2 44 2 4 深度优先遍历迷宫函数流程图深度优先遍历迷宫函数流程图 开始 以迷宫入口作为递归入 口 并依此为初始点 判断初始点的相邻 四个方向是否都查 看完毕 判断此点是 否为出口 以此点作为递归 的新入口 并标 记 结束 递归回退 返回 上一个初始点 精品文档 10欢迎下载10欢迎下载10欢迎下载10欢迎下载 5 程序测试和运行的结果 5 15 1 程序测试程序测试 由用户自行规定迷宫的尺寸由用户自行规定迷宫的尺寸 截图截图 5 1 15 1 1 迷宫的初始化 迷宫的初始化 精品文档 11欢迎下载11欢迎下载11欢迎下载11欢迎下载 迷宫的随机形成迷宫的随机形成 截图截图 5 1 25 1 2 迷宫的形成 迷宫的形成 精品文档 12欢迎下载12欢迎下载12欢迎下载12欢迎下载 5 25 2 运行结果运行结果 迷宫的广度优先搜索迷宫的广度优先搜索 截图截图 5 2 15 2 1 迷宫的广度搜索 迷宫的广度搜索 迷宫的深度优先搜索迷宫的深度优先搜索 图图 5 2 25 2 2 迷宫的深度优先搜索 迷宫的深度优先搜索 精品文档 13欢迎下载13欢迎下载13欢迎下载13欢迎下载 输出迷宫输出迷宫 图图 5 2 35 2 3 输出迷宫 输出迷宫 参考文献 精品文档 14欢迎下载14欢迎下载14欢迎下载14欢迎下载 1 高富平 张楚 电子商务法 M 北京 北京大学出版社 2002 2 谭浩强著 C 程序设计 第三版 北京 清华大学出版社 2005 3 数据结构 C 语言版 严蔚敏 吴伟明编著 北京 清华大学出版社 2007 精品文档 15欢迎下载15欢迎下载15欢迎下载15欢迎下载 附 录 关键部分程序清单 include include include include struct node int state 4 0123 表示上下左右四扇门的闭合情况 0 表示关闭 1 表示打 开 arry 5000 struct stu int x y int loc q 10000 stack 1000 cun 100000 bor 1000 int n m en ex father 5000 front rear vis 10000 10000 der 4 2 0 1 0 1 1 0 1 0 mark 1000 1000 top xian 1000 1000 将二维数组转化为一 维数组 二维坐标 a b 转化为一维坐标 a m b 一维坐标 x 转化为二维坐标 x m x m 二维数组的行和列从 0 开始 int find int x if father x x return x else father x find father x void unite int hx int hy int i j i find hx j find hy father i j void inint for int i 0 i n i for int j 0 j m j 精品文档 16欢迎下载16欢迎下载16欢迎下载16欢迎下载 father i m j i m j printf d father i m j printf n for int k 0 k m n k arry k state 0 arry k state 1 arry k state 2 arry k state 3 0 所有的门都是闭合的 void nprint int i j printf for i 0 i m i if i 10 printf d i else printf d i printf n printf for i 0 i m i if i en printf else printf printf n for i 0 i n i if i 10 printf d i else printf d i printf for j 0 j m j if arry i m j state 3 1 printf else 精品文档 17欢迎下载17欢迎下载17欢迎下载17欢迎下载 printf printf n printf for j 0 j m j if i n 1 else if arry i m j state 1 1 printf else printf printf n void maze 随机生成迷宫 int row col num nrow ncol clock t start time start time clock 计时函数 数据类型是 clock t 长整型 毫秒 在 time h 文件中 syx while find en find n 1 m ex 入口和出口不连通 row rand n 随机找出一个房间 col rand m num rand 4 switch num case 0 与上相通 nrow row 1 if row 0 continue else if find nrow m col find row m col 判断是否 连通 如果连通 说明曾经操作过 否则 相连通 精品文档 18欢迎下载18欢迎下载18欢迎下载18欢迎下载 arry row m col state 0 arry nrow m col state 1 1 将两个相邻方格 的相对应的墙拆掉 unite nrow m col row m col break case 1 与下相通 nrow row 1 if row n 1 continue else if find nrow m col find row m col arry row m col state 1 arry nrow m col state 0 1 unite nrow m col row m col break case 2 与左相通 ncol col 1 if col 0 continue else if find row m col find row m ncol arry row m col state 2 arry row m ncol state 3 1 unite row m col row m ncol break case 3 与右相通 ncol col 1 if col m 1 精品文档 19欢迎下载19欢迎下载19欢迎下载19欢迎下载 continue else if find row m col find row m ncol arry row m col state 3 arry row m ncol state 2 1 unite row m col row m ncol break void bfs xy 为入口的坐标 int i j k px py hx hy while front rear px q front x py q front y if px n 1 for i 0 i 0 q rear y hy vis hx hy 1 q rear loc px m py rear if px hx q rear y hy vis hx hy 1 q rear loc px m py rear if hy py q rear y hy vis hx hy 1 q rear loc px m py rear if hy py q rear y hy vis hx hy 1 q rear loc px m py rear front void initmaze int i j k printf for i 0 i m i if i 10 printf d i else printf d i printf n 精品文档 21欢迎下载21欢迎下载21欢迎下载21欢迎下载 printf for i 0 i m i printf printf n for i 0 i n i if i 10 printf d i else printf d i printf for j 0 j m j printf printf n printf for j 0 j m j printf printf n void printbfs int j rx ry k printf 打印广度优先搜索的存储顺序 n for j 0 j 0 k 精品文档 22欢迎下载22欢迎下载22欢迎下载22欢迎下载 if q k x rx printf 根据广度搜索记录父级地址打印从入口到出口的路径如下 n for int t count 1 t 0 t printf d d n stack t x stack t y void dfs int px int py int i j k hx hy cun top x px cun top y py top if px n 1i top i bor i x cun i x bor i y cun i y bor i x 1 return for i 0 i 0 dfs hx hy mark hx hy 0 top if px hx dfs hx hy mark hx hy 0 精品文档 23欢迎下载23欢迎下载23欢迎下载23欢迎下载 top if hy py dfs hx hy mark hx hy 0 top if hy py dfs hx hy mark hx hy 0 top mark px py 0 void finalprint int i j printf for i 0 i m i if i 10 printf d i else printf d i printf n printf for i 0 i m i if i en printf else printf 精品文档 24欢迎下载24欢迎下载24欢迎下载24欢迎下载 printf n for i 0 i n i if i 10 printf d i else printf d i printf for j 0 j m j if arry i m j state 3 1 if xian i j 1 printf else printf else if xian i j 1 printf else printf printf n printf for j 0 j m j if i n 1 else if arry i m j state 1 1 printf else printf printf n int main 精品文档 25欢迎下载25欢迎下载25欢迎下载25欢迎下载 int j i char ch srand int time NULL srand 初始化随机种子 rand 产生随机数 time 0 clock t start time start time clock 计时函数 数据类型是 clock t 长整型 毫秒 在 time h 文件中 syx printf 是否输入迷宫的尺寸 输入请选择 A 否则输入 B 默认值为 50 50 n scanf c if ch A printf 请输入迷宫的尺寸 n scanf d d if ch B n 50 m 50 inint initmaze en rand m ex rand m arry en state 0 1 arry n 1 m ex state 1 1 入口和出口的相对应的门被打开 printf 随机选择的入口和出口坐标为 n printf 入口 0 printf d en printf printf 出口 printf d n