Линейные и нелинейные структуры данных, представление деревьев

ДЕНЬ 1 – РАЗДЕЛ 1: ДЕРЕВЬЯ ТЕМА: Линейные и нелинейные структуры данных, древовидное представление 1. ВВЕДЕНИЕ В СТРУКТУРЫ ДАННЫХ Структура данных: Структура данных — это способ организации, хранения и управления данными в памяти для обеспечения эффективного доступа и изменения данных. Структуры данных в основном классифицируются на: 1. Линейные структуры данных 2. Нелинейные структуры данных 2. ЛИНЕЙНЫЕ СТРУКТУРЫ ДАННЫХ Определение: Линейная структура данных — это структура данных, в которой элементы расположены последовательно или линейно, причем каждый элемент связан со своим предыдущим и следующим элементом. Характеристики: Элементы хранятся в линейном порядке Одноуровневая организация данных Простой обход Использование памяти может быть последовательным или связанным Примеры: Массив Связный список Стек Очередь Двусторонняя очередь Пример пояснения: В массиве элементы хранятся в смежных ячейках памяти. Пример: Массив A = [10, 20, 30, 40] Здесь: 10 → 20 → 30 → 40 3. НЕЛИНЕЙНЫЕ СТРУКТУРЫ ДАННЫХ Определение: Нелинейная структура данных — это структура данных, в которой элементы не расположены последовательно и могут быть соединены несколькими способами. Характеристики: Иерархическая или графовая структура Многоуровневая организация данных Сложный обход Эффективное представление связей Примеры: Дерево Граф Куча Префиксное дерево (Trie) Почему нелинейные структуры? Они используются, когда данные имеют иерархические связи, например: Файловые системы Организационные схемы Индексирование баз данных 4. ДРЕВЕСНАЯ СТРУКТУРА ДАННЫХ Определение: Дерево — это нелинейная иерархическая структура данных, состоящая из узлов, соединенных ребрами, с одним корневым узлом и нулем или более поддеревьями. Основные термины: Узел: элемент дерева Корень: самый верхний узел Родитель: узел, имеющий дочерних узлов Дочерний узел: узел, производный от родителя Листовой узел: узел без дочерних узлов Ребро: соединение между двумя узлами Уровень: позиция узла в дереве Высота: максимальная глубина дерева Степень: количество дочерних узлов Пример дерева: A / \ B C / \ \ D E F 5. ПРЕДСТАВЛЕНИЕ ДЕРЕВА Деревья могут быть представлены в памяти двумя основными способами: 1. Последовательное представление (массив) 2. Связанное представление 5.1 ПОСЛЕДОВАТЕЛЬНОЕ (МАССИВНОЕ) ПРЕДСТАВЛЕНИЕ Определение: Элементы дерева хранятся в массиве на основе их индексов. Формула: Если узел находится по индексу i: Левый потомок = 2i Правый потомок = 2i + 1 Родитель = i / 2 Пример: Дерево: A / \ B C / \ D E Представление в виде массива: Индекс: 1 2 3 4 5 Значение: A B C D E Преимущества: Простая реализация Быстрый доступ Недостатки: Расход памяти для разреженных деревьев Фиксированный размер 5.2 СВЯЗАННОЕ ПРЕДСТАВЛЕНИЕ Определение: Каждый узел содержит данные и указатели на своих потомков. Структура узла дерева: Данные Указатель на левого потомка Указатель на правого потомка Синтаксис (подобный C): struct node { int data; struct node* left; struct node* right; }; Преимущества: Динамический размер Эффективное использование памяти Недостатки: Дополнительная память для указателей Сложная реализация 6. ПРИМЕНЕНИЕ ДЕРЕВЬЕВ В РЕАЛЬНОЙ ЖИЗНИ Структура файлов и папок Индексирование баз данных (B-деревья) Вычисление выражений Анализ XML/HTML Искусственный интеллект (деревья решений)