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

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

    Изобразим однонаправленный список с заглавным звеном следующим образом:

Рис.1. Схематичное изображение однонаправленного списка с заглавным звеном

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

    Существует два способа построения однонаправленного списка:

    1). Каждый новый элемент добавляется в начало или в конец списка.

    2). Каждый элемент добавляется в свое место в списке, например, так, чтобы обеспечить упорядоченность по возрастанию или убыванию.

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

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

      Var    pBegin, pAux : PtrRec; 
             Elem : Integer;

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

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

      New (pBegin);

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

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

      pAux := pBegin;

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

    4 шаг. Определим ссылку заглавного звена (следующего элемента возможно и не будет):

      pAux^.pNext := NIL;

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

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

     Write ('Задайте первый элемент ');
     ReadLn (Elem);
     While Elem <> ... Do
           Begin
              New (pAux^.pNext);   {резервируем место для нового объекта}

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

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

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

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

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

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

    В результате будет построен однонаправленный список с заглавным звеном с сохранением порядка поступления элементов.

    Приведенный алгоритм оформим в виде процедуры:

 Procedure Create_List (var pBegin : PtrRec);
      var pAux : PtrRec; 
          Elem : Integer;
 Begin 
   New (pBegin);
   pAux := pBegin;
   pAux^.pNext := Nil;{Построили пустой список с заглавным звеном}
   Write ('Задайте первое целое число '); 
   ReadLn (Elem);
   While Elem <> 0 do 
       Begin 
           New (pAux^.pNext);
           pAux := pAux^.pNext;
           pAux^.Element := Elem;
           pAux^.pNext:= Nil;
           Write ('Следующий элемент ');
           ReadLn (Elem); 
       End; 
   WriteLn;
 End;

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

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