- •Структуры и алгоритмы обработки данных
- •Логическая и физическая структуры данных
- •Классификация структур данных
- •Основные операции над структурами данных
- •Алгоритм и примеры задач, решаемых с помощью алгоритмов
- •Адресация и распределение памяти
- •Адресные пространства и модели оперативной памяти
- •Формирование физического адреса в реальном режиме
- •Особенности адресации в защищенном режиме
- •Кэширование
- •Анализ алгоритмов
- •Быстродействие – основной показатель эффективности алгоритма
- •Подсчет числа простейших операций
- •Лучший, средний и худший случаи
- •Алгоритмы и платформы
- •Виртуализация памяти
- •Использование кэша
- •Выравнивание данных
- •Рандомизированные алгоритмы
- •Общая характеристика записей и способы описания в Delphi
- •Многоуровневые записи
- •Выравнивание и упакованные записи
- •Записи с вариантной частью
- •Массивы
- •Общая характеристика массивов
- •Статические (стандартные) массивы
- •Многомерные статические массивы
- •Свойства статических массивов
- •Открытые массивы
- •Динамические массивы
- •Динамические векторы
- •Многомерные динамические массивы
- •Массивы типа Variant
- •Вставка и удаление в массиве
- •Связные списки и алгоритмы их обработки
- •Списки и их разновидности
- •Односвязный список
- •Общая характеристика односвязного списка
- •Структура элемента односвязного списка
- •Формирование односвязного списка
- •Просмотр односвязного списка
- •Вставка элемента в односвязный список
- •Удаление элемента из односвязного списка
- •Линейный двухсвязный список
- •Структура элемента двухсвязного списка
- •Реализация операций в линейном двухсвязном списке
- •Нелинейный двухсвязный список
- •Нелинейный трехсвязный список
- •Определение плекса и его общие признаки
- •Иерархическая списковая структура. Сетевая структура
- •Достоинства и недостатки связных списков
- •Функциональные и свободные списки
- •Общая характеристика функционального и свободного списка
- •Методы формирования свободного списка
- •Стеки, очереди, деки и операции в них
- •Общая характеристика
- •Очередь
- •Динамические множества и словари
- •Общая характеристика
- •Операции в динамических множествах
- •Деревья
- •Общая характеристика и некоторые определения
- •Представление дерева в памяти
- •Естественное представление дерева
- •Представление дерева с помощью вектора
- •Представление дерева с использованием списков сыновей
- •Методы обхода деревьев
- •Бинарное дерево
- •Структура бинарного дерева
- •Формирование бинарного дерева
- •Обход бинарного дерева
- •Преобразование любого дерева к бинарному дереву
- •Включение и исключение в дереве
- •Включение в дереве
- •Исключение в дереве
- •Поиск: определение и общая терминология
- •Линейный (последовательный) поиск
- •Последовательный поиск в упорядоченной таблице
- •Последовательный поиск при накоплении запросов
- •Индексно-последовательный поиск
- •Бинарный поиск
- •Поиск, использующий бинарное дерево
- •Сортировка
- •Общие сведения и некоторые определения
- •Внутренняя сортировка
- •Сортировка прямыми включениями
- •Сортировка бинарными включениями
- •Сортировка прямым выбором
- •Сортировка прямым обменом
- •Сортировка методом Шелла
- •Сортировка с помощью бинарного дерева
- •Пирамидальная сортировка
- •Быстрая сортировка разделением
- •Внешняя сортировка
- •Сортировка прямым слиянием
- •Сортировка естественным слиянием
- •Сортировка многопутевым слиянием
- •Многофазная сортировка
- •Хеширование и хеш-таблицы
- •Общие сведения и определения
- •Коллизии при хешировании
- •Разрешение коллизий при хешировании
- •Разрешение коллизий методом открытой адресации
- •Разрешение коллизий методом цепочек
- •Функции хеширования
- •Поисковые деревья
- •Бинарное дерево поиска
- •Структура бинарного дерева поиска и алгоритм поиска
- •Вставка элемента в бинарное дерево поиска
- •Удаление из бинарного дерева поиска
- •Красно-черные деревья
- •Определение красно-черного дерева, структура его элементов
- •Повороты
Реализация операций в линейном двухсвязном списке
Пока список пуст, курсоры его концов Left и Right не должны никуда указывать. Следовательно, способ инициализировать двухсвязный список заключается в присваивании этим указателям значения Nil:
Left:= Nil; Right:= Nil;
Текст программного кода формирования линейного двухсвязного списка из N элементов может быть записан следующим образом:
Var i: Integer;
Begin
i:= N;
While i > 0 Do Begin
New(Current);
Current^.Dir := Left; Current^.Back:= Nil;
IF i = N Then Right:= Current
Else Current^.Dir^.Back:= Current;
Left:= Current; Current^.Key:= i;
<заполнение полей Current^.Dat>
i:= i-1;
End; {While}
End;
Под управлением этого кода список дополняется элементами в направлении справа налево, т. е. первый созданный элемент окажется концевым правым элементом, а последний расположится на левом конце. Курсор текущего элемента будет ссылаться на левый концевой элемент.
Программа просмотра ЛДС аналогична программе просмотра односвязного списка. Необходимо только указать от какого конца, левого или правого, следует начинать продвижение по узлам. Например, если требуется выполнить просмотр списка слева направо, то можно использовать следующий фрагмент:
Current:= Left;
While Current <> Nil Do Begin
With Current^ Do Begin
<действия с полями элемента Current^>
End;
Current:= Current^.Dir;
End;
Для прохождения узлов справа налево в приведенном фрагменте нужно заменить идентификаторы Left на Right и Dir на Back.
Рассмотрим наиболее общий случай вставки, когда элемент, рядом с которым в логической структуре вставляется новый элемент, не является кольцевым элементом. Коды, реализующие дополнение линейного двухсвязного списка со стороны одного из концевых узлов, во многом напоминают вставку в начало односвязного списка. Итак, фрагмент программы вставки справа от текущего элемента, расположенного в средней части ЛДС, может содержать следующую последовательность операторов:
New(G); G^.Key:= 20;
G^.Dir:= Current^.Dir;
Current^.Dir:= G;
G^.Back:= Current;
G^.Dir^.Back:= G;
На рисунке 6.9 а показана логическая схема, изображающая ЛДС из трех элементов и элемент G^, созданный в результате выполнения первой строки рассматриваемого фрагмента. А на рисунке 6.9 б показана логическая структура, сформированная в после завершения вставки.
Рисунок 6.9 Операция вставки в ЛДС
Для иллюстрации операции удаления приведем фрагмент кода, при выполнении которого удаляется текущий элемент с перемещением его указателя на один элемент направо. Этот фрагмент может иметь вид:
G:= Current;
Current:= Current^.Dir;
G^.Back^.Dir:= Current;
Current^.Back:= G^.Back;
Dispose(G);
Плексы
Нелинейный двухсвязный список
Односвязный список всегда линейный. Двусвязный же список может быть и нелинейным, о чем свидетельствует следующий пример.
Представим себе, что двухсвязный список формируется из данных об абитуриентах ВУЗа. Причем первый указатель связывает элементы списка в порядке подачи абитуриентами документов в приемную комиссию, а второй – устанавливает упорядоченность элементов, соответствующую алфавитному порядку фамилий абитуриентов. Тогда, если к текущему моменту времени заявления о поступлении в ВУЗ подали шестеро абитуриентов, двусвязная структура, состоящая из данных об абитуриентах, может принять вид, изображенный на рисунке 6.10.
Рисунок 6.10 Логическая структура нелинейного двухсвязного списка
Ссылки List1 и List2 являются указателями двух отдельных односвязных списков, в каждый из которых одновременно входят все шесть элементов. Поля Р1 и Р2 всех элементов служат для хранения структурных ссылок, с помощью которых элементы связываются, формируя тем самым каждый из двух списков.
На рисунке 6.10 показано лишь одно из содержательных полей узлов, а именно, поле фамилии абитуриента (объекта предметной области). Из рисунка видно, что в списке, сформированном с помощью ссылки Р1, установлен следующий порядок следования узлов:
Фокин Лавров Бойко Яшина Власова Жеглов
В цепном списке, указателем которого является List2, этот список сформирован с помощью структурной ссылки Р2 элементы располагаются в следующем порядке:
Бойко Власова Жеглов Лавров Фокин Яшина
Представление логической структуры этого же двухсвязного списка может быть преобразовано к другому, эквивалентному, виду, который показан на рисунке 6.11. Рисунки 6.10 и 6.11 отображают структуру одного и того же нелинейного двухсвязного списка. Сопоставление рисунков 6.10 и 6.11 показывает, что оба цепных списка двухсвязной структуры, рассматриваемые по отдельности, являются линейными. Вся структура в целом, с учетом обеих связок, не линейна
Рисунок 6.11 Эквивалентная логическая структура нелинейного двухсвязного списка, изображенного на рисунке 6.10