Шаг 3.
Линейные однонаправленные списки. Построение списка с заглавным звеном

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

    Чтобы сделать действия, выполняемые при включении элемента в список (исключении элемента из списка), единообразными, обычно применяется следующий прием. В начало каждого списка добавляется заглавное звено (заголовок списка). Оно никогда не исключается из списка и перед ним в список никогда не включаются новые элементы.

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

    Приведем алгоритм построения однонаправленного списка с заглавным звеном с сохранением порядка поступления звеньев. Шаги построения алгоритма будем иллюстрировать с помощью схем "до и после" Д.Кнута.

1. Вначале отведем место для указателей в статической памяти:

       struct node *phead;   
       struct node *t;
   

   
   Рис.1. Резервирование места в памяти

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

       phead = new(node);
   

   
   Рис.2. Выделили место для элемента списка

       Построено заглавное звено будущего однонаправленного списка.
   
   

3. Выполним еще ряд подготовительных действий:

       t = phead;
   

   
   Рис.3. Присвоим значение t

       (*t).sled = NULL;
   

   
   Рис.4. Присвоим указателю заглавного звена NULL

4. Теперь можно приступить к циклическому процессу построения списка. Идентификатор Число обозначает объект языка C++, вводимый с клавиатуры.

       cin>>Число;
       while  (Число != Числу, определяющему окончание ввода)
         {
             (*t).sled = new (node); //Резервируем место для нового объекта.
   

   
   Рис.5. Создаем новый объект

             t = (*t).sled;  //Указатель t содержит адрес 
                             //расположения созданного объекта.
   

   
   Рис.6. Определяем t

             (*t).elem = Число; //Заполняем поля объекта.
             (*t).sled = NULL;
   

   
   Рис.7. Результат заполнения полей

             cin>>Число; //Запрос на ввод следующего значения.
         }
   

       Алгоритм построения оформим в виде функции на языке C++:

   void POSTROENIE (node **phead)
   // Построение списка с заглавным звеном.
   // *phead - указатель на заглавное звено.
   {
       node *t;
       int el;
       // Вначале создадим заглавное звено 
       *phead = new (node);
       t = *phead; (*t).sled = NULL;
       cout<<"Вводите элементы звеньев списка: ";
       cin>>el;
       while (el!=0)
       { 
         (*t).sled = new (node); t = (*t).sled; 
         (*t).elem = el; (*t).sled = NULL; 
         cin>>el;
       }
   }
   

       Ясно, что пустой однонаправленный список с заглавным звеном можно схематически представить так:

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

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

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