Структура данных Dahua (чтение заметок)

структура данных

что такое структура данных

являются одним или несколькими друг от другаконкретное отношениеизсбор элементов данных.

Грубо говоря, это набор данных, но между данными в наборе существует особая связь (этот перевод, кажется, не говорит того же)

Логическая структура структуры данных

относится к взаимосвязи между элементами данных

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

• Линейная структура: между элементами данных в линейной структуре существует отношение один к одному.

• Древовидная структура: существует иерархическая связь «один ко многим» между элементами данных в древовидной структуре.

• Структура графа: элементы данных структуры графа находятся в отношениях «многие ко многим».

Физическая структура структуры данных

Относится к логической структуре данных в виде компьютерного хранилища.

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

тип данных

Тип данных относится к набору значений одинаковой природы и общему термину для некоторых операций, определенных на этом наборе.

Типы данных можно разделить на две категории

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

алгоритм

что такое алгоритм

Алгоритм — это описание шагов решения для решения конкретной проблемы. Появляется в компьютере как конечная последовательность инструкций, и каждая инструкция представляет собой одну или несколько операций.

Характеристики алгоритма

Пять свойств алгоритмов: вход, выход, конечность, детерминизм, выполнимость.

• Алгоритм имеет ноль или более входных данных, алгоритм имеет по крайней мере один или несколько выходных данных, алгоритм должен нуждаться в выходных данных и не нуждается в выходных данных, зачем вам этот алгоритм
• Конечность: Алгоритм выполняет конечное число шагов, завершается автоматически без бесконечного цикла и завершает каждый шаг за приемлемое время.
• Детерминированный: каждый шаг алгоритма имеет четкое значение и не имеет двусмысленности. Один и тот же вход может иметь только уникальный выходной результат
• Выполнимость: каждый шаг алгоритма должен быть выполним, то есть каждый шаг может быть выполнен путем выполнения конечного числа раз.

Требования к разработке алгоритма

• правильность
• удобочитаемость
• прочность
• Высокая эффективность использования времени и низкая емкость хранилища

Временная сложность алгоритма

При анализе алгоритма общее количество выполнений оператора T(n) является функцией размера задачи n, а затем анализируется изменение T(n) в зависимости от n и определяется порядок величины T(n).

Временная сложность алгоритма, то есть измерение времени работы алгоритма, обозначается как T(n) = O(f(n)), что означает, что с увеличением размера задачи n скорость роста время выполнения алгоритма и скорость роста f(n) одинаковы. где f(n) — некоторая функция размера задачи n.

Используйте O() в верхнем регистре для обозначения временной сложности алгоритма.

В общем случае алгоритм с самым медленным ростом T(n) при увеличении n называется оптимальным алгоритмом.

O(1) постоянный порядок, O(n) линейный порядок, O(n^2) квадратный порядок, O(logn) логарифмический порядок

Общая временная сложность

O(1)<O(logn)<O(n)<O(nlogn)<O(n^2)<O(n^3)<O(2^n)<O(n!)<O(n^n)

• постоянный порядок
• логарифмический
• Линейный порядок
• Квадратный заказ
• Экспоненциальный порядок
• факторный порядок

худший случай против среднего случая

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

Среднее время работы является самым жирным из всех, потому что это ожидаемое время работы.

Сложность пространства алгоритмов

Пространственная сложность алгоритма реализуется путем вычисления объема памяти, необходимого алгоритму, и запоминается формула расчета пространственной сложности алгоритма: S(n)=O(f(n)). где n — размер задачи, а f(n) — функция объема памяти оператора для n.

Линейный стол

Ограниченное количество нулевых или более элементов данныхпоследовательность

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

Последовательная структура хранения линейной таблицы

Последовательная структура хранения линейной таблицы относится к использованию сегмента адресаблок непрерывного храненияХраните элементы данных линейной таблицы последовательно

Преимущества и недостатки

• произвольный доступ
• Нет необходимости добавлять дополнительное пространство для хранения для представления логической связи между таблицами.
• Вставка и удаление элементов требует перемещения большого количества объектов
• Когда длина линейного стола сильно различается, трудно определить размер места для хранения.
• мусор, создающий пространство

Цепная структура хранения линейной таблицы

Сравните структуру односвязного списка с последовательной структурой хранения.

• выделение памяти
  • Структура последовательного хранения использует непрерывную пару единиц хранения для одновременного хранения элементов данных линейной таблицы.
  • Односвязный список принимает цепную структуру хранения и использует набор произвольных единиц хранения для хранения элементов линейного списка.
• найти
  • Структура последовательного хранения O(1)
  • Односвязный список O (n)
• Вставить и удалить
  • Структура последовательного хранения требует среднего сдвига половины элементов таблицы, а время составляет O(n)
  • После нахождения позиции в односвязном списке время вставки и удаления составляет всего O(1)
• космическая производительность
  • Последовательная структура хранения, предварительное распределение, большие потери, небольшое переполнение
  • Односвязный список не требует предварительного размещения, а количество элементов не ограничено

