JavaScript實作集合與字典

JavaScript實作集合與字典

一、集合結構

1.1.簡介

集合比較常見的實作方式是哈希表，這裡使用JavaScript的Object類進行封裝。

集合通常是由一組無序的、不能重複的元素構成。

數學中常指的集合中的元素是可以重複的，但是計算機中集合的元素不能重複。

集合是特殊的數組：

特殊之處在于裡面的元素沒有順序，也不能重複。

沒有順序意味着不能通過下标值進行通路，不能重複意味着相同的對象在集合中隻會存在一份。

實作集合類：

在ES6中的Set類就是一個集合類，這裡我們重新封裝一個Set類，了解集合的底層實作。

JavaScript中的Object類中的key就是一個集合，可以使用它來封裝集合類Set。

集合常見的操作：

add（value）：向集合添加一個新的項；

remove（value）：從集合中移除一個值；

has（value）：如果值在集合中，傳回true，否則傳回false；

clear（）：移除集合中的所有項；

size（）：傳回集合所包含元素的數量，與數組的length屬性相似；

values（）：傳回一個包含集合中所有值的數組；

還有其他的方法，用的不多這裡不做封裝；

1.2.代碼實作

複制代碼

//封裝集合類
function Set() {
  //屬性
  this.items = {}

  //方法
  //一.has方法
  Set.prototype.has = value => {
    return this.items.hasOwnProperty(value)
  }

  //二.add方法
  Set.prototype.add = value => {
    //判斷集合中是否已經包含該元素
    if (this.has(value)) {
      return false
    }
    //将元素添加到集合中
    this.items[value] = value//表示該屬性鍵和值都為value
    return true//表示添加成功
  }

  //三.remove方法
  Set.prototype.remove = (value) => {
    //1.判斷集合中是否包含該元素
    if (!this.has(value)) {
      return false
    }

    //2.将元素從屬性中删除
    delete this.items[value]
    return true
  }

  //四.clear方法
  Set.prototype.clear = () => {
    //原來的對象沒有引用指向，會被自動回收
    this.items = {}
  }

  //五.size方法
  Set.prototype.size = () => {
    return Object.keys(this.items).length
  }

  //擷取集合中所有的值
  //六.values方法
  Set.prototype.values = function() {
    return Object.keys(this.items)
  }
}           

測試代碼：

//測試集合類
//1.建立Set類對象
let set = new Set()

//添加元素
//2.測試add方法
console.log(set.add('a'));                                      //67
console.log(set.add('a'));                                      //68
console.log(set.add('b'));                                      //69
console.log(set.add('c'));                                      //70
console.log(set.add('d'));                                      //71

//3.測試values方法
console.log(set.values());                                      //74

//删除元素
//4.測試remove方法
console.log(set.remove('a'));                                   //78
console.log(set.remove('a'));                                   //79
console.log(set.values());                                      //80

//5.測試has方法
console.log(set.has('b'));                                      //83

//6.測試size方法和clear方法
console.log(set.size());                                        //86
set.clear()
// 由于clear方法的實作原理為指向另外一個空對象，是以不影響原來的對象
console.log(set.size());                                        //89
console.log(set.values());                                      //90           

測試結果：

1.3.集合間的操作

集合間操作：

并集：對于給定的兩個集合，傳回一個包含兩個集合中所有元素的新集合；

交集：對于給定的兩個集合，傳回一個包含兩個集合中共有元素的新集合；

差集：對于給定的兩個集合，傳回一個包含所有存在于第一個集合且不存在于第二個集合的元素的新集合；

子集：驗證一個給定集合是否是另一個集合的子集；

并集的實作：

實作思路：建立集合C代表集合A和集合B的并集，先将集合A中的所有元素添加到集合C中，再周遊集合B，如果是集合C所沒有的元素就把它添加到集合C中。

Set.prototype.union = otherSet => {

// this:集合對象A
  // otherSet:集合對象B
  //1.建立一個新的集合
  let unionSet = new Set()

  //2.将A集合中的所有元素添加到新集合中
  let values = this.values()
  // for(let i of values){
  //   unionSet.add(i)
  // }
  for(let i = 0;i < values.length;i++){
    unionSet.add(values[i])
  }

  //3.取出B集合中的元素,判斷是否需要加到新集合中
  values = otherSet.values()
  // for(let i of values){
  //   //由于集合的add方法已經對重複的元素進行了判斷,是以這裡可以直接添加
  //   unionSet.add(i)
  // }
  for(let i = 0;i < values.length;i++){
    unionSet.add(values[i])
  }
  return unionSet
}           

