Go数据结构之集合

rhan-zz · · 3295 次点击 · · 开始浏览    
这是一个创建于 的文章,其中的信息可能已经有所发展或是发生改变。

一、什么是集合

集合就是不同对象的无序聚集。那么链表和集合有什么关系呢?我们来变个魔术。如下图是各种颜色组成的链表:

下面我们一步步把链表变成集合。

第一步砍去链接

第二步去掉重复

第三步放到一个框里摇一摇就成集合了

可以看出集合有这些特点:

  • 无序:链表去掉链接,就是去掉元素间有序状态。
  • 不重复:去掉重复的玫红色。

虽然说集合是一种数学概念,但在实际生活中无处不透露着集合。比如一个班级的学生是一个集合。班级里的男生又是一个集合。

二、集合的结构

大卫哥这里为了简化概念的描述,继续用单链表来表示集合,但是在对集合做计算的时候单链表并不合适,数据量大的时候它的弊端就会显现,在讲到后面的数据结构和算法的时候,我们再回头来完善前面讲的数据接口的实现。

三、接口说明及实现

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
}

四、小结
集合在概率中有很多应用,这里我们仅仅是用单链表简单的实现了集合,在大量数据下,计算效率很低。随着学习的深入,我们会优化这些数据接口的实现。

 

代码下载

入群交流(和以上内容无关):加入Go大咖交流群,或添加微信:muxilin131420 备注:入群;或加QQ群:977810755

3295 次点击  
加入收藏 微博
被以下专栏收入,发现更多相似内容
2 回复  |  直到 2017-12-11 03:32:46
暂无回复
添加一条新回复 (您需要 登录 后才能回复 没有账号 ?)
  • 请尽量让自己的回复能够对别人有帮助
  • 支持 Markdown 格式, **粗体**、~~删除线~~、`单行代码`
  • 支持 @ 本站用户;支持表情(输入 : 提示),见 Emoji cheat sheet
  • 图片支持拖拽、截图粘贴等方式上传