Курсовая работа: Динамические структуры данных. Решение задач. Стек. Очередь. Дек

P: =Sn;

Remove= Sn^. Elem;

Sn: =Sn^. Next;

Dispose;

Тема №3: деки .

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

Дек можно представить в виде звеньев, каждый из которых состоит из трех полей: первое поле – поле элемента, второе – поле ссылки на последующий элемент, третье – поле ссылки на предыдущий. В схеме имеются две ссылки nil , каждая из которых ограничивает движение по деку на его концах. Способ описания используемых типов данных, сравним с очередями, но здесь уже имеются три поля.

Uses CRT ; {описание переменных}

Type typeelem=Integer;

connect=^data;

data=Record

elem: typeelem;

Next: connect;

Pred : connect

End ;

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

Для уменьшения процедур можно использовать вспомогательные процедуры:

Procedure insert1;

{занесение элемента в дек после заданного звена}

var s1, s2, p:connect;

Begin

s1:=sn1;

s2:=sn2;

while s1^.elem<>y do s1:=s1^.next;

while s2^.pred^.elem<>y do s2:=s2^.pred;

new;

p^.elem:=x;

p^.next:=s2;

p^.pred:=s1;