不相交集合课程设计报告+源码.docx
- 文档编号:13896677
- 上传时间:2023-06-19
- 格式:DOCX
- 页数:23
- 大小:227.04KB
不相交集合课程设计报告+源码.docx
《不相交集合课程设计报告+源码.docx》由会员分享,可在线阅读,更多相关《不相交集合课程设计报告+源码.docx(23页珍藏版)》请在冰点文库上搜索。
不相交集合课程设计报告+源码
不相交集合
一目的
通过课程设计,培养综合运用数据结构及有关编程语言的基本知识去解决一些实际问题的实际本领,并且加深对本门课程知识的理解。
在做课程设计的过程中,可以培养以下的能力:
查阅资料:
了解了课程设计的题目之及其要求,就需要通过自己去搜集资料来明白自己应该从何入手,所以需要从大量的资料中来寻找灵感;方案的选择:
树立既考虑技术上的先进性和可能性,又考虑代码的实用性,通过合理的选择,写出来一种符合要求并且可以扩展功能的算法;实际应用能力:
面对现实中的一些问题,通过对其进行分析,然后转化成计算机可以识别并且进行处理的数据,建立与计算机相一致的思维。
课程设计就是对自己学习的巩固和自己能力的提高,是自己的编程能力得到进一步的锻炼,为以后的毕业设计及以后的工作奠定了坚实的基础。
二需求分析
1、现实问题
题目:
亲戚(Relations)
或许你并不知道,你的某个朋友是你的亲戚。
他可能是你的曾祖父的外公的女婿的外甥的表姐的孙子。
如果能得到完整的家谱,判断两个人是否亲戚应该是可行的,但如果两个人的最近公共祖先与他们相隔好几代,使得家谱十分庞大,那么检验亲戚关系实非人力所能及.在这种情况下,最好的帮手就是计算机。
为了将问题简化,你将得到一些亲戚关系的信息,如同Marry和Tom是亲戚,Tom和Ben是亲戚,等等。
从这些信息中,你可以推出Marry和Ben是亲戚。
请写一个程序,对于我们的关心的亲戚关系的提问,以最快的速度给出答案。
像这类的题目有很多,还有例如食物链、军舰的指挥官、路的连接等,对于这一类的问题,大都可以归结为集合的一些运算,判断两个元素是否属于一个集合,及合并两个不相交的集合。
2、不相交集合算法
不相交集合又称并查集:
(union-findsets)是一种简单的用途广泛的集合.并查集是若干个不相交集合,能够实现较快的合并和判断元素所在集合的操作,应用很多。
一般采取树形结构来存储并查集,在合并操作时可以利用树的节点树或者利用一个rank数组来存储集合的深度下界--启发式函数,在查找操作时进行路径压缩使后续的查找操作加速。
这样优化实现的并查集,空间复杂度为O(N),建立一个集合的时间复杂度为O
(1),N次合并M查找的时间复杂度为O(MAlpha(N)),这里Alpha是Ackerman函数的某个反函数,在很大的范围内这个函数的值可以看成是不大于4的,所以并查集的操作可以看作是线性的。
它支持以下三种操作:
-Union(Root1,Root2)//合并操作;把子集合Root2和子集合Root1合并.要求:
Root1和Root2互不相交,否则不执行操作.
-Find(x)//搜索操作;搜索单元素x所在的集合,并返回该集合的名字--根节点标示.
-make_Set(s)//构造函数。
将并查集中s个元素初始化为s个只有一个单元素的子集合.
-对于并查集来说,每个集合用一棵上树树表示。
图1上树集合A{1,2,3,5,7}图2上树集合B{4,6,8,9,10}
通过建立如图1和图2的上树,进而实现不相交集合。
在本次课程设计中,用数字为代表建立不相交集合,进而实现:
1.查询两个元素是否属于同一个不相交集合。
2.合并两个不相交集合。
在程序中,采用的是数组parent[],通过输入涉及的元素个数n以及元素与元素之间关系的个数m,来进行初始化,数组中的元素值就是其根。
然后根据m进行关系的输入,最后建立不相交集合。
根据根来区别不同的集合,并且进行合并。
三概要设计
不相交集合程序流程图
图3不相交集合程序流程图
四详细设计
1、main()函数
main()中采用switch()函数,因为其很适合有不同选择的函数。
再加上while()循环,就可以实现菜单选项。
通过输入k(在程序顶部声明为全局变量)来选择要是现实的功能。
然后输入x选择继续还是结束。
intmain()
{
intx=1;
while(x)
{
printf("**********不相交集合************\n");
printf("1.创建不相交集合.\n");
printf("2.查询两个元素是否属于同一个集合\n");
printf("3.输出某个根的集合.\n");
printf("4.合并两个不相交集合\n");
printf("5.退出\n");
printf("********************************\n");
printf("请输入你的选择:
");
scanf("%d",&k);
switch(k){
}
printf("\n0:
结束\n");
printf("\n1:
继续\n");
scanf("%d",&x);
}
return0;
}
2、初始化函数
定义全局变量n,m,k和数组parent[MAX],rank[MAX],对集合中的元素的根初始化为-1,。
深度初始化为0.
#include
#include
#defineMAX2001
intn,m,q,k=1;
intparent[MAX],rank[MAX];
voidmake_set(inti)
{
parent[i]=-1;
rank[i]=0;
}
3、找根节点函数
在这个函数中,通过递归parent[i]=find(parent[i]);来实现找根的功能,并且使不相交集合的整体深度降低,提高程序的效率。
本来时间复杂度是O(i),进行压缩后时间复杂度为O
(1)。
intfind(inti)
{
if(parent[i]!
=-1)
parent[i]=find(parent[i]);
if(parent[i]==-1)
returni;
else
returnparent[i];
}
4、元素集合的归属
根据输入的两个相关的元素进行创建不相交集合,并且通过判断两个元素是否是已经属于一个不相交集合,如果是,则找到其根,让相应深度较小的根指向相应深度较大的根,并对相应深度较大的根的深度进行增加。
voidunion_set(inti,intj)
{
introot1,root2;
root1=find(i);
root2=find(j);
if(root1!
=root2){
if(rank[root1]>rank[root2])
parent[root2]=root1;
else{
parent[root1]=root2;
if(rank[root1]==rank[root2])
++rank[root2];
}
}
}
5、创建不相交集合函数
通过输入涉及元素个数n及元素之间的关系数m,然后由for循环控制输入有关系的元素,进而创建不相交集合。
voidcj_set()
{
inti,a,b;
printf("请输入涉及元素的个数,和元素与元素有关系的个数,中间用空格隔开:
");
scanf("%d%d",&n,&m);
for(i=1;i<=n;++i)
make_set(i);
printf("请输入有关系的元素,中间用空格隔开:
");
for(i=1;i<=m;++i)
{
scanf("%d%d",&a,&b);
union_set(a,b);
}
}
6、打印相应根的集合元素
找数组中所有的元素的根为g的元素进行打印。
voidp_set(intn)
{
intg;
ints=1;
while(s<=n){
if(parent[s]<0)
printf("集合的根为%d\n",s);
s++;
}
printf("请输入一个根\n");
scanf("%d",&g);
printf("{");
for(s=1;s<=n;s++)
{
if(find(s)==g)
{
printf("%d",s);
}
}printf("}");
}
7、查询两个元素是否属于同一个集合
输入两个元素,找到两个元素的根,比较是否相等,若相等吗,则位于同一个集合中,否则不位于同一个集合。
voidc_set()
{
inti,c,d;
printf("请输入您要查询是否属于同一集合的元素的对数:
");
scanf("%d",&q);
for(i=1;i<=q;++i)
{
printf("请输入您要查询是否属于同一集合的元素,中间用空格隔开:
");
scanf("%d%d",&c,&d);
if(find(c)==find(d))
printf("元素%d和元素%d属于同一个集合\n",c,d);
else
printf("元素%d和元素%d不属于同一个集合\n",c,d);
}
}
8、合并两个不相交集合并打印合并后的集合
通过输入两个想要合并的不相交集合的根,来进行合并,并且输出合并后的集合元素。
voidhe_set(intn)
{
inty,z,s;
printf("请输入你想合并的集合的根,中间用空格隔开:
");
scanf("%d%d",&y,&z);
union_set(y,z);
printf("合并后的集合为:
");
printf("{");
for(s=1;s<=n;s++)
{
if(find(s)==find(y))
{
printf("%d",s);
}
}printf("}");
}
五调试分析
1、创建不相交集合
如下图所示,创建两个不相交集合A={1,2,3,5,7},B={4,6,8,9,10}。
图4不相交集合A和B
通过上图可以看出,共涉及元素n=10,元素之间的关系个数m=8,有关系的元素为1和5,2和5,7和5,3和2,6和10,8和10,9和10,4和8。
2、查询两个元素是否属于同一个集合
查询5对,即q=5,查询元素为1和7,1和3,2和8,2和9,3和4。
3、输出根为5的集合元素
输入根5,然后输出相应的集合元素。
4、合并两个集合,并且输出合并后的集合的元素
输入根5和根10,然后输出相应的集合元素。
六测试结果
1.创建不相交集合
创建两个不相交集合A={1,2,3,5,7},B={4,6,8,9,10}。
结果如下。
图5创建不相交集合成功
2、查询两个元素是否属于同一个集合
查询5对,即q=5,查询元素为1和7,1和3,2和8,2和9,3和4。
选择1继续,选择2.
图6选择查询两个元素是否属于同一个集合
图7查询结果
3、输出根为5的集合元素
输入根5,然后输出相应的集合元素。
图8输出根为5的集合元素
4、合并两个集合,并且输出合并后的集合的元素
输入根5和根10,然后输出相应的集合元素。
图9合并的结果
5、退出
图10退出
七用户使用说明
在此程序中,元素的代表为数字,通过输入涉及元素的个数和关系数,并且中间用空格隔开,然后把有关系的元素中间用空格进行输入,建立不相交集合。
此相交集合的初始化为大小为2000,如果超出这个大小,则需要重新定义数组parent数组的大小。
在查询时,需要输入查询的对数,输入要查询的元素时,中间用空格隔开。
在打印集合的元素时,会把根打印出来,根据跟来打印并且合并。
八课程设计总结
当刚刚领到自己课程设计的题目时,根本不知道如何入手,自己就去网络上面进行搜索,有了点眉目,但是还是有点迷迷糊糊的,不知道用什么来实现。
后来宋老师给我们门做了讲解,我才知道原来树状图还有上图这个分支,通过这个就可以很容易的实现集合,进而根据根来进行集合的合并,很容易实现。
学习了数据结构这门课程,对我的帮助很大,让我的编程思想有了进一步的提高,然后通过这一次的课程设计,让我的能力得到了实践和巩固。
对于现实中的问题,要通过分析思考进而转化为计算机所能理解的程序,这是一个很重要的过程,只要做好了这个连接,就很容易实现现实与计算机之间的联系。
在程序的调试过程中,总会有很多错误,然而错误并不可怕,可怕的是不知道错误在哪里,改了一个一个错误,最后程序运行成功,这是最棒的时候。
通过不断地编程,这样可以锻炼自己的能力,培养自己思维,接下类会继续努力。
附录:
源码
#include
#include
#defineMAX2001
intn,m,q,k=1;
intparent[MAX],rank[MAX];
voidmake_set(inti)
{
parent[i]=-1;
rank[i]=0;
}
intfind(inti)
{
if(parent[i]!
=-1)
parent[i]=find(parent[i]);
if(parent[i]==-1)//如果i结点还是只有根的树
returni;
else
returnparent[i];
}
voidunion_set(inti,intj)
{
introot1,root2;
root1=find(i);
root2=find(j);
if(root1!
=root2){
if(rank[root1]>rank[root2])
parent[root2]=root1;
else{
parent[root1]=root2;
if(rank[root1]==rank[root2])
++rank[root2];
}
}
}
voidcj_set()
{
inti,a,b;
printf("请输入涉及元素的个数,和元素与元素有关系的个数,中间用空格隔开:
");
scanf("%d%d",&n,&m);
for(i=1;i<=n;++i)
make_set(i);
printf("请输入有关系的元素,中间用空格隔开:
");
for(i=1;i<=m;++i)
{
scanf("%d%d",&a,&b);
union_set(a,b);
}
printf("不相交集合创建成功");
}
voidc_set()
{
inti,c,d;
printf("请输入您要查询是否属于同一集合的元素的对数:
");
scanf("%d",&q);
for(i=1;i<=q;++i)
{
printf("请输入您要查询是否属于同一集合的元素,中间用空格隔开:
");
scanf("%d%d",&c,&d);
if(find(c)==find(d))
printf("元素%d和元素%d属于同一个集合\n",c,d);
else
printf("元素%d和元素%d不属于同一个集合\n",c,d);
}
}
voidp_set(intn)
{
intg;
ints=1;
while(s<=n){
if(parent[s]<0)
printf("集合的根为%d\n",s);
s++;
}
printf("请输入一个根\n");
scanf("%d",&g);
printf("{");
for(s=1;s<=n;s++)
{
if(find(s)==g)
{
printf("%d",s);
}
}printf("}");
}
voidhe_set(intn)
{
inty,z,s;
printf("请输入你想合并的集合的根,中间用空格隔开:
");
scanf("%d%d",&y,&z);
union_set(y,z);
printf("合并后的集合为:
");
printf("{");
for(s=1;s<=n;s++)
{
if(find(s)==find(y))
{
printf("%d",s);
}
}printf("}");
}
intmain()
{
intx=1;
while(x)
{
printf("**********不相交集合************\n");
printf("1.创建不相交集合.\n");
printf("2.查询两个元素是否属于同一个集合\n");
printf("3.输出某个根的集合.\n");
printf("4.合并两个不相交集合\n");
printf("5.退出\n");
printf("********************************\n");
printf("请输入你的选择:
");
scanf("%d",&k);
switch(k){
case1:
cj_set();
break;
case2:
c_set();
break;
case3:
p_set(n);
break;
case4:
he_set(n);
break;
case5:
exit(0);
break;
default:
printf("请重新选择");
}
printf("\n0:
结束\n");
printf("\n1:
继续\n");
scanf("%d",&x);
}
return0;
}
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 相交 集合 课程设计 报告 源码