StackEmpty

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