Несколько дней назад общался с Ао Бином, он сказал, что те из нас, кто пишет, постоянно сжигают себя, поэтому нам нужно постоянно дозаправляться. Я не мог не согласиться с его точкой зрения, поэтому я начал втискивать основы вычислений, включая мои относительно слабые структуры данных.
Энциклопедия Baidu определяет структуру данных как набор элементов данных, которые имеют одно или несколько конкретных отношений друг с другом. Определение является абстрактным, и его необходимо прочитать вслух несколько раз, чтобы почувствовать его. Как сделать это чувство сильнее и интимнее? Позвольте мне перечислить 8 распространенных структур данных, массивов, связанных списков, стеков, очередей, деревьев, куч, графов и хеш-таблиц.
В чем разница между этими 8 структурами данных?
①, массив
преимущество:
- Запрос элементов по индексу выполняется быстро;
- Также удобно перемещаться по массиву по индексу.
недостаток:
- Размер массива определяется после создания и не может быть расширен;
- Массивы могут хранить только один тип данных;
- Добавление и удаление элементов занимает много времени, поскольку другие элементы перемещаются.
②, связанный список
В книге «Алгоритмы (4-е издание)» связанный список определяется следующим образом:
Связанный список — это рекурсивная структура данных, которая либо пуста (null), либо является ссылкой на узел, содержащий элемент и ссылку на другой связанный список.
Класс Java LinkedList может представлять структуру связанного списка в виде кода:
public class LinkedList<E> {
transient Node<E> first;
transient Node<E> last;
private static class Node<E> {
E item;
Node<E> next;
Node<E> prev;
Node(Node<E> prev, E element, Node<E> next) {
this.item = element;
this.next = next;
this.prev = prev;
}
}
}
Это двусвязный список.Текущий элемент элемента имеет и предыдущий, и следующий, но предыдущий из первого равен нулю, а следующий из последнего равен нулю. Если это односвязный список, есть только следующий и нет предыдущего.
Недостаток односвязного списка в том, что его можно пройти только от начала до конца, тогда как двусвязный список может идти вперед и назад, а также может найти как следующий, так и предыдущий — нужно еще одно место для хранения. размещаться на каждом узле.
Данные в связанном списке хранятся в «цепной» структуре, поэтому можно добиться эффекта несмежной памяти, а массив должен быть непрерывным участком памяти.
Поскольку его не нужно хранить по порядку, связанный список может достичь временной сложности O (1) при вставке и удалении (нужно только повторно указать ссылку, нет необходимости перемещать другие элементы, такие как массив). Кроме того, связанный список устраняет недостаток, заключающийся в том, что размер данных массива должен быть известен заранее, что обеспечивает гибкое динамическое управление памятью.
преимущество:
- Нет необходимости инициализировать емкость;
- Любой элемент может быть добавлен;
- При вставке и удалении необходимо обновить только ссылку.
недостаток:
- Содержит большое количество ссылок и занимает большой объем памяти;
- Поиск элемента требует обхода всего связанного списка, что занимает много времени.
③, стек
Стопка похожа на ведро, дно закрыто, а верх открыт, вода может входить и выходить. Друзья, которые пользовались ведрами, должны понимать следующее: вода, налитая первой, находится на дне ведра, а вода, налитая последней, находится наверху ведра; вода, налитая последней, выливается первой, а вода, которая поступает первой, выливается.
Точно так же стек хранит данные в соответствии с принципами «последний пришел, первый ушел» и «первый пришел, последний ушел». вершина стека.При чтении данных они начинаются с вершины стека.Чтение последовательно.
④, очередь
Очередь похожа на участок водопроводной трубы, открытый с обоих концов, вода входит с одного конца и выходит с другого конца. Вода, которая поступает первой, выходит первой, а вода, которая поступает позже, выходит.
В отличие от водопровода, очередь будет определена на обоих концах, один конец называется головой очереди, а другой конец называется хвостом очереди. В начале очереди разрешены только операции удаления (dequeue), а в хвосте — только операции вставки (enqueue).
Обратите внимание, что в стеке используется принцип «первым пришел — последним вышел», а в очереди — «первым пришел — первым вышел» — хотя обе таблицы являются линейными, принципы у них разные, а структура — разная.
⑤, дерево
Дерево — это типичная нелинейная структура, представляющая собой совокупность иерархических отношений, состоящую из n (n>0) конечных узлов.
Это называется «деревом», потому что эта структура данных выглядит как перевернутое дерево с корнем наверху и листьями внизу. Древовидная структура данных имеет следующие характеристики:
- Каждый узел имеет только ограниченное количество дочерних элементов или не имеет дочерних элементов;
- Узел без родительского узла называется корневым узлом;
- Каждый некорневой узел имеет один и только один родительский узел;
- В дополнение к корневому узлу каждый дочерний узел может быть разделен на несколько непересекающихся поддеревьев.
Следующая диаграмма показывает некоторую терминологию для деревьев:
Корневой узел имеет уровень 0, его дочерние узлы — уровень 1, дочерние узлы — уровень 2 и так далее.
- Глубина: для любого узла n глубина n — это длина уникального пути от корня до n, а глубина корня равна 0.
- Высота: для любого узла n высота n — это длина самого длинного пути от n до листа, а высота всех листьев равна 0.
Существует множество видов деревьев, наиболее распространенными являются:
- Неупорядоченное дерево: между дочерними элементами любого узла в дереве нет упорядоченных отношений. Так как же понять неупорядоченное дерево, как оно выглядит?
Если есть три узла, один из которых является родительским узлом, а два — дочерними узлами одного уровня, то возможны три ситуации:
Если есть три узла, один родительский узел и два дочерних узла разных уровней, то возможны шесть случаев:
Всего неупорядоченное дерево, состоящее из трех узлов, имеет девять случаев.
- Двоичное дерево: каждый узел содержит не более двух поддеревьев. Бинарные деревья можно разделить на множество типов в соответствии с различными выражениями.
Полное бинарное дерево: для бинарного дерева предполагается, что его глубина равна d (d > 1). За исключением d-го слоя число узлов других слоев достигло максимального значения, а все узлы d-го слоя расположены тесно и непрерывно слева направо Такое бинарное дерево называется полным бинарным дерево.
Взяв приведенный выше рисунок в качестве примера, d равно 3. За исключением третьего слоя, первый слой и второй слой достигли максимального значения (2 дочерних узла), и все узлы третьего слоя тесно связаны слева направо. right (H , I, J, K, L), которые удовлетворяют требованиям полного бинарного дерева.
Полное бинарное дерево: бинарное дерево с максимальным количеством узлов на каждом уровне. Есть две формы выражения.Первая, как показано на рисунке ниже (каждый слой заполнен), удовлетворяет тому, что количество узлов в каждом слое достигает максимального значения 2.
Во-вторых, как показано на рисунке ниже (хотя каждый слой не удовлетворен), количество узлов в каждом слое все еще достигает максимального значения 2.
Двоичное дерево поиска: английское название Binary Search Tree или BST, которое должно соответствовать следующим условиям:
- Левое поддерево любого узла не пусто, и значение всех узлов левого поддерева меньше значения его корневого узла;
- Правое поддерево любого узла не пусто, и значение всех узлов в правом поддереве больше, чем значение его корневого узла;
- Левое и правое поддеревья любого узла также являются бинарными деревьями поиска соответственно.
Основываясь на характеристиках бинарного дерева поиска, его преимущество по сравнению с другими структурами данных заключается в том, что временная сложность поиска и вставки невелика, что составляет O (logn). Если мы хотим найти 5 элементов из приведенного выше рисунка, начнем с корневого узла 7, 5 должен быть слева от 7, найти 4, затем 5 должен быть справа от 4, найти 6, затем 5 должен быть с левой стороны 6 сторона, найдена.
В идеале, просматривая узлы через BST, количество узлов, которые необходимо проверить, можно сократить вдвое.
Сбалансированное бинарное дерево: бинарное дерево тогда и только тогда, когда разница в высоте между двумя поддеревьями любого узла не превышает 1. Высокосбалансированное бинарное дерево, предложенное бывшими советскими математиками Адельсом-Вельскилом и Лэндисом в 1962 году, также называется деревом АВЛ по имени ученого на английском языке.
Сбалансированное бинарное дерево по сути также является бинарным деревом поиска, но для того, чтобы ограничить разницу в высоте между левым и правым поддеревьями и избежать эволюции линейной структуры, такой как наклонное дерево, левое и правое поддеревья каждого узла в Для ограничения бинарного дерева поиска разница высот между левым и правым поддеревьями называется коэффициентом баланса, а абсолютное значение коэффициента баланса каждого узла в дереве не превышает 1.
Сложность балансировки бинарного дерева заключается в том, как поддерживать баланс между левым и правым с помощью левшей или правшей, когда узлы удаляются или добавляются.
Наиболее распространенным сбалансированным бинарным деревом в Java является красно-черное дерево, узлы которого бывают красными или черными, а баланс бинарного дерева поддерживается цветовыми ограничениями:
1) Каждый узел может быть только красным или черным
2) Корневой узел черный
3) Каждый листовой узел (узел NIL, пустой узел) черный.
4) Если узел красный, оба его потомка черные. Другими словами, два соседних красных узла не могут появиться на пути.
5) Все пути от любого узла к каждому его листу содержат одинаковое количество черных узлов.
- B-дерево: самобалансирующееся двоичное дерево поиска, оптимизированное для операций чтения и записи, сохраняющее порядок данных и имеющее более двух поддеревьев. B-дерево используется в технологии индексации баз данных.
⑥, куча
Куча может рассматриваться как дерево объектов массива со следующими характеристиками:
- Значение узла в куче всегда не больше и не меньше значения его родительского узла;
- Куча всегда является полным бинарным деревом.
Куча с наибольшим корневым узлом называется максимальной кучей или большой корневой кучей, а куча с наименьшим корневым узлом называется минимальной кучей или малой корневой кучей.
⑦, рисунок
Граф представляет собой сложную нелинейную структуру, состоящую из конечного непустого множества вершин и множества ребер между вершинами, обычно выражаемую как: G(V, E), где G представляет собой граф, а V — граф в G. Множество вершин, E — множество ребер в графе G.
На приведенном выше рисунке 4 вершины V0, V1, V2, V3, и 5 ребер между 4 вершинами.
В линейной структуре между элементами данных выполняется уникальная линейная связь, и каждый элемент данных (кроме первого и последнего) имеет уникального «предшественника» и «последователя»;
В древовидной структуре существует очевидная иерархическая связь между элементами данных, и каждый элемент данных связан только с одним элементом (родительским узлом) на предыдущем уровне и несколькими элементами (дочерними узлами) на следующем уровне;
В структуре графа отношения между узлами произвольны, и может быть корреляция между любыми двумя элементами данных в графе.
⑧, Хэш-таблица
Хеш-таблица, также известная как хеш-таблица, представляет собой структуру данных, к которой можно получить прямой доступ через ключ-значение.Ее самая большая особенность заключается в том, что она может быстро выполнять поиск, вставку и удаление.
Самая большая особенность массива заключается в том, что его легко искать, но трудно вставлять и удалять; наоборот, связанный список трудно искать, но легко вставлять и удалять. Хеш-таблица прекрасно сочетает в себе преимущества обоих, и HashMap в Java также добавляет преимущества дерева на этой основе.
Хеш-функция играет очень важную роль в хэш-таблице, она может преобразовывать входные данные любой длины в выходные данные фиксированной длины, а на выходе получается хэш-значение. Хеш-функции делают процесс доступа к последовательности данных более эффективным и действенным.С помощью хеш-функций можно быстро найти элементы данных.
Если ключ k, его значение сохраняется вhash(k)место хранения. Таким образом, значение, соответствующее k, может быть получено напрямую без обхода.
Для любых двух разных блоков данных вероятность одинакового значения хеш-функции крайне мала, то есть для данного блока данных крайне сложно найти блок данных с одинаковым значением хеш-функции. Кроме того, для блока данных, даже если изменится только один его бит, изменение его хеш-значения будет очень большим — это ценность существования хэша!
Хотя это крайне маловероятно, это все же произойдет.Если произойдет коллизия хешей, HashMap в Java добавит связанный список в ту же позицию массива.Если длина связанного списка больше 8, он будет преобразован в красно-черное дерево для обработки - это так называемый метод зиппер (массив + связанный список).
Честно говоря, если я продолжу наверстывать упущенное в таком темпе, мне кажется, что мне нужно облысеть, но если я смогу стать сильнее, это того стоит — да, оно того стоит. Также есть несколько друзей, которые хотят, чтобы я порекомендовал несколько книг по алгоритмам и структурам данных. Я собрал несколько популярных на GitHub. Нажмите на ссылку, чтобы скачать их. Надеюсь, мои намерения помогут вам.
Ссылка на сайт:Disk.Baidu.com/Yes/1RB-cc — это JP…Пароль: g5pl
Я Silent King Er, тихий, но интересный программист.Обратите внимание на повышение эффективности обучения. Друзья, кому понравилась эта статья, пожалуйста, не забудьте четверку, лайк, избранное, вперед, оставить сообщение, вы самые красивые и вы самые красивые!