4.3 Данные

4.3.1 Обзор структур данных

Любая программа — это формальное описание решения некоторой задачи реального мира. Как часть этого решения конкретные данные тоже должны быть формализованы таким образом, чтобы программа могла проводить вычисления. Для облегчения процесса формализации задачи в языки программирования включены наборы различных типов данных. Но так как ни один разработчик языка не сможет предвидеть всех возможных применений последнего, набор типов данных неизбежно окажется неполным.

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

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

Переменные, объявленные как элементарные типы данного языка, называются скалярными переменными, а переменные, состоящие из наборов существующих типов данных, называются агрегативными переменными. Из агрегативных переменных можно строить новые типы данных, для работы с которыми создаются специальные операторы. Цель наших исследований — понять, по какой концепции строятся абстрактные (определенные пользователем) типы данных из агрегативных структур.

4.3.1.1 Массивы

Массивы — это простейшие агрегативные данные в языках программирования. Массивом называется упорядоченный набор данных одного типа

declare A(10) FIXED BINARY;

Объявлен массив A из десяти двоичных переменных с фиксированной точкой с именами A(1), A(2), A(3),…, A(9), A(10). Аналогично

declare B(5:10) FIXED BINARY;

объявлен массив B из шести элементов с именами B(5), B(6), ..., B(10). Массивы могут быть как одномерными, так и многомерными.

4.3.1.2 Структуры

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

declare 1 X,

2 Y FIXED BINARY,

2 Z BIT(12);

Объявляется структура с именем Х, состоящая из двоичной переменной с фиксированной точкой с именем X.Y и строки длиной 12 бит с именем X.Z.

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

4.3.1.3 Списки

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

Список может быть объявлен как:

declare 1 LIST(N),

2 DATA_ENTRIES TYPE (некоторый тип данных),

SIZE; /* текущий размер списка */

Элементами списка являются DATA_ENTRIES(1), DATA_ENTRIES(2),... , DATA_ENTRIES(SIZE).

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

declare 1 LIST BASED,

2 DATA_ENTRIES TYPE (некоторый тип данных);

2 FPTR POINTER /* указатель следующей записи

в списке */

LIST_HEAD POINTER; /* указатель первого

элемента в списке */

В первом случае элементами списка являются

LIST.DATA_ENTRIES(1),

LIST.DATA_ENTRIES(2),

LIST.DATA_ENTRIES(3),

...

LIST.DATA_ENTRIES(SIZE),

а во втором

LIST_HEAD  DATA_ENTRIES

(LIST_HEAD  FPTR)  DATA_ENTRIES

((LIST_HEAD  FPTR)  FPTR)  DATA_ENTRIES

...

Для работы со списками обычно используются следующие операторы (рис. 4.9, а):

1) ADD — поместить новый элемент в список;

2) DELETE — удалить элемент из списка;

3) SEARCH — проверить наличие элемента в списке.

Рис. 4.9 — Агрегативные структуры и соответствующие им операторы