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

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

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

535

за один проход по массиву.

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

,...

— значения базового типа

— значения или переменные типа

set of

1. x ∈ S — предикат;

2. S1 = S2 — предикат;

3. S1 ∩ S2 — пересечение;

4. S1 ∪ S2 — объединение;

5. S1 − S2 — дополнение;

6. S1 ⊆ S2 — предикат включение;

7. |S| — размер множества (число элементов).

Поскольку физическая структура памяти машин близка к массиву булевых

значений, представление множества можно сделать еще эффективнее. Но в

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

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

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

принципиально различаться:

(I) маленькое n, меньшее либо равное числу разрядов адресуемого реги-

стра машины

Cell

;

(II) небольшое n, меньшее величины k∗

Cell

, где k — размер не очень боль-

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

ми.

(III) конечное, но довольно большое n, когда несколько прямо построенных

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

(IV) величина n не определяется как конечное с точки зрения машинной

памяти целое число.

Случай (I) наиболее легок с практической точки зрения: он реализуется наи-

более эффективно, красиво и концептуально естественно на уровне машин-

ной логики. При этом используются шкалы — битовые наборы, размещае-

мые в ячейках. Каждый бит шкалы указывает наличие или отсутствие того

536

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

или иного признака. В частности, пустое множество — шкала из всех нулей,

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

из всех единиц.Указанные выше операции вычисляются почти что на уровне

пары машинных команд.

К примеру, если

— множества-шкалы со следующими значени-

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

как логическая дизъюнкция шкал:

A: 1 1 1 1 1 1 1 1

: 1 1 1 1 1 1

A ∪ B

: 1 1 1 1 1 1 1 1 1 1 1 1

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

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

Случай (II) ненамного сложнее, но технические детали, которые придет-

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

принципам случая (I).

Случай (III) требует перехода от представления множества шкалой к мас-

сивам или спискам.В зависимости от мощностей множеств, с которыми пред-

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

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

представляющие, соответственно плотные или разреженные множества, для

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

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

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

фективного расположения значений (какого?), а во-вторых, надстройку, свя-

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

лать удобнее для выполнения нужных операций.

В данном случае есть три варианта представления:

• хранение значений —явный перечень элементов множества,например,

в виде списка;

• хранение ссылок на значения — эту лучше, когда возможных значений

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

ссылки;

В языке

Pascal

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

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

537

• хранение кодов значений — использование таблицы кодов (функция

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

код) может оказаться экономнее явного перечня элементов (шкала —

это частный случай данного метода, ссылка — другой частный случай).

Случай (IV). Вообще говоря, здесь требуется реализация символических вы-

числений

(не путать с символьными!), в которых объектами оперирова-

ния являются утверждения, т. е. предикаты, формирующие множества. Та-

ким образом, явное представление множеств элементов, мест элементов или

каких бы то ни было значений базового типа либо их заменителей не требует-

ся. Более того, оно было бы ограничительным по отношению к бесконечным

множествам.

В языке

Pascal

есть только минимально необходимый набор операций над

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

рениях должен быть перечислением. Под единой синтаксической оболочкой

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

ветствуют случаям (I) и (II). Этого хватает даже для множеств всех коротких

целых чисел.

В языке

Pascal

и его расширениях имеются литералы для изображения

множеств. Например, множество четырех приемлемых состояний выхода из

подпрограммы может быть изображено как

const

goodend=

[OK, User_break, Suspended_and_saved, Negative_result]

Пожалуй, небольшие множества — это единственное ‘гармоничное’ сред-

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

лизации.

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

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

ются исходными константами. Для реализации литеральных изображений

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

ей в стандартные представления. Естественное ограничение: за исключени-

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

чает вычисления, представленные обозначениями значений (символами). Все, что можно

вычислить в рамках символических вычислений — это преобразование символических вы-

ражений, направленные на их сокращение, на доказательство их свойств и т. п. В отличие от

символических вычислений символьные вычисления имеют дело с данными символьного и

строкового типов.

538

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

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

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

базового типа не предусмотрены.

Некоторые из перечисленных операций требуют более одной команды,

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

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

Почему в

С/С++

этого средства в явном виде нет? Ответ: есть побитовые

