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

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

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

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

Динамическая структура  данных характеризуется тем что:

• она не имеет имени;
• ей выделяется память в процессе выполнения программы;
• количество элементов структуры может не фиксироваться;
• размерность структуры может меняться в процессе выполнения программы;
• в процессе выполнения программы может меняться характер взаимосвязи между элементами структуры.

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

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

Необходимость в  динамических структурах данных обычно возникает в следующих случаях.

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

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

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

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

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

Вместе с тем, связное  представление не лишено и недостатков, основными из которых являются следующие:

• на поля, содержащие указатели для связывания элементов друг с другом, расходуется дополнительная память;
• доступ к элементам связной структуры может быть менее эффективным по времени.

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

Порядок работы с  динамическими структурами данных следующий:

1. создать (отвести место в динамической памяти);
2. работать при помощи указателя;
3. удалить (освободить занятое структурой место).

Классификация динамических структур данных

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

• однонаправленные (односвязные) списки;
• двунаправленные (двусвязные) списки;
• циклические списки;
• стек;
• дек;
• очередь;
• бинарные деревья.

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

Объект - это экземпляр  некоторого класса

Во время выполнения программная система, содержащая класс C, может в разных точках, используя процедуры создания или клонирования, создавать экземпляры C, - структуры данных, соответствующие образцу, заданному классом C. Например, экземпляр класса POINT представляет собой структуру данных, состоящую из двух полей, соответствующих атрибутам x и y класса. Экземпляры всех возможных классов составляют множество объектов системы.

Это официальное  определение в мире ОО-ПО. Но в  повседневном языке термин "объект" имеет гораздо более широкий  смысл. Любая программная система  связана с определенной внешней  системой, которая может содержать "объекты": точки, линии, поверхности  и тела в графической системе; сотрудников и их оклады в системе  расчета заработной платы и т.д. В таких ситуациях, как правило, реальным объектам соответствуют программные  объекты. Примером может служить  класс EMPLOYEE в системе расчета зарплаты, экземпляры которого являются компьютерными моделями сотрудников.

Хорошим следствием дуализма слова "объект" является естественность и мощь ОО-метода, применяемого для целей моделирования реальных систем. Это уже отмечалось при  рассмотрении принципа Прямого Отображения  ( direct mapping ), который, как отмечалось, является принципиальным требованием модульного проектирования. Неудивительно, что некоторые классы являются моделями внешних типов объектов проблемной области, а экземпляры классов - моделями реальных объектов. (См. "Прямое отображение", лекция 3)

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

• Не все классы соответствуют типам проблемной области. Многие классы, введенные в интересах проектирования и реализации, не имеют двойников в моделируемой системе. Именно эти классы на практике могут иметь наибольшее значение и именно их труднее всего спроектировать.
• Некоторые концепции проблемной области естественно приводят к классам, хотя в проблемной области не существует реальных объектов, которые можно было бы поставить в соответствие экземплярам этих классов. Примерами могут быть класс STATE, описывающий состояние системы, или классCOMMAND. Когда слово "объект" используется в этой книге, то из контекста ясно, в общем или техническом смысле используется этот термин. В тех случаях, когда эту разницу необходимо подчеркнуть, используется уточнение - программный объект или внешний объект.

Базовая форма

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

Пусть O - объект. По определению  он является экземпляром некоторого класса. Точнее, он является прямым экземпляром (direct instance) только одного класса, например C.

Класс C называется порождающим классом ( generating class ) или просто генератором ( generator ) объекта O. Заметьте, C - программный текст, а O - структура данных времени выполнения, появляющаяся в результате работы рассмотренных ниже механизмов создания объектов.

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

Рассмотрим класс POINT из предшествующей

class POINT feature

   x, y: REAL

   ... Объявления подпрограмм ...

end

Подпрограммы опущены, так как форма объектов полностью  определяется атрибутами соответствующих  классов. Данный класс имеет два  атрибута x и yтипа REAL, следовательно, его экземпляр - это объект с двумя полями, содержащими значения этого типа:

 
Рис. 8.1.  Экземпляр класса POINT

Простые поля

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

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

• BOOLEAN, может иметь только два различных экземпляра, соответствующих булевым значениям true и false ;
• CHARACTER, экземпляры которого представляют символы;
• INTEGER, экземпляры которого представляют целые числа;
• REAL и DOUBLE, экземпляры которых представляют действительные числа одинарной и двойной точности.