數據結構-集合

SegmentFault 發布于2019-08-23 12:15 / 1051人閱讀

摘要：集合是一種包含不同元素的數據結構集合中的元素稱為成員集合的兩個最重要的特性是首先集合中的成員是無序的其次集合中不允許相同成員存在集合在計算機科學中扮演了非常重要的角色然而在很多編程語言中并不把集合當成一種數據類型當你想要創建一個數據結構用來

集合(set)是一種包含不同元素的數據結構. 集合中的元素稱為成員. 集合的兩個最重要的特性是: 首先, 集合中的成員是無序的; 其次, 集合中不允許相同成員存在. 集合在計算機科學中扮演了非常重要的角色, 然而在很多編程語言中, 并不把集合當成一種數據類型. 當你想要創建一個數據結構, 用來保存一些獨一無二的元素時, 比如一段文本中用到的單詞, 集合就變得非常有用. 
在ES6中已加入集合Set

集合的定義、操作和屬性

集合是由一組無序但彼此之間又有一定相關性的成員構成的, 每個成員在集合中只能出現一次.

集合的定義

下面是一些使用集合必須了解的定義.

不包含任何成員的集合稱為 空集_, _全集 則是包含一切可能成員的集合.

如果兩個集合的成員完全相同, 則稱兩個集合相等.

如果一個集合中所有的成員都屬于另外一個集合, 則前一集合稱為后一集合的子集.

對集合的操作

對集合的基本操作有下面幾種:

并集 : 將兩個集合中的成員進行合并, 得到一個新的集合.

交集 : 兩個集合中共同存在的成員組成一個新的集合.

補集 : 屬于一個集合而不屬于另一個集合的成員組成的集合.

Set類的實現

Set類的實現基于數組, 數組用來存儲數據.

window.log = console.log.bind(console)

class Set {
    constructor() {
        this._dataStore = [];
    }
    add(data) {
        if(!this._dataStore.includes(data)) {
            this._dataStore.push(data);
            return true;
        };
        return false;
    }
    remove(data) {
        const pos = this._dataStore.indexOf(data);
        if(pos > -1) {
            this._dataStore.splice(pos, 1);
            return true;
        };
        return false;
    }
    show() {
        return this._dataStore;
    }
};

add()方法: 因為集合中不能包含相同的元素, 所以, 使用add()方法將數據存儲到數組前, 先要確保數組中不存在該數據. 我們使用indexof()檢查新加入的元素在數組是否存在. 如果找到, 該方法返回該元素在數組中的位置; 如果沒找到, 該方法返回-1. 如果數組中還未包含該元素, add()方法將新加入的元素保存在數組中并返回true; 反之返回false. 將add()方法的返回值定義為布爾類型, 可以明確告訴我們是否將一個元素成功加入到了集合中. 這里使用ES6中的includes()也是可以的.

remove()方法和add()方法的工作原理類似. 首先檢查待刪除元素是否在數組中, 如何在, 則使用數組的splice()方法刪除該元素并返回true; 反之返回false, 表示集合中不存在這樣的一個元素.

show()顯示集合中的成員.
測試程序:

const s = new Set();
s.add("a");
s.add("b");
s.add("c");
s.add("d");
s.add("e");
s.add("f");
log(s.show());
if(s.add("f")) {
    log("f: 添加成功")
} else {
    log("已存在f, 添加失敗")
}

輸出:

(6)?["a", "b", "c", "d", "e", "f"]
已存在f, 添加失敗

更多集合操作

定義union()、subset()和difference()方法會更有意思. union()方法執行并集操作, 將兩個集合合并成一個. 該方法首先將第一個集合里的成員悉數加入一個臨時集合, 然后檢查第二個集合中的成員, 看它們是否也同時屬于第一個集合. 如果屬于, 則跳過該成員, 否則就將該成員加入臨時集合.

在定義union()方法前, 先定一個輔助方法contains(), 該方法檢查一個成員是否屬于該集合.

contains(data) {
    return this._dataStore.includes(data);
}
// 并集
union(set) {
    const tempSet = new Set();
    this._dataStore.forEach(i => {
        tempSet.add(i);
    });
    set._dataStore.forEach(i => {
        if(!tempSet.contains(i)) {
            tempSet._dataStore.push(i)
        }
    });

    return tempSet;
}

執行程序:

const s = new Set();
s.add("a");
s.add("b");
s.add("c");
s.add("d");
s.add("e");
s.add("f");
log(s.show());

const s1 = new Set();
s1.add("a");
s1.add("f");
s1.add("g");

let res = new Set();
res = s.union(s1);
log(res.show());

//輸出:
// (6)?["a", "b", "c", "d", "e", "f"]
// (7)?["a", "b", "c", "d", "e", "f", "g"]

使用intersect()方法求兩個集合的交集. 該方法定義起來相對簡單. 每當發現第一個集合的成員也屬于第二個集合時, 便將該成員加入一個心機和, 這個心機和即為方法的返回值.

