- •Понятие о структуре данного. Уровни представления структур данных.
- •Классификация сд в программах пользователя и в памяти эвм
- •Сд в оперативной памяти
- •Сд типа массив.
- •Сд типа запись (прямое декартово произведение).
- •Сд типа таблица.
- •Операции над таблицей:
- •Временная сложность алгоритмов.
- •Сд типа хеш-таблица.
- •Операция включения элемента в таблицу.
- •Операция исключения элемента из таблицы:
- •Сортировки. Улучшенные методы сортировок.
- •Классификация задач по временной сложности.
- •Сд типа стек.
- •Алгоритм сортировки Хоара (стек используется для хранения границ сортируемой области в таблице):
- •Сд типа очередь.
- •Связное распределение памяти.
- •Сд типа линейный односвязный список.
- •Сд типа указатель.
- •Статические и динамические переменные.
- •Сд типа циклический линейный список.
- •Сд типа двусвязный линейный список.
- •Сд типа дек.
- •Многосвязные списки.
- •Средства объектно-ориентированного программирования.
- •Объекты и свойства инкапсуляции.
- •Наследование и переопределение.
- •Полиморфизм. Виртуальные методы.
- •Динамические объекты. Деструкторы.
- •Обработка ошибок при работе с динамическими объектами.
- •Модули, экспортирующие объекты.
- •Нелинейные структуры данных.
- •Сд типа дерево.
- •Представление деревьев в связной памяти эвм.
- •Алгоритмы прохождения деревьев в глубину и в ширину.
- •Представление деревьев в виде бинарных.
- •Представление бинарных деревьев в связной памяти. Прошитые деревья
- •Формирование бинарного дерева.
- •Применение бинарных деревьев в алгоритмах поиска.
- •Операция включения в сд типа бинарное дерево.
- •Операция исключения из бинарного дерева.
- •Представление бинарного дерева в прямоугольной памяти.
- •Применение бинарных деревьев.
- •Сд типа граф.
- •Представление графа в памяти эвм.
- •Алгоритмы прохождения графа.
- •Топологическая сортировка.
- •Организация данных во внешней памяти. Типы и характеристики устройств внешней памяти.
- •Сд типа последовательный файл.
- •Сд типа файл прямого доступа.
- •Сд типа индексно-последовательный файл.
- •Сд типа хеш-файл.
- •Внешняя сортировка.
- •Алгоритм прямого слияния.
- •Многофазная сортировка.
- •Сущность базы данных. Системы управления базами данных.
- •Общая структура субд.
- •Реляционная модель субд.
- •Язык реляционной алгебры.
Динамические объекты. Деструкторы.
Экземпляры объектовых типов могут быть определены также и динамически, с использованием стандартной процедуры New. На практике этот способ применяется значительно чаще. Экземпляр в общем виде определяется так:
Var <имя ссылки на объект>^. <тип объекта>
Техника динамического порождения и инициализации объектов выглядит для нашего примера следующим образом:
Var ObCirclePtr: ^Circle;
begin
New (ObCirclePtr);
ObCirclePtr^.Init (20, 30, 10);
………………………
В целях большей наглядности Turbo Pascal допускает совмещение порождения объекта и его инициализации конструктором в одном вызове New:
New (ObCirclePtr, Init (20, 30, 10));
Освобождение динамической памяти, выделенной объекту, реализуется стандартной процедурой Dispose: Dispose (<имя ссылки на объект>);
Необходимо учесть, что если поля данных объекта были динамическими и для них выделялась дополнительная память, то их надо освободить до уничтожения самого объекта. Для этих целей или для других завершающих действий перед уничтожением вводится специальный вид метода – деструктор. Он объявляется среди прочих методов с помощью замены ключевого слова Procedure на служебное слово Destructor. Функции деструктора по сути противоположны функциям конструктора. Действие завершается ключевым словом Done. Деструкторы могут наследоваться, при этом желательно делать их виртуальными, чтобы выполнялся тот деструктор, который соответствует именно этому типу объекта.
Имеется также расширенная возможность использования процедуры уничтожения: Dispose (<имя ссылки на объект>, <имя деструктора>); При этом вначале выполняется деструктор, а затем объект уничтожается.
Если объект содержит виртуальные методы, то деструктор осуществляет поиск размера объекта, т.е. того участка памяти, который нужно уничтожить. Чтобы выполнение уничтожения было корректным, используют пустой блок: Begin End;
Обработка ошибок при работе с динамическими объектами.
HeapError – системная переменная, имеющая указательный тип pointer. Она указывает на функцию:
HeapError := @HeapFunc;
Function HeapFunc (Size: word): integer;
Данная функция вызывается каждый раз, когда работают процедуры генерирования динамического объекта, и когда не может быть выполнен запрос на распределение объекта. Здесь Size указывает на то, какой блок памяти не может разместиться в динамической памяти. В качестве результата функция возвращает значения 0, 1 или 2. Если функция возвращает значение 0, то осуществляется аварийный останов. Если значение 1, то при выполнении процедуры New (P) ссылка на объект принимает значение константы. Если значение 2, то вызов повторяется.
{$F+}
Function HeapFunc (Size: word): integer;
begin
HeapFunc:=1;
end;
{$F-}
New (P);
if P = nil then <обработка исключительной ситуации>
else <нормальный ход программы>
Таким образом, если мы имеем расширенные процедуры генерирования объекта (New (<>,<>)), необходимо учитывать следующее: когда начинает выполняться тело конструктора, то при выполнении алгоритма может потребоваться дополнительная память. В этом случае мы должны сделать откат, т.е. отменить все проделанные распределения в конструкторе и, в завершение, освободить экземпляр типа объекта. Ссылка должна получить значение константы. Для выполнения отката используется стандартная процедура Fail, располагающаяся в конструкторе. Вызов этой процедуры освобождает динамический экземпляр, который был размещен в памяти до входа в конструктор, и возвращает в ссылке значение nil.
Нехватка памяти может иметь место и для статических объектов с динамическими полями. Так как объект статический, то необходимо передать сигнал о невозможности распределения. В этом случае имя конструктора используется как логическая функция (если значение False, то распределение невозможно).