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

Реализация очередей.

{Дан член последовательности, который надо исключить и сама последовательность}

procedure Put(a:T;с:pComponent);

var p:pComponent;

begin

new(p);

p^.info:=a;

p^.next:=nil;

c^.next:=p;

с:=p;

end;

procedure Create(b,c:pComponent);

{Указатели на начало и конец очереди}

var p:pComponent;

begin

new(p);

p^.info:=zero; {zero=const – нулевой элемент}

p^.next:=nil;

b:=p;

c:=p;

end;

procedure Get(a:T;var b:pComponent);

{Ссылка на «болванчик»}

var first:pComponent;

{Ссылка на первый элемент}

begin

first:=b^.next; {по моему здесь должно быть b, т.е. first:=b}

a:=first^.info;

b^.next:=first^.next;{b:=first^.next}

dispose(first);

end;

function Empty(b:pComponent):boolean;

begin

empty:=b^.next=nil;

end;

Операции:

1) Конкатенация списка;

2) Вставка компоненты после, до или вместо заданной;

3) Выделение подсписка.

Во всех случаях списки задаются ссылкой на начало и конец.

firsta lasta

¯ ¯

firstb lastb

concat

lasta^.next:=firstb;

Вставка после:

firsta vstavka lasta

¯ ¯ ¯

···

firstb lastb

¯ ¯

lastb^.next:=vstavka^.next;

vstavka^.next:=firstb;

Вставка до:

lastb^.next:=vstavka^.next;

vstavka^.next:=firstb^.next;

x:=vstavka^.info; вставка вместо

vstavka^.info:=firstb^.info;

firstb^.info:=x;

firstb^.next:=lastb^.next;

lastb^.next:=firstb;

Упражнение. Выделение и включение подсписка, если задана ссылка на конец подсписка и

а) голову (первый компонент);

б) стоящий перед ним.

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

Дата добавления: 2014-01-05