Основы программирования. Указатели. Динамические структуры данных. Абстрактные типы данных. Классы - 25 стр.

UptoLike

Составители:

Рубрика:

должны по-прежнему оставаться указателями на начало и конец списка, а если

список пуст, то получать нулевое значение.

1. Инициализация.

При инициализации список пуст:

first:=nil;

last:=nil;

2. Добавление элемента со значением x в начало.

Осуществляется аналогично добавлению в односвязный список. Если список

был пустым, то last также должен указывать на

добавленный элемент.

first:=NewNode(x,nil,first);

if last=nil then last:=first;

3. Добавление элемента со значением x в конец.

Симметрично добавлению в начало:

last:=NewNode(x,last,nil);

if first=nil then first:=last;

4. Вставка элемента со значением x перед текущим.

Пусть указатель p хранит адрес текущего элемента.

first

last

Создадим новый элемент, поле next которого указывает на текущий, поле prev

– на предыдущий. При этом поле prev текущего элемента и поле next преды-

дущего должны указывать на вставляемый. Если же предыдущего элемента нет,

то осуществляется вставка в начало, и требуется скорректировать указатель на

первый элемент:

t:=NewNode(x,p^.prev,p);

p^.prev:=t;

if p^.prev<>nil then

p^.prev^.next:=t

else first:=t;

first

last

Аналогично производится вставка после текущего элемента.