Удаление указанного элемента из двунаправленного списка

Лекция №1.

Двунаправленный список. Кольцо

 

1. Понятие двунаправленного списка, кольца.

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

Type

<имя типа>=^<имя>;

<имя>=record

<имя_информационной_часпш>:<тип_информац._части>;

<имя_указателя_1>,<имя_указателя_2>:<имя_типа>;

епd;

Например, описание двунаправленного списка, у которого в информационной части (inf) каждого элемента содержится символ, указатель на следующий элемент назван sled, а на предыдущий — рrеd:

type kolco=^k;

k=record

inf:char;

sled, pred:kolco;

end;

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

Добавление элемента в двунаправленный список до указанного

Головной элемент head необходим для исключения повторного обхода.

Создание кольцаначинается с создания головного элемента:

new (head);

head^.sled:=head;

head^.pred:=head;

 

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

young^.pred:=old;

young^.sled:=old^.sled;

old^.sled^.pred:=young;

old^.sled:=young;

 

Вставка “до”:

young^.sled:=old;

young^.pred =old^.pred;

old^.pred ^.sled:=young;

old^.pred:=young.

1.Исходное состояние:

 

2.Выделение памяти под новый элемент: new(p);

3. Занесение информации в новый элемент:

p^.inf:=88;

4.Установка связей между элементами: 4.1. p^.pred:=ukaz^. pred (p^.pred будет указывать на тот элемент, на который указывает ukaz^{^}.pred);

4.2. p^.sled:=ukaz (p^{^}.sled будет указывать на тот элемент, на который указывает ukaz);

4.3. ukaz^.pred^.sled:=p (ukaz^{^}.pred^{^}.sled – это указатель sled элемента, стоящего перед указанным/ будет указывать на тот элемент, на который указывает р);

4.4. ukaz^.pred:=p (ukaz^{^}.pred будет указывать на тот элемент, на который указывает р);

 

 

Добавление элемента в двунаправленный список после указанного

1. Исходное состояние:

 

2. Выделение памяти под новый элемент new(p);

3. Занесение информации в новый элемент:

p^.inf:=88;

4. Установка связей между элементами: 4.1. p^.sled:=ukaz^. sled (p^.sled будет указывать на тот элемент, на который указывает ukaz^{^}.sled);

4.2. p^.pred:=ukaz (p^{^}.pred будет указывать на тот элемент, на который указывает ukaz);

4.3. ukaz^.sled^.pred:=p (ukaz^{^}.sled^{^}.pred – это указатель pred элемента, стоящего перед указанным/ будет указывать на тот элемент, на который указывает р);

ukaz^.sled:=p(ukaz^{^}.sled будет указывать на тот элемент, на который указывает р);

 

Удаление указанного элемента из двунаправленного списка

(на удаляемый элемент указывает Ukaz)

Ukaz^.pred^.sled:=Ukaz^.sled;

Ukaz^.sled^.pred:=Ukaz^.pred;

dispose (Ukaz);

 

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

 

Пример: Функция поиска в списке.

Необходимо найти элемент Res, информационная часть которого содержит значение i1.

 

function poisk (nead:ukaz; i1:integer; var p:ukaz):booleam;

var u:ukaz;

begin

poisk:=false;

res:=nil;

u:=nead;

while (u<>nil) and (p=nil) do

begin

if u^.inf=i1 then begin

poisk:=true;

p:=u

end;

u:=u^.next;

end

end;