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

данные

Отношения между элементами данных

Установить структуру

линейная структура

древовидная структура

структура графа

последовательная структура хранения

структура хранения цепи

Структура хранения индекса

Структура хранения хеша

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

Конечность

уверенность

осуществимость

входить

выход

правильность

читабельность

Надежность

Высокая эффективность и малый объем хранения

Поиск в таблице последовательностей по значению

Вставка таблицы последовательности

удалить

вершина стека

нижняя часть стека

top=-1 — пустой стек

top=MAXSIZE-1 означает полный стек

Похоже на односвязный список

хвост очереди

Лидер группы

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

Операции с участием головного узла требуют особого обращения.

Указатель головы не равен нулю

Поле указателя последнего узла хранит адрес первого узла, образуя кольцо.

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

Есть предшественники и продолжатели

Базовый адрес (i 1)*n (j-1)

Траверс

Средняя длина поиска=n 1/2

Создать индексную запись

Средняя длина поиска = (n/s s)/2 1

Метод построения хеш-функции

Анализ производительности поиска хеша

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

Разделенный на две части, левая часть упорядочена, а правая сторона неупорядочена. Первый элемент справа занимает соответствующую позицию слева.

О (квадрат)

Стабилизировать

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

нестабильный

Сравнить n-i 1 элемент последовательно слева направо.

Стабилизировать

квадрат/2

Возьмите максимальное значение из неупорядоченной последовательности и добавьте его в конец упорядоченной последовательности.

квадрат

Стабилизировать

Множественная сортировка по ключевым словам

Разделите последовательность на две части (необходимо для обеспечения относительного соотношения размеров)

нлогн

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

Назовите себя прямо или косвенно

Определение рекурсивно

Структуры данных рекурсивны

Небольшой масштаб, легко решить

Проблему можно разложить на подзадачи одного типа с оптимальной подструктурой.

Решение исходной задачи можно получить объединением подзадач

подзадачи независимы

Итерационный метод

основной метод

Тратить

лист

ребенок

родители

предок

Уровень узла

степень двоичного дерева

Глубина двоичного дерева

полное двоичное дерево

полное двоичное дерево

Полное двоичное дерево должно быть полным двоичным деревом, а полное двоичное дерево не может быть полным двоичным деревом.

1. В непустом бинарном дереве общее количество узлов i-го уровня не превышает i>=1.

2. Бинарное дерево глубины h имеет не более 2^h - 1 узлов (h>=1) и не менее h узлов.

3. Для любого бинарного дерева, если количество листовых узлов равно N0, а общее количество узлов степени 2 равно N2, то N0=N2 1.

4. Глубина полного двоичного дерева с n узлами равна logn 1.

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

1. Обход предзаказа:

2. Обход по порядку:

3. Обход постзаказа:

Обход приложения

вставлять

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

Преобразование двоичного отсортированного дерева в сбалансированное двоичное дерево.

Бинарное дерево с наименьшей длиной взвешенного пути

Конструкция дерева Хаффмана

Кодирование Хаффмана

Узлы Brother соединены линиями

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

Количество ребер n(n-1)

Количество ребер n(n-1)/2

степень

степень

Количество сторон == сумма градусов/2

простой путь

Длина пути – это количество ребер, которые он содержит.

Сильно связный граф

список обратной смежности

тиалвекс

Неориентированный граф

Полный граф с n вершинами имеет n (n-2) различных остовных деревьев.

Алгоритм Прима

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

Разделен на два набора точек.

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