Исключение. Function искл_очередь (var d: тип данных; var q: очередь): boolean;

Function искл_очередь (var d: тип данных; var q: очередь): boolean;

Var x: ссылка;

Begin

if q.l = nil then искл_очередь:= true

else

begin

искл_очередь:= false;

x:= q.l;

with x^ do

begin

d:= данные;

q.l:= связь

end;

dispose (x)

end

End;

Дек – очередь с двумя концами с обоих сторон

2. Кольцевые списки. Многосвязные списки, примеры применения.

Список описывается дескриптором — особой записью, со­держащей имя списка, указатель начала списка (РВ), текущее количество элементов, описание структуры элемента. Для доступа к элементу списка необходим его просмотр «с головы» — каждый раз с начала списка, что может быть медленным. Чтобы устранить этот недостаток, делают кольцевой список, т.е. указатель от последнего элемента направ­ляют на первый элемент. В таком случае просмотр списка можно начинать с любого элемента, а после доступа к нужному элементу в РВ надо занести адрес его последователя.

Характерные черты кольцевого списка:

1.из любого элемента списка можно достичь любого др.эл-та списка

2.цикл.список не имеет 1-го и последнего эл-та.Удобно исп-ть к.-л. Внешний указатель на последний

эл-т l(st), когда след.за ним эл-т становится первым

Циклический список исп-т для организации стека и очереди

1)в стеке указатель lst является ссылкой на последний элемент и явл.вершиной стека

2)для очереди:

Двунаправленный связанный список – это линейный список, в котором каждый элемент содержит два указателя: один указатель указывает на предшествующий элемент, а другой – на последний.

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

Рис. 14 – Двунаправленный связанный линейный список.

Рис. 15 – Двунаправленный циклический список без заголовка.

Внешний указатель

на заголовок

Рис. 16 – Двунаправленный циклический список с заголовком.

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

Используют цикл.списки: СУБД; трансляторы, компиляторы,ОС; мат.задачи, сложение многочлена.

Поиск по сайту: