Ортогональные списки

 
 

Линейные списки могут рассматриваться как некая альтернатива одномерным массивам. Для многомерных массивов такой альтернативой являются ортогональные списки. В качестве примера рассмотрим представление матрицы. Пусть имеется разреженная матрица, то есть такая матрица, в которой большинство элементов тривиально (обычно это значения 0 или ), и мы не хотим тратить память на их хранение и стремимся избежать многочисленных сложений с нулём и умножений на нуль при выполнении операций с такой матрицей. Пример такой матрицы приведен на рис.14.

Рис 14. Разреженная матрица

 

Для представления элемента матрицы воспользуемся структурой:

struct EM {

int Row,Col; // строка и столбец элемента

double Value; // значение элемента матрицы

EM *Right;// указатель на последователя в строке

EM *Down; // указатель на последователя в столбце

};

Ортогональный список, соответствующий матрице рис.14 изображен на рис. 15.

 
 

Рис 15. Представление разреженной матрицы ортогональным списком