DevGang
Авторизоваться

8 общих структур данных в Javascript 

Возможно, вы хотите улучшить свои фундаментальные знания в области компьютерных наук, особенно в области структуры данных и алгоритмов. Сегодня мы рассмотрим некоторые общие структуры данных и реализуем их в JavaScript.

Надеюсь, эта часть дополнит ваши навыки!

1. Стек

Стек следует принципу LIFO (Last In First Out). Если вы складываете книги, верхняя книга берется перед нижней. Или, когда вы просматриваете Интернет, кнопка «Назад» ведет к последней просмотренной странице.

Стек имеет следующие распространенные методы:

  1. push: введите новый элемент
  2. pop : удалить верхний элемент, вернуть удаленный элемент
  3. peek : вернуть верхний элемент
  4. length : вернуть количество элементов в стеке

Массив в Javascript имеет атрибуты стека, но мы создаем стек с нуля, используя function Stack()

function Stack () { 
this.count = 0; 
  this.storage = {}; 

  this.push = function (value) { 
    this.storage [this.count] = value; 
    this.count ++; 
  } 

  this.pop = function () { 
    if (this.count === 0) { 
      return undefined; 
    } 
    this.count--; 
    var result = this.storage [this.count]; 
    удалить this.storage [this.count]; 
    вернуть результат; 
  } 

  this.peek = function () { 
    return this.storage [this.count - 1]; 
  } 

  this.size = function () { 
    return this.count; 
  } 
}

2. Очередь

Очередь похожа на стек. Единственное отличие состоит в том, что в очереди используется принцип FIFO («первым вошел - первым вышел»). Другими словами, когда вы стоите в очередь на автобус, первый в очереди всегда будет первым.

В очереди есть следующие методы:

  1. enqueue: введите очередь, добавьте элемент в конце
  2. dequeue: покинуть очередь, убрать передний элемент и вернуть его
  3. front: получить первый элемент
  4. isEmpty: определить, пуста ли очередь
  5. size: получить количество элементов в очереди

Массив в JavaScript имеет некоторые атрибуты очереди, поэтому мы можем использовать массив для построения примера для очереди:

function Queue () { 
  var collection = []; 
  this.print = function () { 
    console.log (collection); 
  } 
  this.enqueue = function (element) { 
    collection.push (element); 
  } 
  this.dequeue = function () { 
    return collection.shift (); 
  } 
  this.front = function () { 
    return collection [0]; 
  } 

  this.isEmpty = function () { 
    return collection.length === 0; 
  } 
  this.size = function () { 
    return collection.length; 
  } 
}

Очередь с приоритетом

В очереди есть еще одна продвинутая версия. Выделите каждый элемент с приоритетом, и он будет отсортирован в соответствии с уровнем приоритета:

function PriorityQueue() {

  ...

  this.enqueue = function (element) {
    if (this.isEmpty()) {
      collection.push(element);
    } else {
      var added = false;
      for (var i = 0; i < collection.length; i++) {
        if (element[1] < collection[i][1]) {
          collection.splice(i, 0, element);
          added = true;
          break;
        }
      }
      if (!added) {
        collection.push(element);
      }
    }
  }
}

Тестируем:

var pQ = new PriorityQueue();
pQ.enqueue([ gannicus , 3]);
pQ.enqueue([ spartacus , 1]);
pQ.enqueue([ crixus , 2]);
pQ.enqueue([ oenomaus , 4]);
pQ.print();

Результат:

[
  [  spartacus , 1 ],
  [  crixus , 2 ],
  [  gannicus , 3 ],
  [  oenomaus , 4 ]
]

3. Связанный список

Связанный список буквально представляет собой цепочечную структуру данных, где каждый узел состоит из двух частей информации: данных узла и указателя на следующий узел. Связанный список и обычный массив являются линейными структурами данных с сериализованным хранилищем. Конечно, они также имеют различия:

Односторонний связанный список обычно имеет следующие методы:

  1. size: Вернуть номер узла (ов)
  2. head: Вернуть элемент головы
  3. add: Добавить еще один узел в хвост
  4. remove: Удалить определенный узел
  5. indexOf: Вернуть индекс узла
  6. elementAt: Вернуть узел индекса
  7. addAt: Вставить узел по определенному индексу
  8. removeAt: Удалить узел по определенному индексу