стеки и очереди

Стек — это линейный список, ограниченный операциями вставки и удаления только в конце списка.

Очередь — это линейный список, который допускает только вставки на одном конце и удаления на другом.

куча

Во-первых, это линейная таблица, то есть элементы стека имеют линейную связь, то есть связь предшественника и преемника, но это особая линейная таблица. В определении сказано, что операции вставки и удаления выполняются в хвосте линейного списка, и хвост здесь — это только вершина стека, а не низ стека.

Применение стека - рекурсия

Прямо или косвенно вызывает саму функцию.

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

Применение стека - вычисление четырех арифметических выражений

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

очередь

Линейная таблица имеет последовательное хранение, а стек — это линейная таблица, поэтому существует два метода хранения. Такая же очередь, как специальная линейная таблица, существует и в этих двух способах хранения.

круговая очередь

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

нить

Строка — это конечная последовательность из нуля или более символов, также известная как строка.

KMP

Алгоритм сопоставления шаблонов KMP разработан таким образом, чтобы не возникало ненужного возврата.

Дерево

Дерево — это конечное множество из n (n>=0) узлов, а n=0 называется пустым деревом. В любом непустом дереве

• имеет один и только один конкретный узел, называемый корнем
• При n>1 оставшиеся узлы можно разбить на m (m>0) конечных множеств T1, T2, T3, не пересекающихся друг с другом. где каждое множество само является деревом и называется поддеревом корня

Классификация узлов

Количество поддеревьев узла называется степенью узла. Узлы со степенью 0 называются узлами страницы или терминальными узлами. Узел, степень которого не равна 0, называется неконечным узлом.

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

Степень дерева - это максимальная степень каждого узла в дереве.

отношения между узлами

Поддеревья узла называются потомками узла, и, соответственно, сам узел называется родителями потомка.

Другие концепции дерева

Уровень узла определяется от корня, корень — это первый уровень, а потомки корня питают второй уровень.

Максимальный уровень узлов в дереве называется глубиной дерева.

Если поддеревья узлов в дереве считаются упорядоченными слева направо и не могут быть заменены местами, дерево называется упорядоченным деревом, в противном случае оно называется неупорядоченным деревом.

Лес — это совокупность m непересекающихся деревьев.

бинарное дерево

— это конечное множество из n узлов, либо пустое множество, либо бинарное дерево, состоящее из корневого узла и двух непересекающихся левого и правого поддеревьев, называемых корневым узлом.

Особенности бинарного дерева

• Каждый узел имеет не более двух поддеревьев, поэтому в бинарном дереве нет узла со степенью больше 2.
• Левое поддерево и правое поддерево идут по порядку, и порядок нельзя изменить
• Даже если в дереве есть только одно поддерево, различайте, является ли оно левым поддеревом или правым поддеревом.

специальное бинарное дерево

• наклонное дерево

  Бинарное дерево, в котором все узлы имеют только левые поддеревья, называется деревом с левым наклоном. Бинарное дерево, узлы которого имеют только правые поддеревья, называется деревом с наклоном вправо. Эти два вместе называются наклонными деревьями.

• полное бинарное дерево

  В бинарном дереве, если все узлы ветвления имеют левые и правые поддеревья, а все листья находятся на одном уровне, такое бинарное дерево называется полным бинарным деревом.

• полное бинарное дерево

  Для бинарного дерева с n узлами оно нумеруется в порядке слоев.Если позиции узла с номером i и узла с номером i в полном бинарном дереве той же глубины в бинарном дереве полны, то такое бинарное дерево называется полное бинарное дерево...

  • Листовые узлы могут появляться только в двух нижних слоях.
  • Самые нижние листья должны быть сосредоточены в левом непрерывном положении
  • Предпоследний слой, если есть листовой узел, он должен находиться в непрерывном положении справа
  • Если степень узла равна 1, узел имеет только левое поддерево, и не существует случая, когда существует только правое поддерево.
  • Бинарное дерево с одинаковым количеством узлов и полное бинарное дерево имеют наименьшую глубину.

свойства бинарного дерева

• На i-м уровне бинарного дерева не более 2^(i-1) узлов.
• Двоичное дерево глубины k имеет не более 2^k - 1 узлов.

обход бинарного дерева

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

• обход предварительного заказа

  Если бинарное дерево пусто, возвращается no-op, в противном случае сначала посещается корневой узел, затем в прямом порядке просматривается левое поддерево, а затем в прямом порядке просматривается правое поддерево.

• Неупорядоченный обход

  Если бинарное дерево пусто, возвращается пустая операция, в противном случае она начинается с корневого узла (обратите внимание, что сначала не следует посещать корневой узел), проходите по порядку левое поддерево корневого узла, затем посещаете корневой узел, лучше всего пройти по правому поддереву в дереве по порядку

