Калайда В.Т., Романенко В.В. Технология разработки программного обеспечения (2007), страница 10

число имассив с фиксированной точкой. Принцип информационной локализованности позволяет пользователю не описывать структуру данных в модуле, в котором происходит обращение к данным. Пользователю достаточно знать, что существует некоторая переменная типа STACK, и только в одном модуле, выполняющем все операции со стеком, должно быть известно представление этого стека.64Данные абстрактного типа создаются с использованиемпринципа информационной локализованности. Предполагается,что программа выполняет все необходимые преобразованияданных.

Каждый модуль в системе, в которой описываютсяданные, имеет вид:Имя_модуля: moduleОписание структуры данныхfun1: functionОператоры функцииendfun2: functionОператоры функцииendend имя_модуляДругие модули системы обращаются к этому модулю спомощью функций (fun1, fun2), и только непосредственно вмодуле известна подробная структура данных.В практике программирования используются два способапрограммирования. Первый способ — по управлению (т.е. выбор решения «что делать дальше?»). В этом случае структурапрограммы понятна, а влияние логики программы на данныенеясно (рис.

4.10). Второй способ — модульное программирование (программист создает отдельные модули, которые выполняют определенное количество операций). В этом случае для обращения к модулю достаточно его имени и определения функций, с помощью которых можно обращаться к этому модулю(рис. 4.11). Согласно рисунку, пользователю известно, что кпеременной типа STACK можно обращаться с помощью функций PUSH, POP и EMPTY.65НачалоMAX = 0I=1ДаPRINT MAXНетI=NНетMAX < A[I]КонецДаMAX = A[I]I = I+1Рис.

4.10 — Структурная схема программы проектированияпо управлениюКак реализуется выполнение этих функций и какие структуры данных используются для создания стека пользователюнеизвестно. Все обращение к стеку должно осуществляться спомощью этих функций, поэтому вносить изменения в структуру данных довольно просто. В этом состоит принцип проектирования программ по методу информационной локализованности.66TOPOFSTACK:FIXEDИмя: STACKОператор: PUSHОператор: POPОператор: EMPTYПредставлениеENTRIES(100):BLIPPOКод для:PUSHКод для:POPИмя: BLIPPOОператор: ASSIGNОператор: EQUALОператор: ...Код для:EMPTYРис. 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. В этом случае стек можетбыть определен следующим образом.67declare 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 известна структура переменной.Основная сложность применения этого метода проектирования программ заключается в том, что не все языки программирования представляют возможность для создания такихконструкций.Несмотря на это, проектирование программ с абстрактными типами данных эффективно.

Можно создавать наборы данных и определять на них функции. Обращение к таким даннымпроисходит в модуле, который описывает данные абстрактного68типа. Хотя при переводе проекта программы на некоторый языкмогут появиться ошибки, хороший проект является предпосылкой хорошо написанной программы.Для создания абстрактного типа данных при проектировании язык программирования должен обеспечивать два свойства: возможность формирования структур данных абстрактного вида; возможность организации процедур обращения к таким типам данных.В настоящее время (в зависимости от возможностей языка) используются три основных способа создания данных абстрактного типа.4.3.2.1 Фиксированные типы данных абстрактного типаДанный подход ориентирован на использование языков,«плохо» поддерживающих сложные структуры данных.

При реализации такого подхода правильность проектирования программ зависит, главным образом, от программиста. Компиляторне в состоянии найти ошибки в использовании этих данных, таккак программист определяет данные абстрактного типа какструктуру данных и оформляет каждую операцию с такимиданными в виде отдельной процедуры; при этом со структурами обращаются как с параметрами.Например, для того чтобы задать стек, программист должен добавить следующее объявление в каждую процедуру, которая содержит обращение к стеку.declare 1 STACK,2 ENTRIES(100) TYPE(INTEGER),2 TOPOFSTACK TYPE(INTEGER);После этого программист должен написать процедурыдля PUSH, POP и любых других функций над стеком. Еслипроект построен по такому способу, то его перевод на языкпрограммирования сохранит структуру данных абстрактноготипа.

