稀疏矩陣

Question

我們如何顯示稀疏矩陣？有人想幫我說：使用鏈表。
我也看過一些在那裏，我們應該像這樣創建類：

SpMatrix 
{ 
    int non_zero_value; 
    int i,j; 
} 

究竟什麼是稀疏矩陣，我已閱讀wekipedia和其他網站。但問題尚未解決。

在此先感謝。

Answer 1

稀疏是與大多數元素等於0。例如僅具有在對角線上顯然是一個稀疏矩陣中非零元素的矩陣的矩陣：

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

顯然這是浪費空間，以存儲矩陣的所有元素，因爲大多數都是零。有許多技術可以存儲這些矩陣，這實際上取決於你想要的通用性以及手頭的具體問題。大多數時候你最終都會爲你想要支持的每種不同類型的稀疏矩陣有一個特定的類，例如，對角線，三角形，帶對角線等等。這通常會比通用解決方案提供更高效的代碼。

這是一個複雜的問題，沒有現成的食譜。你可以使用鏈表或其他任何東西。