/** Node in the linked list **/
function Node(element) {  
    // Data in the node
    this.element = element;  
    // Pointer to the next node 
    this.next = null;
}
    function LinkedList() {  
        var length = 0;  
        var head = null;  
        this.size = function () {    
            return length;  
        }  
        this.head = function () {    
            return head;  
        }  
        this.add = function (element) {    
            var node = new Node(element);    
            if (head == null) {      
                head = node;    
            } else {      
                var currentNode = head;      
                while (currentNode.next) {        
                    currentNode = currentNode.next;      
                }      
                currentNode.next = node;    
            }    
            length++;  
        }  
        this.remove = function (element) {    
            var currentNode = head;    
            var previousNode;    
            if (currentNode.element === element) {      
                head = currentNode.next;    
            } else {      
                while (currentNode.element !== element) {        
                    previousNode = currentNode;        
                    currentNode = currentNode.next;      
                }      
                previousNode.next = currentNode.next;    
            }    
            length--;  
        }  
        this.isEmpty = function () {    
            return length === 0;  
        }  
        this.indexOf = function (element) {    
            var currentNode = head;    
            var index = -1;    
            while (currentNode) {      
                index++;      
                if (currentNode.element === element) {        
                    return index;      
                }      
                currentNode = currentNode.next;    
            }    
            return -1;  
        }  
        this.elementAt = function (index) {    
            var currentNode = head;    
            var count = 0;    
            while (count < index) {      
                count++;      
                currentNode = currentNode.next;    
            }    
            return currentNode.element;  
        }  
        this.addAt = function (index, element) {    
            var node = new Node(element);    
            var currentNode = head;    
            var previousNode;    
            var currentIndex = 0;    
            if (index > length) {      
                return false;    
            }    
            if (index === 0) {      
                node.next = currentNode;      
                head = node;    
            } else {      
                while (currentIndex < index) {        
                    currentIndex++;        
                    previousNode = currentNode;        
                    currentNode = currentNode.next;      
                }      
                node.next = currentNode;      
                previousNode.next = node;    
            }    
            length++;  
        }  
        this.removeAt = function (index) {    
            var currentNode = head;    
            var previousNode;    
            var currentIndex = 0;    
            if (index < 0 || index >= length) {      
                return null;    
            }    
            if (index === 0) {      
                head = currentIndex.next;    
            } else {      
                while (currentIndex < index) {        
                    currentIndex++;        
                    previousNode = currentNode;        
                    currentNode = currentNode.next;      
                }      
                previousNode.next = currentNode.next;    
            }    
            length--;    
            return currentNode.element;  
        }
    }

4. Set

Набор является основным понятием в математике: набор четко определенных и отличных объектов. ES6 ввел понятие множества, которое имеет определенный уровень сходства с массивом. Однако набор не позволяет повторять элементы и не индексируется.

Типичный набор имеет следующие методы:

  1. values: Вернуть все элементы в наборе
  2. size: Вернуть количество элементов
  3. has: Определить, существует ли элемент
  4. add: Вставить элементы в набор
  5. remove: Удалить элементы из набора
  6. union: Вернуть пересечение двух множеств
  7. difference: Вернуть разницу двух комплектов
  8. subset: Определить, является ли определенный набор подмножеством другого набора

Чтобы дифференцировать set в ES6, мы объявляем как MySet в следующем примере:

