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

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

9.3. СТРУКТУРНЫЕ ТИПЫ

515

…

Компонент

Статический

набор

Конструктор

Компонент 1

Динамический

упорядоченный

Компонент

Компонент N

Конструктор

набор

Компонент

Динамический

неупорядоченный

Конструктор

набор

Схемы для каждого N

Компонент

Динамический

упорядоченный

Конструктор

набор

(d)

Динамический

неупорядоченный

Конструктор

набор

(e)

(C)

* *

(b)(a)

Рис. 9.3. Структура набора

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

цами программ. Используемые на практике варианты — это то, что действи-

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

турного програмирования и ООП.

9.3.2. Записи

Этот конструктор представляет в программах структуру, в которой реа-

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

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

писей (

Pascal

) или конструктором структур (

С/С++, Алгол-68

). Компонен-

ты записи называются полями. Каждое поле имеет собственное имя и явно

516

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

Неструктурный

компонент

Компонент набора

Имя

комп

онента

Тип

компонента

? ?

Структурный

компонент

Компонент набора

Имя

компонента

Статический набор

Динамический набор

Гибкий набор

Конструктор

Рис. 9.4. Схемы для компонент набора

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

число компонентов-полей всегда статически определено.

Существуют две точки зрения на понятие записи, касающиеся упорядо-

ченности ее полей. Первая отражает абстрактный подход, согласно которо-

му совокупность полей для их использования не требует знания порядка их

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

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

представлению. В

С/С++

структуры — это упорядоченный набор, а стандарт

языка

Pascal

разрешает при реализации размещать поля записи в любом по-

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

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

предлагаются средства организации цикла по полям: запись объединяет, как

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

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

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

страктных селекторов: единственный их идентификационный аргумент —

это имя поля. Традиционное обозначение для такого селектора

<имя записи> “.” <имя поля>.

С/С++

есть возможность наложения записи (структуры) на произвольную

область памяти. Она предоставляется как результат вычисления указателей.

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

него и последующей точки писать “

”. Такой способ может приводить к дву-

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

9.3. СТРУКТУРНЫЕ ТИПЫ

517

ных записей.

Средства оперирования для записей расширяются за счет оператора при-

соединения

with

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

применяются селекторы для извлечения полей:

with <имя записи> do <оператор /* фрагмент */>

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

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

при поиске определяющих вхождений идентификаторов в программе.

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

очень часто он помогает повысить выразительность программ. Для фрагмен-

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

нованный (именем записи). Т. е. фрагмент может использовать поля в каче-

стве добавочной системы понятий. Полезность этого качества хорошо по-

нимали разработчики языка

Симула-67

, появившегося, когда записей еще не

придумали.Они отразили его в конструкции префикс-класса для (операцион-

ного) блока, тем самым дали возможность наиболее выразительно предста-

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

С++

как и в других языках того же рода, объектная ориентированность строит-

ся на базе понятия записи (структуры), но нет присоединений, которые мог-

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

(в

Object Pascal

такая возможность есть). Мотивируется это тем, что из-за

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

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

чения, какие имена к чему относятся.

Представление записей в программе допускает следующие варианты:

• стандартное, когда каждое поле получает собственный адрес. В этом

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

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

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

ступ по сравнению со стандартным случаем, если вычислитель не до-

пускает байтовой адресации;

• с жесткой упаковкой,когда размер памяти, выделяемой под поле, стро-

го соответствует необходимому для размещения самого большого зна-

чения числу разрядов;

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

записи уровня представления, состоящие из двух полей:

518

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

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

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

сти памяти, доступной через указатель.

В ссылочном представлении поле исходной записи заменено указателем на

то место, где хранятся его значения. Это удобно в двух случаях:

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

го памяти, могут повторяться,

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

мера.

В качестве примера первого рода можно рассмотреть записи в базе дан-

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

variant

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

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

ле является невидимым и не участвует в оперировании. Задача реализации

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

ном уровне.

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

концепции абстрактных типов данных с объектно-ориентированным програм-

мированием. Корректно решить в языке указанную задачу, игнорируя требо-

вание существования функции абстракции (см. п. 9.1.5), не представляется

возможным.

В связи с типом записей полезно проследить аналогию между двумя ви-

дами структур программы: операционной и данных, т. е. указать параллели

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

выполнением операторов.

(1). Оператор как элемент операционной абстракции играет ту же роль, что

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

(2). Последовательность операторов как синтаксическая единица аналогич-

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

версального набора.

(3). Исполнение последовательности операторов может быть последователь-

ным, параллельным, а также параллельно-совместным и последователь-

