数据结构与算法课程设计报告-哈工大-应用不相交集合生成随即迷宫 - 图文

哈尔滨工业大学课程设计报告

Harbin Institute of Technology

数据结构与算法 课程设计报告

(2014年度秋季学期)

设计题目： 应用不相交集合 生成随机迷宫

小组成员： 院 系： 软件学院 指导教师： 设计时间： 2014.11.14~2015.1.6

哈尔滨工业大学

1

哈尔滨工业大学课程设计报告

项目任务分工及进度计划表

任务编号 1 2 3 4 5 6 确定题目 撰写文档系统目的部分 撰写文档系统功能需求部分 查阅不相交集合数据结构资料 查阅先深度搜索资料 撰写文档系统关键技术部分 具体内容 执行人 预计 开始时间 预计 完成时间 实际 完成情况 已完成 已完成 已完成 已完成 已完成 已完成 周方恬 2014.11.14 2014.11.14 周方恬 2014.11.14 2014.11.14 周方恬 2014.11.14 2014.11.14 赵杰 2014.11.14 2014.11.17 张丹丹 2014.11.14 2014.11.17 李晓璇 2014.11.14 2014.11.17 里程碑1：完成选题，完成文档中“需求分析”部分的撰写，具有一定的设计/开发思路。 时间节点：第10周 周五 7 8 9 10 11 12 13 不相交集合数据结构算法构思 构造随机迷宫算法构思 先深度搜索寻找路径算法构思 画出迷宫和路径算法构思 绘制构造随机迷宫算法流程图 绘制寻找路径算法流程图 绘制画出迷宫和路径算法流程图 赵杰 2014.11.17 2014.11.21 已完成 已完成 已完成 已完成 已完成 已完成 已完成 周方恬 2014.11.17 2014.11.21 李晓璇 2014.11.17 2014.11.21 张丹丹 2014.11.17 2014.11.21 周方恬 2014.11.17 2014.11.21 李晓璇 2014.11.17 2014.11.21 赵杰 2014.11.17 2014.11.21 里程碑2：确定项目整体设计思路，完成文档中“算法设计”部分的撰写。 时间节点：第11周 周五 14 15 16 17 构造随机迷宫部分代码开发 寻找路径部分代码开发 画出迷宫部分代码开发 画出路径部分代码开发 周方恬 2014.11.22 2014.12.25 李晓璇 2014.11.22 2014.12.25 张丹丹 2014.11.22 2014.12.25 赵杰 2014.11.22 2014.12.25 已完成 已完成 已完成 已完成 里程碑3：项目开发完成90%以上，文档中“算法实现”部分完成80%以上。 时间节点：第16周 周四 18 19 20 21 程序调试 分析程序复杂度及优缺点 完善文档 制作答辩PPT 周方恬 2014.12.26 李晓璇 2014.12.26 张丹丹 2014.12.26 赵杰 2014.12.26 2015.1.5 2015.1.5 2015.1.5 2015.1.5 已完成 未完成 未完成 未完成 里程碑4：开发任务全部完成，完成系统测试，文档撰写全部完成，答辩PPT全部完成。 时间节点：第18周 周一 22 23 24 25 打印文档 上传文档及PPT电子版 协助准备答辩 答辩 张丹丹 赵杰 李晓璇 周方恬 2015.1.6 2015.1.6 2015.1.6 2015.1.6 2015.1.6 2015.1.6 2015.1.6 2015.1.6 未完成 未完成 未完成 未完成 里程碑5：项目结题验收 时间节点：第18周 周二 2015-1-6

[每条任务的执行人只能是一个；如果多个人一起完成，请拆分任务，具体到人]

2

哈尔滨工业大学课程设计报告

目 录

任务分工及进度计划表 ...................................................................................................... 2 目 录................................................................................................................................... 3 1 需求分析........................................................................................................................... 4

1.1 系统目标................................................................................................................ 4 1.2 系统功能需求........................................................................................................ 4 1.3 系统关键技术........................................................................................................ 4 2 算法设计........................................................................................................................... 6

2.1 系统整体思路........................................................................................................ 6 2.2 关键数据结构设计................................................................................................ 6 2.3 构建随机迷宫功能相关算法................................................................................ 6

2.3.1算法基本思想.............................................................................................. 6 2.3.2算法流程图.................................................................................................. 6 2.4 寻找迷宫路径功能相关算法................................................................................ 7

2.4.1算法基本思想.............................................................................................. 7 2.4.2算法流程图.................................................................................................. 7 2.5 画出迷宫和路径功能相关算法............................................................................ 7

2.5.1算法基本思想.............................................................................................. 7 2.5.2算法流程图.................................................................................................. 8

3 算法实现........................................................................................................................... 9

3.1 开发语言及工具.................................................................................................... 9 3.2 算法关键代码........................................................................................................ 9

3.2.1 构造随机迷宫算法关键代码..................................................................... 9 3.2.2 寻找迷宫路径算法关键代码..................................................................... 9

3.2.3 图形界面算法关键代码.............................................................................9

3.3 主要功能界面........................................................................................................ 9

3.3.1 XXX功能运行结果 .................................................................................... 9 3.3.2 XXX功能运行结果 .................................................................................... 9 3.3.3 XXX功能运行结果 .................................................................................... 9

4 算法分析......................................................................................................................... 10

4.1算法复杂性分析................................................................................................... 10 4.2算法优缺点分析................................................................................................... 10 5 项目总结......................................................................................................................... 11

3

哈尔滨工业大学课程设计报告

1 需求分析

1.1 系统目标

使用不相交集合数据结构来构造一个N×N的从左上角到右下角只有一条路径的随机迷宫，然后在这一迷宫上执行深度优先搜索。利用不相交集合应用数组进行物理存储，用先深度搜索找到最短路径，记录下最短路径，最后将随机生成的迷宫和相应的路径显示出来。

1.2 系统功能需求

（1）构建随机迷宫功能

提示用户输入迷宫大小N，随机生成一个N×N的迷宫。 （2）寻找迷宫路径功能

每次生成迷宫后，自动开始寻找迷宫路径，将此次随机生成的迷宫的最短路径记录下来。

（3）画出迷宫和路径功能

当用户选择生成迷宫时，将生成的随机迷宫用图形方式画出，用线段来表示迷宫中的墙。当用户选择显示路径时，将所计算出的最短路径画出，用每个方格的中心点连成的线段来表示路径。

1.3 系统关键技术

（1）不相交集合数据结构的设计和实现

不相交即对于任意两个集合A和B，A∩B=￠。不相交集合常可以表示为树，此时两个不相交的集合的并很容易实现，如图1-1所示。不相交集合常可用来根据等价关系对集合进行等价划分。

图1-1 不相交集合的树的表示

（2）构建随机迷宫算法

给定一个N×N的方格，初始时每个方格的四面都是墙，如图1-2所示，期中的S是迷宫的开始处，F是迷宫的结束处。N×N迷宫的N2个方格0，1，??，N2-1初始时每个方格自己成为一个等价类，即{0}，{1}，??，{N2-1}。生成随机迷宫的方法是随机选择一个内部墙（连接两个相邻方格的墙），如果该内部墙关联的两个相邻的方格属于不同的等价类就将该墙除去，在除去该墙的同时将这两个等价类合并。直到所有的方格都在一个等价类中，就完成了随机迷宫的生成。

4