交集的實作：

實作思路：周遊集合A，當取得的元素也存在于集合B時，就把該元素添加到另一個集合C中。

Set.prototype.intersection = otherSet => {

// this:集合A
  // otherSet:集合B
  //1.建立新的集合
  let intersectionSet = new Set()
  
  //2.從A中取出一個元素，判斷是否同時存在于集合B中，是則放入新集合中
  let values = this.values()
  for(let i =0 ; i < values.length; i++){
    let item = values[i]
    if (otherSet.has(item)) {
      intersectionSet.add(item)
    }
  }
  return intersectionSet
}           

差集的實作：

實作思路：周遊集合A，當取得的元素不存在于集合B時，就把該元素添加到另一個集合C中。

Set.prototype.diffrence = otherSet => {

//this:集合A
    //otherSet:集合B
    //1.建立新的集合
    var diffrenceSet = new Set()

    //2.取出A集合中的每一個元素，判斷是否同時存在于B中，不存在則添加到新集合中
    var values = this.values()
    for(var i = 0;i < values.length; i++){
      var item = values[i]
      if (!otherSet.has(item)) {
        diffrenceSet.add(item)
      }
    }
    return diffrenceSet
  }           

子集的實作：

實作思路：周遊集合A，當取得的元素中有一個不存在于集合B時，就說明集合A不是集合B的子集，傳回false。

Set.prototype.subset = otherSet => {

//this:集合A
    //otherSet：集合B
    //周遊集合A中的所有元素，如果發現，集合A中的元素，在集合B中不存在，那麼放回false，如果周遊完整個集合A沒有傳回false，就傳回true
    let values = this.values()
    for(let i = 0; i < values.length; i++){
      let item = values[i]
      if(!otherSet.has(item)){
        return false
      }
    }
    return true
  }           

二、字典結構

2.1.簡介

字典的特點：

字典存儲的是鍵值對，主要特點是一一對應；

比如儲存一個人的資訊：數組形式：[19，‘Tom’，1.65]，可通過下标值取出資訊；字典形式：{"age"：19，"name"："Tom"，"height"：165}，可以通過key取出value。

此外，在字典中key是不能重複且無序的，而Value可以重複。

字典和映射的關系：

有些程式設計語言中稱這種映射關系為字典，如Swift中的Dictonary，Python中的dict；

有些程式設計語言中稱這種映射關系為Map，比如Java中的HashMap&TreeMap等；

字典類常見的操作：

set(key,value)：向字典中添加新元素。

remove(key)：通過使用鍵值來從字典中移除鍵值對應的資料值。

has(key)：如果某個鍵值存在于這個字典中，則傳回true，反之則傳回false。

get(key)：通過鍵值查找特定的數值并傳回。

clear()：将這個字典中的所有元素全部删除。

size()：傳回字典所包含元素的數量。與數組的length屬性類似。

keys()：将字典所包含的所有鍵名以數組形式傳回。

values()：将字典所包含的所有數值以數組形式傳回。

2.2.封裝字典

字典類可以基于JavaScript中的對象結構來實作，比較簡單，這裡直接實作字典類中的常用方法。

//封裝字典類

function Dictionary(){

//字典屬性

this.items = {}

//字典操作方法

//一.在字典中添加鍵值對

Dictionary.prototype.set = function(key, value){

this.items[key] = value           

}

//二.判斷字典中是否有某個key

Dictionary.prototype.has = function(key){

return this.items.hasOwnProperty(key)           

//三.從字典中移除元素

Dictionary.prototype.remove = function(key){

//1.判斷字典中是否有這個key
if(!this.has(key)) return false

//2.從字典中删除key
delete this.items[key]
return true           

//四.根據key擷取value

Dictionary.prototype.get = function(key){

return this.has(key) ? this.items[key] : undefined           

//五.擷取所有keys

Dictionary.prototype.keys = function(){

return Object.keys(this.items)           

//六.size方法

return this.keys().length           

//七.clear方法

Dictionary.prototype.clear = function(){

this.items = {}           

原文位址

https://www.cnblogs.com/AhuntSun-blog/p/12474890.html