3.1.2. Связанное представление последовательностей

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

Например, пусть требуется хранить результаты «испытаний» некоторой функции в порядке возрастаний значений функции. Введем в рассмотрение односвязанный список SFUN (см. рис. 7).

Каждый элемент списка занимает отдельное место в памяти (не обязательно смежное), и связаны они между собой с помощью указателей (адресов) (на рисунке «стрелками»). В данном случае список можно просматривать с права на лево. При этом необходимо позаботится о хранении заголовка списка (указателя на первый элемент). Признаком конца списка служит «пустое» значение указателя в последнем элементе списка (NULL).

Представленный на рисунке 7 конструктивный объект данных описывается следующим образом:

typedef double FUNC; // ввод нового типа данных для значений функции.

typedef struct LTF{

double x; // переменная x

double y; // переменная y

FUNC z; // значение функции

LTF *right;// указатель на следующий элемент списка

} LFUN; // описание элемента списка

typedef LFUN* HFUN; // указатель на «голову» списка

Естественно, что в этом случае необходимо создать программы внесение в список нового элемента и удаление из списка существующего элемента (см. рис. 8).