End
Type
Var
End
Var
reclist: array [1.. 4] of record
data: real;
next: integer
задает имя reclist (список записей) четырехэлементного массива, значениями которого являются записи с двумя полями: data (данные) и next (следующий).
Третий метод агрегирования ячеек, который можно найти в Pascal и некоторых других языках программирования – это файл. Файл, как и одномерный массив, является последовательностью значений определенного типа. Однако файл не имеет индексов: его элементы доступны только в том порядке, в каком они были записаны в файл. В отличие от файла, массивы и записи являются структурами с «произвольным доступом», подразумевая под этим, что время доступа к компонентам массива или записи не зависит от значения индекса массива или указателя поля записи. Достоинство агрегирования с помощью файла (частично компенсирующее описанный недостаток) заключается в том, что файл не имеет ограничения на количество составляющих его элементов и это количество может изменяться во время выполнения программы.
|
|
В дополнение к средствам агрегирования ячеек в языках программирования можно использовать указатели и курсоры. Указатель (pointer) – это ячейка, чье значение указывает на другую ячейку. При графическом представлении структуры данных в виде схемы тот факт, что ячейка А является указателем на ячейку В, показывается с помощью стрелки от ячейки А к ячейке В.
В языке Pascal с помощью следующего объявления можно создать переменную-указатель prt, указывающую на ячейку определенного типа, например ТипЯчейки:
prt: ^ТипЯчейки
Постфикс в виде символа «^», в Pascal используется как оператор разыменования, т.е. выражение prt ^ обозначает значение (типа ТипЯчейки) в ячейке, указанной prt.
Курсор (cursor) – это ячейка с целочисленным значением, используемая для указания на массив. В качестве способа указания курсор работает так же, как и указатель «^», но курсор можно использовать и в языках (подобных Fortran), которые не имеют явного типа указателя. Интерпретировав целочисленную ячейку как индексное значение для массива, можно эффективно реализовать указания на ячейки массива. К сожалению, этот прием подходит только для ячеек массива и не позволяет организовать указание на ячейки, не являющиеся частью массива.
В схемах структур данных принято рисовать стрелку из ячейки курсора к ячейке, на которую указывает курсор. Иногда указывают целое число в ячейке курсора, напоминая тем самым, что это не настоящий указатель. Механизм указателя Pascal разрешает ячейкам массива только "быть указанными" с помощью курсора, но не быть истинным указателем. Другие языки программирования, подобные PL/1 или С, позволяют компонентам массивов быть истинными указателями и, конечно, "быть указанным" с помощью курсора. В отличие от этих языков, в языках Fortran и Algol, где нет типа указателя, можно использовать только курсоры.
|
|
Рисунок 1.3 – Пример составной структуры данных
На рис. 1.3 показана структура данных, состоящая из двух частей. Она имеет цепочку ячеек, содержащих курсоры для массива reclist (список записей), определенного выше. Назначение поля next (следующий) заключается в указании на следующую запись в массиве reclist. Например, reclist [ 4 ] .next равно 1, поэтому запись 4 предшествует записи 1. Полагая первой запись 4, в соответствии со значениями поля next получим следующий порядок записей: 4, 1, 3, 2. Отметим, что значение поля next в записи 2, равное 0, указывает на то, что нет следующей записи. Целесообразно принять соглашение, что число 0 будет обозначать нуль-указатель при использовании курсоров и указателей. Но, чтобы не возникали проблемы при реализации этого соглашения, необходимо также условиться, что массивы, на которые указывают курсоры, индексируются начиная с 1, а не с 0.
Ячейки в цепочке на рис. 1.3 имеют тип
recordtype = record
cursor: integer;
prt: ^recordtype
На цепочку можно ссылаться с помощью переменной header (заголовок), имеющей тип recordtype, header указывает на анонимную запись типа recordtype.
Вообще, тип данных и класс являются синонимами. Класс инкапсулирует (encapsulates) информацию, связывая вместе члены и методы и обращаясь сними как с одним целым. Структура класса скрывает
реализацию деталей и тщательно ограничивает внешний доступ как к дан
ным, так и к операциям. Этот принцип, известный как скрытие информации
(information hiding),защищает целостность данных.
Класс использует свои открытую и закрытую части для контроля за доступом клиентов к данным. Члены внутри закрытой части используются
методами класса и изолированы от внешней среды. Данные обычно определяются в закрытой части класса для предотвращения нежелательного доступа клиента. Открытые члены взаимодействуют с внешней и могут использоваться клиентами.
В приложении доступ клиентов к открытым членам какого-либо объекта
может быть реализован вне этого объекта. Доступом управляют главная про
грамма и подпрограммы (master centrol modules), которые наблюдают за
взаимодействием между объектами. Управляющий код руководит объектом
для доступа к его данным путем использования одного из его методов или
операций. Процесс управления деятельностью объектов называется передачей
сообщений (message passing). Отправитель передает сообщение получающему
объекту и указывает этому объекту выполнить некоторую задачу.
В нужный момент отправитель включает в сообщение информацию, которая используется получателем. Эта информация передается как данные
ввода для операции. После выполнения задачи получатель может возвращать
информацию отправителю (данные вывода) или передавать сообщения другим
объектам, запрашивая выполнение дополнительных задач. Когда получающий объект выполняет операцию, он может обновлять некоторые из его
собственных внутренних значений. В этом случае считается, что происходит
изменение состояния (state change) объекта и возникают новые постусловия.
Абстрактный тип данных (АТД) представляет собой наиболее высокий из возможных уровень описания типов, создаваемых пользователем. В англоязычной литературе он обозначается как Abstract Data Type (ADT).
ADT НаименованиеАбстрактногоТипаДанных
Данные
… перечисление данных, входящих в состав описываемого типа
Операции
Конструктор
Операция …
Операция …
Конец ADT НаименованиеАбстрактногоТипаДанных |
Ниже представлен пример абстрактного типа данных «стек».
ADT Stack
Данные
Список элементов с позицией top, указывающей на вершину стека.
Операции
Конструктор
|
Вход: | Нет |
Предусловия: | Нет |
Процесс: | Проверка, пустой ли стек |
Выход: | Возвращать True, если стек пустой, иначе возвращать False. |
Постусловия: | Нет |
Pop
Вход: | Нет |
Предусловия: | Стек не пустой |
Процесс: | Удаление элемента из вершины стека |
Выход: | Возвращает элемент из вершины стека |
Постусловия: | Элемент удаляется из вершины стека |
Push
Вход: | Элемент для стека |
Предусловия: | Нет |
Процесс: | Сохранение элемента в вершине стека |
Выход: | Нет |
Постусловия: | Стек имеет новый элемент в вершине |
Peek
Вход: | Нет |
Предусловия: | Стек не пустой |
Процесс: | Нахождение значения элемента в вершине стека |
Выход: | Возвращать значение элемента в вершине стека |
Постусловия: | Стек неизменный |
ClearStack
Вход: | Нет |
Предусловия: | Нет |
Процесс: | Удаление всех элементов из стека и переустановка вершины стека |
Выход: | Нет |
Постусловия: | Стек переустановлен в начальные условия |
Конец ADT Stack