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

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

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

Пожалуйста, поддержите меня, если вы чувствуете, что я приношу вам пользу!

Вы можете прочитать мою статью, чтобы лучше понять.

Реклама электронной книги: Здравое руководство по структурам данных и алгоритмам: повышайте уровень своих основных навыков программирования, написанное Джеем Венгроу

Классификация структур данных

Структуры данных — это способы организации и хранения данных в компьютере.

Примитивная структура данных

• Базовые структуры данных не могут быть далее разделены.

1. 8-битные целые числа с арифметическими операциями (Byte) — имеет минимальное значение -128 и максимальное значение 127 (включительно).
2. 16-битные целые числа с арифметическими операциями (короткие) — имеет минимальное значение -32 768 и максимальное значение 32 767 (включительно).
3. 32-битные целые числа с арифметическими операциями (Int) — имеет минимальное значение -231 и максимальное значение 230.
4. 64-битные целые числа с арифметическими операциями (длинные) — имеет минимальное значение -263 и максимальное значение 262.
5. 16-битные символы Unicode/буквенно-цифровые символы/символы (char) — минимальное значение '\u0000' (или 0) и максимальное значение '\uffff' (или 65 535 включительно)
6. 32-битные действительные числа одинарной точности IEEE 754 с арифметическими операциями (с плавающей запятой)
7. 64-битные действительные числа двойной точности IEEE 754 с арифметическими операциями (двойные)
8. Булевы значения (набор значений {true, false} с логическими операциями (Boolean) — имеет только два возможных значения: true и false.

Непримитивная структура данных

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

Линейный

• Элементы образуют последовательность

1. Массив

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

• Одномерный массив: элементы хранятся линейно, и к ним можно получить доступ по отдельности, указав значение индекса каждого элемента, хранящегося в массиве.
• int a[n], строка a[n]
• Многомерный массив — массив с более чем одним измерением.
• int a[m][n], строка a[m][n],

Возможности:

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

Преимущества

• Высокая эффективность чтения по индексу (поддерживает приложения с произвольным доступом)
• Поиск: временная сложность O(1)

Недостатки:

• Низкая эффективность записи (удаление и вставка относительно низкоэффективны, потому что это зависит от позиции вставки и удаления, и необходимо выполнить много перемещений данных, если позиция вставки и удаления не является последним битом)
• Вставка/удаление: временная сложность O(n)

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

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

Преимущества

• Элементы можно добавлять или вычитать произвольно.

Недостатки

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

3. Стек

• Это специальный линейный список, который можно вставлять и удалять только с одного конца.
• Он хранит данные по принципу «последний пришел, первый ушел» (LIFO).
• Данные, введенные первыми, помещаются в нижнюю часть стека, а последний элемент данных оказывается наверху стека.
• Последний элемент данных считывается первым или извлекается из вершины стека.
• Вставка = нажать
• Удаление = поп
• Количество элементов в стеке равно нулю = пустой стек
• Вставка/удаление: временная сложность O(1)

4. Очередь

• Это линейный список, который допускает вставки на одном конце и удаление на другом конце.
• Работает по принципу «первым пришел — первым ушел» (FIFO).

Основные операции

1. Enqueue: вставить элемент в очередь
2. Dequeue: удалить элемент и вернуть первый элемент очереди

• Вставка/удаление: временная сложность O(1)
• Циркулярная очередь, приоритетная очередь

Нелинейный

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

5. Дерево

• Это нелинейное хранилище, состоящее из n (n≥1) конечных узлов, образующих набор с иерархическими отношениями.
• Он отображает набор элементов данных с отношением «один ко многим».
• Каждый узел имеет ноль или более дочерних узлов
• Узел без родительского узла = корневой узел
• Каждый некорневой узел имеет один и только один родительский узел.
• Каждый дочерний узел может быть разделен на несколько непересекающихся поддеревьев.
• Глубина узла = длина пути от корневого узла до узла x. Глубина корневого узла равна 0, глубина узла второго слоя равна 1 и т. д.
• Высота узла = длина пути от конечного узла до узла x.
• Степень узла= количество поддеревьев узла.
• конечный узел = узел с нулевой степенью

Двоичное дерево

• Каждый узел имеет не более 2 поддеревьев, а максимальная степень узла равна 2.
• Левое поддерево и правое поддерево идут по порядку, и порядок нельзя изменить
• Даже если узел имеет только 1 поддерево, необходимо различать левое и правое поддеревья.
• Дерево AVL, красно-черное дерево, дерево растяжения, дерево козлов отпущения, B-дерево, дерево B+, дерево B*, дерево словарей (дерево Trie)

6. Хэш-таблица

• Это специальная структура данных, доступ к которой осуществляется напрямую в соответствии с функцией сопоставления и которая хранит данные в виде ключ: значение.
• f(клавиша) = место хранения
• Хеш-таблица предназначена для преобразования уникального идентификатора в соответствующую позицию с помощью хэш-функции.
• Поиск, вставка: временная сложность O(1)
• Однако, если все хеш-значения сопоставляются с одним и тем же адресом, временная сложность поиска составляет O (n).
• Связывание адресации: хеш-функция сопоставляет значение ключа с каждой позицией в хеш-таблице.
• Адресация открытия — если есть конфликт сопоставления местоположения, когда ключ 1 и ключ 2 имеют одно и то же местоположение, поместите ключ 2 в пустое место и инициируйте процесс поиска свободной позиции.
• Методы обнаружения = линейное зондирование, квадратичное зондирование, двойное хеширование

7. Куча

• это полное бинарное дерево
• Это древовидная структура графа, которая используется для реализации «очередей с приоритетом».
• Значение узла в куче всегда не больше и не меньше значения его родительского узла.
• Min Heap = куча с наименьшим корневым узлом, удовлетворяющим ki ≤ K2i+1 и ki ≤ k2i+2
• Max Heap = куча с наибольшим корневым узлом, удовлетворяющим ki ≥ k2i+1 и ki ≥ k2i+2

8. График

• Это относительно сложная структура данных и относительно сложные и эффективные алгоритмы хранения данных.
• Он показывает сложное «многие ко многим» между объектами и отношением объектов.
• Он состоит из конечного множества V вершин и множества E ребер.

Его можно разделить на неориентированный граф и ориентированный граф.

• (v, w) представляет собой неориентированное ребро, т. е. v и w взаимосвязаны
• ‹v, w› представляет собой направленное ребро, которое начинается в v и заканчивается в w

Графики можно разделить на взвешенные и невзвешенные:

• Взвешенный граф: каждое ребро имеет определенный вес, обычно число
• Невзвешенный граф: каждое ребро не имеет веса, что также можно понимать как вес 1

Графы можно разделить на связные графы и несвязные графы:

• Связный граф: все точки соединены путями
• Несвязный граф: есть две точки, не соединенные путем.

Вершины в графе имеют понятие степени

1. Степень — Сумма всех точек, связанных с ней
2. Входящая степень — существующая в ориентированном графе сумма всех ребер, имеющих доступ к этой точке.
3. Outстепень — Существующий в ориентированном графе, сумма количества ребер, соединенных с точкой

Представление графа

• Матрица смежности. Граф с n вершинами должен иметь матрицу размера n x n.
• Список смежности — граф с массивом связанных списков.
• Алгоритмы: алгоритм поиска для графов, поиск в ширину (BFS), поиск в глубину (DFS) и т. д.

Большая сложность

Ссылки