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

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

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

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

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

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

---

---