一、什么是集合
集合就是不同对象的无序聚集。那么链表和集合有什么关系呢？我们来变个魔术。如下图是各种颜色组成的链表：
下面我们一步步把链表变成集合。
第一步砍去链接
第二步去掉重复
第三步放到一个框里摇一摇就成集合了
可以看出集合有这些特点：
- 无序：链表去掉链接，就是去掉元素间有序状态。
- 不重复：去掉重复的玫红色。
虽然说集合是一种数学概念，但在实际生活中无处不透露着集合。比如一个班级的学生是一个集合。班级里的男生又是一个集合。
二、集合的结构
大卫哥这里为了简化概念的描述，继续用单链表来表示集合，但是在对集合做计算的时候单链表并不合适，数据量大的时候它的弊端就会显现，在讲到后面的数据结构和算法的时候，我们再回头来完善前面讲的数据接口的实现。
三、接口说明及实现
2、Init
初始化集合，本质是初始化链表。
func (set *Set) Init(match ...MatchFun) {
lst := new(List)
(*set).list = lst
if len(match) == 0 {
lst.Init()
} else {
lst.Init(match[0])
}
}
要比较集合中的元素，我们得传入一个比较函数，这里的match是我们的自定义类型MatchFun，大家可以查看代码里的定义。
2、Insert
把元素放入集合中。
func (set *Set) Insert(data Object) bool {
if (!set.IsMember(data)) {
return (*set).list.Append(data)
}
return false
}
3、IsEmpty
是否是空集合。
func (set *Set) IsMember(data Object) bool {
return (*set).list.IsMember(data);
}
4、IsMember
是否是集合元素。
func (set *Set) IsMember(data Object) bool {
return (*set).list.IsMember(data);
}
5、Remove
删除指定集合元素。
func (set *Set) Remove(data Object) bool {
return (*set).list.Remove(data)
}
6、Union
并集计算。
func (set *Set) Union(set1 *Set) *Set {
if (set1 == nil) {
return nil
}
nSet := new(Set)
nSet.Init((*((*set).list)).myMatch)
if (set.IsEmpty() && set1.IsEmpty()) {
return nSet
}
for i := uint64(0); i < set.getSize(); i++ {
nSet.Insert(set.getAt(i))
}
var data Object
for i := uint64(0); i < set1.getSize(); i++ {
data = set1.getAt(i)
if (!nSet.IsMember(data)) {
nSet.Insert(data)
}
}
return nSet
}
计算set和set1的并集。
7、InterSection
计算交集。
func (set *Set) InterSection(set1 *Set) *Set {
if (set1 == nil) {
return nil
}
nSet := new(Set)
nSet.Init((*((*set).list)).myMatch)
if (set.IsEmpty() || set1.IsEmpty()) {
return nSet
}
fSet := set
sSet := set1
lenth := set.getSize()
if (set1.getSize() < lenth) {
fSet = set1
sSet = set
}
var data Object
for i := uint64(0) ; i < lenth; i++ {
data = fSet.getAt(i)
if (sSet.IsMember(data)) {
nSet.Insert(data)
}
}
return nSet
}
8、Difference
计算差集。
func (set *Set) Difference(set1 *Set) *Set {
if (set1 == nil) {
return nil
}
nSet := new(Set)
nSet.Init((*((*set).list)).myMatch)
if (set.IsEmpty()) {
return nSet
}
var data Object
for i := uint64(0); i < set.getSize(); i++ {
data = set.getAt(i)
if (!set1.IsMember(data)) {
nSet.Insert(data)
}
}
return nSet
}
返回的集合是属于set，但不属于set1的集合。
9、IsSubSet
func (set *Set) IsSubSet(subSet *Set) bool {
if (set == nil) {
return false
}
if (subSet == nil) {
return true
}
for i := uint64(0); i < subSet.getSize(); i++ {
if (!(set.IsMember(subSet.getAt(i)))) {
return false
}
}
return true
}
确认subSet是否是set的子集。
10、Equals
func (set *Set) Equals(set1 *Set) bool {
if (set == nil || set1 == nil) {
return false
}
if (set.IsEmpty() && set1.IsEmpty()) {
return true
}
nSet := set.InterSection(set1)
return (set.getSize() == nSet.getSize())
}
判断set和set1中集合元素是否一样。
11、访问集合元素
因为集合是没有顺序的，所以没法用序号来访问集合元素（虽然这里是用单链表实现）。这里我们用迭代器的方式来实现元素的访问。首先我们定义一个迭代器的接口。
(1) Iterator
type Iterator interface{
HasNext() bool
Next() Object
}
(2) SetIterator
type SetIterator struct {
index uint64
set *Set
}
因为Iterator是接口，没法保存状态，所以我们得定义一个类型来保存每次访问的游标。这里的游标是序号。
(3) GetIterator
返回一个实现了Iterator接口的对象。
func (set *Set) GetIterator() *SetIterator {
iterator := new(SetIterator)
(*iterator).index = 0
(*iterator).set = set
return iterator
}
(4) HasNext
是否有其他元素没访问到？
func (iterator *SetIterator) HasNext() bool {
set := (*iterator).set
index := (*iterator).index
return (index < set.getSize())
}
这是Iterator中HasNext方法的实现。
(5) Next
获取其他元素。
func (iterator *SetIterator) Next() Object {
set := (*iterator).set
index := (*iterator).index
if (index < set.getSize()) {
data := set.getAt(index)
(*iterator).index++
return data
}
return nil
}
四、小结
集合在概率中有很多应用，这里我们仅仅是用单链表简单的实现了集合，在大量数据下，计算效率很低。随着学习的深入，我们会优化这些数据接口的实现。
有疑问加站长微信联系（非本文作者）
