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

 

 

 
 

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

 

 

 
 

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

 

 

 
 

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

 

—

 

удалить

 

элемент

 

из

 

множества;

 

 

 

 
 

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)

 

в

 

каждый

 

узел

 

можно

 

попасть

 

из

 

корневого

 

узла

 

за

 

не-

сколько

 

шагов.

 

 

 

 
 

65

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

В

 

современных

 

языках

 

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

 

основное

 

вни-

мание

 

уделяется

 

структурам

 

данных.

 

Управляющие

 

операторы

 

остались

 

почти

 

такими

 

же,

 

какими

 

они

 

были

 

в

 

первых

 

версиях

 

языка

 

ALGOL.

 

Кроме

 

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

 

оператора

 

case

 

и

 

замены

 

оператора

 

goto

,

 

обработка

 

операторов

 

if

,

 

for

 

и

 

процедур

 

вы-

зова

 

претерпела

 

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

 

изменения.

 

Однако

 

структуры

 

данных

 

за

 

это

 

время

 

изменились

 

в

 

зна-

чительной

 

степени.

 

Ранее

 

назначение

 

данных

 

состояло

 

в

 

пред-

ставлении

 

чисел

 

в

 

системе

 

исчисления,

 

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

 

на

 

ЭВМ.

 

Поэтому

 

в

 

первых

 

языках

 

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

 

использова-

лись

 

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

 

и

 

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

 

типы

 

данных,

 

к

 

которым

 

применялась

 

арифметика

 

с

 

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

 

и

 

плавающей

 

точ-

кой.

 

В

 

более

 

развитых

 

языках,

 

кроме

 

числовых

 

данных,

 

вклю-

чались

 

данные,

 

состоящие

 

из

 

строк

 

символов.

 

Кроме

 

того,

 

под

 

одним

 

именем

 

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

 

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

 

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

 

структуры,

 

состоящие

 

из

 

различных

 

типов

 

данных.

 

Программи-

сту

 

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

 

возможность

 

составлять

 

структуры

 

данных

 

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

 

сложности.

 

Поскольку

 

структуры

 

данных

 

становятся

 

все

 

более

 

слож-

ными,

 

это

 

сильно

 

затрудняет

 

процесс

 

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

 

и

 

сопрово-

ждение

 

тех

 

систем,

 

в

 

которых

 

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

 

такие

 

данные.

 

Не-

большие

 

изменения

 

одной

 

структуры

 

данных

 

могут

 

вызвать

 

разлад

 

в

 

работе

 

всей

 

системы

 

и

 

превратить

 

процесс

 

сопровож-

дения

 

в

 

сложную

 

и

 

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

 

задачу.

 

Кроме

 

того,

 

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

 

структуры

 

становятся

 

все

 

более

 

машинно-

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

 

Поэтому

 

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

 

приходится

 

мыс-

лить

 

категориями

 

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

 

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

 

строки),

 

а

 

не

 

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

 

прикладной

 

задачей.

 

Для

 

того

 

чтобы

 

избежать

 

таких

 

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

 

в

 

настоящее

 

время

 

при

 

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

 

больших

 

программных

 

систем

 

ис-

пользуется

 

принцип

 

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

 

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

 

Этот

 

принцип

 

заключается

 

в

 

том,

 

что

 

вся

 

информация

 

о

 

структуре

 

данных

 

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

 

в

 

одном

 

модуле.

 

Доступ

 

к

 

данным

 

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

 

из

 

этого

 

модуля.

 

Таким

 

образом,

 

внесение

 

из-

менения

 

в

 

структуру

 

данных

 

не

 

сопряжено

 

с

 

особыми

 

затруд-