Разреженные матрицы

Question

Как мы можем отобразить разреженную матрицу? Кто-то, кто хотел помочь мне, сказал: используйте связанные списки.
Также я читал, где мы должны создать класс, как это:

SpMatrix
{
    int non_zero_value;
    int i,j;
}

Точно, что такое разреженная матрица, я читал википедии и других сайтах. но проблема еще не решена.

Заранее спасибо.

Answer 1

Разреженная - это матрица, большинство элементов которой равны 0. Например, матрица, имеющая ненулевые элементы только на диагонали, является явно разреженной матрицей:

1 0 0 0
0 2 0 0 
0 0 3 0 
0 0 0 4

Очевидно, что хранить все элементы матрицы - пустая трата места, поскольку большинство из них равно нулю. Существует несколько способов хранения таких матриц, и это действительно зависит от того, насколько универсальным вы хотите быть, и от конкретной проблемы.

В большинстве случаев у вас есть определенный класс для каждого типа разреженной матрицы, которую вы хотите поддерживать, например, диагональ, треугольник, диагональ полосы и т. д. Это обычно дает вам более эффективный код, чем общее решение.

Это сложная проблема без готовых рецептов. Вы можете использовать связанные списки или что-нибудь еще на самом деле.