§2. Создание списка

Список можно создать двумя способами:

а) в прямом направлении “слева направо”, когда новый элемент добавляется в конец списка “справа”;

б) в обратном направлении, когда новый элемент вставляется слева, то есть в начало (вершину) списка. Так создаётся список, который называется стек.

2.1. Первый способ (+)

// Создаём фиктивный элемент (см. §1).

T=new tsp;

/* Зарезервировали память для фиктивного элемента списка и его адрес поместили в T */

T->num=0;

/* Определили его информационную часть. Это можно не делать, так как в просмотре этот элемент участвовать не будет. */

P=T;

/* В переменной P — адрес начала списка. При наличии фиктивного элемента его менять не будем, даже после вставки в начало списка, так как перед фиктивным элементом вставлять ничего никогда не будем. */

int n; cin>>n;

// n — количество реальных элементов списка без учёта фиктивного.

for (int i=1; i<=n;i++)

// Цикл для добавления n реальных элементов списка

{

/* Резервируем память для одного элемента списка и его адрес помещаем в Q */

Q=new tsp;

// Определяем информационную часть нового элемента .

cin>>Q->num;

/* “Cоединяем” его с предыдущим элементом. Другими словами, адрес нового подготовленного элемента, который находится в Q, помещаем в адресное поле структуры, адрес которой в T, то есть в T->next. */

T->next=Q;

/* Чтобы на следующем шаге это (T->next=Q;) можно было бы повторить, адрес только что созданного и присоединённого к списку элемента (Q) помещаем в T. */

T=Q;

/* Тогда после этого присваивания этот элемент Q, а точнее T, будет играть роль предшествующего, а новый элемент Q создадим. */

} // Конец цикла

/*Последний элемент должен содержать адрес NULL. Это означает, что после него в цепочке нет больше элементов списка. Элемент, в адресной части которого значение NULL, похож на “тупик”. */

Q->next=NULL;

Кроме ввода с экрана (cin>>Q->num;) при подготовке информационной части одного нового элемента списка возможны следующие варианты:

получение информационных полей с помощью датчика случайных чисел;

вычисление их или части полей по некоторому алгоритму, который реализуется, как правило, в функции. Вместо cin>>Q->num; тогда вызываем эту функцию;

все или некоторые информационные поля элемента списка можно прочитать из предварительно созданного файла (см. главу “Файлы”).

2.2. Второй способ (создание стека). (+)

Создание списка в обратном направлении рассмотрим на примере списка, в информационной части элемента которого не одно число, как в предыдущем примере, а одномерный статический массив фиксированной размерности m. Соответствующая структура для такого списка объявляется следующим образом:

const m=5;

struct tsp2 { float a[m]; tsp2 *next} *P2, *Q2, *T2;

Заметим, что при такой организации данных будет иметь место ещё один способ работы с “матрицей”. Информационная часть каждого элемента — это одна строка “матрицы”. При этом количество строк, то есть количество элементов списка, не обязательно фиксируется в виде константы. Его мы можем объявить как переменную и каким-нибудь способом определить, например, ввести, как это сделали в предыдуще примере. В предложенном ниже варианте количество элементов списка определяется в процессе создания списка

Вместо записанного в первом варианте цикла for, в котором используется заданное количество элементов списка, то есть количество одномерных массивов, можно использовать так называемый вечный цикл

while (1) { }

Выход из него выполним с помощью break, если введём, например, массив, в котором будет хотя бы одно число 1000 в любом месте. Для ввода и анализа массива составим логическую функцию, которая возвращает true или false в зависимости от того, есть ли это число 1000 в одномерном массиве:

bool fun1 (float *x, unsigned size)

{ for( int j=0; j<size; j++)

{ cin>>x[j];

if (x[j] ==1000) return true;

}

return false;

}

Фиктивный элемент в этом способе создавать не будем, хотя никто не мешает это сделать. Так как первым готовим последний “правый” элемент списка, то надо не забыть в него занести тупиковый адрес NULL. В отличие от рассмотренного выше варианта это надо сделать не после цикла (см. 2.1), а в начале алгоритма. Поэтому начинаем алгоритм так:

P2=NULL;

unsigned n=0; // Счётчик для количества элементов списка

while (1)

{ /* Резервируем память для одного элемента списка и его адрес помещаем в Q2 */

Q2=new tsp2;

/* Определяем информационную часть нового элемента, то есть один одномерный массив, и проверяем условие выхода из цикла с помощью функции fun1. Как и в первом варианте, кроме ввода с экрана, возможны другие способы определения массива (см. 2.1) */

if (fun1(Q2->a, m)) break;

n++;

/* Присоединяем этот подготовленный элемент “справа”, а не “слева”, как в первом варианте. В адресную часть этого нового только что созданного элемента списка помещаем адрес последнего присоединённого к этому моменту элемента. Для первого элемента списка в его адресную часть занесём NULL. */

Q2->next=P2;

/* Чтобы на следующем шаге иметь возможность в адресное поле нового элемента занести адрес последнего сформированного перед этим элемента, необходимо выполнить следующее присваивание: */

P2=Q2;

} // Конец цикла while

Этот способ используется для создания одного из видов списка, который называется стек .