Файл: Алгоритмы и структуры данныхНовая версия для Оберона cdмосква, 2010Никлаус ВиртПеревод с английского под редакцией.pdf

1.3.2. Тип REAL
Тип
REAL
представляет подмножество вещественных чисел. Если для арифмети%
ческих операций с операндами типа
INTEGER
предполагается, что они дают точные результаты, то арифметические операции со значениями типа
REAL
могут быть неточными в пределах ошибок округления, вызванных тем, что вычисления про%
изводятся с конечным числом значащих цифр. Это главная причина для того, что%
бы явно различать типы
INTEGER
и
REAL
, как это делается в большинстве языков программирования.
Стандартные примитивные типы

Фундаментальные структуры данных
24
Стандартные операции – четыре основные арифметические операции: сложе%
ние (+), вычитание (–), умножение (*) и деление (/). Сущность типизации дан%
ных – в том, что разные типы становятся несовместимыми по присваиванию. Ис%
ключение делается для присваивания целочисленных значений вещественным переменным, так как семантика в этом случае однозначна. Ведь целые числа со%
ставляют подмножество вещественных. Однако присваивание в обратном на%
правлении запрещено: присваивание вещественного значения целой переменной требует отбрасывания дробной части или округления. Стандартная функция пре%
образования
ENTIER(x)
дает целую часть величины x
. Тогда округление величины x
выполняется с помощью
ENTIER(x + 0.5)
Многие языки программирования не содержат операций возведения в степень.
Следующий алгоритм обеспечивает быстрое вычисление величины y = x n
, где n
–
неотрицательное целое:
y := 1.0; i := n;
(* ADruS13 *)
WHILE i > 0 DO
(* x
0
n
= x i
* y *)
IF ODD(i) THEN y := y*x END;
x := x*x; i := i DIV 2
END
1.3.3. Тип BOOLEAN
Два значения стандартного типа
BOOLEAN
обозначаются идентификаторами
TRUE
и
FALSE
. Булевские операции – это логические конъюнкция, дизъюнкция и отри%
цание, которые определены в табл. 1.1. Логическая конъюнкция обозначается символом
&
, логическая дизъюнкция – символом
OR
, а отрицание – символом

Заметим, что операции сравнения всегда вычисляют результат типа
BOOLEAN
Поэтому результат сравнения можно присвоить переменной или использовать как операнд логической операции в булевском выражении. Например, для булев%
ских переменных p
и q
и целых переменных x = 5
, y = 8
, z = 10
два присваивания p := x = y q := (x
≤ y) & (y < z)
дают p = FALSE
и q = TRUE
p q
p & q p OR q
p
TRUE
TRUE
TRUE
TRUE
FALSE
TRUE
FALSE
TRUE
FALSE
FALSE
FALSE
TRUE
TRUE
FALSE
TRUE
FALSE
FALSE
FALSE
FALSE
TRUE
Таблица 1.1.
Таблица 1.1.
Таблица 1.1.
Таблица 1.1.
Таблица 1.1. Булевские операции
В большинстве языков программирования булевские операции
&
(
AND
) и
OR
обладают дополнительным свойством, отличающим их от других бинарных опера%
ций. Например, сумма x+y не определена, если не определен любой из операндов x

25
или y
, однако конъюнкция p&q определена, даже если не определено значение q
, при условии что p
равно
FALSE
. Такое соглашение оказывается важным и полезным. По%
этому точное определение операций
&
и
OR
дается следующими равенствами:
p & q
= если p
, то q
, иначе
FALSE
p OR q
= если p
, то
TRUE
, иначе q
1.3.4. Тип CHAR
Стандартный тип
CHAR
представляет литеры, которые можно напечатать.
К сожалению, нет общепринятого стандартного множества литер для всех вычислительных систем. Поэтому прилагательное «стандартный» в этом случае может привести к путанице; его следует понимать в смысле «стандартный для вычислительной установки, на которой должна выполняться программа».
Чаще всего используется множество литер, определенное Международной организацией по стандартизации (ISO), и, в частности, его американский вариант
ASCII (American Standard Code for Information Interchange). Поэтому множество
ASCII приведено в приложении A. Оно содержит 95 графических (имеющих изоб%
ражение) литер, а также 33 управляющие (не имеющих изображения) литеры,
используемые в основном при передаче данных и для управления печатающими устройствами.
Чтобы можно было создавать алгоритмы для работы с литерами (то есть со значениями типа
CHAR
), которые не зависели бы от вычислительной системы,
нужно иметь возможность сделать некоторые минимальные предположения о свойствах множества литер, а именно:
1. Тип
CHAR
содержит 26 заглавных латинских букв, 26 строчных букв, 10 де%
сятичных цифр, а также некоторые другие графические символы, например знаки препинания.
2. Подмножества букв и цифр упорядочены и между собой не пересекаются:
("A"
≤
x) & (x
≤
"Z")
подразумевает, что x
– заглавная буква;
("a"
≤
x) & (x
≤
"z")
подразумевает, что x
– строчная буква;
("0"
≤
x) & (x
≤
"9")
подразумевает, что x
– десятичная цифра.
3. Тип
CHAR
содержит непечатаемые символы пробела и конца строки, кото%
рые можно использовать как разделители.
Для написания машинно независимых программ особенно важны две стандартные функции преобразования между типами
CHAR
и
INTEGER
. Назовем их
ORD(ch)
(дает порядковый номер литеры ch в используемом множестве литер)
Рис. 1.1. Представление текста
Стандартные примитивные типы

Фундаментальные структуры данных
26
и
CHR(i)
(дает литеру с порядковым номером i
). Таким образом,
CHR
является обратной функцией для
ORD
и наоборот, то есть
ORD(CHR(i)) = i
(если
CHR(i)
определено)
CHR(ORD(c)) = c
Кроме того, постулируем наличие стандартной функции
CAP(ch)
. Ее значе%
ние – заглавная буква, соответствующая ch
, если ch
– буква.
если ch
– строчная буква, то
CAP(ch)
– соответствующая заглавная буква если ch
– заглавная буква, то
CAP(ch) = ch
1.3.5. Тип SET
Тип
SET
представляет множества, элементами которых являются целые числа из диапазона от 0 до некоторого небольшого числа, обычно 31 или 63. Например,
если определены переменные
VAR r, s, t: SET
то возможны присваивания r := {5}; s := {x, y .. z}; t := {}
Здесь переменной r присваивается множество, состоящее из единственного элемента
5
; переменной t
присваивается пустое множество, а переменной s
– мно%
жество, состоящее из элементов x
, y
, y+1
, … , z–1
, z
Следующие элементарные операции определены для операндов типа
SET
:
*
пересечение множеств
+
объединение множеств
–
разность множеств
/
симметрическая разность множеств
IN
принадлежность множеству
Операции пересечения и объединения множеств часто называют умножением и сложением множеств соответственно; приоритеты этих операций определяются так, что приоритет пересечения выше, чем у объединения и разности, а приори%
теты последних выше, чем у операции принадлежности, которая вычисляет логи%
ческое значение. Ниже даются примеры выражений с множествами и их версии с полностью расставленными скобками:
r * s + t
= (r*s) + t r – s * t
= r – (s*t)
r – s + t = (r–s) + t r + s / t = r + (s/t)
x IN s + t = x IN (s+t)
1.4. Массивы
Вероятно, массив – наиболее широко используемая структура данных; в некото%
рых языках это вообще единственная структура. Массив состоит из компонент,
имеющих одинаковый тип, называемый базовым; поэтому о массиве говорят как

