Понедельник, Июль 5th, 2010

Структуры и алгоритмы обработки данных

Для очереди определены три примитивные операции. Операция insert (q,x) помещает элемент х в конец очереди q. Операция remove(q) удаляет элемент из начала очереди q и присваивает его значение переменной х. Третья операция, empty (q), возвращает значение true или false в зависимости от того, является ли данная очередь пустой или нет. Кроме того. Учитывая то, что полустатическая очередь реализуется на одномерном массиве, необходимо следить за возможностью его переполнения. Сэтой целью вводится опнрация full(q).
Операция insert может быть выполнена всегда, поскольку на количество элементов, которые может содержать очередь, никаких ограничений не накладывается. Операция remove, однако, применима только к непустой очереди, поскольку невозможно удалить элемент из очереди, не содержащей элементов. Результатом попытки удалить элемент из пустой очереди является возникновение исключительной ситуации потеря значимости. Операция empty, разумеется, выполнима всегда.

Пример реализации очереди в виде одномерного массива на Паскале:
const
MaxQ = …
type
E = …
Queue = Array [1..MaxQ] of E;
var
Q: Queue;
F, R: Integer;
{Указатель F указывает на начало очереди. Указатель R указывает на конец очереди.     Если очередь пуста, то F = 1, а R = 0 (То есть R < F – условие пустоты очереди).}

Procedure Insert(I: Integer; var Q: Queue);
begin
Inc(R);
Q[R]:=I;
end;

Function Empty(Q: Queue): Boolean;
begin
If R < F then Empty:=True Else Empty:=False;
end;

Procedure Remove(var I: Integer; Q: Queue);
begin
If Not Empty(Q) then
begin
I:=Q[F];
Inc(F);
end;
end;

Пример работы с очередью с использованием стандартных процедур.
MaxQ = 5

Производим вставку элементов A, B  и C  в очередь.

Insert(q, A);
Insert(q, B);
Insert(q, C);

Убираем элементы A и B из очереди.
Remove(q);
Remove(q);

К сожалению, при подобном представлении очереди, возможно возникновение абсурдной ситуации, при которой очередь является пустой, однако новый элемент разместить в ней нельзя (рассмотрите последовательность операций удаления и вставки, приводящую к такой ситуации). Ясно, что реализация очереди при помощи массива является неприемлемой.
Одним из решений возникшей проблемы может быть модификация операции remove таким образом, что при удалении очередного элемента вся очередь смещается к началу массива. Операция remove (q) может быть в этом случае реализована следующим образом.

X = q[1]
For I =1 to R-1
q[I] =q[I+1]
next I
R =R-1

Переменная F больше не требуется, поскольку первый элемент массива всегда является началом очереди. Пустая очередь представлена очередью, для которой значение R равно нулю.

Страницы: 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84

работа с детьми в школе

Категория: Учебники