Шаг 3.
Формирование списка с сохранением порядка поступающих элементов

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

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

    1 шаг. Отведем место для указателей pBegin и pAux, переменной Elem в статической области памяти:

      Var    pBegin, pAux : PtrRec; 
             Elem : Integer;


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

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

      New (pBegin);


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

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

      ReadLn (Elem);
      pBegin^.Element := Elem; 
      pBegin^.pNext := Nil; 


Рис.3. Информационное поле и ссылка нового звена списка

    4 шаг. Пусть вспомогательная переменная pAux ссылается на построенное звено:

      pAux := pBegin;


Рис.4. pAux ссылается на построенное звено

    5 шаг. Заполняем список, пока не выполнится условие …:

     Write ('Задайте первый элемент ');
     ReadLn (Elem);
     While Elem <> ... Do
           Begin
                 New (pAux^.pNext);


Рис.5. Резервирование места под новое звено

               pAux := pAux^.pNext;    {передвигаем указатель}


Рис.6. pAux ссылается на новое звено

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


Рис.7. Заполнение нового звена списка данными

            Write ('Задайте следующий элемент ');
            ReadLn (Elem);
     End;


    Замечание.
    Окончание ввода элементов списка определяется в каждом случае индивидуально, т.е. вместо многоточия в заголовке цикла размещают признак окончания заполнения.

    Приведенный алгоритм оформим в виде процедуры (признаком окончания заполнения однонаправленного списка будем считать ввод числа 0):

 Procedure Create_List1 (var pBegin: PtrRec);
   var pAux : PtrRec;
       Elem : Integer;
 Begin
   New (pBegin);
   WriteLn ('Введите элементы списка: ');
   ReadLn (Elem); 
   If Elem <> 0
     Then 
       Begin
        pBegin^.Element := Elem;  {Формирование первого звена}
        pBegin^.pNext := Nil;
        pAux := pBegin;
        ReadLn (Elem);          {Формирование остальных звеньев}
        While Elem <> 0 do
          Begin
             New (pAux^.pNext);
             pAux := pAux^.pNext;
             pAux^.Element := Elem; 
             pAux^.pNext := Nil;
             ReadLn (Elem);
          End;
       End
     Else 
      Begin
       pBegin := Nil; 
       WriteLn ('Список пуст!')
      End;
 End;

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




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