Collection de structures de données et d'algorithmes JavaScript (Set)_Connaissances de base

Ensemble

En parlant d'ensembles, je me souviens que lorsque je suis entré au lycée, le premier cours de mathématiques portait sur les ensembles. Par conséquent, cela semble plus intime lors de l’apprentissage de la structure des données des collections.
Il existe une propriété fondamentale des ensembles : les éléments de l’ensemble ne sont pas répétés. En raison de cette propriété, nous avons choisi des objets comme conteneurs pour les collections plutôt que comme tableaux.
Bien que les tableaux puissent également réaliser toutes les non-répétitions, ils sont finalement trop encombrants et moins performants que les collections.

Opérations de collecte

Les opérations de base des ensembles incluent l'intersection, l'union, la différence, etc. Nous introduisons ici l'implémentation de l'intersection, de l'union et de la différence dans les collections JavaScipt.

Implémentation des collections en JavaScipt

Tout d’abord, créez un constructeur.

/**
 * 集合的构造函数
 */
function Set方法 {
 /**
  * 集合元素的容器，以对象来表示
  * @type {Object}
  */
 var items = {};
}

La collecte doit avoir les méthodes suivantes :

1. has(value) : Vérifiez s'il y a un élément dans la collection
2. add(value) : Ajouter un élément à la collection
3. remove(value) : Supprimer un élément de la collection
4. clear(value) : Effacer la collection
5. size() : renvoie la longueur de la collection
6. values() : renvoie le tableau converti à partir de l'ensemble
7. union(otherSet) : renvoie l'union de deux ensembles
8. intersection(otherSet) : renvoie l'intersection de deux ensembles
9. difference(otherSet) : renvoie la différence entre deux ensembles
10. subset(otherSet) : Déterminez si l'ensemble est un sous-ensemble de l'ensemble entrant

a la méthode :

Remarque : les éléments de l'ensemble ne sont pas répétés. Par conséquent, avant toute autre opération, vous devez utiliser la méthode has pour confirmer si la collection contient un certain élément. La méthode hasOwnProperty est utilisée ici pour détecter.
Mise en œuvre :

/**
 * 检测集合内是否有某个元素
 * @param {Any} value  要检测的元素
 * @return {Boolean}    如果有，返回true
 */
this.has = function(value) {
 // hasOwnProperty的问题在于
 // 它是一个方法，所以可能会被覆写
 return items.hasOwnProperty(value)
};

ajouter une méthode :

Description : Ajouter un élément à la collection.
Mise en œuvre :

/**
 * 给集合内添加某个元素
 * @param {Any} value 要被添加的元素
 * @return {Boolean}    添加成功返回True。
 */
this.add = function(value) {
 //先检测元素是否存在。
 if (!this.has(value)) {
  items[value] = value;
  return true;
 }
 //如果元素已存在则返回false
 return false;
};

méthode de suppression :

Description : Supprimer un élément de la collection
Mise en œuvre :

/**
 * 移除集合中某个元素
 * @param {Any} value 要移除的元素
 * @return {Boolean}    移除成功返回True。
 */
this.remove = function(value) {
 //先检测元素是否存在。
 if (this.has(value)) {
  delete items[value];
  return true;
 }
 //如果元素不存在，则删除失败返回false
 return false;
};

méthode claire :
Description : Effacer la collection
Mise en œuvre :

/**
 * 清空集合
 */
this.clear = function() {
 this.items = {};
};

méthode de taille

Description : renvoie la longueur de la collection. Il existe deux méthodes ici. La première méthode utilise l'API Object.keys, mais ne prend en charge que IE9 et versions ultérieures. Le second fonctionne dans tous les navigateurs.
Mise en œuvre :

/**
 * 返回集合长度，只可用于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;
}

méthode des valeurs

Description : renvoie le tableau de conversion d'ensemble. Il existe deux méthodes ici. La raison est la même que ci-dessus. Object.keys est utilisé et ne peut prendre en charge que IE9 et versions ultérieures.
Mise en œuvre :

/**
 * 返回集合转换的数组，只可用于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;
};

méthode syndicale

Description : Renvoie l'union de deux ensembles
Mise en œuvre :

/**
 * 返回两个集合的并集
 * @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;
};

méthode d'intersection

Description : Renvoie l'intersection de deux ensembles
Mise en œuvre :

/**
 * 返回两个集合的交集
 * @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;
};

méthode de différence

Description : Renvoie la différence entre deux ensembles
Mise en œuvre :

/**
 * 返回两个集合的差集
 * @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;
};

méthode de sous-ensemble

Description : Déterminez si l'ensemble est un sous-ensemble de l'ensemble entrant. Après avoir fini d'écrire ce code, je l'ai comparé à celui du livre et j'ai senti qu'il était super faible. Celui que j'ai écrit nécessite de parcourir le tableau trois fois, tandis que celui du livre n'en a besoin qu'une seule fois, et la complexité de l'algorithme est bien inférieure à la mienne.
Mise en œuvre :

/**
 * 判断该集合是否为传入集合的子集
 * @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;
 }
};

Collections dans ES6

ES6 fournit également des collections, mais j'ai toujours été dérouté par les opérations de collecte d'ES6 auparavant. Après l’avoir implémenté et revu, j’ai senti que le concept était beaucoup plus clair.
Je n'ai pas une bonne compréhension des détails. J'apprends encore, donc je ne l'écrirai pas. Je recommande de lire l'introduction à ES6 Set dans "Introduction à ECMAScript 6" du professeur Ruan Yifeng.
"Introduction à ECMAScript 6" – Définir et mapper les structures de données

Impressions

À ce stade, vous maîtrisez certaines structures de données de base. Le reste est difficile à résoudre (pour moi).

Tables de hachage de dictionnaire, graphiques, arbres et algorithmes de tri. Il est considéré comme les Quatre King Kong, c'est pourquoi la récente série d'articles sur les structures de données et les algorithmes peut être mise à jour très lentement. Pour moi, c'est aussi un obstacle. J'espère pouvoir surmonter cet obstacle pendant les vacances d'hiver.