реди последнего элемента программа присваивает величинам FRONT и REAR значения, равные 0. В разд. 3.6 очереди будут рассмотрены с точки зрения моделирования.

SUeROUTINE QADO (QUEUE.NiFRONTfREARtVAUUE) INTEGER GUEUE(N> »FRONTtREARiVAl.UE

С ПРОВЕРКА, ПУСТА ЛИ ОЧЕРЕДЬ.

IF ( REAR .NE. О > GOTO 20

С ТОГДА СДОБАВИТЬ ПЕРВЫЙ ЭЛЕМЕНТ)

.10 FROMT = г

REAR = 1 GUEUEHJ s VALUE RETURN

С ПРОВЕРКА, REAf?=N?

20 IF ( REAR .NE, N } GOTO 40

С ТОГДА (УСТАНОВИТЬ ЗНАЧЕНИЕ REAR=0) С

30 BEAR = О

С ПЕРЕДВИНУТЬ REAR.

40 REAR = REAR+1

С ПРОВЕРКА, НЕ ПЕРЕПОЛНИЛАСЬ Ш ОЧЕРЕДЬ.

IF ( REAR .NE. FRONT ) бОТО 60

С ТОГДА С

50 WRlTEfe.lOOO)

аООО FORMAT (1ЧН QUEUE IS FUU

REAR = REAR-i IF { REAR ,EQ, 0 ) REAR s N RETURN

С ИНАЧЕ (ДОБАВИТЬ К REAR) С

£0 QUEUE(REAR) = VALUE

RETURN END ,"

Рис. 2.3.15. Подпрограмма, добавляющая к очереди один элемент. (Текст в операторе

1000: «Очередь полна».)

Деревья

Линейные массивы можно также использовать для компактного представления деревьев определенного вида. Пусть Т - дерево с М вершинами, в котором вершины помечены целыми числами 1,2,... , М. Говорят, что дерево Т рекурсивно помечено (или рекурсивное), если каждая вершина с меткой больше 1 смежна ровно с одной вершиной, у которой метка имеет меньшее значение. На рис. 2.3.17 приведены примеры рекурсивного дерева Ti и нерекурсивного дерева Г.

с с с

10 10DO

SUBROUTINE QDELET (QUEUE.N.FRONT.REAR»VfiLUE INTEGER QUEUE(N)iFRONTiREAR,VALUE

ПРОВЕРКА, ПУСТА ЯИ ОЧЕРЕДЬ.

IF ( REAR ,NEt 0 J GOTO 20

ТОГДА

WRiTEtS.IOOOJ

FORMAT(ISH QUEUE IS ЕНРТГ» RETURN

проверка: остался только один элемент?

IF t FRONT .NE. REAR i GOTO 10 ТОГДА (УСТАНОВИТЬ ПУСТУЮ ОЧЕРЕДЬ)

VALUE = OUEUEVFRONT) REAR = 0 RETURN

УДАЛИТЬ ИЗ ОЧЕРЕДИ ЭЛЕМЕНТ И ПЕРЕДВИНУТЬ-1FR0NT VALUE = ©UEUEiFRONTJ FRONT = FRONT+1

ЕСЛИ FRONT >N, TO УСТАНОВИТЬ FRONTS 1.

IF ( FRONT .GT, N ) FRONT = 1 RETURN С

Рис. 2.8.16. Подпрограмма, удаляющая из очереди один элемент. (Текст в операторе

1000: «Очередь пуста»).

с с с

Рис. 2.3.17. Рекурсивное дерево Ti и нерекурсивное дерево Tg.

На примере линейного массива ДЕРЕВО показано, как компактно можно представить рекурсивное дерево Ti, ДЕРЕВО (/)=./ обозначает, что вершина / смежна вершине J.

123456789 10

TREE

0111245451

Упражнения 2.3

2.3.1. Какие структуры данных вы использовали бы для каждого из следующих множеств данных: (а) план посадочных мест; (б) таблица среднего роста как функции веса, пола и возраста; (в) множество всех подмножеств М элементов; (г) колода карт; (д) множество * людей и отношение X знаком с F; (е) играв шашки; (ж) jt=3,14159... ; (з) организационная иерархия; (и) множество значений одной случайной переменной? Заметьте, что вам может понадобиться хранить кое-какую дополнительную информацию (например, потенциальное применение данных, желаемая точность jt), поэтому не торопитесь с ответом для некоторых множеств данных.

2.3.2. Большие целые. Напишите программу для работы с очень большими целыми числами, т. е. целыми числами, для которых недостаточен размер машинного слова. Более конкретно, вы могли бы попытаться вычислить большое число из ряда Фибоначчи или значение факториала.

L2.3.3. Железнодорожшя станция. Разработайте и реализуйте на вычислительной машине функционирование небольшой сортировочной железнодорожной станции. Поезда будут прибывать в соответствии с некоторым расписанием. Вагоны прибывающих поездов должны быть перераспределены и сформированы в отбывающие поезда, уходящие в различные пункты назначения в соответствии с другим расписанием. Могут прибьшать также пустые вагоны, принадлежащие другим железным дорогам. Последние нужно комплектовать и периодически возвращать владельцам.

2.3.4. Рассмотрите некоторые преимущества и недостатки использования связанных линейных списков в сравнении с последовательными линейными списками. Обратите особое внимание на вопросы объема памяти, добавления, удаления и доступа к элементам списка.

2.3.5. Напишите две подпрограммы, которые будут (а) удалять и (б) добавлять элемент в хорошо упорядоченный массив CSIOO(N). Сравните их скорость и эффективность с подпрограммами DELETE и INSERT для связанных списков.

2.3.6. Напишите подпрограммы, которые будут (а) добавлять элемент в начало связанного списка, (б) добавлять элемент в конец связанного списка и (в) распечатывать содержимое всех ячеек связанного списка.

2.3.7. Перестановки (стеки). Пусть целые 1, 2, 3, 4 прибывают в естественном порядке на вход стека. Рассмотрев все возможные последовательности операций занесения в стек и выборки из стека, определите, какие из 24 возможных перестановок можно получить на выходе. Например, перестановку 2314 можно получить, применив такую последовательность действий: занести 1, занести 2, выбрать 2, занести 3, выбрать 3, выбрать 1, занести 4, выбрать 4.

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

2.3.9. Моделирование (очереди). Напишите программу, моделирующую линию ожидания емкостью в 10 человек, если для обслуживания клиента и удаления его из очереди требуются 2 единицы времени. Вероятность появления одного нового клиента в