Информатика и технология программирования

         

Способы формирования списков


Хотя списки представляют собой динамические структуры данных, способы их формирования могут быть различными, вплоть до статических. Рассмотрим их на примере односвязного списка.

Вариант 1. Элементы -обычные переменные, связи инициализируются транслятором, вся структура данных "зашита" в программный код:


struct list
{
list *next;
int val;
} a={0,NULL}, b={1,&#38a}, c={2,&#38b}, *ph = &#38c;

Вариант 2. Элементы списка создаются в обычном массиве, поэтому их количество ограничено. Связи устанавливаются динамически, то есть программой. Такой вариант используется, когда заданное количество элементов образуют несколько различных динамических структур, переходя из одной в другую. Примером является управление задачами в операционной системе, которые в процессе работы организуются в несколько различных очередей (списков):


struct list A[100],*ph; // Создать список из


for (i=0; i&#60 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-&#62val = n; // динамическую переменную,


pnew-&#62next = *ph; // заполнить его и


ph = pnew; // поместить в начало списка


return ph; // вернуть новый заголовок


}



Содержание раздела