6.3 Представление очереди

b

_{^-ЕТЗ г(}

R

_^К

|=В1 I I

I

Nil Nil

Рис. 16 Представление очереди в виде линейного списка

Указатель F должен указывать на первый элемент очереди, а R - на последний. Указатель последнего эле­мента очереди должен быть равен NIL (рис. 16). Таким образом для работы с очередью нужны три переменных типа "указатель". Тогда описание:

TYPE ТР = ^ASP;

SP = RECORD INF : CHAR; LINK : TP

END;

VAR F, K, R : TP; CH : CHAR;

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

Операция удаления из очереди полностью эквивалентна операции удаления из стека по указателю F.

K := F;

F := KMJNK;

СН := KMNF;

DISPOSE(K);

Операция добавления в очередь - это добавление после элемента, на который указывает R: NEW (К); - память для нового элемента

KMNF := СН; - информация в новый элемент

KMJNK := NIL; - занести указатель, т.к. этот элемент послед­ ний RELINK := К; - связь с последним элементом

R := К; - указатель на последний элемент

При работе с динамической очередью снимается проблема переполнения очереди.

Проверка на пустую очередь осуществляется сравнением F с NIL.

6.4 Ведение динамических списков с помощью указателей

Динамические списки легко ведутся, если в качестве ссылок использовать переменные типа "указатель". В этом случае снимается проблема переполнения, т.к. теоретически память ЭВМ можно считать неограниченной.

Кроме того, указатели дают возможность повторного использования свободной памяти не только для од­ного списка, но и для нескольких.

Опишем односвязный список.

TYPE ТР = ^ASP; SP = RECORD

INF : CHAR; { INF : T₀ }

LINK : TP END;

VAR NACH, I, J, К : TP С : CHAR;

Обратите внимание: переменной типа SP нет!

Основные операции со списками.

Переход к следующему элементу.

Пусть I - указатель на текущий элемент списка. Тогда

J := I^A.LINK; - указывает на следующий элемент списка.

Поиск нужного элемента с начала списка.

Пусть хотим найти элемент со значением 'А'.

I := NACH;

WHILE (С <> 'A') AND (I <> NIL) DO BEGIN С := IMNF; I := I^A.LINK

END;

IF С <> 'A' THEN { нет элемента }

Сравните с той же операцией при моделировании массивом.

Включение в список после элемента с указателем I.

NEW(J);

JMNF := С;

J^A.LINK := I^A.LINK;

I^A.LINK := J;

Удаление из списка после элемента с указателем I.

J := I^A.LINK;

I^A.LINK := J^A.LINK;

С := JMNF; { убрать, если информацию сохранять не надо }

DISPOSE(J);

Мы выполнили операции включения и удаления после элемента, на который указывает I.

Добавлять перед элементом или удалять сам текущий элемент невозможно, т.к. связь с предыдущим эле­ментом отсутствует.

Однако простой прием позволяет преодолеть эту трудность.

Добавление перед: добавить после элемента с указателем I, а затем поменять местами информационные части добавленного и предыдущего элементов.

NEW(J);

J^A.LINK := I^A.LINK;

I^A.LINK := J;

J^A.INF:= IMNF;

IMNF := C;

Удаление самого элемента: поменять местами следующий и текущий элементы списка, а затем удалить следующий элемент.

J := I^A.LINK; - нашли следующий

С := JMNF; - запомнили следующий (если нужно)

IMNF := С; - заслали в предыдущий

I^A.LINK := J^A.LINK; - сменили связь DISPOSE(J); Операция удаления возможна, когда удаляемый элемент не последний в списке.