27
об однородной структуре. Массив допускает произвольный доступ, так как можно произвольно выбрать любую компоненту, и доступ к ним осуществляется одина
ково быстро. Чтобы обозначить отдельную компоненту, к имени всего массива нужно присоединить индекс, то есть номер компоненты. Индекс должен быть це
лым числом в диапазоне от
0
до n–1
, где n
– число элементов, или длина массива.
TYPE T = ARRAY n OF T0
Примеры
TYPE Row
= ARRAY 4 OF REAL
TYPE Card
= ARRAY 80 OF CHAR
TYPE Name = ARRAY 32 OF CHAR
Конкретное значение переменной
VAR x: Row у которой все компоненты удовлетворяют уравнению x
i
= 2
–i
, можно представить как на рис. 1.2.
Отдельная компонента массива выбирается с по
мощью индекса. Если имеется переменнаямассив x
, то соответствующий селектор (то есть конструкцию для выбора отдельной компоненты) будем изображать по
средством имени массива, за которым следует индекс со
ответствующей компоненты i
, и будем писать x
i или x[i]
Первое из этих обозначений принято в математике, по
этому компоненту массива еще называют индексирован
ной переменной.
Обычный способ работы с массивами, особенно с большими, состоит в том,
чтобы выборочно изменять отдельные компоненты, вместо того чтобы строить новое составное значение целиком. Для этого переменнуюмассив рассматривают как массив переменныхкомпонент и разрешают присваивания отдельным компонентам, например x[i]
:=
0.125
. Хотя при выборочном присваивании меня
ется только одна компонента, с концептуальной точки зрения мы должны счи
тать, что меняется все составное значение массива.
Тот факт, что индексы массива (фактически имена компонент массива) суть целые числа, имеет весьма важное следствие: индексы могут вычисляться. Вместо индексаконстанты можно поставить общее индексное выражение; тогда подра
зумевается, что выражение вычисляется, а его значение используется для выбора компоненты. Такая общность не только дает весьма важное и мощное средство программирования, но и приводит к одной из самых частых ошибок в программах:
вычисленное значение индекса может оказаться за пределами диапазона индек
сов данного массива. Будем предполагать, что «приличные» вычислительные сис
темы выдают предупреждение, если имеет место ошибочная попытка доступа к несуществующей компоненте массива.
Мощность стуктурированного типа, то есть количество значений, принадлежа
щих этому типу, равна произведению мощностей его компонент. Поскольку все компоненты массивового типа
T
имеют одинаковый базовый тип
T0
, то получаем
Рис. 1.2. Массив типа
Row
, в котором x
i
= 2
–i
Массивы

Фундаментальные структуры данных
28
card(T) = card(T0)
n
Элементы массивов сами могут быть составными. Переменная%массив, у кото%
рой все компоненты – тоже массивы, называется матрицей. Например,
M: ARRAY 10 OF Row является массивом, состоящим из десяти компонент (строк), причем каждая ком%
понента состоит из четырех компонент типа
REAL
. Такой массив называется мат%
рицей
10
×
4
с вещественными компонентами. Селекторы могут приписываться один за другим, так что
M
ij и
M[i][j]
обозначают j
%ю компоненту строки
M
i
, которая,
в свою очередь, является i
%й компонентой матрицы
M
. Обычно используют сокра%
щенную запись
M[i,j]
, и аналогично для объявления
M: ARRAY 10 OF ARRAY 4 OF REAL
можно использовать сокращенную запись
M: ARRAY 10, 4 OF REAL
Если нужно выполнить некоторое действие со всеми компонентами массива или с группой идущих подряд компонент, то удобно подчеркнуть этот факт, ис%
пользуя оператор цикла
FOR
, как показано в следующих примерах, где вычисляет%
ся сумма и находится максимальный элемент массива a
:
VAR a: ARRAY N OF INTEGER;
(* ADruS14 *)
sum := 0;
FOR i := 0 TO N–1 DO sum := a[i] + sum END
k := 0; max := a[0];
FOR i := 1 TO N–1 DO
IF max < a[i] THEN k := i; max := a[k] END
END
В следующем примере предполагается, что дробь f
представляется в десятич%
ном виде с k–1
цифрами, то есть массивом d
, таким, что f = S
S
S
S
Si: 0
≤
i < k: d i
* 10
–i или f = d
0
+ 10*d
1
+ 100*d
2
+ … + 10
k–1
*d k–1
Предположим теперь, что мы хотим поделить f
на
2
. Это делается повторением уже знакомой операции деления для всех k–1
цифр d
i
, начиная с i=1
. Каждая циф%
ра делится на
2
с учетом остатка деления в предыдущей позиции, а возможный остаток от деления в данной позиции, в свою очередь, запоминается для следую%
щего шага:
r := 10*r +d[i]; d[i] := r DIV 2; r := r MOD 2
Этот алгоритм используется для вычисления таблицы отрицательных степеней числа
2
. Повторные деления пополам для вычисления величин
2
–1
, 2
–2
, ... , 2
–N
снова удобно выразить оператором цикла
FOR
, так что в итоге получается пара вложен%
ных циклов
FOR

29
PROCEDURE Power (VAR W: Texts.Writer; N: INTEGER);
(* ADruS14 *)
(* 2*)
VAR i, k, r: INTEGER;
d: ARRAY N OF INTEGER;
BEGIN
FOR k := 0 TO N–1 DO
Texts.Write(W, "."); r := 0;
FOR i := 0 TO k–1 DO
r := 10*r + d[i]; d[i] := r DIV 2; r := r MOD 2;
Texts.Write(W, CHR(d[i] + ORD("0")))
END;
d[k] := 5; Texts.Write(W, "5"); Texts.WriteLn(W)
END
END Power
В результате для
N = 10
печатается следующий текст:
.5
.25
.125
.0625
.03125
.015625
.0078125
.00390625
.001953125
.0009765625
1.5. Записи
Самый общий способ строить составные типы заключается в том, чтобы объединять в некий агрегат элементы произвольных типов, которые сами могут быть составными типами. Примеры из математики: комплексные числа, составленные из пары веще%
ственных, а также координаты точки, составленные из двух или более чисел в соот%
ветствии с размерностью пространства. Пример из обработки данных: описание лю%
дей посредством нескольких свойств, таких как имя и фамилия, дата рождения.
С точки зрения математики, такой составной тип (compound type) является прямым (декартовым) произведением составляющих типов (constituent types):
множество значений составного типа состоит из всевозможных комбинаций зна%
чений, каждое из которых взято из множества значений соответствующего со%
ставляющего типа. Поэтому число таких комбинаций, называемых также n
ками
(n%tuples), равно произведению чисел элементов каждого составляющего типа;
другими словами, мощность составного типа равна произведению мощностей со%
ставляющих типов.
В обработке данных сложные типы, такие как описания людей или объектов,
обычно хранятся в файлах или базах данных и содержат нужные характеристики человека или объекта. Поэтому для описания составных данных такой природы
Записи