function MySet() {  
    var collection = [];  
    this.has = function (element) {    
        return (collection.indexOf(element) !== -1);  
    }  
    this.values = function () {    
        return collection;  
    }  
    this.size = function () {    
        return collection.length;  
    }  
    this.add = function (element) {    
        if (!this.has(element)) {      
            collection.push(element);      
            return true;    
        }    
        return false;  
    }  
    this.remove = function (element) {    
        if (this.has(element)) {      
            index = collection.indexOf(element);      
            collection.splice(index, 1);      
            return true;    
        }    
        return false;  
    }  
    this.union = function (otherSet) {    
        var unionSet = new MySet();    
        var firstSet = this.values();    
        var secondSet = otherSet.values();    
        firstSet.forEach(function (e) {      
            unionSet.add(e);    
        });    
        secondSet.forEach(function (e) {      
            unionSet.add(e);    
        });    
        return unionSet;  }  
        this.intersection = function (otherSet) {    
            var intersectionSet = new MySet();    
            var firstSet = this.values();    
            firstSet.forEach(function (e) {      
                if (otherSet.has(e)) {        
                    intersectionSet.add(e);      
                }    
            });    
            return intersectionSet;  
        }  
        this.difference = function (otherSet) {    
            var differenceSet = new MySet();    
            var firstSet = this.values();    
            firstSet.forEach(function (e) {      
                if (!otherSet.has(e)) {        
                    differenceSet.add(e);      
                }    
            });    
            return differenceSet;  
        }  
        this.subset = function (otherSet) {    
            var firstSet = this.values();    
            return firstSet.every(function (value) {      
                return otherSet.has(value);    
            });  
        }
    }

5. Хеш-таблица

Хеш-таблица - это структура данных ключ-значение. Из-за молниеносной скорости запроса значения через ключ оно обычно используется в структурах данных Map, Dictionary или Object. Как показано на приведенном выше графике, в хэш-таблице используется hash function для преобразования ключей в список чисел, и эти числа служат значениями соответствующих ключей. Чтобы получить значение с помощью ключа невероятно быстро, временная сложность может достичь O(1). Одни и те же ключи должны возвращать одинаковые значения - это основа хеш-функции.

Хеш-таблица имеет следующие методы:

  1. add: Добавить пару ключ-значение
  2. remove: Удалить пару ключ-значение
  3. lookup: Найти соответствующее значение с помощью ключа

Пример упрощенной хеш-таблицы в Javascript:

function hash(string, max) {
  var hash = 0;
  for (var i = 0; i < string.length; i++) {
    hash += string.charCodeAt(i);
  }
  return hash % max;
}

function HashTable() {
  let storage = [];
  const storageLimit = 4;

  this.add = function (key, value) {
    var index = hash(key, storageLimit);
    if (storage[index] === undefined) {
      storage[index] = [
        [key, value]
      ];
    } else {
      var inserted = false;
      for (var i = 0; i < storage[index].length; i++) {
        if (storage[index][i][0] === key) {
          storage[index][i][1] = value;
          inserted = true;
        }
      }
      if (inserted === false) {
        storage[index].push([key, value]);
      }
    }
  }

  this.remove = function (key) {
    var index = hash(key, storageLimit);
    if (storage[index].length === 1 && storage[index][0][0] === key) {
      delete storage[index];
    } else {
      for (var i = 0; i < storage[index]; i++) {
        if (storage[index][i][0] === key) {
          delete storage[index][i];
        }
      }
    }
  }

  this.lookup = function (key) {
    var index = hash(key, storageLimit);
    if (storage[index] === undefined) {
      return undefined;
    } else {
      for (var i = 0; i < storage[index].length; i++) {
        if (storage[index][i][0] === key) {
          return storage[index][i][1];
        }
      }
    }
  }
}

6. Дерево

Древовидная структура данных является многослойной структурой. Это также нелинейная структура данных по сравнению с массивом, стеком и очередью. Эта структура очень эффективна во время операций вставки и поиска. Давайте посмотрим на некоторые концепции древовидной структуры данных:

  1. root: Корневой узел дерева, нет родительского узла для корня
  2. parent node: Прямой узел верхнего слоя, только один
  3. child node: Прямой узел (узлы) нижнего уровня, может иметь несколько
  4. siblings: Общий родительский узел
  5. leaf: Узел без потомка
  6. Edge: Ветвь или связь между узлами
  7. Path: Ребра от начального узла до целевого узла
  8. Height of Node: Число ребер самого длинного пути конкретного узла к конечному узлу
  9. Height of Tree: Число ребер самого длинного пути корневого узла к листовому узлу
  10. Depth of Node: Количество ребер от корневого узла до определенного узла
  11. Degree of Node: Количество дочерних узлов

