Динамическая реализация очереди

До сих пор мы рассматривали только статические программные объекты. Этим термином обозначаются объекты, которые порождаются непосредственно перед выполнением программы, существуют в течение всего времени ее выполнения и размер значений которых не изменяется по ходу выполнения программы.

Поскольку статические объекты порождаются до выполнения программы и размер их значений можно выделить еще на этапе трансляции исходного текста программы на языке машины.

Однако использование при программировании только статических объектов может вызвать определенные трудности, особенно с точки зрения получения эффективной машинной программы, а такая эффективность бывает чрезвычайно важной при решении ряда задач. Дело в том, что иногда мы заранее не знаем не только размера значения того или иного программного объекта, но даже и того, будет существовать этот объект или нет. Такого рода программные объекты, которые возникают уже в процессе выполнения программы, называют динамическими объектами.

В языке ПАСКАЛЬ для работы с динамическими объектами предусматривается специальный тип данных — так называемый ссылочный тип. Значением этого типа является ссылка на какой — либо программный объект, по которой осуществляется непосредственный доступ к этому объекту. На машинном языке такая ссылка как раз и представляется указанием места в памяти соответствующего объекта.

В этом случае для описания действий над динамическими объектами каждому такому объекту в программе сопоставляется статическая переменная ссылочного типа — в терминах этих ссылочных переменных и описываются действия над соответствующими динамическими объектами.

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

Наиболее распространенными динамическими структурами являются связанные списки. Очередь представляет собой это частный случай линейного связного списка.

Каждый элемент очереди должен иметь ссылку на следующий за ним элемент, поэтому элемент очереди объявляется как структура с двумя полями — информационное поле и связующее поле. Для реализации операций с очередью также удобно завестие еще два поля указателя: first на начало очереди и last на конец очереди.

const.

QUE_SIZE = 20; // максимальное кол-во элементов в очереди.

type.

// тип Магазин.

TMagazine = Record.

Mag_Num: Integer; // номер магазина.

Mag_Name: string[30]; // наименование магазина.

FIO_Dir: string[30]; // ФИО директора магазина.

Kol_Sotr: Integer; // количество сотрудников.

Dohod: Double; // годовой доход.

end;

// односвязный список.

PNode = ^TNode;

TNode = Record.

Magazine: TMagazine;

next: PNode;

end;

TQueue = record.

first, last: PNode;

count: Integer;

end;

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

Основные операции с динамической очередью:

• · добавление нового элемента в конец очереди
• · удаление элемента из начала очереди
• · проверка отсутствия элементов в очереди
• · проход по очереди от начала к концу

Для создания пустой очереди объявим в программе переменные.

var.

// переменные для работы с очередью.

que: TQueue; // очередь.

mag: TMagazine; // магазин и вызовем функцию инициализации очереди в которой обнулим указатели и счетчик количества элементов:

procedure InitQueue (var que: TQueue);

begin.

que.first := nil;

que.last := nil;

que.count := 0;

end;

Поскольку у нас по условию очередь циклическая то указатель last всегда будет указывать на узел first.

Пустоту очереди будем проверять равенством количества элементов // очередь пуста?

function IsEmpty (que: TQueue): Boolean;

begin.

Result := (que.count = 0);

end;

А заполненность очереди будем проверять равенством количества элементов максимально разрешенному количеству:

// очередь заполнена?

function IsFull (que: TQueue): Boolean;

begin.

Result := (que.count = QUE_SIZE);

end;

Функция добавления элемента в конец очереди принимает два аргумента: ссылку на очередь и добавляемые данные. Выполнение функции состоит из шести шагов:

• 1. запомнить текущий указатель на хвост;
• 2. выделить память для нового элемента с помощью стандартной функции new;
• 3. заполнить поле данных нового элемента данными из переданного аргумента;
• 4. изменить указатель next запомненного узла (бывшего хвоста) таким образом, чтобы он указывал на новый добавленный элемент;
• 5. изменить значение указателя next у нового хвоста на голову очереди first;
• 6. увеличить количество элементов очереди;

// добавление элемента в хвост очереди.

procedure EnQueue (var que: TQueue; new_mag: TMagazine);

var.

new_node, last_node: PNode;

begin.

if IsFull (que) then.

raise EInvalidOperation. Create ('Очередь заполнена.');

last_node := que. last; // запомним последний узел.

New (new_node);

que.last := new_node;

que.last.Magazine := new_mag;

if que. first = nil then.

que.first := que. last;

if last_node nil then.

last_node^.next := que. last;

que.last^.next := que. first; // замыкание на голову).

Inc (que.count);

end;

Функция удаления элемента из головы очереди получает два аргумента: ссылку на очередь и указатель на удаляемые данные. Выполнение функции состоит из четырех шагов:

• 1. запомнить указатель на голову;
• 2. запомнить удаляемые данные в переменную Result для возврата;
• 3. сместить указатель головы на следующий элемент очереди;
• 4. изменить указатель хвоста новую голову;
• 5. изменить значение указателя next у нового хвоста на голову очереди first;
• 6. освободить память удаленной головы
• 7. уменьшить количество элементов;

// удаление элемента из головы очереди.

function DeQueue (var que: TQueue): TMagazine;

var.

new_node: PNode;

begin.

if IsEmpty (que) then.

raise EInvalidOperation. Create ('Очередь пуста!');

new_node := que. first;

Result := new_node^.Magazine; // возврат удаленного.

que.first := new_node^.next;

que.last.next := que. first;

Dispose (new_node);

Dec (que.count);

if que. count = 0 then.

begin.

que.first := nil;

que.last := nil;

end;

end;

Для прохода по очереди от головы до хвоста необходимо:

• 1. ввести вспомогательную ссылочную переменную temp_node: PNode;
• 2. установить ее равной адресу головы: temp _node = que. first
• 3. организовать цикл в теле которого обработать очередной элемент с помощью указателя temp_node, затем перекинуть temp_node на следующий по его ссылке next;
• 4. крутить цикл пока не достигнем конца очереди last у которого указатель next указывает на голову first: temp _node = que. first

Этот алгоритм прохода используется при выводе очереди:

// вывод очереди на экран.

function PrintQueue (que: TQueue): string;

const.

CR = #13#10;

var.

tmp_node: PNode;

i: Integer;

begin.

Result := '';

i := 0;

if not IsEmpty (que) then.

begin.

tmp_node := que. first;

repeat.

Inc (i);

Result := Result.

+ '—- №п/п ' + IntToStr (i) + ' ——————————' + CR.

+ IntToStr (tmp_node^.Magazine.Mag_Num) + CR.

+ tmp_node^.Magazine.Mag_Name + CR.

+ tmp_node^.Magazine.FIO_Dir + CR.

+ IntToStr (tmp_node^.Magazine.Kol_Sotr) + CR.

+ FloatToStrF (tmp_node^.Magazine.Dohod, ffFixed, 10, 2) + CR;

tmp_node := tmp_node^.next;

until tmp_node = que. first;

end;

end;