《课程设计报告范例》由会员分享，可在线阅读，更多相关《课程设计报告范例（24页珍藏版）》请在金锄头文库上搜索。
1、Harbin Institute of Technology课程设计报告课程名称： 数据结构与算法课程设计设计题目：应用不相交集合生成随机迷宫院 系： 实验学院计算机科学与技术系 班 级： 设 计 者： 学 号： 指导教师： 辛明影 设计时间： 2010 哈尔滨工业大学一、 题目分析 在本设计题目中，需要使用不相交集合数据结构(disjoint set data structure)来构造一个N*N 的从左上角到右下角只有一条路径的随机迷宫，然后在这一迷宫上执行深度优先搜索，找寻出唯一路径走出迷宫。分析题目，如要构建只有一条路径的随机迷宫，则要用到不相交集合即并查集，构建迷宫是本题目的重中之重
2、，寻找迷宫路径只需深搜即可，最后做好图形界面，以图形方式画出迷宫 即可完成题目的基本要求。二、 总体设计基于上面的题目分析，此处可以总结出Maze的设计共包含如下四个部分：1 不相交集合的设计与实现(Box&Maze类)2 构建随机迷宫（Create_Maze( )）3 寻找迷宫路径（Search_Path( )）4 将迷宫路径用图形方式画出(Display_Maze( )。其中Box用于模拟迷宫方格，完成对不相交集合的模拟；Maze：Create_()用于随机化选择方向“拆墙”，从而构建随机迷宫；在构建好随机迷宫的基础上利用Maze：Search_Path( )寻找最佳走出迷宫路径，Maze
3、：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
4、方格；Box方格形成的迷宫结构；现就每种数据给出详细的分析。（一） 各个Box之间的关系是对等的，形成一种顺序结构。所以此处需构建线性表结构。由于我们不考虑Box的增加和较少，所以在这一线性表上不需要定义增加和删除的操作，只需要定义查询(定位)的操作，这是因为需要定位某个Box其ADT可定义为：ADT Box 数据之间的逻辑结构为线性结构； 基本操作： Box Locate(int i); /定位第i个Sensor （二） Box集上形成的迷宫出路Maze_Path结构是一种栈结构。，需在这一栈结构上定义如下基本操作：进栈，出栈。其ADT定义为：ADT Maze_Path 数据之间的逻辑结构为
5、栈结构； 基本操作： Maze_push( ); /进栈 Maze_pop(); /出栈 四、 算法设计迷宫设计的基本工作流程如下图所示： 开始 初始化迷宫信息迷宫的建立 搜索最佳路径 以图形方式显示迷宫 结束图2 Maze的基本工作流程从该图可以看出基本算法主要包括迷宫初始化建立、最佳路径搜索和迷宫信息图形化三个方面，下面我们依次进行分析：1迷宫初始化建立的算法的设计迷宫初始化建立最主要的就是并查集的实现其基本思想就是集合用树结构（父链）来表示，令集合的元素对应数组的下标，而相应的元素值表示其父结点所对应的数组单元下标。其基本操作包括“并”：把其中一株当成另一株的子树。“包含”：求元素所在的
6、树根。其“并”的核心算法如下：改进并操作的规则，将结点少的并入结点多的；相应存储结构也要提供支持以加权规则压缩高度。void Union(int A,int B,MFSET C) if(CA.countCB.count) /* |B|A| *CB.father=A; /* 并入A */CA.count+=CB.count;else /*|A|B|*/CA.father=B; /* 并入B */CB.count+=CA.count;2、最佳路径搜索搜索在已经建立好的迷宫上完成，其算法的核心部分为：:Search_Path(BoxTeam)BoxTeam.push_back(MyMaze);whi
7、le(i4)switch(i) if(BoxTeam.back().position=(s-1)break;if(BoxTeam.back().Statusi=1)BoxTeam.push_back();BoxTeam.back().Status=0;Search_Path(BoxTeam);break;i+;if(i=4)BoxTeam.pop_back(); 3迷宫信息图形化在该系统中，主要完成如下三个部分的可视化：建立迷宫之前的方格集合。“破墙”之后建立的随机迷宫搜索最佳路径之后，将路径显示在迷宫之中。迷宫显示由函数Display（） 完成，显示初始迷宫时参数只需const string
8、 &str，显示具有走出路径的迷宫时参数有两个 一个是const string &str 及存放的迷宫路径 vector,下面是 Display（）的核心算法。void Maze:DisPlay(const string &str,vector& v)iter=MyMaze.begin();while(iter!=MyMaze.end()if(iter-Status1=0)outfile_; /同理将“_”换成”|”elseif(MyMaze.end()-iter)=row)outfile_; /同理将“_”换成”|”elseif(Path_In(v,*iter)outfile*;elseou
9、tfile ;五、 物理实现及结果1. 主要数据结构的物理设计 (1) 迷宫方格的设计Boxstruct Box int Ancestor; /记录方格(树）的祖先 int position; /记录方格的位置（从左到右 从上到下 依次编号为0、1、2. int Status4; /记录上下左右四面墙的开启闭合状态 1为开,0为闭; (3) 存储迷宫路径的MyMaze由于MyMaze集合采用的是线性结构。且在该集合上没有Box的增加和删除(不考虑结点的动态变化)，所以适合于采用连续存储结构，即设计一个由Box对象组成的容器vector MyMaze (3) 存储迷宫信息的类 Mazeclass
10、 Mazepublic:Maze(int m,int n);void CreateMaze(); /构建迷宫void Search_Path(vector& v); /寻找迷宫路径void DisPlay(const string &s); /输出迷宫void DisPlay(const string &s, vector& v); /输出带路径的迷宫private:vector MyMaze; /存储迷宫int row; /存储每行房间数bool Path_In(vector& v,Box& m); /查询迷宫中房间是否在迷宫路径中bool isConnect(Box& m,Box& n);
11、 /查看两个房间是否连通int Find_Ancestor(Box& m,int& n); /查找集合并保留祖宗的位置void MergeBox(Box& m,Box& n); /合并房间以生成路径;。2. 核心算法的物理实现(1)并查集的实现：求方格的祖先 及方格合并int Maze:Find_Ancestor(Box& m,int& n) /寻找方格所在的集合及祖先所在的位置int s=m.Ancestor;n=m.position;if(s=0)s=Find_Ancestor(MyMazes,n);return s; void Maze:MergeBox(Box& m,Box& n) /
12、合并统一祖先的方格int s1,s2,p1,p2;s1=Find_Ancestor(m,p1);s2=Find_Ancestor(n,p2);if(s1=s2)MyMazep1.Ancestor+=MyMazep2.Ancestor;MyMazep2.Ancestor=m.position;elseMyMazep2.Ancestor+=MyMazep1.Ancestor;MyMazep1.Ancestor=n.position;(2) 最佳路径的搜索算法的实现开始BoxTeam.size()=0 yesBoxTeam.push_back(MyMaze0);Noi=?i=1 i=2 i=3 i=0将方格下面紧邻的方格加入路径，并封掉此墙将方格左面紧邻的方格加入路径，并封掉此墙将方格上面紧邻的方格加入路径，并封掉此墙将方格右面紧邻的方格加入路径，并封掉此墙i=4? YesBoxTeam.pop_back() No 结束