Вот пример бинарного дерева поиска. Каждый узел имеет максимум два узла, причем левый узел меньше текущего узла, а правый узел больше текущего узла:

Общие методы в бинарном дереве поиска:

  1. add: Вставить узел в дерево
  2. findMin: Получить минимальный узел
  3. findMax: Получить максимальный узел
  4. find: Поиск определенного узла
  5. isPresent: Определить существование определенного узла
  6. remove: Удалить узел из дерева

Пример в JavaScript:

class Node {
  constructor(data, left = null, right = null) {
    this.data = data;
    this.left = left;
    this.right = right;
  }
}

class BST {
  constructor() {
    this.root = null;
  }

  add(data) {
    const node = this.root;
    if (node === null) {
      this.root = new Node(data);
      return;
    } else {
      const searchTree = function (node) {
        if (data < node.data) {
          if (node.left === null) {
            node.left = new Node(data);
            return;
          } else if (node.left !== null) {
            return searchTree(node.left);
          }
        } else if (data > node.data) {
          if (node.right === null) {
            node.right = new Node(data);
            return;
          } else if (node.right !== null) {
            return searchTree(node.right);
          }
        } else {
          return null;
        }
      };
      return searchTree(node);
    }
  }

  findMin() {
    let current = this.root;
    while (current.left !== null) {
      current = current.left;
    }
    return current.data;
  }

  findMax() {
    let current = this.root;
    while (current.right !== null) {
      current = current.right;
    }
    return current.data;
  }

  find(data) {
    let current = this.root;
    while (current.data !== data) {
      if (data < current.data) {
        current = current.left
      } else {
        current = current.right;
      }
      if (current === null) {
        return null;
      }
    }
    return current;
  }

  isPresent(data) {
    let current = this.root;
    while (current) {
      if (data === current.data) {
        return true;
      }
      if (data < current.data) {
        current = current.left;
      } else {
        current = current.right;
      }
    }
    return false;
  }

  remove(data) {
    const removeNode = function (node, data) {
      if (node == null) {
        return null;
      }
      if (data == node.data) {
        // no child node
        if (node.left == null && node.right == null) {
          return null;
        }
        // no left node
        if (node.left == null) {
          return node.right;
        }
        // no right node
        if (node.right == null) {
          return node.left;
        }
        // has 2 child nodes
        var tempNode = node.right;
        while (tempNode.left !== null) {
          tempNode = tempNode.left;
        }
        node.data = tempNode.data;
        node.right = removeNode(node.right, tempNode.data);
        return node;
      } else if (data < node.data) {
        node.left = removeNode(node.left, data);
        return node;
      } else {
        node.right = removeNode(node.right, data);
        return node;
      }
    }
    this.root = removeNode(this.root, data);
  }
}

Тестируем:

const bst = new BST();
bst.add(4);
bst.add(2);
bst.add(6);
bst.add(1);
bst.add(3);
bst.add(5);
bst.add(7);
bst.remove(4);
console.log(bst.findMin());
console.log(bst.findMax());
bst.remove(7);
console.log(bst.findMax());
console.log(bst.isPresent(4));

Результат:

1
7
6
false

7. Trie (произносится “try”)

Trie, или «дерево префиксов», также является типом дерева поиска. Trie хранит данные пошагово - каждый узел в дереве представляет шаг. Trie используется для хранения словаря, поэтому его можно быстро найти, особенно для функции автозаполнения.

Каждый узел в Trie имеет алфавит - следующая ветвь может образовывать целое слово. Он также содержит логический индикатор, чтобы показать, является ли это последний алфавит.

Три имеет следующие методы:

  1. add: Вставить слово в дерево словаря
  2. isWord: Определить, состоит ли дерево из определенного слова
  3. print: Вернуть все слова в дереве
/** Node in Trie **/
function Node() {  
    this.keys = new Map();  
    this.end = false;  
    this.setEnd = function () {    
        this.end = true;  
    };  
    this.isEnd = function () {    
        return this.end;  
    }
}

