Файл: Лекции СД.doc

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Функция 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. Целые типы данных.

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

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

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

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

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

3. 2.3. Символьный тип

Значениями символьного типа являются символы некоторого предопределенного множества. В основном символьный тип данных используется как базовый для построения составного типа «строка символов». В большинстве современных вычислительных машин таким множеством является кодировка ASCII или UNICODE. Множество ASCII состоит из 256 символов, упорядоченных определенным образом, и содержит символы заглавных и строчных букв, цифр и других символов, включая специальные управляющие символы.

Кодировка ASCII не является единственной. Другой схожей кодировкой является EBCDIC (Extended Binary Coded Decimal Interchange Code – расширенный двоично-кодированный десятичный код обмена), применяемый в вычислительных машинах IBM. В EBCDIC код символа также занимает один байт, но с иной кодировкой, чем в ASCII.

Кодировки ASCII и EBCDIC включают в себя буквенные символы только латинского алфавита. Символы национальных алфавитов занимают свободные места в таблицах кодов и, таким образом, одна таблица может поддерживать только один национальный алфавит. Этот недостаток преодолен в кодировке UNICODE, которая в последнее время получила большое распространение.

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

В языке Паскаль используется кодировка ASCII, а стандартным символьным типом данных является тип Char. В памяти переменная типа Char занимает 1 байт. Значениями символьного типа являются множество всех символов кодировки ASCII, включая невидимые символы клавиатуры. Каждому символу присвоен код – целое число типа Byte (0..255), который возвращает функция Ord. Например, Ord(A) = 65; Ord(F) = 70. Стандартная функция Chr(X), возвращающая символ по его коду (аргумент X должен быть байтовым), например, Chr (90) = Z.

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

Табл. 2.3. Специальные коды ASCII.

Операция сравнения является типичной над символьным типом данных. При сравнении коды символов рассматриваются как целые числа без знака. Кодовые таблицы строятся так, что результаты сравнения подчиняются лексикографическим правилам: символы, занимающие в алфавите места с меньшими порядковыми номерами, имеют меньшие коды, чем символы, занимающие места с большими номерами, например, ‘A’  ’Z’ (65 < 90).

4. 2.4. Перечисляемый тип

Язык Паскаль позволяет создавать собственные типы, которые точнее соответствуют объектам решаемой задачи. Предположим, шкала некоторого устройства содержит следующие позиции: off (выключено), low (слабо), medium (средне), high (сильно). Для представления таких позиций можно объявить целочисленную переменную и для обозначения позиций четыре произвольных числа.

Однако в таком случае придется постоянно отслеживать по документации соответствие позиции и принятого для него номера, что усложнит работу с программой и ее дальнейшее сопровождение. Более того, возможно ошибочное присвоение некорректного номера, выход за диапазон или любая другая непредвиденная ситуация. Использование типа-перечисления решает эти проблемы.

Перечисляемый тип – упорядоченный набор идентификаторов, заданный их перечислением. Значение данного типа представляет собой любой идентификатор из этого набора. Перечисляемые типы аналогичны целочисленным, однако набор операций, выполняемых над ними, ограничен: допустимы операции присваивания (:=), равенства (=) и неравенства (<, >, >=, <=). Операции отношений определены потому, что набор значений в объявлении интерпретируется как упорядоченная последовательность.

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

type

< имя типа > = (< идентификатор 1, идентификатор 2,..., идентификатор n >)

Объявление перечисляемого типа для приведенного выше примера:

type

TPosition = (Off, Low, Medium, High);

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