Структуры данных и алгоритмы, страница 6

Каждый набор операторов определяет отдельный АТД. Вот примеры операторов, которые можно определить дляабстрактного типа данных SET (Множество).1.2.3.24MAKENULL(A). Эта процедура делает множество А пустым множеством.UNION(A, В, С). Эта процедура имеет два "входных" аргумента, множества А и В, иприсваивает объединение этих множеств "выходному" аргументу — множеству С.SIZE(A). Эта функция имеет аргумент-множество А и возвращает объект целоготипа, равный количеству элементов множества А.ГЛАВА 1. ПОСТРОЕНИЕ И АНАЛИЗ АЛГОРИТМОВТермин реализация АТД подразумевает следующее: перевод в операторы языкапрограммирования объявлений, определяющие переменные этого абстрактного типаданных, плюс процедуры для каждого оператора, выполняемого над объектами АТД.Реализация зависит от структуры данных, представляющих АТД.

Каждая структура данных строится на основе базовых типов данных применяемого языка программирования, используя доступные в этом языке средства структурирования данных.Структуры массивов и записей — два важных средства структурирования данных,возможных в языке Pascal. Например, одной из возможных реализаций переменнойS типа SET может служить массив, содержащий элементы множества S.Одной из основных причин определения двух различных АТД в рамках одной модели является то, что над объектами этих АТД необходимо выполнять различныедействия, т.е.

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

С этой точки зрения язык Pascal неочень подходящий язык для реализации различных АТД, но, с другой стороны,трудно найти иной язык программирования, в котором можно было бы так непосредственно декларировать АТД. Дополнительную информацию о таких языках программирования см. в библиографических примечаниях в конце главы.1.3. Типы данных, структуры данных и абстрактныетипы данныхХотя термины тип данных (или просто тип), структура данных и абстрактный тип данных звучат похоже, но имеют они различный смысл. В языках программирования тип данных переменной обозначает множество значений, которыеможет принимать эта переменная.

Например, переменная булевого (логического) типа может принимать только два значения: значение true (истина) и значение false(ложь) и никакие другие. Набор базовых типов данных отличается в различных языках: в языке Pascal это типы целых (integer) и действительных (real) чисел, булев(boolean) тип и символьный (char) тип. Правила конструирования составных типовданных (на основе базовых типов) также различаются в разных языках программирования: как мы уже упоминали, Pascal легко и быстро строит такие типы.Абстрактный тип данных — это математическая модель плюс различные операторы, определенные в рамках этой модели.

Как уже указывалось, мы можем разрабатывать алгоритм в терминах АТД, но для реализации алгоритма в конкретномязыке программирования необходимо найти способ представления АТД в терминахтипов данных и операторов, поддерживаемых данным языком программирования.Для представления АТД используются структуры данных, которые представляютсобой набор переменных, возможно, различных типов данных, объединенных определенным образом.Базовым строительным блоком структуры данных является ячейка, котораяпредназначена для хранения значения определенного базового или составного типаданных. Структуры данных создаются путем задания имен совокупностям(агрегатам) ячеек и (необязательно) интерпретации значения некоторых ячеек какпредставителей (т.е.

указателей) других ячеек.В качестве простейшего механизма агрегирования ячеек в Pascal и большинстведругих языков программирования можно применять (одномерный) массив, т.е. последовательность ячеек определенного типа. Массив также можно рассматривать какотображение множества индексов (таких как целые числа 1, 2, ..., га) в множествоячеек. Ссылка на ячейку обычно состоит из имени массива и значения из множестваиндексов данного массива. В Pascal множество индексов может быть нечислового ти1.3.

ТИПЫ ДАННЫХ, СТРУКТУРЫ ДАННЫХ И АБСТРАКТНЫЕ ТИПЫ ДАННЫХ 25па, например (север, восток, юг, запад), или интервального типа (как 1..10). Значения всех ячеек массива должны иметь одинаковый тип данных. Объявлениеимя: array[ТипИндекса] of ТипЯчеек;задает имя для последовательности ячеек, тип для элементов множества индексов итип содержимого ячеек.Кстати, Pascal необычайно богат на типы индексов. Многие языки программирования позволяют использовать в качестве индексов только множества последовательных целых чисел. Например, чтобы в языке Fortran в качестве индексов массиваможно было использовать буквы, надо все равно использовать целые индексы, заменяя "А" на 1, "В" на 2, и т.д.Другим общим механизмом агрегирования ячеек в языках программирования является структура записи. Запись (record) можно рассматривать как ячейку, состоящую из нескольких других ячеек (называемых полями), значения в которых могут быть разных типов.

Записи часто группируются в массивы; тип данных определяется совокупностью типов полей записи. Например, в Pascal объявлениеvarгееlist: array[1..4] of recordda ta: real;next: integerendзадает имя reclist (список записей) 4-элементного массива, значениями которого являются записи с двумя полями: data (данные) и next (следующий).Третий метод агрегирования ячеек, который можно найти в Pascal и некоторыхдругих языках программирования, — это файл. Файл, как и одномерный массив,является последовательностью значений определенного типа.