но-совместным.Именно последний вариант соответствует понятию про-

извольного доступа к полям записи.

9.3. СТРУКТУРНЫЕ ТИПЫ

519

(4). Именование.Для операторов —это метки,к которым можно переходить.

Оно не является обязательным (операторы чаще всего остаются неиме-

нованными). Для процедур это имена (вместе с сигнатурами, если воз-

можен их полиморфизм). Для записей обязательно употребление имен

полей, т. к. лишь они дают идентифицирующую их информацию.

(5). Любой переход к оператору для его выполнения аналогичен вычисле-

нию селектора записи.

(6). Время жизни оператора есть его выполнение после перехода к нему. Вре-

мя жизни записи шире, оно включает выполнение всего контекста, в ко-

тором запись описана. Здесь расхождение полное.

(7). Активность оператора во время его жизни (при исполнении) противопо-

ложна пассивности полей записи.

(8). Операторы используют данные,тогда как записи не используют операто-

ры. Однако при объектно-ориентированном подходе или при функцио-

нальном программировании операторы в некоторой степени становятся

данными.

9.3.3. Объединения

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

ного синтаксиса, к примеру, в

С/С++

оно задается служебным словом

union

вместо

struct

. Однако семантика этих двух конструкторов принципиально

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

ционном представлении объединения сливаются, налагаются друг на друга.

Соответственно, здесь речи нет о селектировании всех объединенных ком-

понент как отдельных объектов, можно выделить лишь один из вариантов

налагаемых компонент.

Каким способом можно обеспечить эту установку, используя возможно-

сти универсального конструктора набора компонент? Объединение строится

как статический неупорядоченный набор. Из этого следует, что для опреде-

ления селекторов можно воспользоваться именами компонент, типами ком-

понент или значениями теговых компонент. Соответственно есть три вида

объединений.

• Размеченное — вводятся разные наименования полей, употребление

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

520

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

та (

case

<тип> языка

Pascal

; считается, что множество значений этого

типа достаточно для отображения в него объединяемых полей). При-

мер:

union ( A : T1, B : T2 );

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

зависимости от контекста. Имя поля (совпадающее для всех вариантов,

иначе объединение превращается в размеченное) может употреблять-

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

или селектируются все объединяемые варианты. Это наиболее нена-

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

стом. Пример:

union ( T1, T2 );

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

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

case

<описатель поля> языка

Pascal

case tag : Tp of

зн1 : A : T1,

зн2 : B : T2);

end;

Легко видеть, что тегированное объединение — это запись, состоящая из

двух полей:

(<тег>, <размеченное или неразмеченное объединение>).

Этот вид объединений выделяется явно по той причине, что он наиболее на-

дежен и удобен в работе

Есть еще один вид объединений, часто предлагаемый в языках програм-

мирования.Это так называемые вариантные записи —комбинация двух кон-

структоров: записей и объединения. Тег, если он есть, последнее поле перед

объединением, которое размещается после постоянной (безвариантной) ча-

сти записи (причины такого ограничения — чисто реализационные).

Таким образом, функции S

и S

дают возможность по-разному тракто-

вать одну и ту же память в зависимости от того, как идентифицируется ком-

понента.

По причине изоморфности логической дизъюнкции в конструктивной логике.

9.3. СТРУКТУРНЫЕ ТИПЫ

521

С прагматической точки зрения здесь речь идет о том, что программист

принимает обязательство никогда не обращаться к объединяемым компонен-

там одновременно в нескольких смыслах (т. е. с разными типами). Языки

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

ше виды объединений. В этом суть обсуждаемой структуры данных.

Ничто не запрещает (хотя и не поощряет!) реализацию, когда в памяти

действительно представлены все компоненты объединения. Но в этой реали-

зации придется каждое присваивание значения одной компоненте сопрово-

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

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

В соответствии со смыслом объединения, правильно располагать объеди-

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

требует ситуация. Однако это решение не со всем сочетается. Так, обычное

для него автоматическое приведение значений совсем не то, что чаще всего

нужно. Наглядный пример: перевод декартовых координат в полярные, когда

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

приведение тривиально, но лишено всякого смысла.

При объединении неприводимых значений обычно память выделяется по

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

variant

Как оформляются селекторы компонент в языках программирования? В

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

ны следующие решения:

• имя поля — применяется для размеченного объединения;

• тип поля — неразмеченное объединение (обычно выглядит как явное

приведение);

• тег —обычно сопровождается оператором выбора вариантов действий.

В контексте обсуждения объединений уместно рассмотреть некоторые сред-

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

см. определение 8.3.1. Например, на языке