Фундаментальные структуры данных
30
стал широко употребляться термин запись, и мы тоже будем его использовать вместо термина «прямое произведение». В общем случае записевый тип (record type)
T
с компонентами типов
T
1
,
T
2
, ... ,
T
n определяется следующим образом:
TYPE T = RECORD s
1
: T
1
; s
2
: T
2
; ... s n
: T
n
END
card(T) = card(T
1
) * card(T
2
) * ... * card(T
n
)
Примеры
TYPE Complex = RECORD re, im: REAL END
TYPE Date =
RECORD day, month, year: INTEGER END
TYPE Person =
RECORD name, firstname: Name;
birthdate: Date;
male: BOOLEAN
END
Конкретные значения записей, например, для переменных z: Complex d: Date p: Person можно изобразить так, как показано на рис. 1.3.
Рис. 1.3. Записи типов
Complex, Date и Person
Идентификаторы s
1
, s
2
, ..., s
n
, вводимые в определении записевого типа, суть имена, данные отдельным компонентам переменных этого типа. Компоненты за%
писи называются полями (field), а их имена – идентификаторами полей (field identifiers). Их используют в селекторах, применяемых к переменным записевых типов. Если дана переменная x:
T
, ее i
%е поле обозначается как x.s i
. Можно выпол%
нить частичное изменение x
, если использовать такой селектор в левой части опе%
ратора присваивания:
x.s i
:= e где e
– значение (выражение) типа
T
i
. Например, если имеются записевые пере%
менные z
, d
, и p
, объявленные выше, то следующие выражения суть селекторы их компонент:
z.im
(
типа
REAL)
d.month
(
типа
INTEGER)

31
p.name
(
типа
Name)
p.birthdate
(
типа
Date)
p.birthdate.day
(
типа
INTEGER)
p.mail
(
типа
BOOLEAN)
Пример типа
Person показывает, что компонента записевого типа сама может быть составной. Поэтому селекторы могут быть применены один за другим. Есте%
ственно, что разные способы структурирования тоже могут комбинироваться.
Например, i
%я компонента массива a
, который сам является компонентой записе%
вой переменной r
, обозначается как r.a[i]
, а компонента с именем s
из i
%го элемента массива a
, состоящего из записей, обозначается как a[i].s
Прямое произведение по определению состоит из всевозможных комбинаций элементов своих составляющих типов. Однако нужно заметить, что в реальных приложениях не все они могут иметь смысл. Например, определенный выше тип
Date допускает значения 31 апреля и 29 февраля 1985, которых в календаре нет.
Поэтому приведенное определение этого типа отражает реальную ситуацию не вполне верно, но достаточно близко, а программист должен обеспечить, чтобы при выполнении программы бессмысленные значения никогда не возникали.
Следующий фрагмент программы показывает использование записевых пере%
менных. Его назначение – подсчет числа лиц женского пола, родившихся после
2000 г., среди представленных в переменной%массиве:
VAR count: INTEGER;
family: ARRAY N OF Person;
count := 0;
FOR i := 0 TO N–1 DO
IF family[i].male & (family[i].birthdate.year > 2000) THEN INC(count) END
END
И запись, и массив обеспечивают произвольный доступ к своим компонентам.
Запись является более общей в том смысле, что ее составляющие типы могут быть разными. Массив, в свою очередь, допускает большую гибкость в том отношении,
что селекторы компонент могут вычисляться (задаваться выражениями), тогда как селекторы компонент записи суть идентификаторы полей, объявленные в определении типа записи.

1   2   3   4   5   6   7   8   9   ...   22

1.6. Представление массивов,
записей и множеств
Смысл использования абстракций в программировании – в том, чтобы обеспе%
чить возможность спроектировать, понять и верифицировать программу, исходя только из свойств абстракций, то есть не зная о том, как абстракции реализованы и представлены на конкретной машине. Тем не менее профессиональному программисту нужно понимать широко применяемые способы представления фундаментальных структур данных. Это может помочь принять разумные реше%
Представление массивов, записей и множеств

Фундаментальные структуры данных
32
ния о построении программы и данных в свете не только абстрактных свойств структур, но и их реализации на конкретной машине с учетом ее специфических особенностей и ограничений.
Проблема представления данных заключается в том, как отобразить абстракт%
ную структуру на память компьютера. Память компьютера – это, грубо говоря,
массив отдельных ячеек, которые называются байтами. Они интерпретируются как группы из 8 бит каждая. Индексы байтов называются адресами.
VAR store: ARRAY StoreSize OF BYTE
Примитивные типы представляются небольшим числом байтов, обычно 1, 2, 4
или 8. Компьютеры проектируются так, чтобы пересылать небольшие группы смежных байтов одновременно, или, как говорят, параллельно. Единицу одновре%
менной пересылки называют словом.
1.6.1. Представление массивов
Представление массива – это отображение (абстрактного) массива, компоненты ко%
торого имеют тип
T
, на память компьютера, которая сама есть массив компонент типа
BYTE
. Массив должен быть отображен на память таким образом, чтобы вычисление адресов его компонент было как можно более простым (и поэтому эффективным).
Адрес i
для j
%й компоненты массива вычисляется с помощью линейной функции i = i
0
+ j*s,
где i
0
– адрес первой компоненты, а s
– количество слов, которые занимает одна компонента. Принимая, что слово является наименьшей единицей пересылки содержимого памяти, весьма желательно, чтобы s
было целым числом, в простей%
шем случае s = 1
. Если s
не является целым (а это довольно обычная ситуация), то s
обычно округляется вверх до ближайшего большего целого
S
. Тогда каждая ком%
понента массива занимает
S
слов, тогда как
S–s слов остаются неиспользованными
(см. рис. 1.4 и 1.5). Округление необходимого числа слов вверх до ближайшего це%
лого называется выравниванием (padding). Эффективность использования памя%
ти u
определяется как отношение минимального объема памяти, нужного для
Рис. 1.4. Отображение массива на память компьютера

33
представления структуры, к реально использованному объему:
u = s /
(
s
, округленное вверх до ближайшего целого).
Поскольку проектировщик компилятора должен стремиться к тому, чтобы эффективность использования памяти была как можно ближе к 1, но при этом доступ к частям слова громоздок и относительно неэффективен, приходится идти на компромисс. При этом учитываются следующие соображения:
1. Выравнивание уменьшает эффективность использования памяти.
2. Отказ от выравнивания может повлечь необходимость выполнять неэф%
фективный доступ к частям слова.
3. Доступ к частям слова может вызвать разбухание скомпилированного кода и тем самым уменьшить выигрыш, полученный из%за отказа от выравнивания.
На самом деле соображения 2 и 3 обычно настолько существенны, что компи%
ляторы автоматически используют выравнивание. Заметим, что эффективность использования памяти всегда u > 0.5
, если s > 0.5
. Если же s
≤
0.5
, то эффек%
тивность использования памяти можно сильно увеличить, размещая более одной компоненты массива в каждом слове. Это называется упаковкой (packing). Если в одном слове упакованы n
компонент, то эффективность использования памяти равна (см. рис. 1.6)
u = n*s /
(
n*s
, округленное вверх до ближайшего целого).
Рис. 1.5. Представление записи с выравниванием
Рис. 1.6. Упаковка шести компонент в одном слове
Доступ к i
%й компоненте упакованного массива подразумевает вычисление ад%
реса слова j
, в котором находится нужная компонента, а также позиции k
%ой ком%
поненты внутри слова:
j = i DIV n k = i MOD n
В большинстве языков программирования программист не имеет возможно%
сти управлять представлением структур данных. Однако должна быть возмож%
ность указывать желательность упаковки хотя бы в тех случаях, когда в одно сло%
во помещается больше одной компоненты, то есть когда может быть достигнут
Представление массивов, записей и множеств

