重庆网站哪里好,天津建设公司网站,宿州网站公司,郑州公司建网站集合我们高中都学过吧#xff1f;
最重要的几个特点#xff1a;元素不能重复、各个元素之间没有关系、没有顺序
集合内的元素可以是单元素或者是集合。
对集合的操作#xff1a;交集并集差集等#xff0c;还有对自身的加减等。
需要频繁的加减元素#xff0c;所以顺序…集合我们高中都学过吧
最重要的几个特点元素不能重复、各个元素之间没有关系、没有顺序
集合内的元素可以是单元素或者是集合。
对集合的操作交集并集差集等还有对自身的加减等。
需要频繁的加减元素所以顺序存储效率较低但是我们还是说一下是怎么实现的 用01向量表示集合因为现实中任何一个有穷集合都能对应到一个0、1、2.....n这么一个序列中。所以可以对应过来每位的01代表这个元素存在与否即可。
链接存储表示使用有序链表来实现虽然集合是无序的但是我们的链表可以是有序的。可以按升序排列。而链表理论上可以无限增加所以链表可以表示无限集。
下面我们来实现一下
我们定义一个节点
typedef int ElemType;
typedef struct SetNode{//节点定义ElemType data;//数据struct SetNode * link;
}*LinkedSet//集合定义
然后要实现那些操作了首先想插入吧我们对于一个新元素查找集合中是否存在存在就不插入不存在就插入到查找失败位置。
删除也简单查找存在就删除。 我们说两个集合的操作
求两个集合的并
两个链表都是升序。把他们去重合并即可。
其实和链表归并的merge过程是一样的只是相等的时候插入一个两个指针都向后走就行了。
我就再写一遍吧。
void UnionSet(LinkedSet A,LinkedSet B,LinkedSet C)
{SetNode *paA-link,*pbB-link,*pcC;while(pa pb)//都不为空{if(pa-datapb-data)//相等插一次两边向后{pc-linknew SetNode;pc-datapa-data;papa-link;pbpb-link;}else if(pa-datapb-data)//插小的小的向后{pc-linknew SetNode;pc-datapa-data;papa-link;}else{pc-linknew SetNode;pc-datapb-data;pbpb-link;}pcpc-link;//注意指针}if(pa)ppa;//剩下的接上else ppb;//只执行一个while(p)//依次复制{pc-linknew SetNode;pc-datap-data;pcpc-link;pp-link;}pc-linkNULL;
}
求两个集合的交更简单还是这三种情况谁小谁向后相等才插入。
void UnionSet(LinkedSet A,LinkedSet B,LinkedSet C)
{SetNode *paA-link,*pbB-link,*pcC;while(pa pb)//都不为空{if(pa-datapb-data)//相等插一次两边向后{pc-linknew SetNode;pc-datapa-data;papa-link;pbpb-link;pcpc-link;//注意指针,就不是每次都向后了只有插入才向后}else if(pa-datapb-data)//小的向后{papa-link;}else{pbpb-link;}}pc-linkNULL;
}
求两个集合的差高中可能没学这个概念其实就是A-B就是B中的元素A都不能有了。
运算你可以把B元素全过一遍A中有就去掉但是这样时间复杂度太高了我们需要O(AB)而不是O(A*B)
因为有序很好操作还是两个指针
如果AB相同都向后移。
或者B小B就向后移。
如果A小说明B中不含这个元素我们把它复制到结果链表里。 思想还行实在懒得写了有时间再说吧。
