Динамические структуры данных: двунаправленные списки

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

Выделим типовые операции:

· добавление звена в начало списка;

· удаление звена из начала списка;

· добавление звена в произвольное место списка, отличное от начала (например, после звена, указатель на которое задан);

· удаление звена из произвольного места списка, отличного от начала (например, после звена, указатель на которое задан);

· проверка, пуст ли список;

· очистка списка;

· печать списка;

· формирование списка.

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

Unit Spisok_2;

Interface

Type BT = LongInt;

U = ^Zveno;

Zveno = Record Inf: BT; N, P: U End;

Procedure V_Nachalo(Var First: U; X: BT);

Procedure Iz_Nachala(Var First: U; Var X: BT);

Procedure V_Spisok(Pred: U; X: BT);

Procedure Iz_Spiska(Pred: U; Var X: BT);

Procedure Ochistka(Var First: U);

Function Pust(First: U): Boolean;

Procedure Print(First: U);

Procedure F(var First: U);

Implementation

Procedure V_Nachalo;

Var Vsp: U;

Begin

New(Vsp);

Vsp^.Inf: = X;

Vsp^.N: = First;

Vsp^.p: = nil;

First: = Vsp;

End;

Procedure Iz_Nachala;

Var Vsp: U;

Begin

Vsp: = First;

First: = First^.N;

First^.P: = nil;

X: = Vsp^.Inf;

Dispose(Vsp);

End;

Procedure V_Spisok;

Var Vsp: U;

Begin

New(Vsp);

Vsp^.Inf: = X;

Vsp^.N: = Pred^.N;

Vsp^.p: = Pred;

Pred^.N: = Vsp;

Pred^.N^.N^.p: = Vsp;

End;

Procedure Iz_Spiska;

Var Vsp: U;

Begin

Vsp: = Pred^.N;

Pred^.N: = Pred^.N^.N;

Vsp^.N^.p: = Pred;

X: = Vsp^.Inf;

Dispose(Vsp);

End;

Procedure Ochistka;

Var Vsp: BT;

Begin

While Not Pust(First) Do Iz_Nachala(First, Vsp)

End;

Function Pust;

Begin

Pust: = First = Nil

End;

Procedure Print;

Var Vsp: U;

Begin

Vsp: = First;

While Vsp < > Nil Do

Begin

Write(Vsp^.Inf: 6);

Vsp: = Vsp^.N

End; WriteLn

End;

Procedure F;

Var V: U; i, n: longint;

Begin

Write ('Введите количество элементов списка: '); readln(n);

New(First);

First^.N: = Nil;

First^.p: = Nil;

write ('введите элемент списка: '); readln(First^.Inf);

V: =First;

For i: = 2 To n Do

Begin

New(V^.N);

V^.N^.p: = V;

V: =V^.N;

V^.N: =Nil;

write ('введите элемент списка: '); readln(v^.Inf);

End

End;

Begin

End.

Пример. Определить в двунаправленном списке количество элементов, у которых соседи справа и слева отрицательны.

program u4_4_7;

uses spisok_2;

function solution(L: U): word;

var v: word; var W: U;

begin

W: =L^.N; v: =0;

while W^.N < > nil do

begin

if (W^.p^.inf < 0) and (W^.N^.inf < 0)

then v: = v+1;

W: = W^.N

end;

solution: = v;

end;

var L: U;

begin

F(L);

print(L);

writeln(solution(L))

end.

Контрольные вопросы и задания

1. Чем отличаются однонаправленный и двунаправленный списки?

2. Могут ли двунаправленные списки быть кольцевыми?

3. Что в языке Pascal обозначает константа Nil (в языке C константа NULL)?

4. Какие типовые действия над двунаправленными списками должны быть реализованы?