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

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

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

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

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

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

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

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

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

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

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

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

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. Какие типовые действия над двунаправленными списками должны быть реализованы?


3917618447305379.html
3917645384859271.html
    PR.RU™