Yanniyanni

集合

上次更新时间：4/6/2021, 6:10:35 PM 0

集合是一种无序且唯一的数据结构。

ES6 中有集合数据结构 - Set。

# 集合的实现

Collection 类的实现基于数组，数组用来存储数据。（使用 Set 可以直接使用对应方法）

# 抽象数据类型定义

  • ADT 集合
    • Data
      • 无逻辑关联的元素集合
    • Operation
      • add(): 添加元素
      • remove(): 移除元素
      • size(): 当前元素个数
      • union()：并集，将两个集合中的成员进行合并，得到一个新集合
      • intersect(): 交集，将两个集合中的成员进行合并，得到一个新集合。
      • difference(): 补集，属于一个集合而不属于另一个集合的成员组成的集合。
      • subset(): 传入集合是否当前集合的子集
      • show(): 显示集合中的成员
  • endADT
function Collection() {
    this.dataStore = []; 
    this.add = add; 
    this.remove = remove; 
    this.size = size; 
    this.union = union; 
    this.intersect = intersect; 
    this.difference = difference; 
    this.subset = subset; 
    this.show = show;
    this.contains = contains;
}
function add(data) { 
    if (this.dataStore.indexOf(data) < 0) { 
        this.dataStore.push(data); 
        return true; 
    } else { 
        return false; 
    } 
}
function remove(data) { 
    var pos = this.dataStore.indexOf(data); 
    if (pos > -1) { 
        this.dataStore.splice(pos,1); 
        return true; 
    } else { 
        return false; 
    } 
}
function show() { 
    return this.dataStore;
}
function contains(data) { 
    if (this.dataStore.indexOf(data) > -1) { 
        return true; 
    } else { 
        return false; 
    } 
}
function union(set) { 
    var tempSet = new Collection(); 
    for (var i = 0; i < this.dataStore.length; ++i) { 
        tempSet.add(this.dataStore[i]); 
    }
    for (var i = 0; i < set.dataStore.length; ++i) {
        if (!tempSet.contains(set.dataStore[i])) { 
            tempSet.dataStore.push(set.dataStore[i]); 
        } 
    }
    return tempSet; 
}
function intersect(set) { 
    var tempSet = new Collection(); 
    for (var i = 0; i < this.dataStore.length; ++i) { 
        if (set.contains(this.dataStore[i])) { 
            tempSet.add(this.dataStore[i]); 
        } 
    }
    return tempSet; 
}
function subset(set) { 
    if (this.size() > set.size()) {
        return false; 
    } else { 
        for (var member in this.dataStore) { 
            if (!set.contains(member)) { 
                return false;
            } 
        } 
    }
    return true; 
}
function size() { 
    return this.dataStore.length; 
}
function difference(set) { 
    var tempSet = new Collection(); 
    for (var i = 0; i < this.dataStore.length; ++i) { 
        if (!set.contains(this.dataStore[i])) { 
            tempSet.add(this.dataStore[i]); 
        } 
    }
    return tempSet; 
}

var s1 = new Collection();
s1.add("A")
s1.add("B")
s1.add("C")
s1.add("D")
var s2 = new Collection();
s2.add("A")
s2.add("B")
s2.add("E")
s2.add("F")

s1.union(s2).dataStore; // [A, B, C, D, E, F]
s1.intersect(s2).dataStore; // [A, B]
s1.difference(s2).dataStore; // [C, D]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99

# 集合的应用

集合的基本操作有：并集、交集、补集。

上次更新时间: 4/6/2021, 6:10:35 PM

← 字典 →