- •Структуры и алгоритмы обработки данных
- •Логическая и физическая структуры данных
- •Классификация структур данных
- •Основные операции над структурами данных
- •Алгоритм и примеры задач, решаемых с помощью алгоритмов
- •Адресация и распределение памяти
- •Адресные пространства и модели оперативной памяти
- •Формирование физического адреса в реальном режиме
- •Особенности адресации в защищенном режиме
- •Кэширование
- •Анализ алгоритмов
- •Быстродействие – основной показатель эффективности алгоритма
- •Подсчет числа простейших операций
- •Лучший, средний и худший случаи
- •Алгоритмы и платформы
- •Виртуализация памяти
- •Использование кэша
- •Выравнивание данных
- •Рандомизированные алгоритмы
- •Общая характеристика записей и способы описания в Delphi
- •Многоуровневые записи
- •Выравнивание и упакованные записи
- •Записи с вариантной частью
- •Массивы
- •Общая характеристика массивов
- •Статические (стандартные) массивы
- •Многомерные статические массивы
- •Свойства статических массивов
- •Открытые массивы
- •Динамические массивы
- •Динамические векторы
- •Многомерные динамические массивы
- •Массивы типа Variant
- •Вставка и удаление в массиве
- •Связные списки и алгоритмы их обработки
- •Списки и их разновидности
- •Односвязный список
- •Общая характеристика односвязного списка
- •Структура элемента односвязного списка
- •Формирование односвязного списка
- •Просмотр односвязного списка
- •Вставка элемента в односвязный список
- •Удаление элемента из односвязного списка
- •Линейный двухсвязный список
- •Структура элемента двухсвязного списка
- •Реализация операций в линейном двухсвязном списке
- •Нелинейный двухсвязный список
- •Нелинейный трехсвязный список
- •Определение плекса и его общие признаки
- •Иерархическая списковая структура. Сетевая структура
- •Достоинства и недостатки связных списков
- •Функциональные и свободные списки
- •Общая характеристика функционального и свободного списка
- •Методы формирования свободного списка
- •Стеки, очереди, деки и операции в них
- •Общая характеристика
- •Очередь
- •Динамические множества и словари
- •Общая характеристика
- •Операции в динамических множествах
- •Деревья
- •Общая характеристика и некоторые определения
- •Представление дерева в памяти
- •Естественное представление дерева
- •Представление дерева с помощью вектора
- •Представление дерева с использованием списков сыновей
- •Методы обхода деревьев
- •Бинарное дерево
- •Структура бинарного дерева
- •Формирование бинарного дерева
- •Обход бинарного дерева
- •Преобразование любого дерева к бинарному дереву
- •Включение и исключение в дереве
- •Включение в дереве
- •Исключение в дереве
- •Поиск: определение и общая терминология
- •Линейный (последовательный) поиск
- •Последовательный поиск в упорядоченной таблице
- •Последовательный поиск при накоплении запросов
- •Индексно-последовательный поиск
- •Бинарный поиск
- •Поиск, использующий бинарное дерево
- •Сортировка
- •Общие сведения и некоторые определения
- •Внутренняя сортировка
- •Сортировка прямыми включениями
- •Сортировка бинарными включениями
- •Сортировка прямым выбором
- •Сортировка прямым обменом
- •Сортировка методом Шелла
- •Сортировка с помощью бинарного дерева
- •Пирамидальная сортировка
- •Быстрая сортировка разделением
- •Внешняя сортировка
- •Сортировка прямым слиянием
- •Сортировка естественным слиянием
- •Сортировка многопутевым слиянием
- •Многофазная сортировка
- •Хеширование и хеш-таблицы
- •Общие сведения и определения
- •Коллизии при хешировании
- •Разрешение коллизий при хешировании
- •Разрешение коллизий методом открытой адресации
- •Разрешение коллизий методом цепочек
- •Функции хеширования
- •Поисковые деревья
- •Бинарное дерево поиска
- •Структура бинарного дерева поиска и алгоритм поиска
- •Вставка элемента в бинарное дерево поиска
- •Удаление из бинарного дерева поиска
- •Красно-черные деревья
- •Определение красно-черного дерева, структура его элементов
- •Повороты
Удаление элемента из односвязного списка
Для удаления простейшим вариантом является удаление элемента, находящегося после текущего узла. В этом случае необходимо установить, чтобы указатель Next текущего узла, указывавший до удаления на удаляемый элемент, стал указывать на элемент, расположенный после удаляемого. Если стартовая структура такая же, как изображенная на рисунке 6.4 а, то для удаления элемента с меткой 3 можно использовать следующий программный код:
G:= Current^.Next;;
Current^.Next:= G^.Next;
Dispose(G);
Процесс и результат выполнения операторов этого фрагмента, показан на рисунке 6.6
Рисунок 6.6 Процесс удаления узла в односвязном списке:
а – «переброска» структурного указателя текущего узла, к узлу с меткой 4, расположенному после удаляемого узла; б – уничтожение элемента с меткой 3
Код операции удаления первого элемента списка может выглядеть следующим образом:
Current:= First^.Next;;
Dispose(First);
First:= Current;
а с помощью фрагмента, приведенного ниже, удаляется последний элемент односвязного списка, если именно этот последний элемент адресуется курсором Current:
G:= First;
While G^.Next <> Current Do
G:= G^.Next;
G^.Next:= Nil;
Dispose(Current); Current:= G;
Здесь в While-цикле курсор G перемещается к предпоследнему элементу. Затем в поле структурного указателя элемента G^ записывается значение Nil, в результате чего этот элемент становится последним в списке. Удаляемый элемент Current^ уничтожается, и текущим становится новый последний элемент.
Линейный двухсвязный список
Односвязный список обеспечивает возможность продвижения лишь в одном направлении от начала к концу при просмотре списка. Линейный двусвязный список (linear double-linked list) дает возможность двигаться в одном из двух направлений. Он отличается от односвязного тем, что каждый его элемент содержит два логических указателя, один из которых, прямой указатель (direct pointer), адресует, как и в односвязном списке, следующий справа элемент, а другой, обратный указатель (backward роinter), адресует предыдущий элемент списка. Логическая структура линейного двусвязного списка (ЛДС) представлена на рисунке 6.7. Начало и конец такого списка логически эквивалентны, так как доступ к любому элементу может быть осуществлен с любого конца. Поэтому вместо терминов «начало» и «конец» списка используются термины «левый конец» и «правый конец».
Рисунок 6.7 Два варианта изображения логической структуры линейного двухсвязного списка
В кольцевом двухсвязном списке прямой указатель самого правого узла ссылается на самый левый элемент, и обратный указатель самого левого узла адресует самый правый в логической структуре узел. Логическая структура кольцевого двухсвязного списка представлена на рисунке 6.8
Рисунок 6.8 Кольцевой двухсвязный список
Структура элемента двухсвязного списка
Структура узла двухсвязного списка, в общем случае, и, в частности, линейного двухсвязного списка, может задаваться следующими описаниями:
Type
PNodeDList = ^TNodeDList;
TNodeDList = Record
Key: Integer;
Dat: <идентификатор типа данных>;
Dir, Back: PNodeDlist;
End;
Тип TNodeDList это самоадресующийся тип. Он предусматривает наличие в элементе двухсвязного списка двух структурных указателей: поле Dir предназначено для размещения указателя на следующий правый элемент, поле Back на следующий элемент, расположенный в логической структуре слева. Поле Key введено с целью облегчения дальнейших пояснений.
Для иллюстрации операций в ЛДС нам потребуется описание некоторых переменных-курсоров:
Var Left, Right, Current, G: PNodeDList;