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

Смежное представление последовательностей

Часто приходится встречаться с представлением конечных последовательностей данных и операциями над ними (вектора, матрицы, тензоры и т.д.). С вычислительной точки зрения простейшим представлением последовательности является точный список ее членов, расположенный по порядку в смежных ячейках памяти (смежное представление данных). В языках высокого уровня – это одномерные, двухмерные и т.д. массивы данных. Например, в языке С подобного рода абстрактные типы данных описываются следующим образом:

typedef double VECT[10]; // описание абстрактного типа VECT как одномерного массива действительных чисел двойной точности с 10 координатами.

typedef int MATR[10][10]; // введение для квадратных матриц размера абстрактного типа данных MATR как двухмерного массива целых чисел.

Двухмерную матрицу действительных чисел можно определить и так

typedef VECT MATR2[20];

Абстрактный тип данных MATR2 описывает матрицу действительных чисел (с двойной точностью) размера .

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

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

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

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

typedef struct LTF{

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

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

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

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

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

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