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

    Приведем алгоритм построения однонаправленного списка без заглавного звена с помощью схем "до и после" [1]. В нежеприведенной схеме переменная phead - указатель на первый элемент списка, а t - указатель, содержащий адрес последнего (текущего) элемента списка.

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

       struct node *phead;                
       struct node *t;
   

   
   Рис.1. Размещение указателей

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

       phead = new (node);
   

   
   Рис.2. Размещение объекта в куче

3. Присвоим значение переменной t, и поместим в информационное поле значение элемента:

       t = phead;
       (*t).value = Элем;
   

   
   Рис.3. Определение t

4. Поместим в поле звена адрес нового динамического объекта, зарезервированного в куче:

       (*t).next = new (node);
   

   
   Рис.4. Добавление нового элемента

5. Переменная t должна содержать адрес последнего добавленного элемента:

       t = (*t).next;
   

   
   Рис.5. t содержит адрес последнего элемента

6. Если требуется завершить построение списка, то в поле указателя последнего элемента нужно поместить NULL:

       (*t).next = NULL;
       (*t).value = Элем1;
   

   
   Рис.6. Результат выполнения операций

    В результате построен линейный однонаправленный список без заглавного звена, содержащий два узла:

Рис.7. Конечный результат

    Оформим алгоритм в виде программы на языке C++.

#include<iostream.h>
struct node
{ 
   int value; 
   node *next;
}; 

void main ()
{
   int i;
   node *phead, *t;

   phead = new (node);
   t = phead;

   (*t).value = 1;
   (*t).next = new (node);
   t = (*t).next;

   (*t).value = 2;
   (*t).next = new (node);
   t = (*t).next;

   (*t).value = 6;
   (*t).next = new (node);
   t = (*t).next;

   (*t).value = 17;
   (*t).next = new (node);
   (*t).next = NULL;
   // Вывод содержимого информационных полей списка
   for (t=phead; t!=NULL; t=(*t).next) 
                cout<<(*t).value << " ";
}

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

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