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

    Список можно формировать путем постоянной вставки нового элемента после заглавного звена. Такой способ позволит получить список с обратным порядком расположения элементов. При помощи диаграмм "до и после" Д.Кнута рассмотрим формирование однонаправленного списка с изменением порядка поступающих элементов.

    1 шаг. Отведем место для переменных рBegin и рAux в статической области:

 Var 
      рBegin, рAux : PtrRec; 

Рис.1. Определение места для pBegin и pAux в статической области

    2 шаг. В динамической области памяти резервируем место для динамического объекта pBegin и определяем ссылку заглавного звена:

   New  (pBegin);
   pBegin^.pNext := Nil ;
   WriteLn ('Первый элемент ');  
   ReadLn  (Elem1);  

Рис.2. Определение места для значения, на которое будет ссылаться pBegin

    3 шаг. В куче резервируем место для динамического объекта pAux, определяем информационное поле и его ссылку:

   New (pAux); 
   pAux^.Element := Elem1; 
   pAux^.pNext := Nil;

Рис.3. Определение места для объекта pAux

    4 шаг. Определим место нового компонента в списке:

  pAux^.pNext := pBegin^.pNext; 
  pBegin^.pNext := pAux;

Рис.4. Определение места нового компонента в списке

  WriteLn ('Следующий элемент ');
  ReadLn (Elem);

    5 шаг. В куче резервируем место для динамического объекта pAux, определяем информационное поле и его ссылку:

  New (pAux); 
  pAux^.Element := Elem2; 
  pAux^.pNext := Nil;

Рис.5. Определение места для объекта pAux

    6 шаг. Определим место нового компонента в списке:

 pAux^.pNext := pBegin^.pNext; 
 pBegin^.pNext := pAux; 

Рис.6. Определение места нового компонента в списке

    7 шаг. Процесс (шаги с 3 по 6) продолжается до тех пор, пока ElemN <> 0.

    Приведем процедуру формирования списка на языке Pascal:

 Procedure Create_List_D (var pBegin: PtrRec);
 var pAux : PtrRec;
     Elem : TypeElement;
 Begin
   New (pBegin);
   pBegin^.pNext := Nil;
   Write ('Введите последовательность... ');
   ReadLn (Elem);
   While Elem <> 0 do 
     Begin
        New (pAux);
        pAux^.Element := Elem;
        pAux^.pNext := Nil;
        pAux^.pNext := pBegin^.pNext;
        pBegin^.pNext := pAux;
        ReadLn (Elem);
     End;
   Writeln;
 End;

    На следующем шаге мы рассмотрим cтеки, сформированные на базе однонаправленных списков.

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