Реферат: Программирование, ориентированное на объекты
Доступ к элементам списка реализуется через указатели. Ука
тель на первый элемент односвязного линейного списка (голову) от
вает доступ ко всем его элементам: стрелки на рисунке ука
правление последовательного доступа. Для реализации та
па необходимо последовательно (в направлении, указы
чивает возможности быстрого доступа к элементам списка. Нап
мер, любой элемент двусвязного списка открывает дос
туп к "левому" и "правому" соседу, а односвязного - только к "правому". Голова яв
бым элементом является последний элемент - на него часто ста
ные внутренние "особенности" (как, нап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авилу: вычис
ние условия (H#NIL), опpеделяющего возможность доступа к эле
ту списка "под H", всегда должно пpедшествовать вычислению ус
вия, содеpжащего квалидент с пpефиксом H^. В этом плане могут оказаться очень полезными пpавила последовательного вы
ческих условий:
A AND B = IF A THEN B ELSE FALSE;
A OR B = IF A THEN TRUE ELSE B.
Здесь A и B - логические условия.
Напpимеp, для вычисления (A AND B ) вычисление B пpоводится толь
ко после пpовеpки A с pезультатом TRUE, пpи A=FALSE опеpанд B вообще не вычисляется.
Список относится к особой группе структур - это так на
курсивные структуры.
Приведем рекурсивное определение списка: Списком называется со
купность связанных элементов, из которых один является осо
бым элементом (первым, "головой"), а все остальные образуют спи
сок. Рекурсивные структуры в программировании замечательны тем, что мно
гие операции по их обработке можно эффективно реализовать с использованием рекурсивных процедур, которые отличаются боль
коничностью и наглядностью. В качестве примера приведем про
ру проверки, является ли Н1 подсписком списка Н:
TYPE Указатель = POINTER TO Элемент;
Элемент = RECORD
INFO : Инфоpмация;
LINK : Указатель;
END
PROCEDURE Проверка (Н,Н1 : Указатель) : BOOLEAN;
BEGIN
IF H # NIL THEN
RETURN (Н = Н1) OR Проверка (Н^.LINK, Н1)
ELSE RETURN (Н = Н1)
END
END Проверка.
Проверка (H # NIL) в этом примере нужна только для того, что
бы предотвратить попытку интерпретировать пустую ссылку как эле
мент списка при вызове Проверка (H^.LINK, H1). Ситуация (H=H1=NIL) рассматривается как положительный результат проверки.
Другим примером рекурсивной структуры является структура на
бора, которая определяется следующим образом: Набором называется совокупность связанных элементов, каждый из которых может быть ли
бо атомом, либо набором. Атом определяет "неделимый" элемент на
бора, предназначенный для хранения элементарной порции ин
ции. Реализация наборов основана на использовании разнородных списков. Например, ниже приведена одна из возможных структур на
ров. В этой структуре H1 - набор из четырех элементов (a,b,H2,c), из них H2 - набор, остальные - атомы. H2 состоит в свою очередь из тpех элементов - атома c и двух наборов H3 и H4, причем набор H3 - пуст (не содержит элементов), а H4 содержит два атома (d и f).
v H2
H3 H4
v v v
v v
v
Элементы H2, H3, H4 определяют "головы" новых наборов и од
временно являются членами наборов "верхнего уровня" - при этом структура набора оказывается адекватной для реализации дина
ких "вложенных" понятий предметной области. Например, в ассо
ацию H1-"Акционеры" могут входить как отдельные частные ли
ца, так и коллективы - организации, которые являются ассо
ми собственных акционеров.
Элементы H2, H3, H4 на приведенной иллюстрации участвуют в двух связях - горизонтальной (связь между членами одного набора) и вертикальной (связь с членами "своего собственного" набора). Эта терминология часто используется для организации так назы
мых ортогональных списков, моделирующих структуры динамически изме
няющегося плоского "игрового поля": "разреженных" матриц, "кроссвордов", цепей "домино" и т.д. Понятие "игрового поля", ра
меется, не означает, что ортогональные списки используются лишь в игровых задачах.
Еще один пример рекурсивной структуры, широко использующейся в программировании - структура дерева. Деревом называется сово
купность связанных элементов - вершин дерева, включающая в себя один особый элемент - корень, при этом все остальные эле
ты образуют поддеревья. Наиболее широко используется струк
ра бинарного дерева, все множество вершин которого делится (по отношению к корню) на два подмножества - два поддерева (левое и правое). Любая вершина бинарного дерева реализуется на связанной памяти элементом с двумя связями: с левым поддеревом и с правым.
v К
Информационное поле
Связь с левым потомком
Связь с правым потомком
v
На этой иллюстрации изображена структура бинарного дерева на связанной памяти, здесь К - корень; Л1,Л2,Л3 - "листья" - вер
ны с "пустыми" связями ("не выросшими" поддеревьями).
Страницы: 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12