Фундаментальные структуры данных
34
выигрыш в экономии памяти в два раза и более. Можно предложить указывать желательность упаковки с помощью символа
PACKED
, который ставится перед символом
ARRAY
(или
RECORD
) в соответствующем объявлении.
1.6.2. Представление записей
Записи отображаются на память компьютера простым расположением подряд их компонент. Адрес компоненты (поля) r
i относительно адреса начала записи r
на%
зывается смещением (offset) поля k
i
. Оно вычисляется следующим образом:
k i
= s
1
+ s
2
+ ... + s i–1
k
0
= 0
где s j
– размер (в словах) j
%й компоненты. Здесь видно, что равенство типов всех компонент массива имеет приятным следствием, что k
i
= i
×
s
. К несчастью, общ%
ность записевой структуры не позволяет использовать простую линейную функ%
цию для вычисления смещения компоненты; именно поэтому требуют, чтобы компоненты записи выбирались с помощью фиксированных идентификаторов.
У этого ограничения есть то преимущество, что смещения полей определяются во время компиляции. В результате доступ к полям записи более эффективен.
Упаковка может привести к выигрышу, если несколько компонент записи мо%
гут поместиться в одном слове памяти (см. рис. 1.7). Поскольку смещения могут быть вычислены компилятором, смещение поля, упакованного внутри слова, то%
же может быть определено компилятором. Это означает, что на многих вычисли%
тельных установках упаковка записей в гораздо меньшей степени снижает эффек%
тивность доступа к полям, чем упаковка массивов.
Рис. 1.7. Представление упакованной записи
1.6.3. Представление множеств
Множество s
удобно представлять в памяти компьютера его характеристической функцией
C(s)
. Это массив логических значений, чья i
%я компонента означает, что i
присутствует в s
. Например, множество небольших чисел s = {2, 3, 5, 7, 11, 13}
представляется последовательностью или цепочкой битов:

35
C(s) = (… 0010100010101100)
Представление множеств характеристическими функциями имеет то преиму%
щество, что операции вычисления, объединения, пересечения и разности двух множеств могут быть реализованы как элементарные логические операции. Сле%
дующие тождества, выполняющиеся для всех элементов i
множеств x
и y
, связыва%
ют логические операции с операциями на множествах:
i IN (x+y) = (i IN x) OR (i IN y)
i IN (x*y) = (i IN x) & (i IN y)
i IN (x–y) = (i IN x) & (i IN y)
Такие логические операции имеются во всех цифровых компьютерах, и, более того, они выполняются одновременно для всех элементов (битов) слова. Поэтому для эффективной реализации базовых операций множества их следует пред%
ставлять небольшим фиксированным количеством слов, для которых можно вы%
полнить не только базовые логические операции, но и операции сдвига. Тогда проверка на принадлежность реализуется единственным сдвигом c последующей проверкой знака. В результате проверка вида x IN {c
1
, c
2
, ... , c n
}
может быть реализована гораздо эффективнее, чем эквивалентное булевское выражение
(x = c
1
) OR (x = c
2
) OR ... OR (x = c n
)
Как следствие множества должны использоваться только c небольшими чис%
лами в качестве элементов, из которых наибольшее равно длине слова компьюте%
ра (минус 1).
1.7. Файлы или последовательности
Еще один элементарный способ структурирования – последовательность. Обыч%
но это однородная структура, подобная массиву. Это означает, что все ее элемен%
ты имеют одинаковый тип – базовый тип последовательности. Будем обозначать последовательность s
из n
элементов следующим образом:
s = 0
, s
1
, s
2
, ... , s n–1
>
Число n
называется длиной последовательности.
Эта структура выглядит в точности как массив. Но существенная разница в том, что у массива число элементов зафиксировано в его определении, а у после%
довательности – нет. То есть оно может меняться во время выполнения програм%
мы. Хотя каждая последовательность в любой момент времени имеет конкретную конечную длину, мы должны считать мощность последовательностного типа бес%
конечной, так как нет никаких ограничений на потенциальную длину последова%
тельностей.
Прямое следствие переменной длины последовательностей – невозможность отвести фиксированный объем памяти под переменные%последовательности. По%
этому память нужно выделять во время выполнения программы, в частности ког%
да последовательность растет. Соответственно, когда последовательность сокра%
Файлы или последовательности

Фундаментальные структуры данных
36
щается, освобождающуюся память можно утилизовать. В любом случае нужна некая динамическая схема выделения памяти. Подобными свойствами обладают все структуры переменного размера, и это обстоятельство столь важно, что мы характеризуем их как «сложные» (advanced) структуры, в отличие от фундамен%
тальных, обсуждавшихся до сих пор.
Тогда почему мы обсуждаем последовательности в главе, посвященной фунда%
ментальным структурам? Главная причина – в том, что стратегия управления памятью для последовательностей оказывается достаточно простой (в отличие от других «сложных» структур), если потребовать определенной дисциплины исполь%
зования последовательностей. И тогда можно обеспечить довольно эффективный механизм управления памятью. Вторая причина – в том, что едва ли не в каждой задаче, решаемой с помощью компьютеров, используются последовательности.
Например, последовательности обычно используют в тех случаях, когда данные пересылаются с одного устройства хранения на другое, например с диска или лен%
ты в оперативную память или обратно.
Упомянутая дисциплина состоит в том, чтобы ограничиться только последова%
тельным доступом. Это подразумевает, что доступ к элементам последовательности осуществляется строго в порядке их следования, а порождается последователь%
ность присоединением новых элементов к ее концу. Немедленное следствие –
невозможность прямого доступа к элементам, за исключением того элемента, ко%
торый доступен для просмотра в данный момент. Именно такая дисциплина дос%
тупа составляет главное отличие последовательностей от массивов. Как мы уви%
дим в главе 2, дисциплина доступа оказывает глубокое влияние на программы.
Преимущество последовательного доступа, который все%таки является серьез%
ным ограничением, – в относительной простоте необходимого здесь способа управ%
ления памятью. Но еще важнее возможность использовать эффективные методы
буферизации (buffering) при пересылке данных между оперативной памятью и внешними устройствами. Последовательный доступ позволяет «прокачивать»
потоки данных с помощью «каналов» (pipes) между разными устройствами хране%
ния. Буферизация подразумевает накопление данных из потока в буфере и последу%
ющую пересылку целиком содержимого всего буфера, как только он заполнится.
Это приводит к весьма существенному повышению эффективности использова%
ния внешней памяти. Если ограничиться только последовательным доступом, то механизм буферизации довольно прост для любых последовательностей и любых внешних устройств. Поэтому его можно заранее предусмотреть в вычислитель%
ной системе и предоставить для общего пользования, освободив программиста от необходимости включать его в свою программу. Обычно здесь речь идет о файловой
системе, где для постоянного хранения данных используют устройства последова%
тельного доступа большого объема, в которых данные сохраняются даже после вык%
лючения компьютера. Единицу хранения данных в таких устройствах обычно на%
зывают (последовательным) файлом. Мы будем использовать термин файл (file)
как синоним для термина последовательность (sequence).
Существуют устройства хранения данных, в которых последовательный дос%
туп является единственно возможным. Очевидно, сюда относятся все виды лент.
Но даже на магнитных дисках каждая дорожка представляет собой хранилище,

