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

Лекция №1.

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

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

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

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

Type

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

<имя>=record

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

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

епd;

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

type kolco=^k;

k=record

inf:char;

sled, pred:kolco;

end;

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

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

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

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

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

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

new (head);

head^.sled:=head;

head^.pred:=head;

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

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

young^.pred:=old;

young^.sled:=old^.sled;

old^.sled^.pred:=young;

old^.sled:=young;

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

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

young^.sled:=old;

young^.pred =old^.pred;

old^.pred ^.sled:=young;

old^.pred:=young.

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

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

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

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

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

p^.inf:=88;

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

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

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

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

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

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

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

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

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

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

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

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

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

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

p^.inf:=88;

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

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

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

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

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

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

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

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

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

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

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

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

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;

Наши рекомендации