淘豆网
下载此文档放大查看缩小查看   1/24
0/100
您的浏览器不支持进度条
更多>>该用户其他文档
下载所得到的文件列表
课程设计报告范例.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的基本工作流程
从该图可以看出基本算法主要包括迷宫初始化建立、最佳路径搜索和迷宫信息图形化三个方面,下面我们依次进行分析:
1.迷宫初始化建立的算法的设计
迷宫初始化建立最主要的就是并查集的实现
其基本思想就是集合用树结构(父链)来表示,令集合的元素对应数组的下标,而相应的元素值表示其父结点所对应的数组单元下标。其基本操作包括“并”:把其中一株当成另一株的子树。“包含”:求元素所在的树根。其“并”的核心算法如下:改进并操作的规则,将结点少的并入结点多的;相应存储结构也要提供支持——以加权规则压缩高度。
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)
{
BoxTeam.push_back(MyMaze[]);
while(i<4)
{
switch(i)
if(BoxTeam.back().position==(s-1))
break;
if(BoxTeam.back().Status[i]==1)
{
BoxTeam.push_back();
BoxTeam.back().Status[]=0;
Search_Path(BoxTeam);
}
break;
i++;
}
if(i==4)
BoxTeam.pop_back();
};
3.迷宫信息图形化
在该系统中,主要完成如下三个部分的可视化:
·建立迷宫之前的方格集合。
·“破墙”之后建立的随机迷宫
·搜索最佳路径之后,将路径显示在迷宫之中。
迷宫显示由函数Display() 完成,显示初始迷宫时参数只需const string &str,显示具有走出路径的迷宫时参数有两个一个是const string &str 及存放的迷宫路径 vector<Box>,下面是 Display()的核心算法。
void Maze::DisPlay(const string &str,vector<Box>& v)
{
iter=MyMaze.begin();
while(iter!=MyMaze.end())
{
if(iter->Status[1]==0)
outfile<<"_"; //同理将“_”换成”|”
else
{
if((MyMaze.end()-iter)<=row)
outfile<<'_'; //同理将“_”换成”|”
else
{
if(Path_In(v,*iter))
outfile<<'*';
else
outfile<<' ';
}
}
五、物理实现及结果
1. 主要数据结构的物理设计
(1) 迷宫方格的设计Box
struct Box{
int Ancestor; //记录方格(树)的祖先
int position; //记录方格的位置(从左到右从上到下依次编号为0、1、2...
int Status[4]; //记录 内容来自淘豆网www.taodocs.com转载请标明出处.
更多>>相关文档
文档信息
最近更新
文档标签