37
допускающее только последовательный доступ. Строго последовательный доступ характерен для любых устройств с механически движущимися частями, а также для некоторых других.
Отсюда следует, что полезно проводить различие между стуктурой данных, то есть последовательностью, с одной стороны, и механизмом доступа к ее элемен
там – с другой. Первая объявляется как структура данных, а механизм доступа обычно реализуется посредством некоторой записи, с которой ассоциированы не%
которые операторы, – или, используя современную терминологию, посредством объекта доступа или «бегунка» (rider object). Различать объявление данных и ме%
ханизм доступа полезно еще и потому, что для одной последовательности могут одновременно существовать несколько точек доступа, в которых осуществляется последовательный доступ к разным частям последовательности.
Суммируем главное из предшествующего обсуждения следующим образом:
1. Массивы и записи – структуры, допускающие произвольный доступ к сво%
им элементам. Их используют, размещая в оперативной памяти.
2. Последовательности используются для работы с данными на внешних устройствах хранения, допускающих последовательный доступ, таких как диски или ленты.
3. Мы проводим различие между последовательностью как структурой дан%
ных и механизмом доступа, подразумевающим определенную позицию в ней.
1.7.1. Элементарные операции с файлами
Дисциплину последовательного доступа можно обеспечить, предоставляя набор специальных операций, помимо которых доступ к файлам невозможен. Поэтому хотя в общих рассуждениях можно использовать обозначение s
i для i
%го элемента последовательности s
, в программе это невозможно.
Последовательности, то есть файлы, – это обычно большие, динамические структуры данных, сохраняемые на внешних запоминающих устройствах. Такое устройство сохраняет данные, даже если программа заканчивается или отключа%
ется компьютер. Поэтому введение файловой переменной – сложная операция,
подразумевающая подсоединение данных на внешнем устройстве к файловой пе%
ременной в программе. Поэтому объявим тип
File в отдельном модуле, опреде%
ление которого описывает тип вместе с соответствующими операциями. Назовем этот модуль
Files и условимся, что последовательностная или файловая перемен%
ная должна быть явно инициализирована («открыта») посредством вызова соответствующей операции или функции:
VAR f: File f := Open(name)
где name идентифицирует файл на внешнем устройстве хранения данных. В не%
которых системах различается открытие существующего и нового файлов:
f := Old(name)
f := New(name)
Файлы или последовательности

Фундаментальные структуры данных
38
Нужно еще потребовать, чтобы связь между внешней памятью и файловой пе%
ременной разрывалась, например посредством вызова
Close(f)
Очевидно, набор операций должен содержать операцию для порождения (за%
писи) последовательности и еще одну – для ее просмотра (чтения). Потребуем,
чтобы эти операции применялись не напрямую к файлу, а к некоторому объекту%
бегунку, который сам подсоединен к файлу (последовательности) и который реа%
лизует некоторый механизм доступа. Дисциплина последовательного доступа обеспечивается ограничением набора операций доступа (процедур).
Последовательность создается присоединением элементов к ее концу после подсоединения бегунка к файлу. Если есть объявление
VAR r: Rider то бегунок r
подсоединяется к файлу f
оператором
Set(r, f, pos)
где pos = 0
обозначает начало файла (последовательности). Вот типичная схема порождения последовательности:
WHILE
DO x; Write(r, x) END
Чтобы прочитать последовательность, сначала к ней подсоединяется бегунок,
как показано выше, и затем производится чтение одного элемента за другим. Вот типичная схема чтения последовательности:
Read(r, x);
WHILE r.eof DO
x; Read(r, x) END
Очевидно, с каждым бегунком всегда связана некоторая позиция. Обозначим ее как r.pos
. Далее примем, что бегунок содержит предикат (флажок) r.eof
,
указывающий, был ли достигнут конец последовательности в предыдущей опера%
ции чтения
(eof – сокращение от англ. «end of file», то есть «конец файла» – прим.
перев.). Теперь мы можем постулировать и неформально описать следующий на%
бор примитивных операций:
1a.
New(f, name)
определяет f
как пустую последовательность.
1b.
Old(f, name)
определяет f
как последовательность, хранящуюся на внеш%
нем носителе с указанным именем.
2.
Set(r, f, pos)
связывает бегунок r
с последовательностью f
и устанавлива%
ет его в позицию pos
3.
Write(r, x)
записывает элемент со значением x
в последовательность,
с которой связан бегунок r
, и продвигает его вперед.
4.
Read(r, x)
присваивает переменной x
значение элемента, на который указывает бегунок r
, и продвигает его вперед.
5.
Close(f)
регистрирует записанный файл f
на внешнем носителе (с не%
медленной записью содержимого буферов на диск).
Замечание. Запись элемента в последовательность – это часто достаточно сложная операция. С другой стороны, файлы обычно создаются присоединением новых элементов в конце.

39
Замечание переводчика. В примерах программ в книге используются еще две операции:
6.
WriteInt(r, n)
записывает целое число n
в последовательность, с которой связан бегунок r
, и продвигает его вперед.
7. ReadInt(r, n)
присваивает переменной n
целое число, на которое указывает бегунок r
, и продвигает его вперед.
Чтобы дать более точное представление об операциях последовательного дос%
тупа, ниже приводится пример реализации. В нем показано, как можно выразить операции, если последовательности представлены массивами. Этот пример наме%
ренно использует только понятия, введенные и обсужденные ранее, и в нем нет ни буферизации, ни последовательных устройств хранения данных, которые, как указывалось выше, делают понятие последовательности по%настоящему нужным и полезным. Тем не менее этот пример показывает все существенные свойства простейших операций последовательного доступа независимо от того, как после%
довательности представляются в памяти.
Операции реализуются как обычные процедуры. Такой набор объявлений ти%
пов, переменных и заголовков процедур (сигнатур) называется определением
(definition). Будем предполагать, что элементами последовательностей являются литеры, то есть что речь идет о текстовых файлах, чьи элементы имеют тип
CHAR
Объявления типов
File и
Rider являются хорошими примерами применения запи%
сей, так как в дополнение к полю, обозначающему массив, представляющий дан%
ные, нужны и другие поля для обозначения текущей длины файла и позиции, то есть состояния бегунка:
DEFINITION Files;
(* ADruS171_Files *)
TYPE File; (* *)
Rider = RECORD eof: BOOLEAN END;
PROCEDURE New(VAR name: ARRAY OF CHAR): File;
PROCEDURE Old(VAR name: ARRAY OF CHAR): File;
PROCEDURE Close(VAR f: File);
PROCEDURE Set(VAR r: Rider; VAR f: File; pos: INTEGER);
PROCEDURE Write(VAR r: Rider; ch: CHAR);
PROCEDURE Read(VAR r: Rider; VAR ch: CHAR);
PROCEDURE WriteInt(VAR r: Rider; n: INTEGER);
PROCEDURE ReadInt(VAR r: Rider; VAR n: INTEGER);
END Files.
Определение представляет собой некоторую абстракцию. Здесь нам даны два типа данных,
File и
Rider
, вместе с соответствующими операциями, но без каких%
либо дальнейших деталей, раскрывающих их реальное представление в памяти.
Что касается операций, объявленных как процедуры, то мы видим только их заго%
ловки. Детали реализации не показаны здесь намеренно, и называется это упря
тыванием информации (information hiding). О бегунках мы узнаем только то, что
Файлы или последовательности

