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

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

Этотпринцип заключается в том, что вся информация о структуреданных сосредотачивается в одном модуле. Доступ к даннымосуществляется из этого модуля. Таким образом, внесение изменения в структуру данных не сопряжено с особыми затруднениями, потому что при этом меняется только один модуль. Вязыках высокого уровня имена данных и представление данныхтесно связаны. Если пользователь объявляет стек следующимобразом:declare 1 STACK,2 TOP FIXED,2 ENTRIES(100) FIXED;то в модуле, который производит обращение к стеку, должнабыть известна внутренняя структура последнего, т.е. число имассив с фиксированной точкой.

Принцип информационной локализованности позволяет пользователю не описывать структуру данных в модуле, в котором происходит обращение к данным. Пользователю достаточно знать, что существует некоторая переменная типа 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ЭлементыРис.