摘要:前言總括本文講解了數據結構中的集合概念,并使用實現了集合。原文博客地址學習數據結構三集合知乎專欄簡書專題前端進擊者知乎前端進擊者簡書博主博客地址的個人博客人生多風雨,何處無險阻。敬請期待學習數據結構四散列表
前言
總括: 本文講解了數據結構中的[集合]概念,并使用javascript實現了集合。
原文博客地址:學習javascript數據結構(三)——集合
知乎專欄&&簡書專題:前端進擊者(知乎)&&前端進擊者(簡書)
博主博客地址:Damonare的個人博客
人生多風雨,何處無險阻。
正文 集合簡介在上一篇學習javascript數據結構(二)——鏈表中我們說了鏈表這種數據結構,但歸根結底,不論是棧,隊列亦或是鏈表都是線性結構。他們都是一種很規矩的數據結構,就像幼兒園的小朋友排隊乖乖的站在那不會動一樣。
然而紛雜的數據并不會總是排隊站在那里,幼兒園小朋友一旦下了課那可就撒歡了,亂糟糟一團。可我們的幼兒園老師卻能分辨出這些小朋友,因為啥?因為每個小朋友都在一個班里,而且每一個小朋友都有自己的名字。老師自然很容易就找到小朋友了。
而本篇博文要說的集合正是一堆亂糟糟的數據,唯一的共同點是這些數據隸屬于同一個集合,看下百科給出的解釋:
由一個或多個元素所構成的叫做集合。
此處的元素就是小朋友了,他們所在的集合就是他們的班級。其實我們在高中的時候也接觸過集合的概念。那時候還沒有套路這個名詞,單純的歲月,那個年代對于集合是這么解釋的:
集合是指具有某種特定性質的具體的或抽象的對象匯總成的集體,這些對象稱為該集合的元素。
然后又是這么分類的:
空集:{}
有限集:{a,b,4}
無限集:{1,2,3,4...}
不過,數據結構中集合是沒有無限集這個概念的。再然后那時候的集合還有這么幾個特性:
確定性:給定一個集合,任給一個元素,該元素或者屬于或者不屬于該集合,二者必居其一,不允許有模棱兩可的情況出現。
互異性:一個集合中,任何兩個元素都認為是不相同的,即每個元素只能出現一次。有時需要對同一元素出現多次的情形進行刻畫,可以使用多重集,其中的元素允許出現多次。
無序性:一個集合中,每個元素的地位都是相同的,元素之間是無序的。集合上可以定義序關系,定義了序關系后,元素之間就可以按照序關系排序。但就集合本身的特性而言,元素之間沒有必然的序。
想當年哥還是個數學學霸,如今卻淪落為了一個碼農......真是讓人唏噓啊。咳咳!接著說:
集合還有這幾種常見的基本操作:
并集
交集
差集
而且我們數據結構中的集合基本是也符合高中時候的數學中的概念的。接下來我們是用ES5來實現集合,為啥子這么說呢......因為在ES6中已經新給出了Set,Map等幾個集合類,更加方便快捷的鎖定鍵值對。
集合的創建首先我們先聲明一個集合類:
function(){ var items={}; }
接下來,我們需要給鏈表聲明一些方法:
add(value):向集合添加一個新的項
remove(value):從集合移除一個值
has(value):如果值在集合中,返回true,否則返回false
clear():移除集合中的所有項
size():返回集合所包含的元素數量,與數組的length屬性相似
values():返回一個集合中所有值的數組
union(setName):并集,返回包含兩個集合所有元素的新集合(元素不重復)
intersection(setName):交集,返回包含兩個集合中共有的元素的集合、
difference(setName):差集,返回包含所有存在本集合而不存在setName集合的元素的新集合
subset(setName):子集,驗證setName是否是本集合的子集
下面是Set類的完整代碼:
function Set() { let items = {}; this.add = function(value){ if (!this.has(value)){ items[value] = value; return true; } return false; }; this.delete = function(value){ if (this.has(value)){ delete items[value]; return true; } return false; }; this.has = function(value){ return items.hasOwnProperty(value); //return value in items; }; this.clear = function(){ items = {}; }; /** * Modern browsers function * IE9+, FF4+, Chrome5+, Opera12+, Safari5+ * @returns {Number} */ this.size = function(){ return Object.keys(items).length; }; /** * cross browser compatibility - legacy browsers * for modern browsers use size function * @returns {number} */ this.sizeLegacy = function(){ let count = 0; for(let key in items) { if(items.hasOwnProperty(key)) ++count; } return count; }; /** * Modern browsers function * IE9+, FF4+, Chrome5+, Opera12+, Safari5+ * @returns {Array} */ this.values = function(){ let values = []; for (let i=0, keys=Object.keys(items); iotherSet.size()){ return false; } else { let values = this.values(); for (let i=0; i 下面是ES6版本代碼:
let Set2 = (function () { const items = new WeakMap(); class Set2 { constructor () { items.set(this, {}); } add(value){ if (!this.has(value)){ let items_ = items.get(this); items_[value] = value; return true; } return false; } delete(value){ if (this.has(value)){ let items_ = items.get(this); delete items_[value]; return true; } return false; } has(value){ let items_ = items.get(this); return items_.hasOwnProperty(value); } clear(){ items.set(this, {}); } size(){ let items_ = items.get(this); return Object.keys(items_).length; } values(){ let values = []; let items_ = items.get(this); for (let i=0, keys=Object.keys(items_); iotherSet.size()){ return false; } else { let values = this.values(); for (let i=0; i 后記 集合是一種比較常見的數據結構,在JS中我們已經有了一種類似哈希表的東西:Object(對象)。但現在我們所說的集合只是以[value,value]形式存儲數據,下一節我們使用[鍵,值]形式存儲數據,和本文集合的實現略有不同。敬請期待:[學習javascript數據結構(四)——散列表]
文章版權歸作者所有,未經允許請勿轉載,若此文章存在違規行為,您可以聯系管理員刪除。
轉載請注明本文地址:http://specialneedsforspecialkids.com/yun/91179.html
摘要:至于這三個的具體概念,可以看圖中集合的實現首先,創建一個構造函數。前端路漫漫,且行且歌的前端樂園原文鏈接寒假前端學習學習數據結構與算法三集合 本系列的第一篇文章: 學習JavaScript數據結構與算法(一),棧與隊列第二篇文章:學習JavaScript數據結構與算法(二):鏈表第三篇文章:學習JavaScript數據結構與算法(三):集合第四篇文章:學習JavaScript數據結構與...
摘要:筆者作為一位,將工作以來用到的各種優秀資料神器及框架整理在此,畢竟好記性不如爛鍵盤,此前端知識點大百科全書前端掘金,,不定期更新技巧前端掘金技巧,偶爾更新。計算數組的極值技巧使你的更加專業前端掘金一個幫你提升技巧的收藏集。 CSS 樣式畫各種圖形 - 前端 - 掘金下面是一些我在 CSS 中經常用到的圖案,還有一些是在css-tricks看到的。記錄一下,以后會用到。會持續更新… 一、...
摘要:筆者作為一位,將工作以來用到的各種優秀資料神器及框架整理在此,畢竟好記性不如爛鍵盤,此前端知識點大百科全書前端掘金,,不定期更新技巧前端掘金技巧,偶爾更新。計算數組的極值技巧使你的更加專業前端掘金一個幫你提升技巧的收藏集。 CSS 樣式畫各種圖形 - 前端 - 掘金下面是一些我在 CSS 中經常用到的圖案,還有一些是在css-tricks看到的。記錄一下,以后會用到。會持續更新… 一、...
閱讀 3223·2021-09-09 11:39
閱讀 1228·2021-09-09 09:33
閱讀 1127·2019-08-30 15:43
閱讀 546·2019-08-29 14:08
閱讀 1733·2019-08-26 13:49
閱讀 2376·2019-08-26 10:09
閱讀 1545·2019-08-23 17:13
閱讀 2283·2019-08-23 12:57