Структурированные типы данных

СТРУКТУРЫ И АЛГОРИТМЫ ОБРАБОТКИ

ДАННЫХ НА ЭВМ

Утверждено Редакционно-издательским советом
университета в качестве учебного пособия

Магнитогорск

УДК 681.3

Рецензенты:

Начальник отдела АСУ и связи ЗАО «МРК»

И. А. Моисеев

Заведующий кафедрой вычислительной
техники и систем управления ЦПК «Персонал»

А. Н. Бурыкин

Торчинский В.Е.
Файнштейн С.И.

Структуры и алгоритмы обработки данных на ЭВМ: Учебное пособие. Магнитогорск: МГТУ, 2005. 131 с.

ISBN 5-89514-549-3

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

Пособие может быть рекомендовано для студентов специальности «Программное обеспечение вычислительной техники и автоматизированных систем управления» при изучении дисциплины «Структуры и алгоритмы обработки данных на ЭВМ».

УДК 681.3

ISBN 5-89514-549-3 © МГТУ им. Г.И. Носова, 2005

© Торчинский В.Е.,
Файнштейн С.И., 2005

ПРОСТЫЕ ТИПЫ ДАННЫХ

Простой тип данных не обладает внутренней структурой и служит для отображения простых фактов и задания базовых компонент структурированных типов.

Классификация простых типов

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

1.1. Целый тип

Целочисленный тип включает некоторое подмножество целых. Целые типы делят на знаковые и беззнаковые. Если для представления целых чисел в машине используется n разрядов (битов), то диапазон знакового типа составляет от -2^n-1 до 2^n-1-1, а беззнакового – от 0 до 2ⁿ-1.

Считается, что все операции над данными этого типа выполняются точно и соответствуют обычным правилам арифметики. Если результат операции выходит за пределы представимого множества, то ответ будет ошибочным. Например, если X – однобайтовое беззнаковое целое, то результат присваивания X:=250+8 будет равен двум. Такое событие называется переполнением. Компилятор паскаля (в отличие от многих других языков программирования) при включенных соответствующих опциях позволяет отлавливать эту ситуацию и генерировать ошибку времени выполнения.

Следующие арифметические операции считаются стандартными: сложение (+), вычитание (-), умножение (*), целочисленное деление (div) и остаток от деления (mod).

Вещественный тип

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

Логический тип

Два значения логического типа обозначаются идентификаторами True и False. Логические операции – это логическая конъюнкция, дизъюнкция и отрицание. Логическая конъюнкция обозначается через AND, логическая дизъюнкция – OR, а отрицание – через NOT. Операции сравнения дают результат логического типа. Таким образом, результат некоторого сравнения можно присвоить какой-то переменной или же использовать в качестве логического операнда в логическом выражении.

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

Символьный тип включает множество символов PC. Наиболее широко распространено множество символов, принятое в качестве стандартного Международной организацией по стандартизации (ISO), и в частности, его американская версия ASCII (American Standard Code for Information Interchange). Это множество состоит из 95 печатаемых (графических) символов и 33 управляющих, последние используются главным образом при передаче данных и для управления печатающими устройствами. Функции ORD() и CHR() позволяют отображать множество символов на множество целых чисел и наоборот.

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

Любой новый простейший тип определяется простым перечислением входящих в него различных значений. Такой тип называется перечисляемым. Его определение имеет следующий вид:

TYPE T = (c₁,c₂,…,c_n),

где T – идентификатор нового типа, а c₁,c₂,…,c_n – идентификаторы новых констант.

Мощность множества T – card(T) = n.

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

Интервальный тип

Часто приходится сталкиваться с положением, когда переменной присваивается значение некоторого типа, лежащее только внутри определенного интервала значений. Такое положение можно подчеркнуть, определив, что указанная переменная относится к интервальному типу (диапазону). Такой тип задается следующим образом:

TYPE T = <min>..<max>,

где <min> и <max> – выражения, определяющие концы такого диапазона.

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

СТРУКТУРИРОВАННЫЕ ТИПЫ ДАННЫХ

Структурированные типы данных предназначены для конструирования сложных структур данных из конечного набора базисных типов.

Массивы

Массив (функция с конечной областью определения) представляет собой отображение некоторого конечного множества данных на множество данных другого типа. Конечное множество, являющееся областью определения данной функции, называется индексным массивом, а его элементы – индексами. Значение данной функции для некоторого индекса i называется элементом массива, соответствующим i. Множество индексов массива должно быть конечно и обладать возможностью его перечисления, т.е. тип индекса должен быть скалярным. Определение типа массива:

TYPE A = ARRAY[I] OF T₀,

где I – тип индекса; T₀ – тип компонент (базовый тип).

Составное значение массива может задаваться с помощью конструктора массива

CONST A: ARRAY[1..3] OF CHAR = (‘a’,’b’,’c’).

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

Мощность типа массива есть произведение мощностей его компонент. Так как все компоненты типа T относятся к одному базовому типу T₀, то при типе индекса T_I получаем:

card(T) = card(T₀)^card(T_I⁾.