2011-01-23 2 views
1

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

SpMatrix 
{ 
    int non_zero_value; 
    int i,j; 
} 

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

благодарит заранее.

+1

Ваш вопрос сводится к тому, «как я могу отобразить разреженную матрицу?», «Как я могу ее создать?», Пока мы здесь, что такое одно? Мне нужно решить мою проблему », но на самом деле не говорит нам, что проблема является. –

+1

Вы явно хотите узнать о разреженных матрицах. Если вы серьезно относитесь к этому начинанию, я предлагаю вам купить книгу Тима Дэвиса: http://www.cise.ufl.edu/research/sparse/CSparse/ –

ответ

4

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

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

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

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

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

+0

Ну, есть и общие подходы. Например, сжатое хранилище строк. – sellibitze

+0

Конечно, вы можете иметь координаты + значения. –

+0

Трудно видеть прецедент, когда связанные списки будут подходящим выбором –