операции, и поэтому реализовывать то, что можно сделать с их помощью,

сочли уже ненужным.

Случай (IV) может показаться экзотическим, имеющим лишь академиче-

ский интерес. По этой причине его редко можно встретить в практических

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

мер, области на рисунке являются множествами точек, а точек слишком мно-

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

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

мание программ.

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

потенциально неограниченными множествами. В частности, они расширяют

выразительность оперирования со сложно устроенными множествами. От-

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

типов данных:

{x ∈ S|P (x)}—формирование множества с помощью предикатного филь-

тра P (x).

Как реализовать эту возможность? Первый приходящий на ум путь: сим-

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

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

ниями (в данном случае — множеств и их элементов), а не над конкретными

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

тематическом смысле (π,

√

2 и др.). Их можно трактовать как абстрактно-син-

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

ка изображения предикатов.

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

бесконечными множествами —

Setl

Интересно,что в первых версиях языка,разработанных Дж. Шварцем для

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

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

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

случая (IV). Реализационная стратегия этого проекта (который уместно на-

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

539

звать

сибирским Сетлом

) опиралась именно на символические вычисления.

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

ческие вычисления с множественными типами могут провоцировать очень

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

делениям. Например:

НОД

(x, y) =

max {n|1 6 n&n 6 min{x, y}&∃k1, k2 (x = k1 ∗ n&y = k2 ∗n)}

Из этого определения (оператора языка

Setl

) извлечь, к примеру, алгоритм

Евклида невозможно.

Задача разграничения эффективных и неэффективных описаний алгорит-

мов в языках, подобных

Setl

, решена не была. Быть может, по этой причине

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

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

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

1. Дать пример,когда разделение единиц измерения,предоставляемое ап-

паратом новых типов языка

Ada

, помогает находить ошибки в програм-

ме.

2. Какие достоинства и недостатки статической системы типов Вы може-

те указать?

3. Построить один из вариантов размещения диагональной матрицы в век-

торе и функцию ϕ, от него зависящую.

4. Для каких массивов целесообразно решеточное представление?

5. Почему прямолинейная реализация ключей неэффективна для боль-

ших массивов?

6. Когда целесообразно представлять множество перечнем его элементов?

Как целесообразно организовать этот перечень в предложенных Вами

случаях?

7. Если для базового типа определен линейный порядок, уточнить пред-

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

ствами:

540

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

(a)

min(S)

— минимальный элемент, содержащийся в

;

(b)

max(S)

— максимальный элемент, содержащийся в

;

(c)

succ(S,x)

— если x ∈ S, то элемент, обладающий свойством

y ∈ S&x < y&∀z (x < z ⇒ y 6 z),

если таковой существует, иначе не определено;

(d)

pred(S,x)

— определяется двойственно

succ

;

(e)

(x1 .. x2 )

— множество

{y ∈ T | x1 6 y&y 6 x2}.

8. Построить на

С++/C#

средства работы с небольшими множествами. С

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

ся достаточно изящно.

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

водится хранение значений — явный перечень элементов множества,

например, в виде списка.

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

дит хранение ссылок на значения — это лучше,когда возможных значе-

ний не очень много, и их размер превышает размер памяти, требуемый

для ссылки.

11. Постройте пакет для работы с большими множествами, когда проис-

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

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

ня элементов (шкала — это частный случай данного метода, ссылка —

другой частный случай).

12. Постройте свой собственный пакет для работы с большими множества-

ми, обладающими некоторыми общими свойствами. Явно сформули-

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

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

жестве нам не нужно хранить конкретные значения элементов.

13. Какими недостатками обладает реализация областей на рисунке как

множества точек экрана (что является не слишком большим множе-

ством и может быть представлено шкалой)?

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

541

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

Пусть R = (K

: T

, . . . , K

: T

) — универсальный набор компонент,

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

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

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

тора, с помощью которого эта структура построена. Это разные сущности. К

примеру,

array

[I1]

of array

[I2]

это рекурсивно определяемая, но не рекурсивная структура данных. В дан-

ном фрагменте указано, что компонентами массива с индексами из

явля-

ются компоненты, которые сами строятся как массивы.

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

ные графовые структуры.