• пост-порядковый обход

  Если бинарное дерево пусто, возвращается пустая операция, в противном случае выполняется обход левого и правого поддеревьев и доступ к ним слева направо, затем осуществляется доступ к узлу и, наконец, осуществляется доступ к корневому узлу.

• обход по уровням

  Если бинарное дерево пусто, возвращается no-op, в противном случае доступ начинается с первого слоя дерева, то есть корневого узла, проходит слой за слоем сверху вниз и обращается к узлам того же слоя из слева направо.

картина

Граф состоит из конечного непустого множества вершин и множества ребер между вершинами, обычно обозначаемых G(V,E). где G представляет собой граф, V — множество вершин в графе G, а E — множество ребер в графе G.

обход в глубину

Также известен как поиск в глубину или сокращенно DFS.

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

обход в ширину

Также известен как поиск в ширину или сокращенно BFS.

Подобно обходу порядка на уровне дерева.

минимальное остовное дерево

Мы называем остовное дерево с минимальной стоимостью для построения связной сети минимальным остовным деревом.

• Алгоритм Прима Прима
• Крускал Алгоритм Крускала

кратчайший путь

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

• Алгоритм Дейкстры
• Алгоритм Флоди

найти

Поиск должен определить элемент, ключ которого равен заданному значению в таблице поиска в соответствии с заданным значением.

Последовательный поиск

Также известный как линейный поиск, это самая основная технология поиска.Его процесс поиска: начиная с первой записи в таблице, сравнивая ключ записи и заданное значение один за другим, если ключ записи и заданное значение Если они равны, то поиск успешен и искомая запись найдена Если сравнение ключа и заданного значения не равно до последней записи, это означает, что в таблице нет искомой записи.

поиск по упорядоченному списку

Найти пополам

Двоичный поиск также известен как бинарный поиск, Его предпосылка заключается в том, что записи в линейной таблице должны быть в порядке ключей, и линейная таблица должна храниться последовательно. Основная идея половинного поиска: в упорядоченной таблице в качестве объекта сравнения взять среднюю запись, если заданное значение равно ключевому слову средней записи, поиск успешен, если заданное значение меньше ключевое слово средней записи, то средняя запись находится в середине Продолжить поиск в левой половине записи, если заданное значение больше ключа средней записи, продолжить поиск в правой половине средней записи записывать. Повторяйте процесс обжалования до тех пор, пока поиск не будет успешным или в области поиска не останется записей.

интерполированный поиск

Интерполяционный поиск - это метод поиска, основанный на искомом ключевом слове и ключевых словах самой большой и самой маленькой записи в таблице поиска.Его суть заключается в формуле расчета интерполяционного ключа-a[низкий] / a[высокий]-a [низкий]

Поиск Фибоначчи

Поиск линейного индекса

Конечной целью структуры данных является повышение скорости обработки данных, а индекс — это структура данных, предназначенная для ускорения скорости поиска. Индексация — это процесс связывания ключа с соответствующей записью.

Индекс можно разделить на линейный индекс, древовидный индекс и многоуровневый индекс в соответствии со структурой.

Так называемый линейный индекс предназначен для организации набора элементов индекса в линейную структуру, также известную как индексная таблица.

Линейные индексы можно разделить на плотные индексы, блочные индексы и инвертированные индексы.

плотный индекс

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

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

Количество плотных индексов равно количеству записей в наборе данных.

блочный индекс

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

• неупорядоченный внутри блока
• межблочное упорядочение

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

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

бинарное дерево поиска

• Если его левое поддерево не пусто, значение всех узлов в левом поддереве меньше, чем значение его корневого узла.
• Если его правое поддерево не пусто, значение всех узлов в правом поддереве больше, чем значение его корневого узла.
• Его левое и правое поддеревья также являются деревьями с бинарной сортировкой.

Целью построения бинарного дерева сортировки является не сортировка, а повышение скорости поиска и вставки и удаления ключевых слов.

Сбалансированное бинарное дерево

Сбалансированное бинарное дерево — это бинарное отсортированное дерево, в котором разница высот между левым и правым поддеревьями каждого узла не превышает 1.

Величина вычитания глубины правого поддерева из глубины левого поддерева узла бинарного дерева называется коэффициентом баланса. Значения только -1, 0, 1

дерево многостороннего поиска

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

B-дерево

B-дерево — это сбалансированное многоходовое дерево поиска.

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

В+ дерево

хеш-таблица

Техника хеширования заключается в установлении определенного отношения соответствия f между позицией хранения и ее ключевым словом записи, ключевым словом, при котором каждый ключ соответствует ячейке памяти f.

разрешать коллизии хешей

• открытая адресация
• Метод перехеширования
• метод цепного адреса
• Закон об общей зоне разлива

Сортировать

• обменная сортировка

  • Пузырькая сортировка
  • быстрая сортировка

• Сортировка вставками

  • сортировка прямой вставкой
  • Сортировка холмов

• сортировка выбором

  • простая сортировка выбором
  • сортировка кучей

• Сортировка слиянием

• сортировка по основанию

структура больших данных