學習數據結構與算法之集合

fai1017 發布于2019-08-21 11:51 / 3499人閱讀

本系列所有文章：
第一篇文章：學習數據結構與算法之棧與隊列
第二篇文章：學習數據結構與算法之鏈表
第三篇文章：學習數據結構與算法之集合
第四篇文章：學習數據結構與算法之字典和散列表
第五篇文章：學習數據結構與算法之二叉搜索樹

集合簡介

記得高一數學第一節課學的就是集合，現在快大四了再看到它有種見了老朋友的感覺。哈哈，閑話不多扯，進入正題。

集合是由一組無序且不重復的項組成的數據結構。這里集合的概念和高中數學類似，也有空集，交集，并集，子集等概念，只不過在這里就沒有那么復雜的證明題了。那么接下來就用JavaScript實現一下集合。

用JavaScript實現集合

老規矩，先弄一個構造函數出來

function Set () {
  // 這里用對象來模擬集合
  var items = {}
}

集合要實現以下方法：

add(value)：向集合添加新的項

remove(value)：從集合刪除一項

has(value)：如果集合中存在該項則返回true，否則返回false

clear()：清除集合中的所有項

size()：返回集合包含元素的數量

values()：返回集合中所有值的數組

實現has

根據hasOwnProperty判斷該元素是否屬于集合，注意：hasOwnProperty可以檢查屬性是否屬于對象，對于原型鏈上的屬性hasOwnProperty會返回false

this.has = function (value) {
  return items.hasOwnProperty(value)
}

實現add

這里添加新的元素到集合中時，首先要保證該元素不存在于集合中。

this.add = function (value) {
  if (!this.has(value)) {
    items[value] = value
    return true
  }
  return false
}

實現remove

刪除前也要先判斷元素是否存在

this.remove = function (value) {
  if (this.has(value)) {
    delete items[value]
    return true
  }
  return false
}

實現values

Object.keys的作用是返回對象中所有可枚舉屬性組成的數組（不包括原型鏈上的屬性）。當然，你也可以用for...in 來實現。

this.values = function () {
  return Object.keys(items)
}

實現clear和size

比較簡單，就直接貼源碼了

this.clear = function () {
  items = {}
}

this.size = function () {
  return Object.keys(items).length
}

實現集合操作

集合有以下操作：

并集

交集

差集

子集

具體的就不多解釋了，請看代碼

實現并集

創建一個新集合unionSet表示兩個集合的并集，之后分別遍歷兩個集合添加進unionSet，最后返回集合

this.union = function (otherSet) {
  var unionSet = new Set()
  
  var values = this.values()
  for (var i = 0; i < values.length; i++) {
    unionSet.add(values[i])
  }
  
  values = otherSet.values()
  for (var i = 0; i < values.length; i++) {
    unionSet.add(values[i])
  }
  return unionSet
}

實現交集

交集是兩者都有的屬性的集合，實現思路與上面類似，只要判斷元素是否同時存在與兩個集合就行了

this.intersection = function (otherSet) {
  var intersectionSet = new Set()

  var values = this.values()
  for (var i = 0; i < values.length; i++) {
    if (otherSet.has(values[i])) {
      intersectionSet.add(values[i])
    }
  }

  return intersectionSet
}

實現差集

差集A-B的意思是：元素只在集合A中存在，集合B中不存在，因此實現也很簡單。

this.difference = function (otherSet) {
  var differenceSet = new Set()
  
  var values = this.values()
  for (var i = 0; i < values.length; i++) {
    if (!otherSet.has(values[i])) {
      differenceSet.add(values[i])
    }
  }
  
  return differenceSet
}

實現子集

數學中A是B的子集意味著A中的所有元素都存在于B中，按照這個思路實現代碼如下

this.subSet = function (otherSet) {
  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])) {
        return false
      }
    }
    return true
  }
}

放上源代碼，有興趣的可以看看：

集合的實現－源代碼

小結

到目前為止，比較簡單的數據結構基本都掌握了，后面就是字典、散列表、樹、圖以及排序算法了，都是難啃的骨頭，但是必須要啃下來。繼續加油～

云服務器 GPU云服務器二分圖集合算法最小集合覆蓋貪心算法最小集合覆蓋遺傳算法 webrtc之vad算法

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

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

我的阿里之路+Java面經考點

摘要：我的是忙碌的一年，從年初備戰實習春招，年三十都在死磕源碼，三月份經歷了阿里五次面試，四月順利收到實習。因為我心理很清楚，我的目標是阿里。所以在收到阿里之后的那晚，我重新規劃了接下來的學習計劃，將我的短期目標更新成拿下阿里轉正。我的2017是忙碌的一年，從年初備戰實習春招，年三十都在死磕JDK源碼，三月份經歷了阿里五次面試，四月順利收到實習offer。然后五月懷著忐忑的心情開始了螞蟻金...

姘擱『 2019-08-15 14:42 評論0 收藏0
學習數據結構與算法之鏈表

摘要：本系列所有文章第一篇文章學習數據結構與算法之棧與隊列第二篇文章學習數據結構與算法之鏈表第三篇文章學習數據結構與算法之集合第四篇文章學習數據結構與算法之字典和散列表第五篇文章學習數據結構與算法之二叉搜索樹簡單介紹鏈表鏈表一種常見的數據結構，可本系列所有文章：第一篇文章：學習數據結構與算法之棧與隊列第二篇文章：學習數據結構與算法之鏈表第三篇文章：學習數據結構與算法之集合第四篇文章：學習數...

jerryloveemily 2019-08-21 11:50 評論0 收藏0
學習數據結構與算法之字典和散列表

摘要：小結實現了字典和哈希表感覺沒有想象中那么困難，當然這還是開始。本系列所有文章：第一篇文章：學習數據結構與算法之棧與隊列第二篇文章：學習數據結構與算法之鏈表第三篇文章：學習數據結構與算法之集合第四篇文章：學習數據結構與算法之字典和散列表第五篇文章：學習數據結構與算法之二叉搜索樹字典不是新華字典哦，這里的字典也稱作_映射_，是一種數據結構，跟set集合很相似的一種數據結構，都可以用來...

Heier 2019-08-21 11:52 評論0 收藏0
一文掌握關于Java數據結構所有知識點（歡迎一起完善）

摘要：是棧，它繼承于。滿二叉樹除了葉結點外每一個結點都有左右子葉且葉子結點都處在最底層的二叉樹。沒有鍵值相等的節點。這是數據庫選用樹的最主要原因。在我們學習Java的時候，很多人會面臨我不知道繼續學什么或者面試會問什么的尷尬情況（我本人之前就很迷茫）。所以，我決定通過這個開源平臺來幫助一些有需要的人，通過下面的內容，你會掌握系統的Java學習以及面試的相關知識。本來是想通過Gitbook的...

keithxiaoy 2019-08-15 15:54 評論0 收藏0