第六节 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 }
四、小结
集合在概率中有很多应用,这里我们仅仅是用单链表简单的实现了集合,在大量数据下,计算效率很低。随着学习的深入,我们会优化这些数据接口的实现。
代码下载
上一篇: 宋末三杰是谁 他们为什么会被称为宋末三杰
下一篇: 使用js做动态时钟