Непейвода Н.Н., Скопин И.Н. Основания программирования

Подождите немного. Документ загружается.

9.4. РЕКУРСИВНЫЕ СТРУКТУРЫ ДАННЫХ

545

В исходном языке

LISP

были приняты два предположения (часто автоматиче-

ски, без критического анализа наследуемые современными системами), одно

из которых было связано с боязнью ввести явный элемент, трактуемый как

ошибка (подобно тому, как обычно трактуется указатель

nil

в современных

языках), а второе является непосредственным следствием данной формы ре-

ализации списков.

NIL

по умолчанию является последним элементом списка и не может

быть никаким другим его элементом, таким образом,

(

NIL

) = (

(A1,A2,A3,...,An)=(A1,(A2,(A3,(...,An)...))).

Таким образом, список с произвольным числом элементов вводился как со-

кращение для частной формы списка бинарных списков. Перечисленные со-

глашения составляют основу скобочной нотации языка

LISP

, которой соот-

ветствует структура связанных указателями записей. Примеры такой струк-

туры даны на рис. 9.12.

(x (y z))

((x) (y z))

Рис. 9.12. Структура списка в языке

LISP

С современных позиций оба приведенных выше соглашения выглядят до

крайности морально устарелыми.

В нынешнем стандартном диалекте язы-

ка

Common Lisp

они сохранены для совместимости со старыми программа-

ми, но основной определяющей функцией для списков стала функция

(list

Во избежание недоразумений!!!

Критика некоторых решений

LISP

в данной книге не является стремлением сделать ‘над-

стройку сверху’. Еще раз повторим, что любое решение, принятое человеком, содержит в

себе в качестве атрибута человека ошибку. Гениальные решения, типа

LISP

, не являются

546

ГЛАВА 9. СТРУКТУРЫ ДАННЫХ

...)

. Теперь можно записать, например,

(list ’a ’b ’c nil)

и получить результат

(A B C NIL)

, не равный ни

(A B C)

, ни

(A (B (C NIL)))

Основная операция над списками, не выводимая из описания структуры

данных — добавление нового элемента:

Add (S,x)











(

), если

= ();

(

S.Head x

), если

= (

S.Head

);

(

S.Head Add

(

S.Tail

) в остальных случаях.

Заметим, что определенный нами тип данных

List(T)

не совпадает со спис-

ками, индуктивно определенными в A.6.1. В частности, ему удовлетворяют

кольцевые списки, пример которых приведен на рис. 9.13.

S = (x y S)

...

Рис. 9.13. Кольцевой список в языке

LISP

Замечание. В языке

LISP

кольцевой список может получиться только как

результат вычислений и, вообще говоря, кольцо невозможно изобразить, по-

этому “

” и “

” на рис. 9.13 не следует рассматривать в качестве символов

языка.

Рекурсивный тип, описывающий произвольные списки, можно опреде-

лить следующим образом:

List1

(

) =

Safearray

(union(

Arc

*List1

(

Atom

));

Здесь

Safearray

—гибкий одномерный массив.Обозначение взято со стр.309,

где описана реализация таких массивов в современных системах распреде-

ленного программирования.

исключением. Нельзя молиться на то, что сотворено человеком, как на Священное Писа-

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

решений. Точно так же, увидев недостаток или даже прямую ошибку, нельзя сразу же стано-

виться в позу высокомерного пренебрежения и игнорировать имеющиеся в данном решении

находки. Тем более это верно потому, что перечисленные недостатки

LISP

являются скорее

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

здавался язык.

9.4. РЕКУРСИВНЫЕ СТРУКТУРЫ ДАННЫХ

547

Для списков необходимо определить операцию конкатенации (ограни-

читься присоединением одного элемента в данном случае уже нецелесообраз-

но):

Conc



) = (K

, . . . , K

nS1

, K

, . . . , K

nS2



;

В разных языках принята разная нотация для изображения списков. Ча-

ще всего специальным образом помечают рекурсивность и закольцованность

списков (по-видимому,метод неподвижной точки рассматривается как слиш-

ком абстрактный и далекий от реализации, базирующейся на понятии адре-

сации памяти).

И, наконец, опишем оснащенный ориентированный мультиграф общего

вида в качестве рекурсивной структуры данных. Пусть оснащениями вершин

служат элементы типа

Т1

, а оснащениями дуг — элементы типа

. Тогда

можно задать следующий шаблон рекурсивных определений типа:

Graph

(

) = (

*Safearray

((

*Graph

(

)).

9.4.2. Указательные типы

В современном практическом ООП сложные системы объектов появля-

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

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

рассмотрим организацию систем объектов в более явной взаимосвязи с ны-

нешней их реализацией и с понятием адреса.

Вначале детализируем вопрос об определении обычного списка (тем бо-

лее, что взаимосвязи объектов часто идут именно через списки объектов).

Пусть имеется специальный примитивный тип pointer, значения которого

есть произвольные адреса. Нетипизированный указатель можно рассматри-

вать как типизированный, но с базовым типом, совпадающим с объединени-

ем всех возможных типов (последнее не является конструкцией языка, по-

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

дусмотрены, в частности, в

C++/C#

Java

Object Pascal

Имеются некоторые тонкости, ткотрые не очень важны для дальнейшего,

но заслуживают упоминания. В

С/С++/C#

Java

специальной нотации для

указателей не требуется, т. к. одновременно с определением типа определя-

ется и указатель для него (спецификатор ‘*’), а следовательно, в определе-

нии структуры, содержащей указатель на нее саму, нет ничего нового: эта

конструкция попадает под формальное определение рекурсивной структуры

548

ГЛАВА 9. СТРУКТУРЫ ДАННЫХ

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

Pascal

и в большинстве других языков (во всех языках со строгой статиче-

ской типизацией) указатель —это конструктор структуры данных (подобный

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

имя своего базового типа.

Теперь

record Inf : T, Next : pointer; end

описывает структуру, которая может представлять список, т. к.

pointer

, ука-

зывая куда угодно, способен на то, чтобы указывать на точно такую же за-

пись, как та, что описывается. Однако фактически он может указывать не

только на такую запись, поэтому нельзя утверждать соответствующая память

будет иметь описываемую структуру. По существу, приведенная запись не

должна рассматриваться в качестве рекурсивной структуры данных, хо-

тя она и может применяться, и применяется для реализации рекурсивных

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

реализует в

C++/C#

Object Pascal

Java

список объектов различных типов,

правда, здесь есть одна тонкость: на первом месте стоит также указатель.

type ListofObjects=record Inf , Next, Prev: pointer; end

Конечно же, здесь нет никаких признаков (за исключением имен) того, что

указывают на такие же структуры. Ничем не помогает здесь огра-

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

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

описание

type R = record Inf: pointer, Next, Prev : ^R; end

можно считать простым сужением предыдущего описания записи с указате-

лем. Однако при описании

фактически используется

, а значит, оно по-

падает под формальное определение рекурсивной структуры данных. Тем не

менее самая прагматически важная характеристика структуры данных — то,

что для каждого ее конкретного экземпляра должно быть выполнено

(

;

(9.8)

никак не отражено в определении типа.

Чисто прагматически этот недоста-

ток обходится тем, что определяются три различных конструктора такого ти-

Смотрите упражнение 5 в качестве комментария к только что приведенным соотношени-

ям.

9.4. РЕКУРСИВНЫЕ СТРУКТУРЫ ДАННЫХ

549

па, соответствующие вставке нового элемента в начало, в конец и в середину

списка, и деструктор, который, удаляя объект, одновременно перекоммути-

рует ссылки.

Рассмотренный пример показывает, почему от тематики АТД никуда не

деться, поскольку любые чисто технологические ограничения остаются на

практике благими пожеланиями, пока они как следует не поддержаны.

Можно считать, что при помощи конструктора указателя создаются про-

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

ские функции указателей в точности те же, что и переменных. Имя перемен-

ной либо указатель на значение используется

(a) как аргумент при извлечении значения;

(b) как аргумент при обновлении значения.

Лишь в языке

Алгол 68

этот семантический и прагматический изоморфизм

был отражен и сущнсти ‘переменная’ и ‘указатель на значение’ были отожде-

ствлены. Это позволило определить общую (семантически естественную и

полезную) операцию приведения значений: разыменование. Разыменование

активизируется, как и любое приведение типов, в зависимости от синтак-

сической позиции; в частности, в левой части присваивания разыменование

происходит лишь для снятия лишних косвенных ссылок, в правой части, вну-

три выражения, оно, как правило, продолжается до получения аргумента ба-

зового типа.

В нынешних языках разыменование всегда указывается явно (какая тро-

гательная аккуратность, особенно в сопоставлении с тем, какие грубые при-

ведения производятся неявно!). Например, в языке

Pascal

для получения зна-

чения из указателя нужно написать

<имя>^

, в

C/C++/C#

—

*<имя>

В языках

Pascal

С++/C#

Java

для создания новых указателей с одновре-

менным отведением памяти для значения базового типа имеется оператор

new

. Практически это — инициализация переменной именно как перемен-

ной, а не значения, которое содержит соответствующая локация. Соответ-

ственно, удаление указателя вместе с именуемым значением производится

при помощи оператора

dispose

(или

delete

, в зависимости от языка). В язы-

ке

Java

) пытаются по мере возможности обойтись без явного уничтожения

указателей, заменяя это неявной сборкой мусора.

Конечно же, явное оперирование с указателями влечет (и практически

всегда на практике приводит к) нерегулярностям в структуре памяти, в част-

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

550

ГЛАВА 9. СТРУКТУРЫ ДАННЫХ

неприятностям (см. рис. 7.6, на котором была показана получающаяся ситу-

ация).

В качестве необходимого элемента, сопуствующего указателям как типам

данных, укажем специальное указательное значение

nil

, свидетельствующее

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

Это не неопределенное значение, оно может анализироваться в программе и

при корректном обращении с ним не приводит к выдаче ошибки, но обраще-

ние к адресу по такому значению обязано в любой корректной реализации

любого языка выдавать ошибку.

Графическое изображение лисповских списков обретает реализационное

содержание.

9.4.3. Специальные рекурсивные структуры

Пусть

В = ( K

, ..., K

: (В,T) ); n > 0

И пусть на операции формирования структуры и селекции компонентов на-

кладываются различные ограничения. Тогда получаются разные специаль-

ные варианты рекурсивных структур данных. Не все они общеупотребитель-

ны, но на некоторых стоит остановиться.

Стек и очередь

Стек

Push (S : В, E : T) = Push ((

, ...,

),E)

⇒

S = S + E = (

, ...,

, E );

Pop (S : В) : E

⇒

if S = (

, ...,

, E ) // или S.n > 0, что то же

then { S = (

, ...,

), result = E }

else result = Error;

Empty (S : В) : Boolean

⇒

result ( S = ());

Это неограниченный стек,который строится как линейный список со спе-

циальными операциями.Графически его можно представить следующим обра-

зом (см. рис. 9.14).

Очередь

Все почти также.

Insert (S : В, E : T) = Insert (( KS1, ..., KSn, ),E)

⇒

9.4. РЕКУРСИВНЫЕ СТРУКТУРЫ ДАННЫХ

551

Начало, Конец

...

Рис. 9.14. Стек

S = S + E = (

, ...,

, E );

Delete (S : В) : E

⇒

if S = ( E,

, ...,

) // или S.n > 0, что то же

then { S = (

, ...,

), result = E }

else result = Error;

Empty (S : В) : Boolean

⇒

result ( S = ());

Это неограниченная очередь. Графически ее можно представить следу-

ющим образом (см. рис. 9.15). Это еще не все, т. к. не определена операция

Начало

Конец

...

Рис. 9.15. Очередь

генерация стека или очереди в их начальном состоянии:

Init (S : В) : В

⇒

s = ();

Абстрактные последовательности и файлы

Линейный список можно рассматривать как основу для построения аб-

страктной последовательности, если определить (наряду с операцией

Add

)

регламент создания и доступа к компонентам (проделать самостоятельно!).

Т. е. все, как для стека и очереди. Но все эти структуры являются абстракт-

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

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

Есть два частных случая такой конкретизации для последовательностей,

которые обычно имеют в виду, когда говорят о языках и системах програм-

мирования:

• последовательности (иногда описываются как специальный конструк-

тор с соответствующими операциями) — употребляются редко, чаще

всего эта структура отождествляется со следующей;

552

ГЛАВА 9. СТРУКТУРЫ ДАННЫХ

• файлы — последовательности, сохраняемые на внешней памяти (часто

по способу доступа к файлам причисляют различные внешние устрой-

ства, по которым программа получает данные и которым она их пере-

дает — связь с потоками).

Главное свойство — чтение и запись подряд (значит, есть операции дать сле-

дующий, записать очередной, установить в начало и др.).

Файлы Паскаля — самый необходимый минимум. Но еще есть понятие

буфера, через который осуществляется перекачка данных. В пределах буфе-

ра — произвольный доступ.

Файлы

С/С++/C#

те же возможности, что дает обычная система програм-

мирования (рассказать).

Ограничения доступа:

• только по чтению;

• только для записи;

• по чтению с возможностью дозаписи в конец (два указателя точек до-

ступа).

К примеру, обратное чтение было бы странным.

Цикл вида

for x from S do

, где

— последовательность или файл.

9.4.4. Деревья

Tree (T)

, где

— базовый тип:

L : T

— Tree (T) — лист;

B1, ..., Bm : Tree (T)

⇒

(B1, ..., Bm)

—

Tree (T)

Если

tr:Tree(T)

,то

R(tr)

—корень и все дерево (причем за счет рекурсивности

это верно и для всех ветвей).

B(tr, i : integer)

объект типа

Tree(T)

, такой что

tr = (..., B(tr, i),...)

Опять можно не говорить про указатели, но пока это только для дере-

вьев, подобным изображенным на рис. 9.16. А как задать стрелки в обратном

направлении? Нужно определить операцию родитель

P(x)

, т. е. рекурсивно

найти ιr ∃i B(r, i) = x.

Разумеется, представление приведет к указательным структурам, напри-

мер, вида, изображенного на рис. 9.17. Для доступа к родителям от детей

нужны дополнительные ссылки, как на рис. 9.18.

9.4. РЕКУРСИВНЫЕ СТРУКТУРЫ ДАННЫХ

553

Рис. 9.16. Дерево

Ветви одного уровня:

Inf

...

Inf Inf

Ссылки на братьев:Ссылки на братьев:

Корень:

(Inf — информационное поле)

Рис. 9.17. Списочное представление дерева

Задания для самопроверки

1. Приведенное нами формальное определение корректности рекурсив-

ного задания структуры не исключает некоторых содержательно бес-

смысленных случаев. Приведите примеры абсурдных, но формально

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

ний типов.

2. Какие еще необычные списки удовлетворяют определнию

List(T)

3. Определите в качестве рекурсивной структуры данных оснащенные муль-

тиграф (неориентированный), орграф и граф. Что мешает представле-

нию орграфа и графа?

4. Запишите построенные определения типов на Вашем языке програм-

мирования (

C++/C#

Object Pascal

Ada

Java

554

ГЛАВА 9. СТРУКТУРЫ ДАННЫХ

...

Ссылки на

родителей

Inf

Inf Inf

Рис. 9.18. Двунаправленное дерево

5. В соотношениях (9.8) есть ошибка. Найдите и исправьте ее.

6. Постройте что определяются три различных конструктора типа линей-

ный список, соответствующие вставке нового элемента в начало, в ко-

нец и в середину списка, и деструктор, который, удаляя объект, одно-

временно перекоммутирует ссылки.