4.3.1.4 Очереди
Очередь — это упорядоченный список, в один конец которого элементы добавляются, а из другого изымаются (рис. 4.9, б). Очередь называют списком FIFO — Fist In, Fist Out (поступивший первым обслуживается первым). Очередь может быть организована любым из рассмотренных выше способов, однако второй способ (использование указателей) более эффективен. Для обслуживания очереди необходимы две операции:
1) INSERT — добавить элемент в очередь;
2) DELETE — удалить элемент из очереди.
4.3.1.5 Стеки
Стек — это упорядоченный список, в один конец которого элементы добавляются и изымаются из этого же конца. Стек называют списком LIFO — Last In, Fist Out (поступивший последним обслуживается первым). Аналогично очереди, стек может быть организован любым из рассмотренных выше способов, однако использование массивов более эффективно. Для работы со стеком обычно используются три операции (рис. 4.9, в).
1) PUSH — поместить элемент в стек;
2) POP — извлечь элемент из стека;
3) EMPTY — функция, принимающая значение ИСТИННО, если стек не заполнен.
4.3.1.6 Множества
Множества — это совокупность переменных одного типа. Множество аналогично списку, за исключением того, что порядок расположения элементов не имеет значения. Множества обычно организуются как списки с помощью любого из двух способов.
Множества обрабатываются с использованием следующих операторов (рис. 4.9, г):
1) INSERT — добавить новый элемент во множество;
2) DELETE — удалить элемент из множества;
3) MEMBER — функция, которая принимает значение ИСТИННО, если данная переменная находится во множестве.
4.3.1.7 Графы
Направленный граф — это структура, состоящая из узлов и дуг, причем каждая дуга направлена от одного узла к другому. Графы обычно организовываются с помощью базированных переменных, где дуги являются переменными типа указатель. Если из каждого узла выходит несколько дуг, то граф можно описать следующим образом:
declare 1 GRAPH BASED,
2 DATA_ENTPIES TYPE (некоторый тип данных),
2 EDGES(N) POINTER;
Для ненаправленных графов дугам соответствуют два направления — вперед и назад:
declare 1 GRAPH BASED,
2 DATA_ENTPIES TYPE (некоторый тип данных),
2 FORWARD_EDGES(N) POINTER,
2 BACKWARD_EDGES(N) POINTER;
Операторы для работы с графами представлены на рис. 4.9, д.
4.3.1.8 Деревья
Дерево — это направленный граф, обладающий следующими свойствами:
1) только один узел не имеет дуг, входящих в него (корневой узел);
2) в каждый узел входит не более одной дуги;
3) в каждый узел можно попасть из корневого узла за несколько шагов.
4.3.2 Абстрактные конструкции
В современных языках программирования основное внимание уделяется структурам данных. Управляющие операторы остались почти такими же, какими они были в первых версиях языка ALGOL. Кроме использования оператора case и замены оператора goto, обработка операторов if, for и процедур вызова претерпела незначительные изменения.
Однако структуры данных за это время изменились в значительной степени. Ранее назначение данных состояло в представлении чисел в системе исчисления, ориентированной на ЭВМ. Поэтому в первых языках программирования использовались целочисленные и действительные типы данных, к которым применялась арифметика с фиксированной и плавающей точкой.
В более развитых языках, кроме числовых данных, включались данные, состоящие из строк символов. Кроме того, под одним именем группировались иерархически составленные структуры, состоящие из различных типов данных. Программисту представлялась возможность составлять структуры данных произвольной сложности.
Поскольку структуры данных становятся все более сложными, это сильно затрудняет процесс тестирования и сопровождение тех систем, в которых используются такие данные. Небольшие изменения одной структуры данных могут вызвать разлад в работе всей системы и превратить процесс сопровождения в сложную и дорогостоящую задачу. Кроме того, агрегативные структуры становятся все более машинно-ориентированными. Поэтому программисту приходится мыслить категориями (целочисленные, действительные, строки), а не рассматриваемой прикладной задачей.
Для того чтобы избежать таких затруднений, в настоящее время при проектировании больших программных систем используется принцип информационной локализованности. Этот принцип заключается в том, что вся информация о структуре данных сосредотачивается в одном модуле. Доступ к данным осуществляется из этого модуля. Таким образом, внесение изменения в структуру данных не сопряжено с особыми затруднениями, потому что при этом меняется только один модуль. В языках высокого уровня имена данных и представление данных тесно связаны. Если пользователь объявляет стек следующим образом:
declare 1 STACK,
2 TOP FIXED,
2 ENTRIES(100) FIXED;
то в модуле, который производит обращение к стеку, должна быть известна внутренняя структура последнего, т.е. число и массив с фиксированной точкой. Принцип информационной локализованности позволяет пользователю не описывать структуру данных в модуле, в котором происходит обращение к данным. Пользователю достаточно знать, что существует некоторая переменная типа STACK, и только в одном модуле, выполняющем все операции со стеком, должно быть известно представление этого стека.
Данные абстрактного типа создаются с использованием принципа информационной локализованности. Предполагается, что программа выполняет все необходимые преобразования данных. Каждый модуль в системе, в которой описываются данные, имеет вид:
Имя_модуля: module
Описание структуры данных
fun1: function
Операторы функции
end
fun2: function
Операторы функции
end
end имя_модуля
Другие модули системы обращаются к этому модулю с помощью функций (fun1, fun2), и только непосредственно в модуле известна подробная структура данных.
В практике программирования используются два способа программирования. Первый способ — по управлению (т.е. выбор решения «что делать дальше?»). В этом случае структура программы понятна, а влияние логики программы на данные неясно (рис. 4.10). Второй способ — модульное программирование (программист создает отдельные модули, которые выполняют определенное количество операций). В этом случае для обращения к модулю достаточно его имени и определения функций, с помощью которых можно обращаться к этому модулю (рис. 4.11). Согласно рисунку, пользователю известно, что к переменной типа STACK можно обращаться с помощью функций PUSH, POP и EMPTY.
Рис. 4.10 — Структурная схема программы проектирования по управлению
Как реализуется выполнение этих функций и какие структуры данных используются для создания стека пользователю неизвестно. Все обращение к стеку должно осуществляться с помощью этих функций, поэтому вносить изменения в структуру данных довольно просто. В этом состоит принцип проектирования программ по методу информационной локализо-ванности.
Рис. 4.11 — Стек
Разработчик при создании данных абстрактного типа свободен в выборе типа организации данных. Например, стек можно представить как массив и число, указывающее номер верхнего элемента в стеке.
declare 1 STACK,
2 ENTRIES(100) TYPE(INTEGER),
2 TOPOFSTACK TYPE(INTEGER);
Для того чтобы объявить стек с именем PARSER_STACK, пользователь должен написать:
declare PARSER_STACK TYPE(STACK);
При этом пользователю известно, что к модулю PARSER_STACK можно обращаться с помощью функций PUSH, POP и EMPTY. Как реализуется выполнение этих функций и какие структуры данных используются для создания стека пользователю неизвестно. Например, массив в стеке может быть данными абстрактного типа BLIPPO. В этом случае стек может быть определен следующим образом.
declare 1 STACK,
2 ENTRIES(100) TYPE(BLIPPO),
2 TOPOFSTACK TYPE(INTEGER);
Каждый раз, когда функции PUSH, POP или EMPTY производят обращение к стеку, последний вызывает функцию, которая обращается к модулю BLIPPO. В качестве примера можно рассмотреть следующую программу.
PUSH: function(STACK, ITEM);
declare 1 STACK,
2 ENTRIES(100) TYPE(BLIPPO),
2 TOPOFSTACK TYPE(INTEGER);
declare ITEM TYPE(BLIPPO);
if TOP < 100 then TOP = TOP + 1;
else call ERROR(‘переполнение стека’);
call BLIPPO_ASSING(ENTRIES(TOP), ITEM);
/* ENTRIES(TOP) = ITEM */
return;
end PUSH;
Таким образом, для получения переменной ITEM типа BLIPPO и загрузки ее в массив, образующий стек, требуется обращение к модулю BLIPPO_ASSING. Функция PUSH не может выполнить эту функцию непосредственно, потому что только в BLIPPO_ASSING известна структура переменной.
Основная сложность применения этого метода проектирования программ заключается в том, что не все языки программирования представляют возможность для создания таких конструкций.
Несмотря на это, проектирование программ с абстрактными типами данных эффективно. Можно создавать наборы данных и определять на них функции. Обращение к таким данным происходит в модуле, который описывает данные абстрактного типа. Хотя при переводе проекта программы на некоторый язык могут появиться ошибки, хороший проект является предпосылкой хорошо написанной программы.
Для создания абстрактного типа данных при проектировании язык программирования должен обеспечивать два свойства:
возможность формирования структур данных абстрактного вида;
возможность организации процедур обращения к таким типам данных.
В настоящее время (в зависимости от возможностей языка) используются три основных способа создания данных абстрактного типа.