// 交集
intersect(set) {
    const tempSet = new Set();
    this._dataStore.forEach(i => {
        if(set.contains(i)) {
            tempSet.add(i)
        };
    });

    return tempSet;
}

下一個要定義的操作是subset()判斷子集. subset()方法首先要確定該集合的長度是否小于帶比較集合.
如果該集合比帶比較集合還要大, 那么該集合肯定不會是待比較集合的一個子集.
當集合的長度小于待比較集合時, 再判斷該集合內的成員是否都屬于待比較集合. 如果有任意一個成員不屬于待比較集合, 則返回false, 程序終止. 如果一直比較完該集合的最后一個元素, 所有元素都屬于待比較集合, 那么該集合就是待比較集合的一個子集, 該方法返回true.
在判斷每個元素是否屬于待比較集合前, 該方法先使用size()方法對比兩個集合的大小.

size() {
    return this._dataStore.length;
}
subSet(set) {
    if(this.size() > set.size()) {
        return false;
    };
    for(let i = 0; i < this._dataStore.length; i++) {
        if(!set.contains(this._dataStore[i])) {
            return false;
        };
    };
    return true;
}

最后一個操作是difference()補集, 該方法返回一個新集合, 該集合包含的是那些屬于第一個集合但不屬于第二個集合的成員.

difference(set) {
    const tempSet = new Set();
    this._dataStore.forEach(i => {
        if(!set.contains(i)) {
            tempSet.add(i);
        };
    });

    return tempSet;
}

云服務器 GPU云服務器數據集合 java集合結構 js 集合數據結構 js存儲集合數據

文章版權歸作者所有，未經允許請勿轉載,若此文章存在違規行為，您可以聯系管理員刪除。

轉載請注明本文地址：http://specialneedsforspecialkids.com/yun/98182.html

學習JavaScript數據結構與算法（三）：集合

摘要：至于這三個的具體概念，可以看圖中集合的實現首先，創建一個構造函數。前端路漫漫，且行且歌的前端樂園原文鏈接寒假前端學習學習數據結構與算法三集合本系列的第一篇文章: 學習JavaScript數據結構與算法（一），棧與隊列第二篇文章：學習JavaScript數據結構與算法（二）：鏈表第三篇文章：學習JavaScript數據結構與算法（三）：集合第四篇文章：學習JavaScript數據結構與...

BDEEFE 2019-08-22 10:59 評論0 收藏0
【前端數據結構基礎】集合

摘要：前言集合是一種包含不同元素的數據結構。二構造集合數據結構我們將使用實現集合結構，各部分功能使用注釋說明。參考資料數據結構與算法描述第章集合由于書上的源代碼出現了錯誤，因此代碼根據實際運行結果做了相應修改。前言集合是一種包含不同元素的數據結構。集合最重要的兩個特性是：首先，集合中的成員是無序的；其次，集合中不允許相同成員存在。一、關于集合集合的定義我們必須要了解以下關于集合的定...

wawor4827 2019-08-22 17:58 評論0 收藏0
Java? 教程（集合介紹）

集合介紹本節介紹Java集合框架，在這里，你將了解集合是什么以及它們如何使你的工作更輕松、程序更好，你將了解構成Java集合框架的核心元素 — 接口、實現、聚合操作和算法。集合 — 有時稱為容器 — 只是一個將多個元素組合到一個單元中的對象，集合用于存儲、檢索、操作和傳遞聚合數據。通常，它們代表形成自然組的數據項，例如撲克牌（卡片集合）、郵件文件夾（信件集合）或電話目錄（名稱到電話號碼的映射）...

taoszu 2019-08-16 14:34 評論0 收藏0
JavaScript的數據結構與算法（五） —— 集合

摘要：集合是由一組無序且唯一的項組成的。這個數據結構使用了與有限集合相同的數學概念，但應用在計算機科學的數據結構中。在數學中，集合也有并集交集差集等基本操作。集合的基本性質有一條集合中元素是不重復的。集合是由一組無序且唯一的項組成的。這個數據結構使用了與有限集合相同的數學概念，但應用在計算機科學的數據結構中。在數學中，集合也有并集、交集、差集等基本操作。集合的基本性質有一條: 集合中元素...

wangshijun 2019-08-21 17:13 評論0 收藏0
學習javascript數據結構(三)——集合

摘要：前言總括本文講解了數據結構中的集合概念，并使用實現了集合。原文博客地址學習數據結構三集合知乎專欄簡書專題前端進擊者知乎前端進擊者簡書博主博客地址的個人博客人生多風雨，何處無險阻。敬請期待學習數據結構四散列表前言總括：本文講解了數據結構中的[集合]概念，并使用javascript實現了集合。原文博客地址：學習javascript數據結構(三)——集合知乎專欄&&簡書專題：前端...

alphahans 2019-08-22 10:45 評論0 收藏0