FORTRAN

при описании процеду-

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

лежащими к определенному

COMMON

-блоку (см. пример 8.3.2). При этом

структура общих данных может быть различна. Язык согласует структуры

на уровне размещения данных в

COMMON

-блоке так, что при использовании

их разными процедурами происходит обращение к одним и тем же (“общим”)

адресам. Отметим,что дисциплинированное использование

COMMON

-блоков,

522

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

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

ние.

В этом случае имя

COMMON

-блока — это имя конструируемой струк-

туры данных, имена общих данных в различных процедурах — поля-вариан-

ты объединения. Вопрос о выборе нужного варианта даже не стоит, посколь-

ку в каждой процедуре виден лишь один вариант

COMMON

-блока. Хотя син-

таксически (и даже семантически, если иметь ввиду недисциплинированное

использование

COMMON

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

версального конструктора, суть от этого не меняется.

Рассмотрим вариантные записи в сопоставлении с оператором выбора.

Здесь, как и для ранее приведенной аналогии между записями и последова-

тельным совместным выполнением операторов можно найти много общего

и отметить расхождения.

(1). Основа определения аналогии та же, что в предыдущем случае. В обоих

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

сутствовать, но это непринципиально, так как в таком случае считается,

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

тег ликвидирован).

(2). Последовательность операторов как синтаксическая единица аналогич-

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

сального набора.

(3). Исполнение последовательности операторов, входящих в состав одно-

го из вариантов оператора выбора, исключает выполнение остальных (в

С/С++

приходится это моделировать). Именно так осуществляется вы-

бор поля объединения, т. е. с гарантиями единственности варианта до-

ступа к совмещенным полям записи.

(4). Именование в обоих случаях возможно через метку варианта, но для за-

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

цедур (вместе с сигнатурами, если возможен их полиморфизм).

(5). Любой переход к оператору для его выполнения аналогичен вычисле-

нию селектора.

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

трицы можно добиться повышения эффективности работы с разреженными массивами.

9.3. СТРУКТУРНЫЕ ТИПЫ

523

(6). Соответствие между временем жизни оператора и временем жизни ва-

риантной записи то же, что и в предыдущем случае (простых записей):

расхождение полное.

(7). То же про активность оператора во время его жизни (при исполнении) и

ее противоположность пассивности полей записи.

(8). Как и в предыдущем случае, имеется асимметрия: данные используются

оператором, а оператор невозможно использовать в вариантной записи.

Однако расхождение здесь сильнее, т. к. нет аналога объектно-ориенти-

рованному расширению понятия вариантной записи.

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

наряду с перечислениями, записи и объединения — это самые простые кон-

структоры структур данных. На это указывал еще Хоор в статье «Структур-

ная организация данных» [29]. При условии, что компоненты записей и объ-

единений элементарны, справедливо следующее:

a) каждый элемент данных занимает фиксированный и, как правило, очень

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

ния;

b) необходимая память может быть выделена экономно, без использования

сложных механизмов распределения памяти;

c) наиболее частые операции достаточно просто и естественно реализуются

с помощью команд вычислительных машин или их последовательностей;

d) для представления этих структур не требуются указатели (ссылки, адре-

са), а потому облегчается решение задач обмена между внешней и опера-

тивной памятью;

e) выбор естественного представления прост.

Но большинство из указанных преимуществ рассыпается, когда базой для

этих конструкторов являются другие, возможно, более сложные типы.

524

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

9.3.4. Массивы

Упорядоченный набор компонент одного и того же типа, для которых не

определяются имена, называется массивом (одномерным). Сейчас стало пра-

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

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

сивы (рекурсивное определение). Для массива как конструктора структуры

определяющими являются:

• однородность (однотипность) компонент,

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

• селектирование с помощью порядкового номера компонента — индек-

сирование.

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

(атрибут) компоненты,который вычисляется при селектировании.Он несколь-

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

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

пример:

• Перечисление, в частности, их отрезки (

Pascal

• Отрезок любого линейно упорядоченного типа, причем не обязательно

перечисления (т. е. операции

succ

pred

могут отсутствовать). Реаль-

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

массивами.

• Абстрактное индексирование: любая совокупность попарно различ-

ных значений (именно это стоило бы называть ассоциативными мас-

сивами).

Нужно только, чтобы существовало отображение из множества атрибутов в

отрезок целых.

Обычное обозначение конструктора массива включает в себя:

• имя определяемой структуры (имя типа массив),

• область изменения индексов (тип индексов, нижняя и верхняя граница,

т. е. отрезок типа) и

• тип компонент.