Фундаментальные структуры данных
40
у них есть свойство с именем eof
. Этот флажок получает значение
TRUE
, когда опе%
рация чтения достигает конца файла. Позиция бегунка скрыта, и поэтому его ин%
вариант не может быть разрушен прямым обращением к его полям. Инвариант выражает тот факт, что позиция бегунка всегда находится в пределах, соответ%
ствующих данной последовательности. Истинность инварианта первоначально устанавливается процедурой
Set
, а в дальнейшем требуется и поддерживается процедурами
Read и
Write
(а также
ReadInt и
WriteInt
– прим. перев.).
Операторы, реализующие описанные процедуры, а также все детали реализа%
ции типов данных содержатся в так называемом модуле (module). Представить данные и реализовать процедуры можно многими способами. В качестве про%
стого примера приведем следующий модуль (с фиксированной максимальной длиной файла):
MODULE Files;
(* ADruS171_Files *)
CONST MaxLength = 4096;
TYPE
File
File
File
File
File = POINTER TO RECORD
len: INTEGER;
a: ARRAY MaxLength OF CHAR
END;
Rider
Rider
Rider
Rider
Rider = RECORD (* 0 <= pos <= f.len <= Max Length *)
f: File; pos: INTEGER; eof: BOOLEAN
END;
PROCEDURE New
New
New
New
New (name: ARRAY OF CHAR): File;
VAR f: File;
BEGIN
NEW(f); f.len := 0; f.eof := FALSE;
(* ! *)
RETURN f
END New;
PROCEDURE Old
Old
Old
Old
Old (name: ARRAY OF CHAR): File;
VAR f: File;
BEGIN
NEW(f); f.eof := FALSE; (* *)
RETURN f
END Old;
PROCEDURE Close
Close
Close
Close
Close (VAR f: File);
BEGIN
END Close;
PROCEDURE Set
Set
Set
Set
Set (VAR r: Rider; f: File; pos: INTEGER);
BEGIN (* # f # NIL*)
r.f := f; r.eof := FALSE;
IF pos >= 0 THEN
IF pos <= f.len THEN r.pos := pos ELSE r.pos := f.len END
ELSE

41
r.pos := 0
END
END Set;
PROCEDURE Write
Write
Write
Write
Write (VAR r: Rider; ch: CHAR);
BEGIN
IF (r.pos <= r.s.len) & (r.pos < MaxLength) THEN
r.f.a[r.pos] := ch; INC(r.pos);
IF r.pos > r.f.len THEN INC(r.f.len) END
ELSE
r.eof := TRUE
END
END Write;
PROCEDURE Read
Read
Read
Read
Read (VAR r: Rider; VAR ch: CHAR);
BEGIN
IF r.pos < r.f.len THEN
ch := r.f.a[r.pos]; INC(r.pos)
ELSE
r.eof := TRUE
END
END Read;
PROCEDURE WriteInt
WriteInt
WriteInt
WriteInt
WriteInt (VAR r: Rider; n: INTEGER);
BEGIN (* !*)
END WriteInt;
PROCEDURE ReadInt
ReadInt
ReadInt
ReadInt
ReadInt (VAR r: Rider; VAR n: INTEGER);
BEGIN (* !*)
END ReadInt;
END Files.
В этом примере максимальная длина, которую могут иметь файлы, задается произвольно выбранной константой. Если какая%то программа попытается со%
здать более длинную последовательность, то это будет не ошибкой программы,
а недостатком данной реализации. С другой стороны, попытка чтения за текущим концом файла будет означать ошибку программы. Здесь флаг r.eof также исполь%
зуется операцией записи, чтобы сообщить, что выполнить ее не удалось. Поэтому условие
r.eof является предусловием как для
Read
, так и для
Write
(предусло%
вие – это логическое выражение, которое должно быть истинным для корректно%
го выполнения некоторой операции – прим. перев.).

1   2   3   4   5   6   7   8   9   ...   22

1.7.2. Буферизация последовательностей
Когда данные пересылаются со внешнего устройства хранения или на него, от%
дельные биты передаются потоком. Обычно устройство налагает строгие времен%
ные ограничения на пересылку данных. Например, если данные записываются на ленту, лента движется с фиксированной скоростью, и нужно, чтобы данные пере%
давались ей тоже с фиксированной скоростью. Когда источник данных исчерпан,
Файлы или последовательности

Фундаментальные структуры данных
42
движение ленты прекращается, и ее скорость падает быстро, но не мгновенно.
Поэтому на ленте остается промежуток между уже записанными данными и дан%
ными, которые поступят позже. Чтобы добиться высокой плотности данных, нуж%
но, чтобы число промежутков было мало, и для этого данные передают относи%
тельно большими блоками, чтобы не прерывать движения ленты. Похожие требования имеют место при работе с магнитными дисками, где данные размеща%
ются на дорожках с фиксированным числом блоков фиксированного размера. На самом деле диск следует рассматривать как массив блоков, причем каждый блок читается или записывается целиком и обычно содержит
2
k байтов с k = 8, 9, … 12
Однако в наших программах не соблюдается никаких временных ограничений.
Чтобы обеспечить такую возможность, передаваемые данные буферизуются. Они накапливаются в переменной%буфере (в оперативной памяти) и пересылаются, ког%
да накапливается достаточно данных, чтобы собрать блок нужного размера. Клиент буфера имеет к нему доступ только посредством двух процедур deposit и fetch
:
DEFINITION Buffer;
PROCEDURE deposit (x: CHAR);
PROCEDURE fetch (VAR x: CHAR);
END Buffer.
Буферизация обладает тем дополнительным преимуществом, что она позволя%
ет процессу, который порождает/получает данные, выполняться одновременно с устройством, которое пишет/читает данные в/из буфера. На самом деле удобно рассматривать само устройство как процесс, который просто копирует потоки данных. Назначение буфера – в какой%то степени ослабить связь между двумя процессами, которые будем называть производителем (producer) и потребителем
(consumer). Например, если потребитель в какой%то момент замедляет работу, он может нагнать производителя позднее. Без такой развязки часто нельзя обеспе%
чить полноценное использование внешних устройств, но она работает, только если скорость работы производителя и потребителя примерно равны в среднем,
хотя иногда и флуктуируют. Степень развязки растет с ростом размера буфера.
Обратимся теперь к вопросу представле%
ния буфера и для простоты предположим по%
ка, что элементы данных записываются в него
(deposited) и считываются из него (fetched)
индивидуально, а не поблочно. В сущности,
буфер представляет собой очередь, организо%
ванную по принципу «первым пришел – пер%
вым ушел» (first%in%first%out, или fifo). Если он объявлен как массив, то две индексные пере%
менные (скажем, in и out
) отмечают те пози%
ции, куда должны писаться и откуда должны считываться данные. В идеале такой массив должен быть бесконечным. Однако вполне до%
Рис. 1.8. Кольцевой буфер с индексами in и out

43
статочно иметь конечный массив, учитывая, что прочитанные элементы больше не нужны. Занимаемое ими место может быть использовано повторно. Это приво%
дит к идее кольцевого буфера.
Операции записи и считывания элемента реализуются в следующем модуле,
который экспортирует эти операции как процедуры, но скрывает буфер и его ин%
дексные переменные – и тем самым механизм буферизации – от процесса%потреби%
теля. В таком механизме еще нужна переменная n
для подсчета количества элемен%
тов в буфере в данный момент. Если
N
обозначает размер буфера, то очевидным инвариантом является условие
0
≤
n
≤
N
. Поэтому операция считывания (проце%
дура fetch
) должна охраняться условием n
>
0
(буфер не пуст), а операция записи
(процедура deposit
) – условием n
<
N
(буфер не полон). Невыполнение первого условия должно считаться ошибкой программирования, а нарушение второго –
недостатком предложенной реализации (буфер слишком мал).
MODULE Buffer; (* ! *)
CONST N = 1024; (* ! *)
VAR n, in, out: INTEGER;
buf: ARRAY N OF CHAR;
PROCEDURE deposit deposit deposit deposit deposit (x: CHAR);
BEGIN
IF n = N THEN HALT END;
INC(n); buf[in] := x; in := (in + 1) MOD N
END deposit;
PROCEDURE fetch fetch fetch fetch fetch (VAR x: CHAR);
BEGIN
IF n = 0 THEN HALT END;
DEC(n); x := buf[out]; out := (out + 1) MOD N
END fetch;
BEGIN n := 0; in := 0; out := 0
END Buffer.
Столь простая реализация буфера приемлема, только если процедуры deposit и fetch вызываются единственным агентом (действующим то как производитель, то как потребитель). Но если они вызываются независимыми процессами, работаю%
щими одновременно, то такая схема оказывается слишком примитивной. Ведь тог%
да попытку записи в полный буфер или попытку чтения из пустого буфера следует рассматривать как вполне законные. Просто выполнение таких действий должно быть отложено до того момента, когда снова будут выполнены соответствующие
охраны (guarding conditions). В сущности, такие задержки и представляют собой необходимый механизм синхронизации между параллельными (concurrent) про%
цессами. Можно представить эти задержки следующими операторами:
REPEAT UNTIL n < N
REPEAT UNTIL n > 0
которые нужно подставить вместо соответствующих двух условных операторов,
содержащих оператор
HALT
Файлы или последовательности

Фундаментальные структуры данных
44
1.7.3. Буферизация обмена между
параллельными процессами
Однако представленное решение нельзя рекомендовать, даже если известно, что два процесса исполняются двумя независимыми агентами. Причина в том, что два процесса должны обращаться к одной и той же переменной n
и, следовательно,
к одной области оперативной памяти. Ожидающий процесс, постоянно проверяя значение n
, мешает своему партнеру, так как в любой момент времени к памяти может обратиться только один процесс. Такого рода ожиданий следует избегать, и поэтому мы постулируем наличие средства, которое, в сущности, скрывает в себе механизм синхронизации. Будем называть это средство сигналом (signal) и при%
мем, что оно предоставляется в служебном модуле
Signals вместе с набором при%
митивных операций для сигналов.
Каждый сигнал s
связан с охраной (условием)
P
s
. Если процесс нужно приостановить, пока не будет обеспечена истинность
P
s
(другим процессом), то он должен, прежде чем продолжить свою работу, дождаться сигнала s
. Это выража%
ется оператором
Wait(s)
. С другой стороны, если процесс обеспечивает истинность
P
s
, то после этого он сигнализирует об этом оператором
Send(s)
. Если для каждого оператора
Send(s)
обеспечивается истинность предусловия
P
s
, то
P
s можно рас%
сматривать как постусловие для
Wait(s)
DEFINITION Signals;
TYPE Signal;
PROCEDURE Wait (VAR s: Signal);
PROCEDURE Send (VAR s: Signal);
PROCEDURE Init (VAR s: Signal);
END Signals.
Теперь мы можем реализовать буфер в виде следующего модуля, который дол%
жен правильно работать, когда он используется независимыми параллельными процессами:
MODULE Buffer;
IMPORT Signals;
CONST N = 1024; (* ! *)
VAR n, in, out: INTEGER;
nonfull: Signals.Signal; (*n < N*)
nonempty: Signals.Signal; (*n > 0*)
buf: ARRAY N OF CHAR;
PROCEDURE deposit deposit deposit deposit deposit (x: CHAR);
BEGIN
IF n = N THEN Signals.Wait(nonfull) END;
INC(n); buf[in] := x; in := (in + 1) MOD N;
IF n = 1 THEN Signals.Send(nonempty) END
END deposit;

45
PROCEDURE fetch fetch fetch fetch fetch (VAR x: CHAR);
BEGIN
IF n = 0 THEN Signals.Wait(nonempty) END;
DEC(n); x := buf[out]; out := (out + 1) MOD N;
IF n = N–1 THEN Signals.Send(nonfull) END
END fetch;
BEGIN n := 0; in := 0; out := 0; Signals.Init(nonfull); Signals.Init(nonempty)
END Buffer.
Однако нужно сделать еще одну оговорку. Данная схема разрушается, если по случайному совпадению как производитель, так и потребитель (или два произво%
дителя либо два потребителя) одновременно обращаются к переменной n
, чтобы изменить ее значение. Непредсказуемым образом получится либо значение n+1
,
либо n–1
, но не n
. Так что нужно защищать процессы от опасных взаимных помех.
Вообще говоря, все операции, которые изменяют значения общих (shared) пере%
менных, представляют собой потенциальные ловушки.
Достаточным (но не всегда необходимым) условием является требование, что%
бы все общие переменные объявлялись локальными в таком модуле, для проце%
дур которого гарантируется, что они взаимно исключают исполнение друг друга.
Такой модуль называют монитором (monitor) [1.7]. Условие взаимного исключе%
ния (mutual exclusion) гарантирует, что в любой момент времени только один про%
цесс сможет активно выполнять какую%либо процедуру монитора. Если другой процесс попытается вызвать некую процедуру того же монитора, его выполнение будет автоматически задержано до того момента, когда первый процесс завершит выполнение своей процедуры.
Замечание. Слова «активно выполнять» означают, что процесс выполняет лю%
бой оператор, кроме оператора ожидания.
Наконец, вернемся к задаче, в которой производитель или потребитель (или оба) требует, чтобы данные к ним поступали блоками определенного размера.
Показанный ниже модуль является вариантом предыдущего, причем предполага%
ется, что размер блоков данных равен
N
p элементов для производителя и
N
c эле%
ментов для потребителя. В этом случае обычно выбирают размер буфера
N
так,
чтобы он делился на
N
p и
N
c
. Чтобы подчеркнуть симметрию между операциями записи и считывания данных, вместо единственного счетчика n
теперь исполь%
зуются два счетчика, ne и nf
. Они показывают соответственно число пустых и за%
полненных ячеек буфера. Когда потребитель находится в состоянии ожидания, nf показывает число элементов, нужных для продолжения работы потребителя; а когда производитель находится в состоянии ожидания, то ne показывает число элементов, необходимых для продолжения работы производителя. (Поэтому ус%
ловие ne + nf = N
выполняется не всегда.)
MODULE Buffer;
IMPORT Signals;
CONST Np = 16; (* *)
Nc = 128; (* *)
Файлы или последовательности

Фундаментальные структуры данных
46
N = 1024; (* ! , Np Nc*)
VAR ne, nf: INTEGER;
in, out: INTEGER;
nonfull: Signals.Signal; (*ne >= 0*)
nonempty: Signals.Signal; (*nf >= 0*)
buf: ARRAY N OF CHAR;
PROCEDURE deposit deposit deposit deposit deposit (VAR x: ARRAY OF CHAR);
BEGIN
ne := ne – Np;
IF ne < 0 THEN Signals.Wait(nonfull) END;
FOR i := 0 TO Np–1 DO buf[in] := x[i]; INC(in) END;
IF in = N THEN in := 0 END;
nf := nf + Np;
IF nf >= 0 THEN Signals.Send(nonempty) END
END deposit;
PROCEDURE fetch fetch fetch fetch fetch (VAR x: ARRAY OF CHAR);
BEGIN
nf := nf – Nc;
IF nf < 0 THEN Signals.Wait(nonempty) END;
FOR i := 0 TO Nc–1 DO x[i] := buf[out]; INC(out) END;
IF out = N THEN out := 0 END;
ne := ne + Nc;
IF ne >= 0 THEN Signals.Send(nonfull) END
END fetch;
BEGIN
ne := N; nf := 0; in := 0; out := 0;
Signals.Init(nonfull); Signals.Init(nonempty)
END Buffer.
1.7.4. Ввод и вывод текста
Под стандартным вводом и выводом мы понимаем передачу данных в ту или иную сторону между вычислительной системой и внешними агентами, например чело%
веком%оператором. Достаточно типично, что ввод производится с клавиатуры,
а вывод – на экран дисплея. Для таких ситуаций характерно, что информация представляется в форме, понятной человеку, и обычно состоит из последователь%
ности литер. То есть речь идет о тексте. Отсюда еще одно усложнение, характерное для реальных операций ввода и вывода. Кроме передачи данных, в них выполняет%
ся еще и преобразование представления. Например, числа, обычно рассматривае%
мые как неделимые сущности и представленные в двоичном виде, должны быть преобразованы в удобную для чтения десятичную форму. Структуры должны представляться так, чтобы их элементы располагались определенным образом, то есть форматироваться.
Независимо от того, что это за преобразование, задача заметно упрощается,
если снова привлечь понятие последовательности. Решающим является наблюде%

47
ние, что если набор данных можно рассматривать как последовательность литер,
то преобразование последовательности может быть реализовано как последова%
тельность (одинаковых) преобразований элементов:
T(0
, s
1
, ... , s n–1
>) = 0
), T(s
1
), ... , T(s n–1
)>
Исследуем вкратце действия, необходимые для преобразования представле%
ний натуральных чисел для ввода и вывода. Математическим основанием послу%
жит тот факт, что число x
, представленное последовательностью десятичных цифр d = , ... , d1, d0>
, имеет значение x = S
S
S
S
Si: i = 0 .. n–1: d i
* 10
i x = d n–1
× 10
n–1
+ d n–2
× 10
n–2
+ … + d
1
× 10 + d
0
x = (… (d n–1
× 10 + d n–2
)
× 10 + … + d
1
)
× 10 + d
0
Пусть теперь нужно прочесть и преобразовать последовательность d
,
а получившееся числовое значение присвоить переменной x
. Следующий простой алгоритм останавливается при считывании первой литеры, не являющейся циф%
рой (арифметическое переполнение не рассматривается):
x := 0; Read(ch);
(* ADruS174.% '- *)
WHILE ("0" <= ch) & (ch <= "9") DO
x := 10*x + (ORD(ch) – ORD("0")); Read(ch)
END
В случае вывода преобразование усложняется тем, что разложение значения x
в набор десятичных цифр дает их в обратном порядке. Младшая значащая цифра порождается первой при вычислении x MOD 10
. Поэтому требуется промежуточ%
ный буфер в виде очереди типа «первым пришел – последним вышел» (то есть стека). Будем представлять ее массивом d
с индексом i
и получим следующую программу:
i := 0;
(* ADruS174.-'% *)
REPEAT d[i] := x MOD 10; x := x DIV 10; INC(i)
UNTIL x = 0;
REPEAT DEC(i); Write(CHR(d[i] + ORD("0")))
UNTIL i = 0
Замечание. Систематическая замена константы 10 в этих алгоритмах на поло%
жительное целое B даст процедуры преобразования для представления по основа%
нию B. Часто используется случай B = 16 (шестнадцатеричное представление),
тогда соответствующие умножения и деления можно реализовать простыми сдвигами двоичных цифр.
Очевидно, было бы неразумным детально описывать в каждой программе та%
кие часто встречающиеся операции. Поэтому постулируем наличие вспомога%
тельного модуля, который обеспечивает чаще всего встречающиеся, стандартные операции ввода и вывода для чисел и цепочек литер. Этот модуль используется в большинстве программ в этой книге, и мы назовем его
Texts
. В нем определен
Файлы или последовательности

Фундаментальные структуры данных
48
тип
Text
, а также типы объектов%бегунков для чтения (
Reader)
и записи (
Writer
)
в переменные типа
Text
, а также процедуры для чтения и записи литеры, целого числа и цепочки литер.
Прежде чем дать определение модуля
Texts
, подчеркнем существенную асим%
метрию между вводом и выводом текстов. Хотя текст порождается последова%
тельностью вызовов процедур вывода целых и вещественных чисел, цепочек ли%
тер и т. д., ввод текста посредством вызова процедур чтения представляется сомнительной практикой. Дело здесь в том, что хотелось бы читать следующий элемент, не зная его типа, и определять его тип после чтения. Это приводит к поня%
тию сканера (scanner), который после каждой попытки чтения позволяет прове%
рить тип и значение прочитанного элемента. Сканер играет роль бегунка для фай%
лов. Однако тогда нужно наложить ограничения на синтаксическую структуру считываемых текстов. Мы определим сканер для текстов, состоящих из последо%
вательности целых и вещественных чисел, цепочек литер, имен, а также специаль%
ных литер. Синтаксис этих элементов задается следующими правилами так назы%
ваемой расширенной нотации Бэкуса–Наура (EBNF, Extended Backus Naur Form;
чтобы точнее отразить вклад авторов нотации в ее создание, аббревиатуру еще раскрывают как Extended Backus Normal Form, то есть «расширенная нормальная нотация Бэкуса» – прим. перев.):
item =
integer | RealNumber | identifier | string | SpecialChar.
integer =
[
“–”] digit {digit}.
RealNumber = [
“–”] digit {digit} “.” digit {digit} [(“E” | “D”)[“+” |
“–” digit {digit}].
identifier =
letter {letter | digit}.
string =
‘”’ {any character except quote} ‘”’.
SpecialChar =
“!” | “?” | “@” | “#” | “$” | “%” | “^” | “&” | “+” | “–” |
“*” | “/” | “\” | “|” | “(” | “)” | “[” | “]” | “{” | “}” |
“<” | “>” | “.” | “,” | “:” | “;” | “”.
Элементы разделяются пробелами и/или символами конца строк.
DEFINITION Texts;
(* ADruS174_Texts *)
CONST Int = 1; Real = 2; Name = 3; Char = 4;
TYPE Text, Writer;
Reader = RECORD eot: BOOLEAN END;
Scanner = RECORD class: INTEGER;
i: INTEGER;
x: REAL;
s: ARRAY 32 OF CHAR;
ch: CHAR;
nextCh: CHAR
END;
PROCEDURE OpenReader (VAR r: Reader; t: Text; pos: INTEGER);
PROCEDURE OpenWriter (VAR w: Writer; t: Text; pos: INTEGER);
PROCEDURE OpenScanner (VAR s: Scanner; t: Text; pos: INTEGER);
PROCEDURE Read (VAR r: Reader; VAR ch: CHAR);

49
PROCEDURE ReadInt (VAR r: Reader; VAR n: INTEGER);
PROCEDURE Scan (VAR s: Scanner);
PROCEDURE Write (VAR w: Writer; ch: CHAR);
PROCEDURE WriteLn (VAR w: Writer); (* v *)
PROCEDURE WriteString (VAR w: Writer; s: ARRAY OF CHAR);
PROCEDURE WriteInt (VAR w: Writer; x, n: INTEGER); (* x
n .  n v , € ,
*)
PROCEDURE WriteReal (VAR w: Writer; x: REAL);
PROCEDURE Close (VAR w: Writer);
END Texts.
(Выше добавлена отсутствующая в английском оригинале процедура ReadInt, ис%
пользуемая в примерах программ – прим. перев.)
Мы требуем, чтобы после вызова процедуры
Scan(S)
для полей записи
S
выпол%
нялось следующее:
S.class = Int означает, что прочитано целое число, его значение содержится в
S.i
;
S.class = Real означает, что прочитано вещественное число, его значение со%
держится в
S.x
;
S.class = Name означает, что прочитана цепочка литер, она содержится в
S.s
;
S.class = Char означает, что прочитана специальная литера, она содержится в
S.ch
;
S.nextCh содержит литеру, непосредственно следующую за прочитан%
ным элементом, которая может быть пробелом.

1   2   3   4   5   6   7   8   9   ...   22