Достоинство такого способа состоит в том, что его можноиспользовать для любого языка программирования (рис. 4.12).69Модуль, использующий данные123456…TOPOFSTACK…TOPOFSTACK123456Модуль, определяющий данные100100ЭлементыЭлементыРис. 4.12 — Фиксированные данные абстрактного типаОднако такая организация данных имеет существенныенедостатки, так как компоненты любой структуры видны вовсех процедурах, которые используют эти структуры. Программист должен изменять структуры осторожно с помощью определенных операторов и не вводить кажущиеся «безвредными»операторы для непосредственного обращения к данным.

Используемый тип оператора может вызвать неприятности, если каждаякомпонента не будет заменена соответствующим образом.Несмотря на отмеченные недостатки, данный способ может оказаться единственно возможным для некоторых языковпрограммирования.4.3.2.2 Размещение указателейИспользуя переменные типа указатель, можно построитьконструкцию, близкую к фиксированным данным абстрактноготипа. Предполагается, что указатель указывает на область памяти, а формат этой памяти определяется с помощью базированных переменных абстрактного типа. Используя данные абстрактного типа, пользователь определяет данные как переменную — указатель и вызывает процедуру для размещения данных и обращения к этой структуре.

Для стека это может быть ввиде:70declare STACK POINTER;call STACK_INITIALIZATION(STACK);В этом случае процедура STACK_INITIALIZATIONдолжна быть вызвана явным образом для того, чтобыразместить стек в памяти (рис. 4.13).Процедура STACK_INITIALIZATION должна иметь следующую структуру:STACK_INITIALIZATION: procedure(X);declare X POINTER;declare 1 STACK BASED(X),/* X – указывает на стек */2 ENTRIES(100) FIXED,2 TOPOFSTACK FIXED;ALLOCATE STACK SET(X);TOPOFSTACK = 0;end;Модуль, использующий данныеTOPOFSTACK123456…STACKМодуль, определяющий данные100ЭлементыРис. 4.13 — Размещение указателей71Только в этой процедуре известна структура данных, накоторые ссылается указатель STACK, поэтому довольно сложноизменить эту структуру за пределами процедуры.Для того чтобы определить функции обращения к стеку,можно использовать операторы ENTRY.

Таким образом, всяконструкция STACK в целом имеет следующий вид:STACK: procedure;declare X POINTER;declare 1 STACK BASED(X);2 ENTRIES(100) FIXED,2 TOPOFSTACK FIXED;/* разместить стек */STACK_INITIALIZATION: ENTRY(X);.../* поместить элемент в стек */PUSH: procedure(X, элемент);...return;/* извлечь элемент из стека */POP: procedure(X, элемент);...return;...end;Рассмотренный способ удовлетворяет основным предъявляемым требованиям: имена структур и их представления разъединены, все операции со стеком сосредоточены внутри однойпроцедуры (только из этой процедуры можно обращаться к данным). Однако данному способу присущ тот же недостаток, что72и первому.

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

Для определения данных этого типа добавляетсяатрибут ENVIRONMENT (среда, окружение).declare X ENVIRONMENT(STACK);Для пользователя Х — это стек, к которому можно обращаться из процедуры STACK (например, с помощью функцийPOP, PUSH, EMPTY) аналогично тому, как если бы Х было действительное число и им можно было бы оперировать, используяоперации сложения или умножения. Пользователь не знает, каксоставлен стек, и не имеет доступа к его внутренней структуретак же, как и большинство программистов находятся в неведении относительно того, каким образом величина с плавающейточкой записывается в память ЭВМ. Стек объявляется компилятором как переменная-указатель, но при этом накладываютсядополнительные ограничения:1) обработка стека Х происходит в процедуре FUNCTIONв модуле с именем STACK;2) описание стека Х может находиться только в оператореREP (представление для переменной) в модуле STACK;3) любые другие обращения к стеку Х запрещены.С точки зрения пользователя, данные абстрактного типане должны отличаться от других переменных в программе.