Способы формирования списков
Хотя списки представляют собой динамические структуры данных, способы их формирования могут быть различными, вплоть до статических. Рассмотрим их на примере односвязного списка.
Вариант 1. Элементы -обычные переменные, связи инициализируются транслятором, вся структура данных "зашита" в программный код:
struct list
{
list *next;
int val;
} a={0,NULL}, b={1,&a}, c={2,&b}, *ph = &c;
Вариант 2. Элементы списка создаются в обычном массиве, поэтому их количество ограничено. Связи устанавливаются динамически, то есть программой. Такой вариант используется, когда заданное количество элементов образуют несколько различных динамических структур, переходя из одной в другую. Примером является управление задачами в операционной системе, которые в процессе работы организуются в несколько различных очередей (списков):
struct list A[100],*ph; // Создать список из
for (i=0; i< 99; i++) // элементов, размещенных
{ // в статическом массиве
A[i].next = A+i+1;
A[i].val = i;
}
A[99].next = NULL;
ph = A;
Вариант 3. Элементы списка являются динамическими переменными, связи между ними устанавливаются программно:
list *InsertFirst(list *ph, int n)
// Включить в начало списка
// ph - заголовок списка
// n - Значение элемента списка
//
{ list *pnew;
pnew = new list; // Создать элемент списка -
pnew->val = n; // динамическую переменную,
pnew->next = *ph; // заполнить его и
ph = pnew; // поместить в начало списка
return ph; // вернуть новый заголовок
}
