Динамические структуры данных

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

Это не всегда удобно так как:

1. Большие структуры данных занимаются большие объемы памяти ЭВМ на все время выполнения программы, то есть неэкономно используется память.

2. Часто требуется, чтобы структуры данных меняли свои размеры и состав в ходе решения задачи.

При использовании динамических структур, решаются эти две проблемы, а также появляется возможность использовать нестандартные структуры данных, такие как списки, очереди, стеки, деревья.

Динамические структуры данных – это структуры, для работы с которыми используются указатели в явном и неявном виде.

В неявном виде указатели используются для динамических строк, массивов и для классов.

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

Динамические массивы

В отличие от статического массива при использовании динамического массива можно задавать количество элементов в массиве в любом месте программы. Память под такие массивы выделяется динамически. Нумерация элементов в динамическом массиве всегда начинается с нуля.

Структура:

Var <имя_перем>:array of <тип_элем>;

При запуске программы массив не содержит элементов и значение переменной-массива равно Nil.

Для того чтобы задать или изменить количество элементов в динамическом массиве используется процедура:

SetLength(<масс>,<кол_эл>)

Если текущее количество элементов в <масс> меньше <кол_эл>, то выделяется память под дополнительные элементы в конце массива, значения старых элементов сохраняются, а новых неопределены. Если текущее количество элементов в <масс> больше <кол_эл>, то в конце массива удаляются необходимые элементы и память из-под них освобождается.

Чтобы удалить все элементы из массива и освободить память необходимо присвоить переменной-массиву значение Nil.

Чтобы получить текущее количество элементов в масиве используется функция Length(<масс>).

Также для динамических массивов применимы функции:

High(<масс>) = – максимальный индекс в массиве (Length(mass)-1 или –1, если пустой))

Low(<масс>) – минимальный индекс в массиве (= 0)

Функция Copy(A,P,K) - возвращает подмассив массива A начиная с Р индекса K элементов.

Стеки

Стеком называется динамическая структура данных, добавление элемента в которую и исключение элемента из которой производится из одного конца, называемого вершиной стека. Стек работает по принципу:

LIFO (Last-In, First-Out) - поступивший последним, обслуживается первым.

Над стеками выполняется две операции:

- добавление элемента в стек;

- извлечение элемента из стека.

В Delphi существует класс TStack, который реализует стек динамических переменных.

Методы этого класса:

Добавить элемент в стек

Функция Push(AItem: Pointer): Pointer;

Извлечь элемент из стека

Функция Pop: Pointer;

Очереди

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

FIFO (First-In, First-Out) - поступивший первым, обслуживается первым.

Над очередями выполняется две операции:

- добавление элемента в начало очереди;

- извлечение элемента из конца очереди.

В Delphi существует класс TQueue, который реализует очередь динамических переменных.

Методы этого класса:

Добавить элемент в начало очереди

Функция Push(AItem: Pointer): Pointer;

Извлечь элемент из конца очереди

Функция Pop: Pointer;

Списки

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

В Delphi существует класс TList, который реализует список динамических переменных.

Методы этого класса:

Добавить элемент вконец списка

Функция Add(Item: Pointer): Integer;

Удалить все элементы

Процедура Clear;

Удалить элемент с номером Index

Процедура Delete(Index: Integer);

Удалить первый встретившийся элемент Item

Функция Remove(Item: Pointer): Integer;

Вставить элемент перед элементом с номером Index

Процедура Insert(Index: Integer; Item: Pointer);

Свойства:

Count – количество элементов в списке

Items[i] – массив элементов стека. i=0,…,Count-1. Необходимо учитывать, что при добавлении или удалении элементов индексы элементов могут изменяться.

В Delphi также существует класс TStrings, наследник класса TList, который реализует список строк.

Классы

Классы — это специальные типы данных языка Object Pascal, которые используются для описания объектов.

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

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

Определение нового класса выглядит следующим образом:

type <Имя класса> = class[(<Класс-предок>)] [<Список элементов класса>]

[private] [<Список элементов класса>]

[protected]

[<Список элементов класса>]

[public] [<Список элементов класса>]

[published] [<Список элементов класса>]

end;

где <Имя класса> — любое корректное имя (выбирается произвольно), <Класс-предок> — название класса, наследником которого является создаваемый класс, а <Cписок элементов класса> содержит свойства и методы нового класса.

Для каждого элемента класса можно установить разную видимость. Для этого предназначены четыре ключевых слова: private, protected, public и published.

Видимость элемента класса определяет, где в программе и как будет виден данный элемент класса. Минимальная видимость элемента класса задается ключевым словом private, ключевое слово protected определяет средний уровень видимости. Наконец, public и published определяют наивысшую степень доступности.

Если перед описанием элемента класса не ставится ключевое слово, определяющее его степень видимости, то считается, что видимость элемента такая же, как и у предыдущего элемента класса. Если элемент перед первым элементом класса не указано ключевое слово, то он будет иметь видимость public.

