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

ВНИМАНИЕ! Если данный файл нарушает Ваши авторские права, то обязательно сообщите нам.
background image

 

 

 
 

61

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), 
... 


background image

 

 

 
 

62

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

 

 

Агрегативные

 

структуры

 

и

 

соответствующие

 

им

 

операторы

 

а)

 

Список

 


 

add

search

delete

в)

 

Стек

 


 

pus

empty

pop

… 

б)

 

Очередь

 

delete insert

г)

 

Множество

 

delete 

insert

member

д)

 

Дерево

 

delete 

add

search


background image

 

 

 
 

63

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

 

 

удалить

 

элемент

 

из

 

множества;

 


background image

 

 

 
 

64

 

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)

 

в

 

каждый

 

узел

 

можно

 

попасть

 

из

 

корневого

 

узла

 

за

 

не-

сколько

 

шагов.

 


background image

 

 

 
 

65

4.3.2 Абстрактные конструкции 

В

 

современных

 

языках

 

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

 

основное

 

вни-

мание

 

уделяется

 

структурам

 

данных.

 

Управляющие

 

операторы

 

остались

 

почти

 

такими

 

же,

 

какими

 

они

 

были

 

в

 

первых

 

версиях

 

языка

 

ALGOL.

 

Кроме

 

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

 

оператора

 

case

 

и

 

замены

 

оператора

 

goto

,

 

обработка

 

операторов

 

if

,

 

for

 

и

 

процедур

 

вы-

зова

 

претерпела

 

незначительные

 

изменения.

 

Однако

 

структуры

 

данных

 

за

 

это

 

время

 

изменились

 

в

 

зна-

чительной

 

степени.

 

Ранее

 

назначение

 

данных

 

состояло

 

в

 

пред-

ставлении

 

чисел

 

в

 

системе

 

исчисления,

 

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

 

на

 

ЭВМ.

 

Поэтому

 

в

 

первых

 

языках

 

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

 

использова-

лись

 

целочисленные

 

и

 

действительные

 

типы

 

данных,

 

к

 

которым

 

применялась

 

арифметика

 

с

 

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

 

и

 

плавающей

 

точ-

кой.

 

В

 

более

 

развитых

 

языках,

 

кроме

 

числовых

 

данных,

 

вклю-

чались

 

данные,

 

состоящие

 

из

 

строк

 

символов.

 

Кроме

 

того,

 

под

 

одним

 

именем

 

группировались

 

иерархически

 

составленные

 

структуры,

 

состоящие

 

из

 

различных

 

типов

 

данных.

 

Программи-

сту

 

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

 

возможность

 

составлять

 

структуры

 

данных

 

произвольной

 

сложности.

 

Поскольку

 

структуры

 

данных

 

становятся

 

все

 

более

 

слож-

ными,

 

это

 

сильно

 

затрудняет

 

процесс

 

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

 

и

 

сопрово-

ждение

 

тех

 

систем,

 

в

 

которых

 

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

 

такие

 

данные.

 

Не-

большие

 

изменения

 

одной

 

структуры

 

данных

 

могут

 

вызвать

 

разлад

 

в

 

работе

 

всей

 

системы

 

и

 

превратить

 

процесс

 

сопровож-

дения

 

в

 

сложную

 

и

 

дорогостоящую

 

задачу.

 

Кроме

 

того,

 

агрегативные

 

структуры

 

становятся

 

все

 

более

 

машинно-

ориентированными.

 

Поэтому

 

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

 

приходится

 

мыс-

лить

 

категориями

 

(целочисленные,

 

действительные,

 

строки),

 

а

 

не

 

рассматриваемой

 

прикладной

 

задачей.

 

Для

 

того

 

чтобы

 

избежать

 

таких

 

затруднений,

 

в

 

настоящее

 

время

 

при

 

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

 

больших

 

программных

 

систем

 

ис-

пользуется

 

принцип

 

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

 

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

 

Этот

 

принцип

 

заключается

 

в

 

том,

 

что

 

вся

 

информация

 

о

 

структуре

 

данных

 

сосредотачивается

 

в

 

одном

 

модуле.

 

Доступ

 

к

 

данным

 

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

 

из

 

этого

 

модуля.

 

Таким

 

образом,

 

внесение

 

из-

менения

 

в

 

структуру

 

данных

 

не

 

сопряжено

 

с

 

особыми

 

затруд-