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
И запись, и массив обеспечивают
произвольный доступ к своим компонентам.
Запись является более общей в том смысле, что ее составляющие типы могут быть разными. Массив, в свою очередь, допускает б
ольшую гибкость в том отношении,
что селекторы компонент могут вычисляться (задаваться выражениями), тогда как селекторы компонент записи суть идентификаторы полей, объявленные в определении типа записи.
Скачать 2.67 Mb.