1. Контрольные вопросы

1. Дайте определение понятию структура данных.

2. В чем заключается защита типов данных?

3. Какие выделяют виды запоминающих устройств?

4. Приведите классификацию структур данных.

5. Опишите общие операции над структурами данных.

6. Приведите определение понятию порядок алгоритма.

7. В чем заключается идея прямого и обратного проектирования?

2. 2. Простые структуры данных

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

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

Рис. 2.1. Структура простых типов языка Паскаль.

1. 2.1. Порядковые типы

Порядковые типы имеют конечное (счетное) множество значений, с каждым из которых соотносится целое число – порядок. Значения порядковых типов упорядочены (расположены) по возрастанию или убыванию. В табл. 2.1 приведены функции, применимые к любому порядковому типу. Для всех функций тип аргумента должен быть порядковым.

Для функций High и Low аргументом может быть переменная порядкового типа, типа-массива, типа-строки. Результат функции для величины порядкового типа – максимальное (минимальное) значение этой величины, типа-массива – максимальное (минимальное) значение индекса, типа-строки – объявленный размер строки (ноль для функции Low).

Табл. 2.1. Функции для величин порядкового типа.

Функция	Определение	Тип результата
Hi	Получение максимального значения величины.	Целый
Lo	Получение минимального значения величины.	Целый
Odd	Проверка на нечетность.	Булевый
Ord	Порядковый номер.	Целый
Pred	Предшествующее значение.	Совпадает с аргументом
Succ	Последующее значение.	Совпадает с аргументом

Функция Odd возвращает True для нечетного аргумента и False для четного.

Функция Ord преобразует любой порядковый тип в целый тип. Например, если x – переменная целого типа, то Ord(x) = x. Для символьного типа в соответствии со стандартом ASCII:

Ord(B) = 66, Pred(B) = A, Succ(B) = C

Для порядковых типов справедливы соотношения:

Ord(Pred(X)) = Ord(X)–1

Ord(Succ(X)) = Ord(X)+1

2. 2.2. Целочисленный тип

С помощью целочисленного типа может быть представлено количество объектов, являющихся дискретными по своей природе. В языке Паскаль существуют два базовых типа для работы с целочисленными значениями: Integer и Cardinal. Подтипы базовых типов включают также ShortInt, SmallInt, LongInt, Int64, Byte, Word и LongWord. В табл. 2.2 перечислены диапазон значений и формат хранения (представление) в памяти для каждого из них.

Табл. 2.2. Целые типы данных.

Тип	Диапазон значений	Представление
Int64	-263..263–1	знаковый 64-битный
Integer	-2147483648..2147483647	знаковый 32-битный
LongInt	-2147483648..2147483647	знаковый 32-битный
Cardinal	0..4294967295	беззнаковый 32-битный
SmallInt	-32768..32767	знаковый 16-битный
ShortInt	-128..127	знаковый 8-битный
Byte	0..255	беззнаковый 8-битный
Word	0..65535	беззнаковый 16-битный
LongWord	0..4294967295	беззнаковый 32-битный

К целочисленным операциям относятся четыре основных арифметических действия (сложение, вычитание, умножение и деление) для которых применимы математические правила старшинства операций. Для изменения порядка вычислений используются круглые скобки. Их можно использовать для составления выражений:

Результат операции над целыми числами не должен выходить за диапазон допустимых значений. В некоторых компиляторах можно задать режим проверки на переполнение каждой целочисленной операции, но это может привести к большим издержкам во время выполнения, если только данная проверка не производится аппаратными средствами.

В математике в результате деления двух целых чисел a/b получается два значения: частное q и остаток r, такие что:

В языке Паскаль для получения частного используется оператор деления «/». Для целочисленного деления используется операция div, а для получения остатка – операция mod, которая может быть представлена через div:

Следует помнить, что арифметические операции для типа LongInt выполняются более чем вдвое дольше, нежели для типа Integer. Причина заключается в необходимости привлечения дополнительных команд для распространения переноса, возникающего из слова (двух байт) младших разрядов в слово старших разрядов.