1. Что такое структура данных?
Структура данных — это особый способ организации и хранения данных в компьютере, обеспечивающий эффективный доступ к ним и их изменение. Точнее, структура данных — это набор значений данных, который представляет отношения между данными, а также включает в себя функции или операции, воздействующие на данные.
1.1 Зачем нужны структуры данных?
- Данные являются наиболее важной сущностью в компьютерных науках, и структура данных может хранить данные в определенной организации, поэтому ценность структуры данных очевидна.
- Независимо от того, как вы решаете какую-либо проблему, вам необходимо работать с данными — будь то зарплата сотрудников, курсы акций, списки покупок или просто проблема с телефонной книгой.
- Данные должны храниться в определенном формате в соответствии с различными сценариями. Существует множество структур данных, которые удовлетворяют потребность в хранении данных в различных форматах.
1.2 Восемь общих структур данных
- множество:
Array - куча:
Stack - очередь:
Queue - Связанный список:
Linked Lists - Дерево:
Trees - картина:
Graphs - Дерево словаря:
Trie - Хэш-таблица (хеш-таблица):
Hash Tables
На высоком уровне существует в основном три типа структур данных:
- Стеки и очереди — это структуры, подобные массивам, которые отличаются только тем, как элементы вставляются и удаляются.
- Узлы в структурах связанных списков, деревьев и графов являются ссылками на другие узлы.
- Хэш-таблицы полагаются на хэш-функции для хранения и поиска данных.
По сложности:
- Стеки и очереди являются самыми простыми, и из них можно строить связанные списки.
- Деревья и графы являются наиболее сложными, поскольку они расширяют концепцию связанных списков.
- Хэш-таблицы и словарные деревья должны использовать эти структуры данных для надежной работы.
Просто эффективность:
- Связанные списки — лучший выбор для записи и хранения данных
- Хэш-таблицы и словарные деревья лучше всего подходят для поиска и извлечения данных.
2. Массивы — дополнение к знаниям
Массивы — простейшая структура данных, поэтому я не буду вдаваться в подробности. Разместите картинку, где каждая функция выполняет 10 000 итераций:
- Сравнение эффективности выполнения 10 000 случайных ключей в массиве из 10 000 объектов:
[
{
id: "key0",
content: "I ate pizza 0 times"
},
{
id: "key1",
content: "I ate pizza 1 times"
},
{
id: "key2",
content: "I ate pizza 2 times"
},
...
]
["key284", "key958", "key23", "key625", "key83", "key9", ... ]
2.1 for... inПочему так медленно?
for... inСинтаксис невероятно медленный. Уже при тестировании цикл почти в 9 раз медленнее, чем обычно.
Это потому чтоfor ... inСинтаксис — это первая инструкция JavaScript, способная перебирать ключи объекта.
Клавиши объектов цикла ({}) и в массиве ([]) на петле по-разному,
Потому что движок выполняет некоторую дополнительную работу, чтобы отслеживать свойства, которые были итерированы.
3. Стек:Stack
Стек — это набор элементов, к которым элементы могут быть добавлены сверху, у нас есть несколько примеров реальных стеков:
- история браузера
- Отменить действие
- рекурсия и другие.
Три предложения объясняют стек:
- Работают два принципа:
pushа такжеpop.Pushдобавляет элемент в начало массива, аPopУдалите их из того же места. - следить"
Last In，First Out",который:LIFO, ЛИФО. - Ушел.
3.1 Реализация стека.
Обратите внимание, что в приведенном ниже примере мы можем изменить порядок стека: нижний становится верхним, верхний становится нижним.
Итак, мы можем использовать массив отдельноunshiftа такжеshiftметод вместо этогоpushа такжеpop.
class Stack {
constructor(...items) {
this.reverse = false;
this.stack = [...items];
}
push(...items) {
return this.reverse
? this.stack.unshift(...items)
: this.stack.push(...items);
}
pop() {
return this.reverse ? this.stack.shift() : this.stack.pop();
}
}
const stack = new Stack(4, 5);
stack.reverse = true;
console.log(stack.push(1, 2, 3) === 5) // true
console.log(stack.stack ===[1, 2, 3, 4, 5]) // true
4. Очередь:Queue
В информатике очередь — это особый тип абстрактного типа данных или коллекции. Объекты в коллекции содержатся в порядке.
Во фронтенд-разработке самое известное использование очередей — это знания о макрозадачах, микрозадачах и очередях задач в браузерах/NodeJ. Я не буду здесь вдаваться в подробности.
В бэкенде наиболее широко используется очередь сообщений:Message queue:Такие какRabbitMQ,ActiveMQЖдать.
С точки зрения мышления программирования,QueueЕго можно описать двумя предложениями:
- Просто массив с двумя основными операциями:
unshiftа такжеpop. - следить
"Fist In，first out"который:FIFO, первым прибыл, первым обслужен.
4.1 Реализация очереди
Обратите внимание, что в следующем примере мы можем изменить порядок стека.
Итак, мы можем использовать массив отдельноunshiftа такжеshiftметод вместо этогоpushа такжеpop.
class Queue {
constructor(...items) {
this.reverse = false;
this.queue = [...items];
}
enqueue(...items) {
return this.reverse
? this.queue.push(...items)
: this.queue.unshift(...items);
}
dequeue() {
return this.reverse ? this.queue.shift() : this.queue.pop();
}
}
5. Связанный список:Linked Lists
Как и массивы, связанные списки хранят элементы данных последовательно.
Вместо индексов связанные списки указывают на другие элементы.
Первый узел называется головным (
head), а последний узел называется хвостом (tail).
Односвязный список и двусвязный список:
- Односвязный список — это структура данных, представляющая ряд узлов, где каждый узел указывает на следующий узел в списке.
- Связанные списки обычно требуют обхода всего списка операций, поэтому они менее производительны.
- Один из способов повысить производительность связанных списков — добавить второй указатель на каждый узел к предыдущему узлу в списке.
- В двусвязном списке есть узлы, указывающие на элементы до и после него.
Преимущества связанных списков:
- Ссылки имеют постоянное время вставки и удаления, потому что мы можем просто изменить указатель.
- Как и массивы, связанные списки могут работать как стеки.
Сценарии применения связанного списка:
Связанные списки полезны как на клиенте, так и на сервере.
- На клиенте что-то вроде
ReduxЛогика построена в виде связанного списка. -
Reactосновной алгоритмReact FiberРеализация представляет собой связанный список.
-
-
React FiberпредыдущийStack Reconciler, это рекурсия сверху внизmount/update, который не может быть прерван (постоянно занимает основной поток), поэтому периодические задачи, такие как макет, анимация и интерактивные ответы в основном потоке, не могут быть обработаны немедленно, что влияет на работу.
-
-
-
React Fiberразрешить прошлоеReconcilerИдея существующей проблемы состоит в том, чтобы разделить процесс рендеринга/обновления (рекурсивный diff) на серию небольших задач, каждый раз проверять небольшую часть дерева и смотреть, есть ли еще время для продолжения следующая задача после завершения. Если это так, приостановите себя и продолжите, когда основной поток не занят.
-
- На сервере что-то вроде
ExpressТакойWebФреймворки также строят свою логику промежуточного программного обеспечения аналогичным образом. Когда запрос получен, он передается от одного промежуточного ПО к другому до тех пор, пока не будет отправлен ответ.
5.1 Реализация односвязного списка
Основные операции односвязного списка:
-
push（value）- добавить узел в конец/начало связанного списка -
pop（）- удалить узел из конца/головы связанного списка -
get（index）- возвращает узел по указанному индексу -
delete（index）- удалить узел по указанному индексу -
isEmpty（）- Возвращает true или false в зависимости от длины списка -
print（）- возвращает видимое представление связанного списка
class Node {
constructor(data) {
this.data = data
this.next = null
}
}
class LinkedList {
constructor() {
this.head = null
this.tail = null
// 长度非必要
this.length = 0
}
push(data) {
// 创建一个新节点
const node = new Node(data)
// 检查头部是否为空
if (this.head === null) {
this.head = node
this.tail = node
}
this.tail.next = node
this.tail = node
this.length++
}
pop(){
// 先检查链表是否为空
if(this.isEmpty()) {
return null
}
// 如果长度为1
if (this.head === this.tail) {
this.head = null
this.tail = null
this.length--
return this.tail
}
let node = this.tail
let currentNode = this.head
let penultimate
while (currentNode) {
if (currentNode.next === this.tail) {
penultimate = currentNode
break
}
currentNode = currentNode.next
}
penultimate.next = null
this.tail = penultimate
this.length --
return node
}
get(index){
// 处理边界条件
if (index === 0) {
return this.head
}
if (index < 0 || index > this.length) {
return null
}
let currentNode = this.head
let i = 0
while(i < index) {
i++
currentNode = currentNode.next
}
return currentNode
}
delete(index){
let currentNode = this.head
if (index === 0) {
let deletedNode
currentNode.next = this.head
deletedNode = currentNode
this.length--
return deletedNode
}
if (index < 0 || index > this.length) {
return null
}
let i = 0
let previous
while(i < index) {
i++
previous = currentNode
currentNode = currentNode.next
}
previous.next = currentNode.next
this.length--
return currentNode
}
isEmpty() {
return this.length === 0
}
print() {
const list = []
let currentNode = this.head
while(currentNode){
list.push(currentNode.data)
currentNode = currentNode.next
}
return list.join(' => ')
}
}
есть тест:
const l = new LinkedList()
// 添加节点
const values = ['A', 'B', 'C']
values.forEach(value => l.push(value))
console.log(l)
console.log(l.pop())
console.log(l.get(1))
console.log(l.isEmpty())
console.log(l.print())
5.2 Реализация двусвязного списка
1. Дизайн двусвязного списка
Подобно односвязному списку, двусвязный список состоит из ряда узлов. Каждый узел содержит некоторые данные и указатель на следующий узел в списке и указатель на предыдущий узел. ЭтоJavaScriptПростое представление в:
class Node {
constructor(data) {
// data 包含链表项应存储的值
this.data = data;
// next 是指向列表中下一项的指针
this.next = null;
// prev 是指向列表中上一项的指针
this.prev = null;
}
}
Просто постучи еще раз:
class DoublyLinkedList {
constructor() {
this.head = null;
this.tail = null;
}
// 各种操作方法
// ...
}
2. Метод работы двусвязного списка
-
Append & AppendAt: добавьте узел в конце / указанное положение связанного списка
append( item ) {
let node = new Node( item );
if(!this.head) {
this.head = node;
this.tail = node;
} else {
node.prev = this.tail;
this.tail.next = node;
this.tail = node
}
}
appendAt( pos, item ) {
let current = this.head;
let counter = 1;
let node = new Node( item );
if( pos == 0 ) {
this.head.prev = node
node.next = this.head
this.head = node
} else {
while(current) {
current = current.next;
if( counter == pos ) {
node.prev = current.prev
current.prev.next = node
node.next = current
current.prev = node
}
counter++
}
}
}
-
Remove & RemoveAt: удалить узел в конце/указанной позиции связанного списка
remove( item ) {
let current = this.head;
while( current ) {
if( current.data === item ) {
if( current == this.head && current == this.tail ) {
this.head = null;
this.tail = null;
} else if ( current == this.head ) {
this.head = this.head.next
this.head.prev = null
} else if ( current == this.tail ) {
this.tail = this.tail.prev;
this.tail.next = null;
} else {
current.prev.next = current.next;
current.next.prev = current.prev;
}
}
current = current.next
}
}
removeAt( pos ) {
let current = this.head;
let counter = 1;
if( pos == 0 ) {
this.head = this.head.next;
this.head.prev = null;
} else {
while( current ) {
current = current.next
if ( current == this.tail ) {
this.tail = this.tail.prev;
this.tail.next = null;
} else if( counter == pos ) {
current.prev.next = current.next;
current.next.prev = current.prev;
break;
}
counter++;
}
}
}
-
Reverse: перевернуть двусвязный список
reverse(){
let current = this.head;
let prev = null;
while( current ){
let next = current.next
current.next = prev
current.prev = next
prev = current
current = next
}
this.tail = this.head
this.head = prev
}
-
Swap: Обмен между двумя узлами.
swap( nodeOne, nodeTwo ) {
let current = this.head;
let counter = 0;
let firstNode;
while( current !== null ) {
if( counter == nodeOne ){
firstNode = current;
} else if( counter == nodeTwo ) {
let temp = current.data;
current.data = firstNode.data;
firstNode.data = temp;
}
current = current.next;
counter++;
}
return true
}
-
IsEmpty & Length: Является ли запрос пустым или длинным.
length() {
let current = this.head;
let counter = 0;
while( current !== null ) {
counter++
current = current.next
}
return counter;
}
isEmpty() {
return this.length() < 1
}
-
Traverse: пройти по связанному списку
traverse( fn ) {
let current = this.head;
while( current !== null ) {
fn(current)
current = current.next;
}
return true;
}
-
Search: Найти индекс узла.
search( item ) {
let current = this.head;
let counter = 0;
while( current ) {
if( current.data == item ) {
return counter
}
current = current.next
counter++
}
return false;
}
6. Дерево:Tree
Нелинейная структура данных, часто используемая в компьютерах, дерево, часто используется для хранения данных с иерархическими отношениями, например, в файловой системе, из-за очевидных иерархических характеристик между всеми хранимыми в нем элементами. используется для хранения упорядоченных списков и т. д.
- В древовидной структуре каждый узел имеет только один родительский узел.Если узел не имеет родительского узла, он называется корневым узлом дерева или, для краткости, корнем дерева.
- Каждый узел может иметь несколько дочерних узлов.
- Узел без дочерних узлов называется листовым узлом.
- Количество дочерних узлов узла называется степенью узла.
- Максимальная степень всех узлов называется деревом. Максимальный уровень дерева называется глубиной дерева.
6.1 Классификация деревьев
Общие классификации деревьев следующие, в которых мы можем освоить двоичное дерево поиска.
- Бинарное дерево:
Binary Search Tree - АВЛ-дерево:
AVL Tree - Красно-черное дерево:
Red-Black Tree - Дерево сегментов:
Segment Tree- with min/max/sum range queries examples - Дерево Фенвика:
Fenwick Tree(Binary Indexed Tree)
6.2 Применение деревьев
-
DOMДерево. Каждая веб-страница имеет древовидную структуру данных.
2.
Vueа такжеReactизVirtual DOMТоже дерево.
6.3 Бинарное дерево:Binary Search Tree
- Бинарное дерево — это особый вид дерева, который имеет не более двух дочерних узлов.
- И называются они левым поддеревом (left subtree) и правым поддеревом (right subtree) узла соответственно.
- Двоичные деревья часто используются как бинарные деревья поиска и бинарные деревья поиска или как бинарные деревья сортировки (BST).
6.4 Обход бинарного дерева
Пройтись по всем узлам бинарного дерева по определенным правилам и порядку так, чтобы каждый узел посещался один и только один раз Эта операция называетсяобход дерева, является одной из самых основных операций над деревьями.
Поскольку бинарное дерево представляет собой нелинейную структуру, обход дерева, по сути, являетсяКаждый узел бинарного дерева преобразуется в линейную последовательностьПредставлять.
В соответствии с порядком доступа к корневому узлу обход бинарного дерева делится на следующие три типа: обход в прямом порядке, обход в порядке и обход в обратном порядке;
обход предварительного заказа:Pre-Order
корневой узел -> левое поддерево -> правое поддерево
Предварительный заказ:In-Order
Левое поддерево -> корневой узел -> правое поддерево
пост-порядковый обход:Post-Order
Левое поддерево -> правое поддерево -> корневой узел
Следовательно, мы можем получить результат обхода приведенного выше бинарного дерева следующим образом:
- Обход предварительного заказа: ABDEFGC
- Порядок обхода: DEBGFAC
- Обход после заказа: EDGFBCA
6.5 Реализация бинарного дерева
class Node {
constructor(data) {
this.left = null
this.right = null
this.value = data
}
}
class BST {
constructor() {
this.root = null
}
// 二叉树的各种操作
// insert(value) {...}
// insertNode(root, newNode) {...}
// ...
1. insertNode& insert: Вставить новый дочерний элемент/узел
insertNode(root, newNode) {
if (newNode.value < root.value) {
// 先执行无左节点操作
(!root.left) ? root.left = newNode : this.insertNode(root.left, newNode)
} else {
(!root.right) ? root.right = newNode : this.insertNode(root.right, newNode)
}
}
insert(value) {
let newNode = new Node(value)
// 如果没有根节点
if (!this.root) {
this.root = newNode
} else {
this.insertNode(this.root, newNode)
}
}
2. removeNode& remove: удалить дочерний элемент/узел
removeNode(root, value) {
if (!root) {
return null
}
// 从该值小于根节点开始判断
if (value < root.value) {
root.left = this.removeNode(root.left, value)
return root
} else if (value > root.value) {
root.right = tis.removeNode(root.right, value)
return root
} else {
// 如果没有左右节点
if (!root.left && !root.right) {
root = null
return root
}
// 存在左节点
if (root.left) {
root = root.left
return root
// 存在右节点
} else if (root.right) {
root = root.right
return root
}
// 获取正确子节点的最小值以确保我们有有效的替换
let minRight = this.findMinNode(root.right)
root.value = minRight.value
// 确保删除已替换的节点
root.right = this.removeNode(root.right, minRight.value)
return root
}
}
remove(value) {
if (!this.root) {
return 'Tree is empty!'
} else {
this.removeNode(this.root, value)
}
}
3. findMinNode: получить минимальное значение дочерних узлов
findMinNode(root) {
if (!root.left) {
return root
} else {
return this.findMinNode(root.left)
}
}
4. searchNode & search: найти дочерние узлы/узлы
searchNode(root, value) {
if (!root) {
return null
}
if (value < root.value) {
return this.searchNode(root.left, value)
} else if (value > root.value) {
return this.searchNode(root.right, value)
}
return root
}
search(value) {
if (!this.root) {
return 'Tree is empty'
} else {
return Boolean(this.searchNode(this.root, value))
}
}
-
Pre-Order: обход предварительного заказа
preOrder(root) {
if (!root) {
return 'Tree is empty'
} else {
console.log(root.value)
this.preOrder(root.left)
this.preOrder(root.right)
}
}
-
In-Order: обход по порядку
inOrder(root) {
if (!root) {
return 'Tree is empty'
} else {
this.inOrder(root.left)
console.log(root.value)
this.inOrder(root.right)
}
}
-
Post-Order: обход после заказа
postOrder(root) {
if (!root) {
return 'Tree is empty'
} else {
this.postOrder(root.left)
this.postOrder(root.right)
console.log(root.value)
}
}
7. Рисунок:Graph
Граф — это структура данных, состоящая из набора узлов с ребрами. Графики могут быть направленными и ненаправленными.
Вступление к картинке популярно, я нашел круг статей, и это лучшее:
7.1 Применение графиков
Вы используете графики в следующих сценариях:
- Используйте поисковые сервисы, такие как
Google, Байду. - использовать
LBSКартографические сервисы, такие как AutoNavi, Google Maps. - Используйте сайты социальных сетей, таких как Weibo,
Facebook.
Диаграммы используются в разных отраслях и областях:
-
GPSСистема и Карты Google используют графики для поиска кратчайшего пути от одного пункта назначения к другому. - Социальные сети используют графики для представления связей между пользователями.
-
GoogleАлгоритмы поиска используют графики для определения релевантности результатов поиска. - Исследование операций — это область, в которой графики используются для поиска наилучших способов снижения затрат на транспортировку и доставку товаров и услуг.
- Даже химия использует диаграммы для представления молекул!
Можно сказать, что графы являются одной из наиболее широко используемых структур данных, и в реальных сценах графы присутствуют повсюду.
7.2 Состав графиков
Диаграммы используются для представления, поиска, анализа и оптимизации связей между элементами (дома, аэропорты, места, пользователи, статьи и т. д.).
1. Основные элементы диаграммы
- узел:
Node, например, станция в метро/деревня в нескольких деревнях/хозяин в Интернете/человек в отношениях. - сторона:
Edge, например прямое соединение между двумя станциями на станции метро, является ребром.
2. Символы и терминология
-
|V|= общее количество вершин (узлов) в графе. -
|E|= общее количество соединений (ребер) в графе.
В примере ниже
|V| = 6
|E| = 7
3. Направленные и нерешенные графики
ФИГ классифицируется по их характеристикам краев (соединений).
1. Ориентированные графы
В ориентированном графе ребра имеют направления. Они идут от одного узла к другому, и нет возможности вернуться к исходному узлу через ребро.
Как показано на изображении ниже, ребра (соединения) теперь имеют стрелки, указывающие в определенных направлениях. Рассматривайте эти ребра как улицы с односторонним движением. Вы можете пойти в одном направлении и добраться до места назначения, но вы не можете вернуться по той же улице, поэтому вам нужно найти другой путь.
2. Неориентированный граф
В этом типе графа ребра неориентированы (у них нет определенного направления). Рассматривайте ненаправленные ребра как улицы с двусторонним движением. Вы можете перейти от одного узла к другому и вернуть тот же «путь».
4. Взвешенный график
Во взвешенном графе каждое ребро имеет связанное с ним значение (называемое весом). Это значение используется для представления некоторых измеримых отношений между узлами, к которым они подключены. Например:
- Веса могут представлять собой расстояние, время, количество связей между двумя пользователями в социальной сети.
- Или что-нибудь, что можно использовать для описания соединений между узлами в контексте, который вы используете.
известныйDijkstraАлгоритмы, использующие эти веса для оптимизации маршрутизации путем поиска кратчайшего или оптимального пути между узлами в сети.
5. ИНЖИР редкий и плотный фиг.
Когда количество ребер в графе близко к максимальному количеству ребер, граф является плотным.
Граф является разреженным, когда количество ребер в графе значительно меньше максимального количества ребер.
6. Петля
Если вы проследите ряд соединений на графике, вы можете найти путь, который приведет вас обратно к тому же узлу. Это похоже на «хождение по кругу», например, когда вы едете по городу, и выбранный вами путь может привести вас обратно в исходное место. 🚗
На схеме эти «круговые» пути называются «петлями». Это допустимые пути, которые начинаются и заканчиваются в одном и том же узле. Например, на изображении ниже вы можете видеть, что если вы начинаете с любого узла, вы можете вернуться к тому же узлу, следуя по ребру.
Круги не всегда «изолированы», потому что они могут быть частью большей карты. Мы можем начать с поиска на определенном узле, и вы найдете обратный путь к тому же узлу, чтобы обнаружить их.
7.3 Реализация графов
Мы реализуем ориентированный граф со списком смежности.
class Graph {
constructor() {
this.AdjList = new Map();
}
// 基础操作方法
// addVertex(vertex) {}
// addEdge(vertex, node) {}
// print() {}
}
1. addVertex: добавить вершину
addVertex(vertex) {
if (!this.AdjList.has(vertex)) {
this.AdjList.set(vertex, []);
} else {
throw 'Already Exist!!!';
}
}
Попробуйте создать вершины:
let graph = new Graph();
graph.addVertex('A');
graph.addVertex('B');
graph.addVertex('C');
graph.addVertex('D');
После печати найдете:
Map {
'A' => [],
'B' => [],
'C' => [],
'D' => []
}
Почему все массивы пустые'[]', потому что ребро нужно хранить в массиве (Edge)Отношение.
Например, следующая картинка:фигуры
Mapбудет:
Map {
'A' => ['B', 'C', 'D'],
// B没有任何指向
'B' => [],
'C' => ['B'],
'D' => ['C']
}
2. addEdge: добавить ребра (Edge)
addEdge(vertex, node) {
// 向顶点添加边之前，必须验证该顶点是否存在。
if (this.AdjList.has(vertex)) {
// 确保添加的边尚不存在。
if (this.AdjList.has(node)){
let arr = this.AdjList.get(vertex);
// 如果都通过，那么可以将边添加到顶点。
if(!arr.includes(node)){
arr.push(node);
}
}else {
throw `Can't add non-existing vertex ->'${node}'`;
}
} else {
throw `You should add '${vertex}' first`;
}
}
3. print: распечатать график (Graph)
print() {
for (let [key, value] of this.AdjList) {
console.log(key, value);
}
}
пройти тест
let g = new Graph();
let arr = ['A', 'B', 'C', 'D', 'E', 'F'];
for (let i = 0; i < arr.length; i++) {
g.addVertex(arr[i]);
}
g.addEdge('A', 'B');
g.addEdge('A', 'D');
g.addEdge('A', 'E');
g.addEdge('B', 'C');
g.addEdge('D', 'E');
g.addEdge('E', 'F');
g.addEdge('E', 'C');
g.addEdge('C', 'F');
g.print();
/* PRINTED */
// A [ 'B', 'D', 'E' ]
// B [ 'C' ]
// C [ 'F' ]
// D [ 'E' ]
// E [ 'F', 'C' ]
// F []
Пока это все, что вам нужно для создания графика. Однако в 99% случаев вам будет предложено реализовать два других метода:
- Алгоритм в ширину,
BFS. - алгоритм поиска в глубину,
DFS -
BFSОсновное внимание уделяется очереди, в то время какDFSДело в рекурсии. В этом их существенное отличие.
5. Реализация алгоритма в ширину
Поиск в ширину, то же, что и поиск в ширину.
это использованиеочередьРеализован алгоритм поиска. Проще говоря, процесс поиска похож на «бросание камня в озеро, чтобы образовалась рябь».
Как показано на рисунке выше, начиная с начальной точки, для каждой точки вне очереди необходимо пройти точки вокруг нее. Следовательно, процесс поиска BFS очень похож на «бросание камня в озеро и создание слоев ряби», что является источником «ширины» в «алгоритме поиска в ширину».
Конкретные шаги алгоритма:
- BFS принимает начальный узел в качестве параметра. (Например
'A') - Инициализировать пустой объект:
visited. - Инициализировать пустой массив:
q, массив будет использоваться как очередь. - Пометить начальный узел как посещенный.
（visited = {'A': true}） - Поместите начальный узел в очередь.
（q = ['A']） - цикл до тех пор, пока очередь не станет пустой
Внутри цикла:
- получить элемент из
qи сохранить его в переменной.（let current = q.pop()） - печатать текущий
current - получить из рисунка
currentкрай.（let arr = this.AdjList.get(current)）. - Если элемент не был посещен, отметьте каждый элемент как посещенный и поместите его в очередь.
visited = {
'A': true,
'B': true,
'D': true,
'E': true
}
q = ['B', 'D', 'E']
Реализация:
createVisitedObject(){
let arr = {};
for(let key of this.AdjList.keys()){
arr[key] = false;
}
return arr;
}
bfs(startingNode){
let visited = this.createVisitedObject();
let q = [];
visited[startingNode] = true;
q.push(startingNode);
while(q.length){
let current = q.pop()
console.log(current);
let arr = this.AdjList.get(current);
for(let elem of arr){
if(!visited[elem]){
visited[elem] = true;
q.unshift(elem)
}
}
}
}
6. Реализация глубинного алгоритма
Алгоритм поиска в глубину (Depth-First-Search, сокращенно DFS) представляет собой алгоритм поиска, реализованный рекурсией. Проще говоря, его процесс поиска похож на «не ударяйся о южную стену, не оглядывайся».
Как показано на рисунке выше, начиная с начальной точки, вы должны пройти все точки в одном направлении, прежде чем изменить направление. Поэтому процесс поиска DFS очень похож на «не ударяйте южную стену и «не оглядывайся назад», что является «происхождением слова «глубина» в «Алгоритмах поиска в глубину».
Начальные шаги алгоритма аналогичны BFS: он принимает начальный узел и отслеживает посещенные узлы и, наконец, выполняет рекурсивную вспомогательную функцию.
Конкретные шаги:
- принимает начальную точку в качестве параметра
dfs(startingNode). - Создание объектов доступа
let visited = this.createVisitedObject(). - Вызов вспомогательной функции рекурсивно запускает узел и посещает объект
this.dfsHelper(startingNode, visited). -
dfsHelperОтметьте его как посещенный и распечатайте.
createVisitedObject(){
let arr = {};
for(let key of this.AdjList.keys()){
arr[key] = false;
}
return arr;
}
dfs(startingNode){
console.log('\nDFS')
let visited = this.createVisitedObject();
this.dfsHelper(startingNode, visited);
}
dfsHelper(startingNode, visited){
visited[startingNode] = true;
console.log(startingNode);
let arr = this.AdjList.get(startingNode);
for(let elem of arr){
if(!visited[elem]){
this.dfsHelper(elem, visited);
}
}
}
doesPathExist(firstNode, secondNode){
let path = [];
let visited = this.createVisitedObject();
let q = [];
visited[firstNode] = true;
q.push(firstNode);
while(q.length){
let node = q.pop();
path.push(node);
let elements = this.AdjList.get(node);
if(elements.includes(secondNode)){
console.log(path.join('->'))
return true;
}else{
for(let elem of elements){
if(!visited[elem]){
visited[elem] = true;
q.unshift(elem);
}
}
}
}
return false;
}
}
Vans,Следующий.
8. Дерево словаря:Trie
Trie(часто произносится как «попробуй») — это древовидная структура данных, оптимизированная для определенного типа поиска. Если вы хотите взять частичное значение и вернуть набор возможных полных значений, вы можете использоватьTrie.典型的例子是自动完成。
Trie, является деревом поиска, также называемым деревом словарей или деревом поиска слов, а также называемым деревом префиксов, потому что потомки узла имеют общий префикс.
Его особенности:
- Все ключи представляют собой строки, которые можно эффективно запрашивать и вставлять, а временная сложность составляет
O(k), k — длина строки - Недостатком является то, что он очень интенсивно использует память, если большое количество строк не имеют общего префикса.
- Его основная идея состоит в том, чтобы уменьшить количество ненужных сравнений символов и сделать запросы более эффективными.
- Готов к использованию пространства для времени, повторно используйте общие префиксы для повышения эффективности запроса.
Например:
Поиск совпадения с префиксом «b» вернет 6 значений:be,bear,bell,bid,bull,buy.
поисковый префикс"be» вернет 2 значения:bear，bell
8.1 Применение словарных деревьев
Всякий раз, когда вы хотите сопоставить префикс с возможным полным значением, вы можете использоватьTrie.
На практике часто используется в:
- Автозаполнение/ввод вперед
- поиск
- Параметры метода ввода
- Классификация
Также может использоваться в:
- Получение IP-адреса
- номер телефона
- и больше...
8.2 Реализация словарного дерева
class PrefixTreeNode {
constructor(value) {
this.children = {};
this.endWord = null;
this.value = value;
}
}
class PrefixTree extends PrefixTreeNode {
constructor() {
super(null);
}
// 基础操作方法
// addWord(string) {}
// predictWord(string) {}
// logAllWords() {}
}
1. addWord: создать узел
addWord(string) {
const addWordHelper = (node, str) => {
if (!node.children[str[0]]) {
node.children[str[0]] = new PrefixTreeNode(str[0]);
if (str.length === 1) {
node.children[str[0]].endWord = 1;
} else if (str.length > 1) {
addWordHelper(node.children[str[0]], str.slice(1));
}
};
addWordHelper(this, string);
}
2. predictWord: предсказать слово
То есть: учитывая строку, вернуть все слова в дереве, которые начинаются с этой строки.
predictWord(string) {
let getRemainingTree = function(string, tree) {
let node = tree;
while (string) {
node = node.children[string[0]];
string = string.substr(1);
}
return node;
};
let allWords = [];
let allWordsHelper = function(stringSoFar, tree) {
for (let k in tree.children) {
const child = tree.children[k]
let newString = stringSoFar + child.value;
if (child.endWord) {
allWords.push(newString);
}
allWordsHelper(newString, child);
}
};
let remainingTree = getRemainingTree(string, this);
if (remainingTree) {
allWordsHelper(string, remainingTree);
}
return allWords;
}
3. logAllWords: распечатать все узлы
logAllWords() {
console.log('------ 所有在字典树中的节点 -----------')
console.log(this.predictWord(''));
}
logAllWords, вызывая пустую строкуpredictWordпечататьTrieвсе узлы в .
9. Хэш-таблица (хеш-таблица):Hash Tables
Использование хэш-таблицы позволяет выполнять очень быстрые операции поиска. Но что такое хеш-таблица?
Многие языки имеют встроенные структуры данных, такие какpythonсловарь в ,javaсерединаHashMap, основаны на реализации хеш-таблицы. Но что такое хеш-таблица?
9.1 Что такое хеш-таблица?
Хэш (хеширование) - это термин, используемый для извлечения индекса информационных наук, вид данных о лечении, благодаря определенной функции / алгоритму (называемую хэш-функцией / алгоритмом), который должен быть получен (называется HASH или HASH Value), связанным с этим, генерируют Структура данных, которая облегчает поиск (называется хэш-таблицей). Также переведено хэш. Старый переводной хэш (ошибочное использование имен и транслитерацию).
Он также широко используется как метод реализации информационной безопасности, который состоит из строки данных, которая хешируется (
Hashing algorithms) рассчитанный отпечаток данных (data fingerprint), который часто используется для определения того, были ли файлы и материалы подделаны, чтобы убедиться, что файлы и материалы действительно предоставлены первоначальным создателем. —Википедия
9.2 Состав хеш-таблицы
Hash TablesОптимизировано хранение пар ключ-значение. В лучшем случае вставка, извлечение и удаление хеш-таблицы выполняются за постоянное время. Хеш-таблицы используются для хранения больших объемов быстродоступной информации, например паролей.
Хеш-таблицу можно представить как массив, содержащий ряд кортежей, хранящихся в подмассивах внутри объекта:
{[[['a'，9]，['b'，88]]，[['e'，7]，['q'，8]]，[['j'，7]，['l '，8]]]};
- Внешний массив имеет несколько сегментов (подмассивов), равных максимальной длине массива.
- Внутри ведра кортеж или двухэлементный массив содержит пары ключ-значение.
9.3 Основы хеш-таблиц
Здесь я попытаюсь объяснить базовые знания о хеш-таблицах в народной форме:
Хэширование — это метод, используемый для уникальной идентификации определенного объекта из группы подобных объектов. Некоторые примеры того, как хеширование используется в нашей жизни, включают:
- В университете каждому студенту присваивается уникальный регистрационный номер, который можно использовать для получения информации о нем.
- В библиотеке каждой книге присваивается уникальный номер, который можно использовать для определения информации о книге, такой как точное местонахождение в библиотеке или пользователь, которому была выдана книга.
В примерах, студенты и книги разделены на уникальный номер.
1. Подумайте о проблеме
Предположим, у вас есть объект, и вы хотите присвоить ему ключ для удобного поиска. Для хранения пар ключ/значение можно использовать простой массив, например структуру данных, где ключи (целые числа) можно использовать непосредственно как индексы для хранения значений.
Однако если ключ большой и его нельзя использовать напрямую в качестве индекса, следует использовать хеширование.
2, рождение хеш-таблицы
Конкретные шаги заключаются в следующем:
- В хеширу, используяхэш-функцияПревратите большие клавиши в маленькие.
- Затем эти значения сохраняются в структуре данных, называемой хеш-таблицей.
- Идея хеширования заключается в равномерном присвоении записей (пар ключ/значение) в массиве. Назначьте клавишу (клавишу перехода) каждому элементу.
- Используя этот ключ, вы можете
O(1)время доступа к элементу. - Используя ключ, алгоритм (хеш-функция) вычисляет индекс, по которому запись может быть найдена или вставлена.
Конкретное выполнить два шага:
- Преобразуйте элементы в целые числа с помощью хеш-функции. Этот элемент можно использовать в качестве индекса для хранения исходного элемента, принадлежащего хеш-таблице.
- Элемент хранится в хеш-таблице, и его можно быстро получить с помощью хеш-ключа.
hash = hashfunc（key）
index = hash ％ array_size
В этом методе хэш не зависит от размера массива, а затем сводится к индексу (между0а такжеarray_size之间的数字 - 1).
3. Хэш-функция
- Хеш-функция используется для сопоставления набора данных с размером любой функции любого набора данных фиксированного размера, набор данных принадлежит хеш-таблице.
- Значение, возвращаемое хеш-функцией, называется хеш-значением, хеш-кодом, хэш-значением или просто хэш-значением.
Чтобы реализовать хороший механизм хеширования, необходимо выполнить следующие основные требования:
- Простота вычислений: должно быть легко вычисляться, и это не может быть сам алгоритм.
- Равномерное распределение: оно должно обеспечивать равномерное распределение в хеш-таблице и не должно вызывать кластеризацию.
- Меньше коллизий: коллизии возникают, когда пары элементов сопоставляются с одним и тем же значением хеш-функции. Их следует избегать.
Примечание. Независимо от того, насколько надежна хеш-функция, коллизии обязательно произойдут. Поэтому для поддержания производительности хеш-таблицы важно управлять коллизиями с помощью различных методов разрешения коллизий.
4. Хорошая хэш-функция
Предполагая, что вам нужно использовать хеширование{“abcdef”，“bcdefa”，“cdefab”，“defabc”}и т.д. Строки хранятся в хеш-таблице.
Первый — создать индекс:
-
a，b，c，d，eа такжеfизASCIIЗначения97,98,99,100,101а также102, сумма:597 -
597не является простым числом, возьмите ближайшее простое число599, чтобы уменьшить возможность индексации разных строк (коллизий).
Хэш-функция вычислит один и тот же индекс для всех строк, и строки будут сохранены в хэш-таблице в следующем формате.
Поскольку все строки имеют один и тот же индекс, в этот момент все строки находятся в одном «корзине».
- Здесь для доступа к определенной строке требуется
O(n)время (где n — количество строк). - Это указывает на то, что хеш-функция не является хорошей хэш-функцией.
Как оптимизировать эту хэш-функцию?
Обратите внимание на сходства и различия между этими строками.
{“abcdef”，“bcdefa”，“cdefab”，“defabc”}
- все по
a，b，c，d，eа такжеfсочинение - Отличие в порядке составления.
попробовать разные хэш-функции.
- Индекс конкретной строки будет равен сумме значений ASCII символов, умноженных на их соответствующий порядок в строке.
- затем совместите его с
2069(простой) взять остаток.
Строковый индекс хэш-функции
| нить | генерация индекса | Рассчитано |
|---|---|---|
| abcdef | (97 1 + 98 2 + 99 3 + 100 4 + 101 5 + 102 6) % 2069 | 38 |
| bcdefa | (98 1 + 99 2 + 100 3 + 101 4 + 102 5 + 97 6) %2069 | 23 |
| cdefab | (99 1 + 100 2 + 101 3 + 102 4 + 97 5 + 98 6) % 2069 | 14 |
| defabc | (100 1 + 101 2 + 102 3 + 97 4 + 98 5 + 99 6) %2069 | 11 |
При разумных предположениях среднее время, необходимое для поиска элемента в хэш-таблице, должно составлять O(1).
9.4 Реализация хеш-таблиц
class Node {
constructor( data ){
this.data = data;
this.next = null;
}
}
class HashTableWithChaining {
constructor( size = 10 ) {
this.table = new Array( size );
}
// 操作方法
// computeHash( string ) {...}
// ...
}
1. isPrime: суждение о простом числе
isPrime( num ) {
for(let i = 2, s = Math.sqrt(num); i <= s; i++)
if(num % i === 0) return false;
return num !== 1;
}
2. computeHash|findPrime: генерация хэш-функции
computeHash( string ) {
let H = this.findPrime( this.table.length );
let total = 0;
for (let i = 0; i < string.length; ++i) {
total += H * total + string.charCodeAt(i);
}
return total % this.table.length;
}
// 取模
findPrime( num ) {
while(true) {
if( this.isPrime(num) ){ break; }
num += 1
}
return num;
}
3. Put: вставить значение
put( item ) {
let key = this.computeHash( item );
let node = new Node(item)
if ( this.table[key] ) {
node.next = this.table[key]
}
this.table[key] = node
}
4. Remove: удалить значение
remove( item ) {
let key = this.computeHash( item );
if( this.table[key] ) {
if( this.table[key].data === item ) {
this.table[key] = this.table[key].next
} else {
let current = this.table[key].next;
let prev = this.table[key];
while( current ) {
if( current.data === item ) {
prev.next = current.next
}
prev = current
current = current.next;
}
}
}
}
5. contains: Суждение содержит
contains(item) {
for (let i = 0; i < this.table.length; i++) {
if (this.table[i]) {
let current = this.table[i];
while (current) {
if (current.data === item) {
return true;
}
current = current.next;
}
}
}
return false;
}
6. Size & IsEmpty: судить о длине или пусто
size( item ) {
let counter = 0
for(let i=0; i<this.table.length; i++){
if( this.table[i] ) {
let current = this.table[i]
while( current ) {
counter++
current = current.next
}
}
}
return counter
}
isEmpty() {
return this.size() < 1
}
7. TraverseТраверс
traverse( fn ) {
for(let i=0; i<this.table.length; i++){
if( this.table[i] ) {
let current = this.table[i];
while( current ) {
fn( current );
current = current.next;
}
}
}
}
Наконец, поместите диаграмму эффективности выполнения хэш-таблицы
10. Зачем это писать
Это все еще об интервью. несмотря на то чтоleetcodeНекоторые из вышеперечисленных вопросов были сняты, но из-за отсутствия общего понимания структуры данных. Много раз, когда его спрашивают или тестируют, делать нечего.
Большинство постов в интернете разной глубины, и я прочитал много материалов и примеров в процессе написания этого. Следующие статьи являются кратким изложением процесса обучения.Если вы обнаружите какие-либо ошибки, пожалуйста, оставьте сообщение, чтобы указать.
Ссылаться на:
- DS с JS — хэш-таблицы — I
- Joseph Crick - Practical Data Structures for Frontend Applications: When to use Tries
- [Thon Ly - Data Structures in JavaScript
Спросите рекомендацию инсайдера в Шэньчжэне
Хорошо, давайте закончим еще одну статью и перейдем к теме:
В настоящее время я (и) готовлюсь к смене работы. Надеюсь, что вы и дамы из отдела кадров сможете предложить надежную работу в Шэньчжэне!
- WeChat:
huab119 - Почта:
454274033@qq.com
❤️ После прочтения трех вещей
Если вы найдете этот контент вдохновляющим, я хотел бы пригласить вас сделать мне три небольших одолжения:
- Ставьте лайк, чтобы больше людей увидело этот контент
- Обратите внимание на паблик «Учитель фронтенд-убеждения», и время от времени делитесь оригинальными знаниями.
- Также смотрите другие статьи
- Те шаблоны проектирования, которые вы используете непреднамеренно (1) - шаблоны создания
- [«Король библиотеки визуализации данных» D3.js быстро приступает к работе с приложениями Vue
](nuggets.capable/post/684490…)
- Руководство "True® Full Stack Road" для веб-интерфейсной разработки
- «Практика Vue» — плагин Vue CLI за 5 минут
- Вооружите свой интерфейсный проект «Практикой Vue»
- «Intermediate and Advanced Front-End Interview» JavaScript Рукописный код Invincible Cheats
- «Узнайте из исходного кода» ответы на вопросы Vue, которые интервьюеры не знают
- JS-операция «Узнать из исходного кода» в исходном коде Vue
- Правильная позиция для обновления vue-cli3 в проекте "Vue Practice"
- Почему вы до сих пор не можете понять цепочку областей видимости JavaScript?
Вы также можете прийти ко мнеGitHubПолучите исходные файлы всех статей в блоге:
Руководство по убеждению:GitHub.com/Roger-Hi RO/…