Реферат: Программирование, ориентированное на объекты
ема. Например, если в предыдущей программе изменить пос
ность обращений к динамической памяти на приведенную ниже, то описанного выше отказа по памяти не произойдет:
BEGIN NEW(T1);...NEW(T2);...NEW(M1);...
DISPOSE(T1);...DISPOSE(T2);... NEW(M2);...
Здесь при обработке запроса NEW(M2) в пуле динамической па
ти будет находиться один свободный фрагмент объема шесть слов, об
ный "склеиванием" элементов Т1^ и T2^, выполненным при об
роса DISPOSE(T2). В общем случае вопросы эффективной ре
ализации управления динамической памятью, обеспечивающей ми
мум отказов при ограниченном объеме, составляют отдельную проб
му. Здесь мы только заметим, что с организацией выделения "пер
вого подходящего" фрагмента памяти в программировании свя
ют такие термины как "хип" или "куча", относящиеся скорее к про
фессиональному жаргону, чем к научно-методической тер
ципы организации динамической памяти.
Организация корректной последовательности запросов связана, кро
ме того, как минимум еще с двумя проблемами. На том же жар
не их называют проблемы "висячих ссылок" и "мусора", а оп
ют они две стороны одной и той же ошибки, заключающейся в некор
ной работе с указателями. Следующий фрагмент программы ил
рует возникновение таких ошибок (тип "Треугольник" описан выше).
VAR T1, T2:Треугольник;
BEGIN NEW(T1);...T2:=T1;...
DISPOSE(T1); (* T2-"висячая ссылка" *)
............
NEW(T1);...NEW(T2);...
T1:=T2; (* Остался "мусор" *)
Из этого примера понятно, что "висячая ссылка" - это ука
кладной программы, указывающий на свободный фрагмент ди
кой памяти. Поскольку этот фрагмент может быть выделен сис
темой по какому-либо запросу другой прикладной программе, Т2 мо
тая" ссылка (имеющая значение NIL, см. pазд.III) являются со
кой памяти, к которому в прикладной программе потерян доступ. В приведенном примере мусором оказался старый треугольник Т1^, на который указывал Т1 до пе
ки (установки на Т2). Этот мусор неустраним: программист не име
ет к нему доступа, а система управления "считает" мусор занятым фраг
ментом памяти.
Объединяет эти два вида ошибок одно общее обстоятельство: они не обнаруживаются исполнительной средой. Идентифицировать по
ные ошибки можно только путем тщательной проверки и отладки прог
раммы. И, наконец, по своим возможным влияниям на работу прог
ки приводит только к увеличенному расходу памяти, в то время как висячая ссылка спо
на" висячей ссылки может оказаться очень высокой.
Использование автоматической памяти связано с соз
жением специальных элементов хранения, связанных с актив
ектами - действиями или процедурами. Любая процедура тpе
бует для выполнения собственной индивидуальной локальной сре
ду образуют локальные переменные, объявленные в про
та в процедуру, т.е. набор объектов, обеспечивающих выполнение дей
ствий, связанных с процедурой. Необходимость в локальной сре
ции объекта процедурного типа. После завершения такой интер
ветственно запрос на создание локальной среды связан с вызовом про
цедуры, а запрос на уничтожение - с окончанием фазы активности объекта (оператор RETURN или END в теле процедуры). Например:
VAR W1, W2: PROC;
PROCEDURE Работа_1;
VAR A: INTEGER;... BEGIN... W2;...
END Работа_1;
PROCEDURE Работа_2;
VAR A: INTEGER;... BEGIN... W2;...
END Работа_2;
BEGIN... W1:=Работа_1;... W2:=Работа_2;... W1;...
В этом фрагменте описаны два активных объекта процедурного типа PROC = PROCEDURE(): W1 и W2 и две процедуры без параметров: Работа_1 и Работа_2, которые могут использоваться как константы ти
па PROC. Интерпретация (активизация) W1 приведет к вызову Работы_1 и созданию локальной среды (содержащей переменную А). В процессе выполнения Работы_1 производится активизация объекта W2 и соответственно создание локальной среды для Работы_2. В любой те
кущий момент времени в системе могут быть активны несколько объ
тов. (В этом примере активизация W1 приводит к активизации W2, за
тем они оба остаются в активном состоянии и затем теряют свою активность в обратной последовательности: сначала пас
руется W2, затем W1). Последовательность активации и пассивации свя
кой памятью основывается на использовании стека - структуры, под
го в течение совместной активности объектов W1 и W2.
Активация
При активации каждого нового объекта вершина стека "опус
ся вниз" на величину, определяемую размерами локальной среды этого объ
екта,- при его пассивации вершина стека "поднимается вверх". С использованием автоматической памяти связаны две ос
лемы: рекурсии и множественности ассоциаций.
Рекурсия - механизм, позволяющий объекту совершать само
ц-ию. Например, по схеме:
W1-->W1 (прямая рекурсия)
или W1-->W2 ...-->W1 (косвенная рекурсия).
Прямая рекурсия связана с непосредственной повторной (вло
ной) активацией, а косвенная - с опосредованной (причем число пос
ников в схеме W1-->...-->W1 может быть произвольным). Ис
ние рекурсии напрямую связано с размерами рабочего прост
сивных схемах (особенно в косвенной рекурсии) возрастает ве
ятность появления трудно идентифицируемых ошибок.
Множественность ассоциаций заключается в том, что в классе ав
матической памяти могут быть одновременно размещены нес
ноименных объектов, имеющих в общем случае различные значе
ния и относящиеся к разным активностям одного и того же или опять-таки разных объектов. В приведенном примере существуют два одно
именных объекта: переменная А, связанная (ассоциированная) с активностью W1, и переменная А, ассоциированная с активностью объ
ответствии с принципом стека система упpавления автоматической па
ную ассоциацию (самую "ближнюю" к вершине стека авто
ти). Возникновение множественности ассоциаций обусловлено только использованием в прикладных программах одно
ных переменных с различной областью действия (областью ви
ит усомниться), то при их интерпретации следует помнить о мно
VI. ДИНАМИЧЕСКИЕ СТРУКТУРЫ ОБЪЕКТОВ
Связанная организация памяти. - Ассоциативные структуры. -Списки. - Очереди. - Рекурсивные структуры. - Наборы. - Деревья.
Связанная организация памяти определяет множество структур, связи между элементами которых реализуются указателями. Каждый эле
мент такой структуры (объект) обладает, таким образом, свой
вом "иметь связи" с другими элементами, на которые указывает зна
ние этого свойства. Связанная организация памяти может ис
ся и для хранения статических структур данных, но пос
лизация связей через ссылки дает возможность исполь
нием связанной организации является динамическое мо
делирование объектно-ориентированных систем.
Динамические структуры объектов, как уже отмечалось, ха
ются наличием особого свойства: "иметь переменный состав эле
тов стpуктуpы". Это свойство позволяет любую динамическую струк
ного состава. (Заметим, что термин "ассоциация" используется в программировании очень часто и смысл, вкладываемый в это поня
тие, во многом зависит от контекста).
Свойство ассоциативности относится к общим групповым свой
ектов. Простейшим примером группового свойства является "Ко
тво объектов в классе"- ни один из объектов класса в от
бует использования специальных структур, "связывающих" объекты-члены этих структур "узами" ассо
сти. В прикладных задачах это могут быть "узы" дружбы, общие ка
ства (например, свойство "Быть молодым") и т.п.. Ассоциация объ
ектов, кроме того, как правило упорядочена по определенной сис
ме правил - отношений порядка на множестве членов ассоциации. Такие правила устанавливают биективную (взаимно-однозначную) связь меж
ра, чем множество объектов.
Правила, регулирующие упорядоченность ассоциации, могут быть скон
струированы как выделяющие свойства на множестве имманентных свойств объекта (например,упорядоченность по "Возрасту" объекта, "Приоритету" объекта). Они могут быть построены на основе вре
ни модификации состава членов ассоциации (например,правило "пер
вым пришел - первым вышел" хорошо известно всем, кто бывал в очередях: каж
дый вновь пришедший в очередь становится последним членом этой ассоциации очередников). Общее свойство ассоциации зак
ся в том, что возможность биекции ее структуры (сос
ный ряд чисел фактически определяет наличие "линейного" по
ляется отношениями предшествования: "предок-потомок", "пре
щий-последующий" и т.п. Это свойство делает основной реа
онной структурой ассоциации линейный список.
С помощью списков могут моделироваться разнообразные ди
кие структуры, поддерживающие различные отношения порядка. В про
мировании широко используются такие структуры, как стек, оче
редь, дек, пул - все они могут быть реализованы на списках. В за
симости от количества связей между соседними элементами раз
ют односвязные и двусвязные списки с "встречным" нап
лок. Ниже пpиведены некотоpые пpимеpы оpганизации спис
ковых стpуктуp на связанной памяти.
Односвязный список
H1
TYPE PTR = POINTER TO Элемент;
Элемент = RECORD INFO: Инфоpмационное_Поле;
LINK: PTR (* Поле связи *)
END;
VAR H1: PTR; (* "Голова" списка *)
Двусвязный список
К2
v
H2
TYPE PTR = POINTER TO Элемент;
Элемент = RECORD INFO: Инфоpмационное_Поле;
RLINK,LLINK: PTR (* Поля связи *)
END;
VAR H2,K2: PTR; (* "Голова" и "Конец" списка *)
^
В общем случае любой элемент списка может содержать про
ное количество связей и являться членом многих списков. Это по
ет большое многообразие списковых структур - фактически любая ди
намическая структура на связанной памяти конструируется из спис
родные, в однородных используются объекты только одного класса, в разнородных - разных классов. Например, членами ассоциации "Эле
мент фигуры" могут быть объекты классов "Точка" и "Окружность":
TYPE Точка = RECORD
X,Y: INTEGER (* Координаты точки *);
LINK : ADDRESS
END;
Окружность = RECORD
Центр: Точка; R: CARDINAL (* Радиус *)
LINK : ADDRESS
END; .
Как члены ассоциации, реализуемой односвязным списком, они ха
теризуются свойством "Иметь одну связь" (LINK) с "соседом" по ас
социации, в информационной же части эти объекты отличаются друг от друга как по представлению так и по интерпретации. Спи
зующий ассоциацию "Элемент фигуры", будет относиться к ка
v
Окружность
Доступ к элементам списка реализуется через указатели. Ука
тель на первый элемент односвязного линейного списка (голову) от
вает доступ ко всем его элементам: стрелки на рисунке ука
правление последовательного доступа. Для реализации та
па необходимо последовательно (в направлении, указы
чивает возможности быстрого доступа к элементам списка. Нап
мер, любой элемент двусвязного списка открывает дос
туп к "левому" и "правому" соседу, а односвязного - только к "правому". Голова яв
бым элементом является последний элемент - на него часто ста
ные внутренние "особенности" (как, напpимеp, К2^.LINK=NIL - условие "конца" в схеме линейного дву
ставлены.
Интерпретация элементов разноpодных списков связана с до
ными трудностями- нужно не только получить доступ к соот
вующему элементу структуры, но и определить, к какому клас
ность"). Для унификации процессов интерпретации таких структур мо
но помочь методы определения наложением (см. pазд.IV). При этом сов
местимость представлений различных классов по полю связи ста
мость в определениях "Точки" и "Окружности" ?.
В задачах динамического моделирования сложных систем особый класс составляют системы с очередями. Очередь - ассоциация объ
тов, ожидающих доступа к системе обслуживания. Такая ди
кая ассоциация характеризуется дисциплиной обслуживания (ожи
ше уже упоминалась дисциплина "первым пришел - первым вы
шел" (First In - First Out), обычно она обозначается аб
рой FIFO. Как разновидность очереди нередко рассматривают ассо
шел - первым вышел" ) - LIFO. С точки зрения реализации на спи
на с двух концов - с "головы" (для выбоpа элемента из оче
ди) и с "хвоста" (для постановки в очеpедь), а стек - только с "го
ловы" (и для включения в стек, и для вывода из стека). (В прог
му возможен с любого из двух концов как для включения элемента в спи
сок, так и для удаления из списка).
Динамическое изменение состава объектов, находящихся в оче
ди, делает размер очереди (длину) величиной переменной. При этом моде
рование очереди в статической структуре массива связано с ре
рованием избыточного объема памяти, достаточного для хра
реди максимально возможного размера. На связанной ди
мяти возможно более эффективное pешение, базиpующееся на ис
зовании стpуктуpы "кольца", в которое включаются и из ко
ся два указателя: на начало (голову) очереди - Н, и на ее конец - К. Такие указатели "передвигаются" по структуре коль
реди. В динамике К как бы "пытается догнать" Н, а Н - пы
ное обращение к динамической памяти для выделения элемента хранения под новый объект, включаемый в оче
на иллюстрация структуры кольца-очереди.
v Н
v K ^ v
^
INFO - информационная часть объекта, LINK - связь с "со
ца (использование его для хранения объекта). В клас
кой связанной памяти возможны и другие решения организации оче
дей.
Основными операциями над списками являются операции вставки-удаления элементов. Такие операции всегда (независимо от техники ре
ализации) должны выполняться корректно:
- сохранять общую структуру связанной организации списка;
- не приводить к образованию "мусора" и "висячих ссылок";
- сохранять отношение порядка элементов в списке.
Выполнение этих требований связано с корректным определением пос
ледовательности операций по модификации списков.
Например, ниже приведена иллюстрация к операции удаления эле
та В из списка Н.
v P v B
Н
| 2 ^ v
+-----------------+
Предполагается, что указатель В предварительно установлен на удаляемый элемент. Для удаления В необходимо:
1) Начав с головы списка Н, "передвинуть" вспомогательный ука
тель Р на элемент, предшествующий В в списке. (Как правило, это де
лается в циклах WHILE или REPEAT).
2) "Перебросить" связь Р^.LINK (пунктир на рисунке). Это делается оператором: Р^.LINK := В^.LINK (или оператором: Р^.LINK := Р^.LINK^.LINK).
При этом связь 1 на рисунке оказывается разорванной, а связь 2 установленной. Список Н сохранил свою структуру, а элемент В не ока
зался "мусором".
При использовании сложных многосвязных списковых структур обе
чение корректности модификаций списков требует от прог
бого внимания - любой "случайный" разрыв связи в спис
щает в "мусор" всю его часть, оставшуюся за этой свя
зью.
Одной из самых распространенных ошибок при модификации спис
ков является также ошибка, связанная с попыткой получить доступ к элементу через указатель Н = NIL. Чтобы пpедотвpатить такие ошиб
ки, пpи констpуиpовании булевских выpажений, опpеделяющих условия завеpшения (пpодолжения) циклов, связанных с поиском элемента и т.п., необходимо следовать пpостому пpавилу: вычис