function Trie() {  
        this.root = new Node();  
        this.add = function (input, node = this.root) {    
            if (input.length === 0) {     
                node.setEnd();      
                return;    
            } else if (!node.keys.has(input[0])) {      
                node.keys.set(input[0], new Node());      
                return this.add(input.substr(1), node.keys.get(input[0]));    
            } else {      
                return this.add(input.substr(1), node.keys.get(input[0]));    
            }  
        }  
        this.isWord = function (word) {    
            let node = this.root;    
            while (word.length > 1) {      
                if (!node.keys.has(word[0])) {        
                    return false;      
                } else {        
                    node = node.keys.get(word[0]);       
                    word = word.substr(1);      
                }    
            }    
            return (node.keys.has(word) && node.keys.get(word).isEnd()) ? true : false;  
        }  
            this.print = function () {    
                let words = new Array();    
                let search = function (node = this.root, string) {      
                    if (node.keys.size != 0) {        
                        for (let letter of node.keys.keys()) {          
                            search(node.keys.get(letter), string.concat(letter));        
                        }        
                        if (node.isEnd()) {          
                            words.push(string);        
                        }      
                    } else {        
                        string.length > 0 ? words.push(string) : undefined;        
                        return;      
                    }    
                };    
                search(this.root, new String());    
                return words.length > 0 ? words : null;  
    }
}

8. Граф

Граф, иногда известный как сеть, относится к наборам узлов со связями (или ребрами). Это может быть далее разделено на две группы (то есть ориентированные графы и неориентированные графы), согласно тому, имеют ли связи направление. График широко используется в нашей жизни - для расчета лучшего маршрута в навигационных приложениях или для рекомендованных друзей в социальных сетях, чтобы взять два примера.

Граф имеет два типа представления:

Список смежности

В этом методе мы перечисляем все возможные узлы слева и показываем связанные узлы справа.

Матрица смежности

Матрица смежности показывает узлы в строке и столбце, пересечения строки и столбца интерпретируют взаимосвязь между узлами, 0 означает, что нет связи, 1 означает, что связано, > 1 означает различный вес.

Для запроса узлов в графе необходимо выполнить поиск по всей древовидной сети с помощью метода Breath-First-Search (BFS) или метода Depth-First-Search (DFS).

Давайте посмотрим пример BFS в Javascript:

function bfs(graph, root) {
  var nodesLen = {};
  for (var i = 0; i < graph.length; i++) {
    nodesLen[i] = Infinity;
  }
  nodesLen[root] = 0;
  var queue = [root];
  var current;
  while (queue.length != 0) {
    current = queue.shift();

    var curConnected = graph[current];
    var neighborIdx = [];
    var idx = curConnected.indexOf(1);
    while (idx != -1) {
      neighborIdx.push(idx);
      idx = curConnected.indexOf(1, idx + 1);
    }
    for (var j = 0; j < neighborIdx.length; j++) {
      if (nodesLen[neighborIdx[j]] == Infinity) {
        nodesLen[neighborIdx[j]] = nodesLen[current] + 1;
        queue.push(neighborIdx[j]);
      }
    }
  }
  return nodesLen;
}

Тестируем:

var graph = [
  [0, 1, 1, 1, 0],
  [0, 0, 1, 0, 0],
  [1, 1, 0, 0, 0],
  [0, 0, 0, 1, 0],
  [0, 1, 0, 0, 0]
];
console.log(bfs(graph, 1));

Результат:

{
  0: 2,
  1: 0,
  2: 1,
  3: 3,
  4: Infinity
}

Вот и все - мы рассмотрели все распространенные структуры данных и привели примеры в JavaScript. Это должно дать вам лучшее представление о том, как структуры данных работают в компьютерах. Удачного кодирования!

Источник:

#JavaScript
Комментарии
Чтобы оставить комментарий, необходимо авторизоваться

Присоединяйся в тусовку

Поделитесь своим опытом, расскажите о новом инструменте, библиотеке или фреймворке. Для этого не обязательно становится постоянным автором.

Попробовать

Оплатив хостинг 25$ в подарок вы получите 100$ на счет

Получить