Sammlung von JavaScript-Datenstrukturen und -Algorithmen (Set)_Grundkenntnisse

Einstellen

Apropos Mengen: Ich erinnere mich, dass es in der ersten Mathematikstunde, als ich in die Highschool kam, um Mengen ging. Daher fühlt es sich beim Erlernen der Datenstruktur von Sammlungen intimer an.
Es gibt eine grundlegende Eigenschaft von Mengen: Die Elemente in der Menge werden nicht wiederholt. Aufgrund dieser Eigenschaft haben wir Objekte als Container für Sammlungen anstelle von Arrays ausgewählt.
Obwohl Arrays auch alle Nichtwiederholungen erreichen können, sind sie letztendlich zu umständlich und nicht so gut wie Sammlungen.

Inkassotätigkeiten

Zu den Grundoperationen von Mengen gehören Schnittmenge, Vereinigung, Differenz usw. Hier stellen wir die Implementierung von Schnittmenge, Vereinigung und Differenz in JavaScipt-Sammlungen vor.

Implementierung von Sammlungen in JavaScipt

Erstellen Sie zunächst einen Konstruktor.

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

Die Sammlung muss über die folgenden Methoden verfügen:

1. has(value): Überprüfen Sie, ob ein Element in der Sammlung vorhanden ist
2. add(value): Füge ein Element zur Sammlung hinzu
3. remove(value): Entferne ein Element aus der Sammlung
4. clear(value): Lösche die Sammlung
5. size(): Gibt die Länge der Sammlung zurück
6. values(): Gibt das aus der Menge konvertierte Array zurück
7. union(otherSet): Gibt die Vereinigung zweier Mengen zurück
8. intersection(otherSet): Gibt den Schnittpunkt zweier Mengen zurück
9. difference(otherSet): Gibt die Differenz zwischen zwei Mengen zurück
10. subset(otherSet): Bestimmen Sie, ob die Menge eine Teilmenge der eingehenden Menge ist

hat Methode:

Hinweis: Die Elemente im Set werden nicht wiederholt. Daher müssen Sie vor allen anderen Vorgängen die Methode has verwenden, um zu bestätigen, ob die Sammlung ein bestimmtes Element enthält. Zur Erkennung wird hier die hasOwnProperty-Methode verwendet.
Umsetzung:

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

Methode hinzufügen:

Beschreibung: Ein Element zur Sammlung hinzufügen.
Umsetzung:

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

Entfernungsmethode:

Beschreibung: Ein Element aus der Sammlung entfernen
Umsetzung:

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

klare Methode:
Beschreibung: Sammlung löschen
Umsetzung:

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

Größenmethode

Beschreibung: Gibt die Länge der Sammlung zurück. Hier gibt es zwei Methoden. Die erste Methode verwendet die Object.keys-API, unterstützt jedoch nur IE9 und höher. Der zweite funktioniert in allen Browsern.
Umsetzung:

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

Wertemethode

Beschreibung: Gibt das Array der Mengenkonvertierung zurück. Hier gibt es zwei Methoden. Der Grund ist derselbe wie oben. Object.keys wird verwendet und kann nur IE9 und höher unterstützen.
Umsetzung:

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

Vereinigungsmethode

Beschreibung: Gibt die Vereinigung zweier Mengen zurück
Umsetzung:

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

Schnittmethode

Beschreibung: Gibt den Schnittpunkt zweier Mengen zurück
Umsetzung:

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

Differenzmethode

Beschreibung: Gibt die Differenz zwischen zwei Sätzen zurück
Umsetzung:

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

Teilmengenmethode

Beschreibung: Bestimmen Sie, ob die Menge eine Teilmenge der eingehenden Menge ist. Nachdem ich diesen Code fertig geschrieben hatte, verglich ich ihn mit dem im Buch und fand, dass er sehr niedrig war. Der von mir geschriebene erfordert das dreimalige Durchlaufen des Arrays, während der im Buch nur einmal benötigt wird und die Komplexität des Algorithmus weitaus geringer ist als bei mir.
Umsetzung:

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

Sammlungen in ES6

ES6 bietet auch Sammlungen, aber die Sammlungsvorgänge von ES6 haben mich bisher immer verwirrt. Nachdem ich es umgesetzt und noch einmal angeschaut hatte, hatte ich das Gefühl, dass das Konzept viel klarer war.
Ich habe noch kein gutes Verständnis für die Einzelheiten, daher werde ich es nicht aufschreiben. Ich empfehle, die Einführung in das ES6-Set in „Einführung in ECMAScript 6“ zu lesen.
„Einführung in ECMAScript 6“ – Datenstrukturen festlegen und zuordnen

Impressionen

An diesem Punkt beherrschen Sie einige grundlegende Datenstrukturen. Der Rest ist (für mich) eine harte Nuss.

Wörterbuch-Hash-Tabellen, Diagramme, Bäume und Sortieralgorithmen. Es gilt als die vier King Kongs, daher wird die aktuelle Artikelserie zu Datenstrukturen und Algorithmen möglicherweise nur sehr langsam aktualisiert. Für mich ist es auch eine Hürde. Ich hoffe, dass ich diese Hürde in diesem Winterurlaub überwinden kann.