При задании только одного конструктора в определении трудно описать

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

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

ниями над типами:

type

T1 = E1(T1,...,Tk);

...

Tk = Ek(T1,...,Tk);

Здесь определяется сразу несколько (k) типов. Эти соотношения трактуются

Явно оговорим некоторые тонкости. Возможен взгляд на массив и как на рекурсивную

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

таким образом:

Базис рекурсии.

M =

array

[]

— массив с компонентами типа

с нулевым числом компонентов;

Шаг рекурсии.

Если

— массив с n или меньшим количеством компонентов типа

, то

M array

[n+1]

— массив, у которого n + 1 компонентов типа

, где M — специальная операция над типа-

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

определяется тип массивов с подвижной верхней границей.

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

С/С++/C#

— это просто сокраще-

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

скалярного типа (это другой конструктор).

542

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

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

= B

; . . . ; T

= B

;

= E

m−1

, . . . , T

m−1

); . . . ; T

= E

m−1

, . . . , T

m−1

);

= lim

m→∞

; . . . ; T

= lim

m→∞

где B

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

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

общему определению рекурсии в теории программирования: (T

; . . . ; T

) —

наименьшая неподвижная точка системы операторов (E

; . . . ; E

= E

, . . . , T

);

. . .

= E

, . . . , T

);

⊆ T

⊆ ··· ⊆ T

;

. . . ;

⊆ T

⊆ ··· ⊆ T

;

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

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

type

X = X; Y = ^Y; Z =

array

[I]

и другие.

При работе с рекурсивными структурами данных, как и при рекурсии дей-

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

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

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

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

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

ходила бы под шаблон описания структуры. Из этого следуют два противо-

положных решения:

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

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

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

сутствия.

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

543

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

ют непосредственное оперирование с рекурсивными структурами данных,

рассматриваемыми в качестве базовых языковых структур данных. Конкре-

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

зовой структуры. Как правило, это специализированная обработка (КС-грам-

матики и синтаксический анализ, выражения

Рефала

и др.)

Для традиционных языков обычным является второе решение. Оно в точ-

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

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

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

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

затели —их значениями могут быть только ссылки на объекты заданного ти-

па.Первый вариант восходит к адресам традиционных архитектур с однород-

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

ствия типов. Второй вариант более точно отражает потребность определения

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

языке

Алгол 68

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

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

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

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

кая иллюстрация тому —

Lisp

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

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

указателями. Обсуждение методологических ошибок

Lisp

’а проведено в сле-

дующем разделе.

Формальную осмысленность списочных структур относительно существу-

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

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

ными в

Алголе 68

1. Любой рекурсивно определяемый ссылочный тип осмыслен, посколь-

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

на указатель, имеет стандартный размер.

2. Рекурсивное использование типа осмысленно, если при раскрытии си-

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

пользованию встретится осмысленный тип.

Таким образом, рекурсивные структуры существеннейшим образом задей-

544

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

ствуют аппарат указателей.

9.4.1. Списочные структуры

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

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

элеентов произвольной природы см. в Определении A.6.1.

В современном программировании наиболее распространенной реализа-

цией этого абстрактного определения являются списки в стиле языка

LISP

которые строятся с помощью следующей конструкции (

— имя типа эле-

ментов):

Sequence(T)

= (

Head

Tail

*Sequence(T)

); (9.6)

Выбор этих двух компонент производится по их именам. Как было сказано

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

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

(

refT

—

Алгол 68

—

Pascal

—

C++/C#

)Иначе конструкция понималась

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

графовой структуры.

Часто такую конструкцию называют также линейный список, или после-

довательность. Мы специально записали здесь уравнение для типа данных с

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

годящийся для последовательностей с произвольным типом элементов.

Конструкция (9.6) неполна в двух отношениях. Во-первых, необходимо

указать на возможность существования пустых списков (пустой список в тра-

диционной нотации

LISP

обозначается

NIL

{( )}

;

Это дополнение не снимается существованием указателя-джокера nil, по-

скольку

NIL

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

не всегда нужно трактовать как ошибку.

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

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

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

List(T)

(

NIL

(

union Head

: (

: ∗

List(T)

Tail

: ∗

List(T)

);

(9.7)