Файл: Технология раработки програмного обеспечения УП.pdf

66

нениями,

потому

что

при

этом

меняется

только

один

модуль.

В

языках

высокого

уровня

имена

данных

и

представление

данных

тесно

связаны.

Если

пользователь

объявляет

стек

следующим

образом:

declare 

1 STACK, 

          2 TOP FIXED, 
          2 ENTRIES(100) FIXED; 

то

в

модуле,

который

производит

обращение

к

стеку,

должна

быть

известна

внутренняя

структура

последнего,

т.е.

число

и

массив

с

фиксированной

точкой.

Принцип

информационной

ло

-

кализованности

позволяет

пользователю

не

описывать

структу-

ру

данных

в

модуле,

в

котором

происходит

обращение

к

дан-

ным.

Пользователю

достаточно

знать,

что

существует

некоторая

переменная

типа

STACK

,

и

только

в

одном

модуле,

выполняю-

щем

все

операции

со

стеком,

должно

быть

известно

представ-

ление

этого

стека.

Данные

абстрактного

типа

создаются

с

использованием

принципа

информационной

локализованности.

Предполагается,

что

программа

выполняет

все

необходимые

преобразования

данных.

Каждый

модуль

в

системе,

в

которой

описываются

данные,

имеет

вид:

Имя_модуля: module 
  

Описание структуры данных 

  fun1: function 
    

Операторы функции 

  end 
  fun2: function 
    

Операторы функции 

  end 
end 

имя_модуля 

Другие

модули

системы

обращаются

к

этому

модулю

с

помощью

функций

(fun1,

fun2

),

и

только

непосредственно

в

модуле

известна

подробная

структура

данных.

В

практике

программирования

используются

два

способа

программирования.

Первый  способ — по

управлению

(т.е.

вы-

бор

решения

«что

делать

дальше?»).

В

этом

случае

структура

67

программы

понятна,

а

влияние

логики

программы

на

данные

неясно

(рис.

4.10).

Второй способ — модульное

программирова-

ние

(программист

создает

отдельные

модули,

которые

выпол-

няют

определенное

количество

операций).

В

этом

случае

для

обращения

к

модулю

достаточно

его

имени

и

определения

функций,

с

помощью

которых

можно

обращаться

к

этому

мо-

дулю

(рис.

4.11).

Согласно

рисунку,

пользователю

известно,

что

к

переменной типа

STACK

можно

обращаться

с

помощью

функ-

ций

PUSH

,

POP

и

EMPTY

.

Рис.

4.10

—

Структурная

схема

программы

проектирования

по

управлению

Как

реализуется

выполнение

этих

функций

и

какие

струк-

туры

данных

используются

для

создания

стека

пользователю

неизвестно.

Все

обращение

к

стеку

должно

осуществляться

с

помощью

этих

функций,

поэтому

вносить

изменения

в

структу-

ру

данных

довольно

просто.

В

этом

состоит

принцип

проекти-

рования

программ

по

методу

информационной

локализо-ванности.

Начало

MAX

=

0

I

=

1

I

= N

PRINT

MAX 

Конец 

Да 

Нет 

MAX

<

A[I]

Нет 

Да 

MAX

=

A[I]

I

=

I+1

68

Рис.

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

.

В

этом

случае

стек

может

быть

определен

следующим

образом. 

Имя:

STACK

Оператор:

PUSH

Оператор:

POP

Оператор:

EMPTY

TOPOFSTACK: 
FIXED

Код

для: 

PUSH

Код

для: 

POP

Код

для: 

EMPTY

ENTRIES(100): 
BLIPPO

Имя:

BLIPPO

Оператор:

ASSIGN

Оператор:

EQUAL

Оператор:

...

Представление

69

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

известна

структура

переменной.

Основная

сложность

применения

этого

метода

проекти-

рования

программ

заключается

в

том,

что

не

все

языки

про-

граммирования

представляют

возможность

для

создания

таких

конструкций.

Несмотря

на

это,

проектирование

программ

с

абстракт-

ными

типами

данных

эффективно.

Можно

создавать

наборы

данных

и

определять

на

них

функции.

Обращение

к

таким

дан-

ным

происходит

в

модуле,

который

описывает

данные

абст-

рактного

типа.

Хотя

при

переводе

проекта

программы

на

неко-

торый

язык

могут

появиться

ошибки,

хороший

проект

является

предпосылкой

хорошо

написанной

программы.

70

Для

создания

абстрактного

типа

данных

при

проектиро-

вании

язык

программирования

должен

обеспечивать

два

свой-

ства:

−

возможность

формирования

структур

данных

абст-

рактного

вида;

−

возможность

организации

процедур

обращения

к

та-

ким

типам

данных.

В

настоящее

время

(в

зависимости

от

возможностей

язы-

ка)

используются

три

основных

способа

создания

данных

абст-

рактного

типа.

4.3.2.1 Фиксированные типы данных абстрактного типа 

Данный

подход

ориентирован

на

использование

языков,

«плохо»

поддерживающих

сложные

структуры

данных.

При

реализации

такого

подхода

правильность

проектирования

про-

грамм

зависит,

главным

образом,

от

программиста.

Компилятор

не

в

состоянии

найти

ошибки

в

использовании

этих

данных,

так

как

программист

определяет

данные

абстрактного

типа

как

структуру

данных

и

оформляет

каждую

операцию

с

такими

данными

в

виде

отдельной

процедуры;

при

этом

со

структурами

обращаются

как

с

параметрами.

Например,

для

того

чтобы

задать

стек,

программист

дол-

жен

добавить

следующее

объявление

в

каждую

процедуру,

ко-

торая

содержит

обращение

к

стеку.

declare 

1 STACK, 

          2 ENTRIES(100) TYPE(INTEGER), 
          2 TOPOFSTACK TYPE(INTEGER); 

После

этого

программист

должен

написать

процедуры

для

PUSH

,

POP

и

любых

других

функций

над

стеком.

Если

про-

ект

построен

по

такому

способу,

то

его

перевод

на

язык

про-

граммирования

сохранит

структуру

данных

абстрактного

типа.

Достоинство

такого

способа

состоит

в

том,

что

его

можно

ис-

пользовать

для

любого

языка

программирования

(рис.

4.12).