欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页  >  IT编程

第六节 Go数据结构之集合

程序员文章站 2022-05-30 09:33:38
一、什么是集合 集合就是不同对象的无序聚集。那么链表和集合有什么关系呢?我们来变个魔术。如下图是各种颜色组成的链表: 下面我们一步步把链表变成集合。 第一步砍去链接 第二步去掉重复 第三步放到一个框里摇一摇就成集合了 可以看出集合有这些特点: 无序:链表去掉链接,就是去掉元素间有序状态。 不重复:去 ......

一、什么是集合

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

下面我们一步步把链表变成集合。
第一步砍去链接
第六节 Go数据结构之集合

第二步去掉重复
第六节 Go数据结构之集合

第三步放到一个框里摇一摇就成集合了
第六节 Go数据结构之集合

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

  • 无序:链表去掉链接,就是去掉元素间有序状态。
  • 不重复:去掉重复的玫红色。
    虽然说集合是一种数学概念,但在实际生活中无处不透露着集合。比如一个班级的学生是一个集合。班级里的男生又是一个集合。

二、集合的结构

第六节 Go数据结构之集合

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

三、接口说明及实现

第六节 Go数据结构之集合

1、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
    }

四、小结

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