课程设计报告范例.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(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);while(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 &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*;elseoutfile ;五、 物理实现及结果1. 主要数据结构的物理设计 (1) 迷宫方格的设计Boxstruct Box int Ancestor; /记录方格(树）的祖先 int position; /记录方格的位置（从左到右 从上到下 依次编号为0、1、2. int Status4; /记录上下左右四面墙的开启闭合状态 1为开,0为闭; (3) 存储迷宫路径的MyMaze由于MyMaze集合采用的是线性结构。且在该集合上没有Box的增加和删除(不考虑结点的动态变化)，所以适合于采用连续存储结构，即设计一个由Box对象组成的容器vector MyMaze (3) 存储迷宫信息的类 Mazeclass 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); /查看两个房间是否连通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) /合并统一祖先的方格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 结束 图 3 搜索路径函数的流程图 (3) 可视化界面的实现略（采用visual c+ MFC）。2. 实现结果(1) 图形界面的可视化效果图4 应用程序初始界面 随机建立迷宫并且搜索路径时的结果图5 迷宫游戏时的图形界面六、结果分析从模拟的结果可以看出，本课程设计最终设计获得的系统已经可以完成随即迷宫的创建和最佳路径搜索的基本工作。并且设计了菜单，对话框等可视化图形界面，使其更具有实用性，方便人们操作。且在本次设计中对并查集合并算法做了比较分析，并设计了一种基于加权规则的合并算法，该算法的时间复杂性为O(n)。七、结论本次课程设计完成了随机迷宫建立及最佳路径搜索基本工作过程，并给出了相应的图形化界面模拟演示。通过本次课程设计，训练了对集合、栈等基本数据结构的应用和掌握。并对面向对象的程序设计技术（C+）和图形界面的程序设计技术有了一定的锻炼。也自学了一部分visual C+中windows MFC 的知识，对visual c+集成开发环境有了更好的认识八、附录（主要功能函数代码） /*函数功能：初始化迷宫信息 函数参数：int m,int n 构建迷宫的行与列 函数返回值：无 */Maze:Maze(int m=2,int n=3):row(m),MyMaze(m*n)int s=MyMaze.size();if(s=0)return;for(int i=0;is;i+)MyMazei.Ancestor=-1; /-1代表每个迷宫初始集合信息MyMazei.position=i; /房间位置 一直保持不可改变for(int j=0;j=0)s=Find_Ancestor(MyMazes,n);return s; /*函数功能：查看两个房间是否连通 函数参数：Box b1,Box b2 两个特定的方格 函数返回值：若两个房间连通返回true 若两个房间不连通返回false; */bool Maze:isConnect(Box& m,Box& n)int p,q;if(Find_Ancestor(m,p)=Find_Ancestor(n,q)if(Find_Ancestor(m,p)=-1) /-1代表两房间不再任何集合中return false;elseif(p=q)return true; else return false;return false;/*函数功能：合并统一祖先的方格 函数参数：两个特定的方格 函数返回值：无 */void Maze:MergeBox(Box& m,Box& n)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; /*函数功能：构建随机迷宫 函数参数：无 函数返回值：无 */void Maze:CreateMaze()int s=MyMaze.size();if(s=0) return;int p,w;int pos;srand(time(0);while(1)p=rand()%s;w=rand()%4;switch(w)case 0:if(p%row)=(row-1)break;if(isConnect(MyMazep,MyMazep+1)break;MergeBox(MyMazep,MyMazep+1);MyMazep.Status0=1;MyMazep+1.Status2=1;break;case 1:if(s-p)=row)break;if(isConnect(MyMazep,MyMazep+row)break;MergeBox(MyMazep,MyMazep+row);MyMazep.Status1=1;MyMazep+row.Status3=1;break;case 2:if(p%row)=0)break;if(isConnect(MyMazep,MyMazep-1)break;MergeBox(MyMazep,MyMazep-1);MyMazep.Status2=1;MyMazep-1.Status0=1;break;case 3:if(prow)break;if(isConnect(MyMazep,MyMazep-row)break;MergeBox(MyMazep,MyMazep-row);MyMazep.Status3=1;MyMazep-row.Status1=1;break;if(Find_Ancestor(MyMaze0,pos)=(-1*s)break;/*函数功能：寻找迷宫路径 函数参数：Vector &BoxTeam 用来存储迷宫路径 函数返回值：无 */void Maze:Search_Path(vector& BoxTeam)int s=MyMaze.size();if(BoxTeam.size()=0)BoxTeam.push_back(MyMaze0);int i=0;while(i4)switch(i)case 0:if(BoxTeam.back().position=(s-1)break;if(BoxTeam.back().Statusi=1)BoxTeam.push_back(MyMazeBoxTeam.back().position+1);BoxTeam.back().Status2=0;Search_Path(BoxTeam);break;case 1:if(BoxTeam.back().position=(s-1)break;if(BoxTeam.back().Statusi=1)BoxTeam.push_back(MyMazeBoxTeam.back().position+row);BoxTeam.back().Status3=0;Search_Path(BoxTeam);break;case 2:if(BoxTeam.back().position=(s-1)break;if(BoxTeam.back().Statusi=1)BoxTeam.push_back(MyMazeBoxTeam.back().position-1);BoxTeam.back().Status0=0;Search_Path(BoxTeam);break;case 3:if(BoxTeam.back().position=(s-1)break;if(BoxTeam.back().Statusi=1)BoxTeam.push_back(MyMazeBoxTeam.back().position-row);BoxTeam.back().Status1=0;Search_Path(BoxTeam);break;if(BoxTeam.back().position=(s-1)break;i+;if(i=4)BoxTeam.pop_back(); /*函数功能：查看小方格是否在路径中 函数参数：vector& BoxTeam保存迷宫信息，Box &m表示特定小方格 函数返回值：若该方格在路径中则返回true 否则返回false */bool Maze:Path_In(vector& BoxTeam,Box& m)vector:iterator iter=BoxTeam.begin();while(iter!=BoxTeam.end()if(iter-position=m.position)return true;iter+;return false; /*函数功能：在文件中模拟迷宫 函数参数：const string &str 表示存储迷宫信息文件名 函数返回值：无 */void Maze:DisPlay(const string &str)vector:iterator iter=MyMaze.begin();int s=MyMaze.size();int count=0;ofstream outfile;outfile.open(str.c_str(),ofstream:app);if(!outfile)coutERROR!Con not Input the Maze MSG into the File:strendl;return;count=0;iter=MyMaze.begin();outfileMazeendl;while(iter!=(MyMaze.begin()+row)if(iter=MyMaze.begin()outfile _ ;+iter;continue;outfile_ ;+iter;outfileendlStatus1=0)outfile_;elseif(MyMaze.end()-iter)=row)outfile_;elseoutfileStatus0=0)outfile|;elseoutfile=s)outfileend