摘要:至于這三個的具體概念,可以看圖中集合的實現首先,創建一個構造函數。前端路漫漫,且行且歌的前端樂園原文鏈接寒假前端學習學習數據結構與算法三集合
</>復制代碼
本系列的第一篇文章: 學習JavaScript數據結構與算法(一),棧與隊列
第二篇文章:學習JavaScript數據結構與算法(二):鏈表
第三篇文章:學習JavaScript數據結構與算法(三):集合
第四篇文章:學習JavaScript數據結構與算法(四):二叉搜索樹
集合(Set)
說起集合,就想起剛進高中時,數學第一課講的就是集合。因此在學習集合這種數據結構時,倍感親切。
集合的基本性質有一條: 集合中元素是不重復的。因為這種性質,所以我們選用了對象來作為集合的容器,而非數組。
雖然數組也能做到所有不重復,但終究過于繁瑣,不如集合。
集合的基本操作有交集、并集、差集等。這兒我們介紹JavaScipt集合中交集、并集、差集的實現。至于這三個的具體概念,可以看圖:
首先,創建一個構造函數。
</>復制代碼
/**
* 集合的構造函數
*/
function Set() {
/**
* 集合元素的容器,以對象來表示
* @type {Object}
*/
var items = {};
}
集合需要有如下方法:
has(value): 檢測集合內是否有某個元素
add(value): 給集合內添加某個元素
remove(value): 移除集合中某個元素
clear(value): 清空集合
size(): 返回集合長度
values(): 返回集合轉換的數組
union(otherSet): 返回兩個集合的并集
intersection(otherSet): 返回兩個集合的交集
difference(otherSet): 返回兩個集合的差集
subset(otherSet): 判斷該集合是否為傳入集合的子集
has方法:說明:集合中元素是不重復的。所以在其它任何操作前,必須用has方法確認集合是否有某個元素。這兒使用了hasOwnProperty方法來檢測。
實現:
</>復制代碼
/**
* 檢測集合內是否有某個元素
* @param {Any} value 要檢測的元素
* @return {Boolean} 如果有,返回true
*/
this.has = function(value) {
// hasOwnProperty的問題在于
// 它是一個方法,所以可能會被覆寫
return items.hasOwnProperty(value)
};
add方法:
說明: 給集合內添加某個元素。
實現:
</>復制代碼
/**
* 給集合內添加某個元素
* @param {Any} value 要被添加的元素
* @return {Boolean} 添加成功返回True。
*/
this.add = function(value) {
//先檢測元素是否存在。
if (!this.has(value)) {
items[value] = value;
return true;
}
//如果元素已存在則返回false
return false;
};
remove方法:
說明: 移除集合中某個元素
實現:
</>復制代碼
/**
* 移除集合中某個元素
* @param {Any} value 要移除的元素
* @return {Boolean} 移除成功返回True。
*/
this.remove = function(value) {
//先檢測元素是否存在。
if (this.has(value)) {
delete items[value];
return true;
}
//如果元素不存在,則刪除失敗返回false
return false;
};
clear方法:
說明: 清空集合
實現:
</>復制代碼
/**
* 清空集合
*/
this.clear = function() {
this.items = {};
};
size方法
說明: 返回集合長度,這兒有兩種方法。第一種方法使用了Object.keys這個Api,但只支持IE9及以上。第二種則適用于所有瀏覽器。
實現:
</>復制代碼
/**
* 返回集合長度,只可用于IE9及以上
* @return {Number} 集合長度
*/
this.size = function() {
// Object.keys方法能將對象轉化為數組
// 只可用于IE9及以上,但很方便
return Object.keys(items).length;
}
/**
* 返回集合長度,可用于所有瀏覽器
* @return {Number} 集合長度
*/
this.sizeLegacy = function() {
var count = 0;
for (var prop in items) {
if (items.hasOwnProperty(prop)) {
++count;
}
}
return count;
}
values方法
說明: 返回集合轉換的數組,這兒也有兩種方法。理由同上。使用了Object.keys,只能支持IE9及以上。
實現:
</>復制代碼
/**
* 返回集合轉換的數組,只可用于IE9及以上
* @return {Array} 轉換后的數組
*/
this.values = function() {
return Object.keys(items);
};
/**
* 返回集合轉換的數組,可用于所有瀏覽器
* @return {Array} 轉換后的數組
*/
this.valuesLegacy = function() {
var keys = [];
for (var key in items) {
keys.push(key)
};
return keys;
};
union方法
說明: 返回兩個集合的并集
實現:
</>復制代碼
/**
* 返回兩個集合的并集
* @param {Set} otherSet 要進行并集操作的集合
* @return {Set} 兩個集合的并集
*/
this.union = function(otherSet) {
//初始化一個新集合,用于表示并集。
var unionSet = new Set();
//將當前集合轉換為數組,并依次添加進unionSet
var values = this.values();
for (var i = 0; i < values.length; i++) {
unionSet.add(values[i]);
}
//將其它集合轉換為數組,依次添加進unionSet。
//循環中的add方法保證了不會有重復元素的出現
values = otherSet.values();
for (var i = 0; i < values.length; i++) {
unionSet.add(values[i]);
}
return unionSet;
};
intersection方法
說明: 返回兩個集合的交集
實現:
</>復制代碼
/**
* 返回兩個集合的交集
* @param {Set} otherSet 要進行交集操作的集合
* @return {Set} 兩個集合的交集
*/
this.intersection = function(otherSet) {
//初始化一個新集合,用于表示交集。
var interSectionSet = new Set();
//將當前集合轉換為數組
var values = this.values();
//遍歷數組,如果另外一個集合也有該元素,則interSectionSet加入該元素。
for (var i = 0; i < values.length; i++) {
if (otherSet.has(values[i])) {
interSectionSet.add(values[i])
}
}
return interSectionSet;
};
difference方法
說明: 返回兩個集合的差集
實現:
</>復制代碼
/**
* 返回兩個集合的差集
* @param {Set} otherSet 要進行差集操作的集合
* @return {Set} 兩個集合的差集
*/
this.difference = function(otherSet) {
//初始化一個新集合,用于表示差集。
var differenceSet = new Set();
//將當前集合轉換為數組
var values = this.values();
//遍歷數組,如果另外一個集合沒有該元素,則differenceSet加入該元素。
for (var i = 0; i < values.length; i++) {
if (!otherSet.has(values[i])) {
differenceSet.add(values[i])
}
}
return differenceSet;
};
subset方法
說明: 判斷該集合是否為傳入集合的子集。這段代碼在我自己寫完后與書上一比對,覺得自己超級low。我寫的要遍歷數組三次,書上的只需要一次,算法復雜度遠遠低于我的。
實現:
</>復制代碼
/**
* 判斷該集合是否為傳入集合的子集
* @param {Set} otherSet 傳入的集合
* @return {Boolean} 是則返回True
*/
this.subset = function(otherSet) {
// 第一個判定,如果該集合長度大于otherSet的長度
// 則直接返回false
if (this.size() > otherSet.size()) {
return false;
} else {
// 將當前集合轉換為數組
var values = this.values();
for (var i = 0; i < values.length; i++) {
if (!otherSet.has(values[i])) {
// 第二個判定。只要有一個元素不在otherSet中
// 那么則可以直接判定不是子集,返回false
return false;
}
}
return true;
}
};
源代碼
源代碼在此~
ES6中的集合</>復制代碼
集合-源代碼
ES6也提供了集合,但之前看ES6的集合操作一直迷迷糊糊的。實現一遍后再去看,感覺概念清晰了很多。
具體的我掌握的不是很好,還在學習中,就不寫出來啦~推薦看阮一峰老師的《ECMAScript 6入門》中對ES6 Set的介紹。
</>復制代碼
《ECMAScript 6入門》-- Set和Map數據結構
感想
到了這兒,已經掌握了一些基本的數據結構。剩下的都是難啃的骨頭了(對我而言)。
字典的散列表、圖、樹、排序算法。算是四大金剛,所以近期關于數據結構與算法系列的文章,可能會更新的很慢。對我來說,也算是一個坎。希望這個寒假,能跨過這個坎。
前端路漫漫,且行且歌~
</>復制代碼
Lxxyx的前端樂園
原文鏈接:寒假前端學習(5)——學習JavaScript數據結構與算法(三):集合
文章版權歸作者所有,未經允許請勿轉載,若此文章存在違規行為,您可以聯系管理員刪除。
轉載請注明本文地址:http://specialneedsforspecialkids.com/yun/91590.html
摘要:筆者作為一位,將工作以來用到的各種優秀資料神器及框架整理在此,畢竟好記性不如爛鍵盤,此前端知識點大百科全書前端掘金,,不定期更新技巧前端掘金技巧,偶爾更新。計算數組的極值技巧使你的更加專業前端掘金一個幫你提升技巧的收藏集。 CSS 樣式畫各種圖形 - 前端 - 掘金下面是一些我在 CSS 中經常用到的圖案,還有一些是在css-tricks看到的。記錄一下,以后會用到。會持續更新… 一、...
摘要:筆者作為一位,將工作以來用到的各種優秀資料神器及框架整理在此,畢竟好記性不如爛鍵盤,此前端知識點大百科全書前端掘金,,不定期更新技巧前端掘金技巧,偶爾更新。計算數組的極值技巧使你的更加專業前端掘金一個幫你提升技巧的收藏集。 CSS 樣式畫各種圖形 - 前端 - 掘金下面是一些我在 CSS 中經常用到的圖案,還有一些是在css-tricks看到的。記錄一下,以后會用到。會持續更新… 一、...
本系列所有文章:第一篇文章:學習數據結構與算法之棧與隊列第二篇文章:學習數據結構與算法之鏈表第三篇文章:學習數據結構與算法之集合第四篇文章:學習數據結構與算法之字典和散列表第五篇文章:學習數據結構與算法之二叉搜索樹 集合簡介 記得高一數學第一節課學的就是集合,現在快大四了再看到它有種見了老朋友的感覺。哈哈,閑話不多扯,進入正題。 集合是由一組無序且不重復的項組成的數據結構。這里集合的概念和高中數學...
閱讀 1360·2021-11-24 09:39
閱讀 1352·2021-11-04 16:12
閱讀 2696·2021-09-24 09:47
閱讀 3342·2021-09-01 10:50
閱讀 1481·2019-08-30 15:55
閱讀 1428·2019-08-30 15:43
閱讀 648·2019-08-30 11:08
閱讀 3586·2019-08-23 18:33