На этом шаге мы рассмотрим формирование двунаправленного списка с заглавным звеном..

Для начала заметим, что существует несколько алгоритмов построения двунаправленных списков.

Рассмотрим первый алгоритм формирования двунаправленного списка при помощи схем "до и после" Кнута:

 {Создание заглавного звена} 
 New (pBegin);

Рис.1. Сформируем заглавное звено двунаправленного списка

 pBegin^.pNext := Nil;
 pBegin^.pPrev := Nil;

Рис.2. Определим ссылку заглавного звена двунаправленного списка

 pEnd := pBegin; {Запомним указатель на последнее звено}
 Elem := Random (6);

Рис.3. Определим ссылку на последнее звено двунаправленного списка

 While Elem <> 0 do 
   Begin
    New (pEnd^.pNext);
    pEnd^.pNext^.pPrev := pEnd;

Рис.4. Определим ссылку нового звена двунаправленного списка на предыдущее звено

    pEnd := pEnd^.pNext;

Рис.5. Передвинем ссылку pEnd на новое звено двунаправленного списка

    pEnd^.pNext := Nil;
    pEnd^.Element := Elem;

Рис.6. Определим информационное поле и ссылку на следующий нового звена двунаправленного списка

    Elem := Random (6);
    Write (Elem:4)
   End;

Рассмотрим процедуру на языке Рascal:

 Рrocedure Create_List2 (var pBegin:PtrRec; var pEnd:PtrRec);
    Var  pAux : PtrRec;
         Elem : TyрeElement;
 Begin 
   {Создание заглавного звена} 
    New (pBegin);
    pBegin^.pNext := Nil;
    pBegin^.pPrev := Nil;
   {Определяем ссылку на последнее звено} 
    pEnd := pBegin; 
    Elem := Random (6); Write (Elem:4);
    While Elem <> 0 do 
       Begin
          New (pEnd^.pNext);
          pEnd^.pNext^.pPrev := pEnd;
          pEnd := pEnd^.pNext; 
          pEnd^.pNext := Nil;
          pEnd^.Element := Elem; 
          Elem := Random (6); Write (Elem:4)
       End;
     Writeln
 End;

На следующем шаге мы рассмотрим проход по двунаправленному списку от его начала.

Предыдущий шаг Содержание Следующий шаг