成人国产在线小视频_日韩寡妇人妻调教在线播放_色成人www永久在线观看_2018国产精品久久_亚洲欧美高清在线30p_亚洲少妇综合一区_黄色在线播放国产_亚洲另类技巧小说校园_国产主播xx日韩_a级毛片在线免费

資訊專欄INFORMATION COLUMN

學(xué)習(xí)數(shù)據(jù)結(jié)構(gòu)與算法之集合

fai1017 / 3501人閱讀 

本系列所有文章：
第一篇文章：學(xué)習(xí)數(shù)據(jù)結(jié)構(gòu)與算法之棧與隊(duì)列
第二篇文章：學(xué)習(xí)數(shù)據(jù)結(jié)構(gòu)與算法之鏈表
第三篇文章：學(xué)習(xí)數(shù)據(jù)結(jié)構(gòu)與算法之集合
第四篇文章：學(xué)習(xí)數(shù)據(jù)結(jié)構(gòu)與算法之字典和散列表
第五篇文章：學(xué)習(xí)數(shù)據(jù)結(jié)構(gòu)與算法之二叉搜索樹
集合簡介

記得高一數(shù)學(xué)第一節(jié)課學(xué)的就是集合，現(xiàn)在快大四了再看到它有種見了老朋友的感覺。哈哈，閑話不多扯，進(jìn)入正題。

集合是由一組無序且不重復(fù)的項(xiàng)組成的數(shù)據(jù)結(jié)構(gòu)。這里集合的概念和高中數(shù)學(xué)類似，也有空集，交集，并集，子集等概念，只不過在這里就沒有那么復(fù)雜的證明題了。那么接下來就用JavaScript實(shí)現(xiàn)一下集合。

用JavaScript實(shí)現(xiàn)集合

老規(guī)矩，先弄一個(gè)構(gòu)造函數(shù)出來

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

集合要實(shí)現(xiàn)以下方法：

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

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

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

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

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

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

實(shí)現(xiàn)has

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

this.has = function (value) {
  return items.hasOwnProperty(value)
}
實(shí)現(xiàn)add

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

this.add = function (value) {
  if (!this.has(value)) {
    items[value] = value
    return true
  }
  return false
}
實(shí)現(xiàn)remove

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

this.remove = function (value) {
  if (this.has(value)) {
    delete items[value]
    return true
  }
  return false
}
實(shí)現(xiàn)values

Object.keys的作用是返回對(duì)象中所有可枚舉屬性組成的數(shù)組（不包括原型鏈上的屬性）。當(dāng)然，你也可以用for...in 來實(shí)現(xiàn)。

this.values = function () {
  return Object.keys(items)
}
實(shí)現(xiàn)clear和size

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

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

this.size = function () {
  return Object.keys(items).length
}
實(shí)現(xiàn)集合操作

集合有以下操作：

并集

交集

差集

子集

具體的就不多解釋了，請(qǐng)看代碼

實(shí)現(xiàn)并集

創(chuàng)建一個(gè)新集合unionSet表示兩個(gè)集合的并集，之后分別遍歷兩個(gè)集合添加進(jìn)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
}
實(shí)現(xiàn)交集

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

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
}
實(shí)現(xiàn)差集

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

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
}
實(shí)現(xiàn)子集

數(shù)學(xué)中A是B的子集意味著A中的所有元素都存在于B中，按照這個(gè)思路實(shí)現(xiàn)代碼如下

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
  }
}

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

集合的實(shí)現(xiàn)－源代碼
小結(jié)

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

文章版權(quán)歸作者所有，未經(jīng)允許請(qǐng)勿轉(zhuǎn)載,若此文章存在違規(guī)行為，您可以聯(lián)系管理員刪除。

轉(zhuǎn)載請(qǐng)注明本文地址：http://systransis.cn/yun/87201.html

相關(guān)文章

  • 我的阿里之路+Java面經(jīng)考點(diǎn)

    摘要：我的是忙碌的一年，從年初備戰(zhàn)實(shí)習(xí)春招，年三十都在死磕源碼，三月份經(jīng)歷了阿里五次面試，四月順利收到實(shí)習(xí)。因?yàn)槲倚睦砗芮宄业哪繕?biāo)是阿里。所以在收到阿里之后的那晚，我重新規(guī)劃了接下來的學(xué)習(xí)計(jì)劃，將我的短期目標(biāo)更新成拿下阿里轉(zhuǎn)正。 我的2017是忙碌的一年，從年初備戰(zhàn)實(shí)習(xí)春招，年三十都在死磕JDK源碼，三月份經(jīng)歷了阿里五次面試，四月順利收到實(shí)習(xí)offer。然后五月懷著忐忑的心情開始了螞蟻金...

    姘擱『 評(píng)論0 收藏0

  • 學(xué)習(xí)數(shù)據(jù)結(jié)構(gòu)與算法之鏈表

    摘要：本系列所有文章第一篇文章學(xué)習(xí)數(shù)據(jù)結(jié)構(gòu)與算法之棧與隊(duì)列第二篇文章學(xué)習(xí)數(shù)據(jù)結(jié)構(gòu)與算法之鏈表第三篇文章學(xué)習(xí)數(shù)據(jù)結(jié)構(gòu)與算法之集合第四篇文章學(xué)習(xí)數(shù)據(jù)結(jié)構(gòu)與算法之字典和散列表第五篇文章學(xué)習(xí)數(shù)據(jù)結(jié)構(gòu)與算法之二叉搜索樹簡單介紹鏈表鏈表一種常見的數(shù)據(jù)結(jié)構(gòu)，可 本系列所有文章：第一篇文章：學(xué)習(xí)數(shù)據(jù)結(jié)構(gòu)與算法之棧與隊(duì)列第二篇文章：學(xué)習(xí)數(shù)據(jù)結(jié)構(gòu)與算法之鏈表第三篇文章：學(xué)習(xí)數(shù)據(jù)結(jié)構(gòu)與算法之集合第四篇文章：學(xué)習(xí)數(shù)...

    jerryloveemily 評(píng)論0 收藏0

  • 學(xué)習(xí)數(shù)據(jù)結(jié)構(gòu)與算法之字典和散列表

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

    Heier 評(píng)論0 收藏0

  • 一文掌握關(guān)于Java數(shù)據(jù)結(jié)構(gòu)所有知識(shí)點(diǎn)（歡迎一起完善）

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

    keithxiaoy 評(píng)論0 收藏0

發(fā)表評(píng)論

0條評(píng)論

最新活動(dòng)
閱讀需要支付1元查看
<