Рассмотрим все четыре ключевых слова более подробно.

Private (частные) — определяет элементы класса, которые не видны вне модуля, в котором был объявлен класс, содержащий эти элементы. Другими словами, частные методы не могут быть вызваны из других модулей, а частные поля или свойства не могут быть считаны или изменены из других модулей.

Protected (защищенные) — определяет элементы класса, которые видны только внутри модуля, где определен класс, содержащий эти элементы, а также внутри других модулей, где присутствуют классы-потомки данного класса.

Public (общедоступные) — определяет элементы класса, которые видны в любом месте программы и из любых модулей, в которых виден сам класс.

Published (опубликованные) — определяет элементы класса, имеющие ту же видимость, что и public-элементы. Единственное отличие заключается в том, что опубликованные элементы порождают информацию о типе времени выполнения (RTTI). Благодаря данной информации, Delphi может осуществить проверку принадлежности элементов объекта к тому или иному классу. Delphi использует RTTI для доступа к значениям свойств при сохранении и загрузке файлов форм, чтобы иметь возможность отобразить свойства в инспекторе объектов и ассоциировать конкретные методы с конкретными свойствами. Все методы классов могут быть опубликованы, за исключением перегруженных (overload) методов, имеющих одинаковые имена.

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

В OPascal имеется понятие абстрактного класса.

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

Все объекты в OPascal созданы из абстрактного класса TObject. Класс TObject — предок многих простых классов. Этот класс объединяет в себе основные функции, которые свойственны всем объектам OPascal. TObject обеспечивает:

• возможность создания, уничтожения и управления экземплярами объектов, а также резервирование памяти и ее освобождение после уничтожения экземпляра;

• поддержку информации об объектах и типах;

• поддержку обработки сообщений.

Класс называется прямым потомком класса TObject, если он произведен непосредственно от класса TObject.

Класс называется косвенным потомком от класса TObject, если он произведен от класса, являющегося прямым или косвенным потомком класса TObject (то есть произведен от промежуточного класса).

Если при создании нового класса не указывается родительский класс, то считается, что родитель — класс TObject.

Переменная типа класс (экземпляр объекта) является динамической переменной, поэтому перед работой с такой переменной ее необходимо создать (выделить память под переменную), а после работы с ней удалить (освободить память).

Для создания экземпляра объекта используются методы-конструкторы, а для удаления объекта метод-деструктор.

Для создания объекта используется конструкция:

<Имя переменной>:=<Имя класса>.<Метод конструктор>

Для удаления объекта необходимо вызвать метод деструктор этого класса.

Класс TObject содержит конструктор Create и деструктор Free, которые соответственно, выделяют и освобождают память под элементы создаваемого класса.

Например:

Var a:TMyObject; // объявление объекта - экземпляра класса TMyObject

...

a:=TMyObject.Create; // создание объекта а

...

работа с объектом a

...

a.Free; // удаление объекта a

Для выполнения каких-либо дополнительных действий при создании или удалении объекта конструктор или деструктор может быть перегружен в классе-потомке.

Поля

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

После создания нового класса он наследует все поля своего класса-предка. Удалить или переопределить поля класса-предка невозможно.

Приведем пример описания поля объекта:

type TNumber = class

FInt: Integer;

end;

Данный пример создает в классе TNumber новое поле FInt целочисленного типа.

Примечание

По взаимному соглашению разработчиков, имена полей должны начинаться с буквы F (по-английски field означает поле).

Методы

Методы — это процедуры или функции, принадлежащие объекту. Методы определяют поведение объекта.

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

type TMyObject = class(TObject) ...

procedure DoSomething; // Объявление метода DoSomething ...

end;

Здесь, внутри описания нового класса, объявляем метод DoSomething с помощью служебного слова procedure. Эта процедура должна находиться в разделе реализации модуля, в котором был описан данный класс. Например:

procedure TMyComponent.DoSomething;

begin // Здесь размещаем команды и операторы, которые должны выполняться // при вызове метода DoSomething на выполнение

end;

Заметим, что при создании процедуры DoSomething мы должны указывать ее полное имя, вместе с указанием имени компонента или класса (procedure TMyComponent.DoSomething;).

В зависимости от вида метода, он может вызываться различными способами. Методы бывают следующих видов:

• статические;

• виртуальные (virtual);

• динамические (dynamic);

• методы обработки сообщений (message);

• конструкторы и деструкторы(constructor/destructor);

• замещенные (override);

• абстрактные (abstract).

По умолчанию методы являются статическими и вызываются как любые другие подпрограммы.

Для методов конструкторов вместо слова procedure указывается constructor.

Для методов деструкторов вместо слова procedure указывается destructor.

Для остальных видов методов, после заголовка метода в описании класса через точку с запятой указывается один из вышеперечисленных идентификаторов.(virtual, ..., abstract).

Виртуальные и динамические методы могут быть замещенными (override) или абстрактными (abstract).