Ортогональные списки
Линейные списки могут рассматриваться как некая альтернатива одномерным массивам. Для многомерных массивов такой альтернативой являются ортогональные списки. В качестве примера рассмотрим представление матрицы. Пусть имеется разреженная матрица, то есть такая матрица, в которой большинство элементов тривиально (обычно это значения 0 или ), и мы не хотим тратить память на их хранение и стремимся избежать многочисленных сложений с нулём и умножений на нуль при выполнении операций с такой матрицей. Пример такой матрицы приведен на рис.14.
Рис 14. Разреженная матрица
Для представления элемента матрицы воспользуемся структурой:
struct EM {
int Row,Col; // строка и столбец элемента
double Value; // значение элемента матрицы
EM *Right;// указатель на последователя в строке
EM *Down; // указатель на последователя в столбце
};
Ортогональный список, соответствующий матрице рис.14 изображен на рис. 15.
Рис 15. Представление разреженной матрицы ортогональным списком