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

Type

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

 

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

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

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

<имя>=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 будет указывать на тот элемент, на который указывает р);