课程设计报告范例.doc

Harbin Institute of Technology
课程设计报告
课程名称: 数据结构与算法课程设计
设计题目:应用不相交集合生成随机迷宫
院系: 实验学院计算机科学与技术系
班级:
设计者:
学号:
指导教师: 辛明影
设计时间: 2010
哈尔滨工业大学
题目分析
在本设计题目中,需要使用不相交集合数据结构(disjoint set data structure)来构造一个N*N 的从左上角到右下角只有一条路径的随机迷宫,然后在这一迷宫上执行深度优先搜索,找寻出唯一路径走出迷宫。分析题目,如要构建只有一条路径的随机迷宫,则要用到不相交集合即并查集,构建迷宫是本题目的重中之重,寻找迷宫路径只需深搜即可,最后做好图形界面,以图形方式画出迷宫即可完成题目的基本要求。
二、总体设计
基于上面的题目分析,此处可以总结出Maze的设计共包含如下四个部分:
1 不相交集合的设计与实现(Box&Maze类)
2 构建随机迷宫(Create_Maze( ))
3 寻找迷宫路径(Search_Path( ))
4 将迷宫路径用图形方式画出(Display_Maze( ))。
其中Box用于模拟迷宫方格,完成对不相交集合的模拟;Maze::Create_()用于随机化选择方向“拆墙”,从而构建随机迷宫;在构建好随机迷宫的基础上利用Maze::Search_Path( )寻找最佳走出迷宫路径,Maze::Display_Maze()将迷宫及迷宫路径以图形的方式画出
Maze::maze(int m,int n)
Create_Maze( )
Search_Path
( )
Display_Maze( )
Path_In()
MergeBox()
Is_Connect( )
Find_Ancestor ()
图1 构建随即迷宫及找寻路径的基本过程
其中Find_Ancestor( )用于寻找方格所在的集合及祖先所在的位置
Is_Connect( ) 查看两个房格是否连通
MergeBox( ) 合并统一祖先的方格
Path_In( ) 查看小方格是否在路径中
三、数据结构设计
针对这一迷宫系统,需要管理的数据主要有:Box方格;Box方格形成的迷宫结构;现就每种数据给出详细的分析。
各个Box之间的关系是对等的,形成一种顺序结构。
所以此处需构建线性表结构。
由于我们不考虑Box的增加和较少,所以在这一线性表上不需要定义增加和删除的操作,只需要定义查询(定位)的操作,这是因为需要定位某个Box
其ADT可定义为:
ADT Box
{
数据之间的逻辑结构为线性结构;
基本操作:
Box Locate(int i); //定位第i个Sensor
}
Box集上形成的迷宫出路Maze_Path结构是一种栈结构。,需在这一栈结构上定义如下基本操作:进栈,出栈。
其ADT定义为:
ADT Maze_Path
{
数据之间的逻辑结构为栈结构;
基本操作:
Maze_push( ); //进栈
Maze_pop(); //出栈
}
四、算法设计
迷宫设计的基本工作流程如下图所示:
开始
初始化迷宫信息
迷宫的建立
搜索最佳路径
以图形方式显示迷宫
结束
图2 Maze的基本工作流程
从该图可以看出基本算法主要包括迷宫初始化建立、最佳路径搜索和迷宫信息图形化三个方面,下面我们依次进行分析:

迷宫初始化建立最主要的就是并查集的实现
其基本思想就是集合用树结构(父链)来表示,令集合的元素对应数组的下标,而相应的元素值表示其父结点所对应的数组单元下标。其基本操作包括“并”:把其中一株当成另一株的子树。“包含”:求元素所在的树根。其“并”的核心算法如下:改进并操作的规则,将结点少的并入结点多的;相应存储结构也要提供支持——以加权规则压缩高度。
void Union(int A,int B,MFSET C)
{
if(C[A].count>C[B].count) /* |B|<|A| *
{
C[B].father=A; /* 并入A */
C[A].count+=C[B].count;
}
else{ /*|A|<|B|*/
C[A].father=B; /* 并入B */
C[B].count+=C[A].count;
}
}
2.、最佳路径搜索
搜索在已经建立好的迷宫上完成,其算法的核心部分为:
:Search_Path(BoxTeam)
{
(MyMaze[]);
while(i