Однако файл не имеетиндексов: его элементы доступны только в том порядке, в каком они были записаныв файл. В отличие от файла, массивы и записи являются структурами с"произвольным доступом", подразумевая под этим, что время доступа к компонентаммассива или записи не зависит от значения индекса массива или указателя поля записи. Достоинство агрегирования с помощью файла (частично компенсирующее описанный недостаток) заключается в том, что файл не имеет ограничения на количество составляющих его элементов и это количество может изменяться во время выполнения программы.Указатели и курсорыВ дополнение к средствам агрегирования ячеек в языках программированияможно использовать указатели и курсоры. Указатель (pointer) — это ячейка, чьезначение указывает на другую ячейку.

При графическом представлении структурыданных в виде схемы тот факт, что ячейка А является указателем на ячейку В, показывается с помощью стрелки от ячейки А к ячейке В.В языке Pascal с помощью следующего объявления можно создать переменнуюуказатель prt, указывающую на ячейку определенного типа, например ТипЯчейки:varprt: Т ТипЯчейкиПостфикс в виде стрелки, направленной вверх, в Pascal используется как операторразыменования, т.е. выражение prtt обозначает значение (типа ТипЯчейки) в ячейке, указанной prt.Курсор (cursor) — это ячейка с целочисленным значением, используемая для указания на массив. В качестве способа указания курсор работает так же, как и указатель, но курсор можно Использовать и в языках (подобных Fortran), которые неимеют явного типа указателя.

Интерпретировав целочисленную ячейку как индексГЛАВА 1. ПОСТРОЕНИЕ И АНАЛИЗ АЛГОРИТМОВное значение для массива, можно эффективно реализовать указания на ячейки массива. К сожалению, этот прием подходит только для ячеек массива и не позволяеторганизовать указание на ячейки, не являющиеся частью массива.В схемах структур данных мы будем рисовать стрелку из ячейки курсора к ячейке, на которую указывает курсор. Иногда мы также будем показывать целое число вячейке курсора, напоминая тем самым, что это не настоящий указатель. Читательможет заметить, что механизм указателя Pascal разрешает ячейкам массива только"быть указанными" с помощью курсора, но не быть истинным указателем. Другиеязыки программирования, подобные PL/I или С, позволяют компонентам массивовбыть истинными указателями и, конечно, "быть указанным" с помощью курсора.

Вотличие от этих языков, в языках Fortran и Algol, где нет типа указателя, можноиспользовать только курсоры.Пример 1.3. На рис. 1.5 показана структура данных, состоящая из двух частей.Она имеет цепочку ячеек, содержащих курсоры для массива reclist (список записей),определенного выше. Назначение поля next (следующий) заключается в указании наследующую запись в массиве reclist. Например, reclist[4].next равно 1, поэтому запись 4 предшествует записи 1. Полагая первой запись 4, в соответствии со значениями поля next получим следующий порядок записей: 4, 1, 3, 2. Отметим, что значение поля next в записи 2, равное 0, указывает на то, что нет следующей записи. Целесообразно принять соглашение, что число 0 будет обозначать нуль-указатель прииспользовании курсоров и указателей.

Но, чтобы не возникали проблемы при реализации этого соглашения, необходимо также условиться, что массивы, на которыеуказывают курсоры, индексируются начиная с 1, а не с 0.header42J•'datanextreclistРис. 1.5. Пример структуры данных'Ячейки в цепочке на рис. 1.5 имеют типtyperecordtype = recordcursor: integer;prt: t recordtypeendНа цепочку можно ссылаться с помощью переменной header (заголовок), имею1щей тип Т recordtype, header указывает на анонимную запись типа recordtype .1Запись анонимна (не имеет имени), так как создается с помощью вызова new(header), гдеheader указывает на вновь создаваемую запись.

В памяти компьютера, конечно, есть адрес, покоторому можно локализовать ячейку с записью.1.3. ТИПЫ ДАННЫХ, СТРУКТУРЫ ДАННЫХ И АБСТРАКТНЫЕ ТИПЫ ДАННЫХ 27Эта запись имеет значение 4 в поле cursor. Мы рассматриваем 4 как индекс массива realist.

Эта запись имеет истинный указатель в поле ptr на другую анонимную запись, которая, в свою очередь, указывает на индекс 4 массива reclist иимеет нуль-указатель в поле prt. П1.4. Время выполнения программВ процессе решения прикладных задач выбор подходящего алгоритма вызываетопределенные трудности. В самом деле, на чем основывать свой выбор, если алгоритм должен удовлетворять следующим противоречащим друг другу требованиям.1.2.Быть простым для понимания, перевода в программный код и отладки.Эффективно использовать компьютерные ресурсы и выполняться по возможности быстро.Если написанная программа должна выполняться только несколько раз, то первоетребование наиболее важно.

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