Динамические структуры данных: стеки, очереди, деревья.

Динамические структуры данных – это структуры данных, память под которые выделяется и освобождается по мере необходимости. Динамические структуры данных в процессе существования в памяти могут изменять не только число составляющих их элементов, но и характер связей между элементами. При этом не учитывается изменение содержимого самих элементов данных. Порядок работы с динамическими структурами данных следующий: создать (отвести место в динамической памяти); работать при помощи указателя; удалить (освободить занятое структурой место). Во многих задачах требуется использовать данные, у которых конфигурация, размеры и состав могут меняться в процессе выполнения программы. Для их представления используют динамические информационные структуры. Стеки.

Стеком будем называть структуру данных, для которой определены операции добавления и удаления элементов и элементы которой организованы таким образом, что их удаление будет осуществляться точно противоположно тому порядку, в каком проводилось добавление. Организация стека - используется доступ по принципу "последней пошел, первый вышел". Представленный здесь стек содержит 6 элементов, причем элементы в стек были помещены в следующем порядке: А, В, С, D, E, F. Извлекаться же они могут только в порядке F, E, D, С, В, А, т. е. для того, чтобы извлечь из стека элемент С, необходимо сначала извлечь элементы F, Е и D. Операции над стеками и их реализация: Init — создает пустой стек; Empty — возвращает значение true, если стек пуст и false в противном случае; Push — добавляет элемент в стек; Pop — удаляет элемент из стека. Исторически сложилось так, что две основные операции для стека - поместить в стек и выбрать из стека - получили название соответственно "затолкнуть" и "вытолкнуть".

Очереди.

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

Например, пусть у нас есть очередь из трех элементов А,В,С, в которую первым был помещен элемент А, затем — элемент В, а последним — элемент С. После удаления элемента А первым элементом очереди будет элемент В. При этом элемент А остался в массиве на своем месте, но его уже нет в очереди, так как указатель начала очереди указывает на элемент В, т. е. следующий элемент массива. Если мы добавим в очередь новый элемент D, то он будет помещен в конец очереди, определяемый указателем конца. Очередь, в которой нет ни одного элемента, называется пустой. В этом случае оба указателя показывают на одно и то же место. Операции над очередями: Init — создает пустую очередь; Empty — возвращает значение true, если очередь пуста, и false в противном случае; Insert — добавляет элемент в конец очереди; Remove — удаляет элемент из начала очереди.

Деревья.
Бинарное (двоичное) дерево (binary tree) - это упорядоченное дерево, каждая вершина которого имеет не более двух поддеревьев, причем для каждого узла выполняется правило: в левом поддереве содержатся только ключи, имеющие значения, меньшие, чем значение данного узла, а в правом поддереве содержатся только ключи, имеющие значения, большие, чем значение данного узла. Бинарное дерево является рекурсивной структурой, поскольку каждое его поддерево само является бинарным деревом и, следовательно, каждый его узел в свою очередь является корнем дерева. Узел дерева, не имеющий потомков, называется листом. Схематичное изображение бинарного дерева:

Бинарное дерево должно реализовывать следующие операции:

Инициализация бинарного дерева: текущий указатель устанавливается неопределенным (или нулевым, nil), а количество узлов нулевым.

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

Получение значения текущего элемента

Поиск заданного элемента: если искомый элемент находится в дереве, то возвращается указатель на него, в противном случае возвращается nil, сигнализирующий о неуспехе поиска значения

Удаление узла из дерева

Уничтожение бинарного дерева

Основные понятия объектно-ориентированного программирования: наследование, полиморфизм, инкапсуляция.

Объектно-ориентированное программирование (ООП) – это методика разработки программ, в основе которой лежит понятие объекта, как некоторой структуры, описывающей объект реального мира, его поведение.

Язык Object Pascal, поддерживая концепцию объектно-ориентированного программирования, дает возможность определять классы.

Класс – это сложная структура, включающая, помимо описания данных, описание процедур и функций, которые могут быть выполнены над представителем класса – объектом.

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

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

В Object Pascal ограничение доступа к полям объекта реализуется при помощи свойств объекта. Свойство объекта характеризуется полем, сохраняющим значение свойства, и двумя методами, обеспечивающими доступ к полю свойства. Метод установки значения свойства называется методом записи свойства (write), а метод получения значения свойства – методом чтения свойства (read).

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

Полиморфизм – это возможность использовать одинаковые имена для методов, входящих в различные классы. Концепция полиморфизма обеспечивает в случае применения метода к объекту использования именно того метода, который соответствует классу объекта.