8 общих структур данных в Javascript
![](/static/storage/22523806971011866882301392955941865930.png)
Возможно, вы хотите улучшить свои фундаментальные знания в области компьютерных наук, особенно в области структуры данных и алгоритмов. Сегодня мы рассмотрим некоторые общие структуры данных и реализуем их в JavaScript.
Надеюсь, эта часть дополнит ваши навыки!
1. Стек
![](/static/storage/326908442502057244585451892240621176647.png)
Стек следует принципу LIFO (Last In First Out). Если вы складываете книги, верхняя книга берется перед нижней. Или, когда вы просматриваете Интернет, кнопка «Назад» ведет к последней просмотренной странице.
Стек имеет следующие распространенные методы:
push
: введите новый элементpop
: удалить верхний элемент, вернуть удаленный элементpeek
: вернуть верхний элемент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. Очередь
![](/static/storage/190216727274882526892227035664178876541.png)
Очередь похожа на стек. Единственное отличие состоит в том, что в очереди используется принцип FIFO («первым вошел - первым вышел»). Другими словами, когда вы стоите в очередь на автобус, первый в очереди всегда будет первым.
В очереди есть следующие методы:
enqueue
: введите очередь, добавьте элемент в концеdequeue
: покинуть очередь, убрать передний элемент и вернуть егоfront
: получить первый элементisEmpty
: определить, пуста ли очередь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. Связанный список
![](/static/storage/100752621215833240054154731827725469404.png)
Связанный список буквально представляет собой цепочечную структуру данных, где каждый узел состоит из двух частей информации: данных узла и указателя на следующий узел. Связанный список и обычный массив являются линейными структурами данных с сериализованным хранилищем. Конечно, они также имеют различия:
![](/static/storage/305532409824546249206925748018533055680.png)
Односторонний связанный список обычно имеет следующие методы:
size
: Вернуть номер узла (ов)head
: Вернуть элемент головыadd
: Добавить еще один узел в хвостremove
: Удалить определенный узелindexOf
: Вернуть индекс узлаelementAt
: Вернуть узел индексаaddAt
: Вставить узел по определенному индексу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
![](/static/storage/183445680583587390617164259697445074376.png)
Набор является основным понятием в математике: набор четко определенных и отличных объектов. ES6 ввел понятие множества, которое имеет определенный уровень сходства с массивом. Однако набор не позволяет повторять элементы и не индексируется.
Типичный набор имеет следующие методы:
values
: Вернуть все элементы в набореsize
: Вернуть количество элементовhas
: Определить, существует ли элементadd
: Вставить элементы в наборremove
: Удалить элементы из набораunion
: Вернуть пересечение двух множествdifference
: Вернуть разницу двух комплектов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. Хеш-таблица
![](/static/storage/118512806164529632348707512048307660443.png)
Хеш-таблица - это структура данных ключ-значение. Из-за молниеносной скорости запроса значения через ключ оно обычно используется в структурах данных Map, Dictionary или Object. Как показано на приведенном выше графике, в хэш-таблице используется hash function
для преобразования ключей в список чисел, и эти числа служат значениями соответствующих ключей. Чтобы получить значение с помощью ключа невероятно быстро, временная сложность может достичь O(1). Одни и те же ключи должны возвращать одинаковые значения - это основа хеш-функции.
Хеш-таблица имеет следующие методы:
add
: Добавить пару ключ-значениеremove
: Удалить пару ключ-значение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. Дерево
![](/static/storage/243806343770843104993661002379297376434.png)
Древовидная структура данных является многослойной структурой. Это также нелинейная структура данных по сравнению с массивом, стеком и очередью. Эта структура очень эффективна во время операций вставки и поиска. Давайте посмотрим на некоторые концепции древовидной структуры данных:
root
: Корневой узел дерева, нет родительского узла для корняparent node
: Прямой узел верхнего слоя, только одинchild node
: Прямой узел (узлы) нижнего уровня, может иметь несколькоsiblings
: Общий родительский узелleaf
: Узел без потомкаEdge
: Ветвь или связь между узламиPath
: Ребра от начального узла до целевого узлаHeight of Node
: Число ребер самого длинного пути конкретного узла к конечному узлуHeight of Tree
: Число ребер самого длинного пути корневого узла к листовому узлуDepth of Node
: Количество ребер от корневого узла до определенного узлаDegree of Node
: Количество дочерних узлов
Вот пример бинарного дерева поиска. Каждый узел имеет максимум два узла, причем левый узел меньше текущего узла, а правый узел больше текущего узла:
![](/static/storage/328897561833089551734793923770600682761.png)
Общие методы в бинарном дереве поиска:
add
: Вставить узел в деревоfindMin
: Получить минимальный узелfindMax
: Получить максимальный узелfind
: Поиск определенного узлаisPresent
: Определить существование определенного узла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”)
![](/static/storage/123535357326768858121411067694039255826.png)
Trie, или «дерево префиксов», также является типом дерева поиска. Trie хранит данные пошагово - каждый узел в дереве представляет шаг. Trie используется для хранения словаря, поэтому его можно быстро найти, особенно для функции автозаполнения.
Каждый узел в Trie имеет алфавит - следующая ветвь может образовывать целое слово. Он также содержит логический индикатор, чтобы показать, является ли это последний алфавит.
Три имеет следующие методы:
add
: Вставить слово в дерево словаряisWord
: Определить, состоит ли дерево из определенного слова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. Граф
Граф, иногда известный как сеть, относится к наборам узлов со связями (или ребрами). Это может быть далее разделено на две группы (то есть ориентированные графы и неориентированные графы), согласно тому, имеют ли связи направление. График широко используется в нашей жизни - для расчета лучшего маршрута в навигационных приложениях или для рекомендованных друзей в социальных сетях, чтобы взять два примера.
Граф имеет два типа представления:
Список смежности
В этом методе мы перечисляем все возможные узлы слева и показываем связанные узлы справа.
![](/static/storage/133874340826710453945922921481143595112.png)
Матрица смежности
Матрица смежности показывает узлы в строке и столбце, пересечения строки и столбца интерпретируют взаимосвязь между узлами, 0 означает, что нет связи, 1 означает, что связано, > 1 означает различный вес.
![](/static/storage/302024992421208603911238619325301740209.png)
Для запроса узлов в графе необходимо выполнить поиск по всей древовидной сети с помощью метода 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. Это должно дать вам лучшее представление о том, как структуры данных работают в компьютерах. Удачного кодирования!