VC++2012程式設計演練資料結構《17》稀疏矩陣

如果在矩陣中，多數的元素為0，稱此矩陣為稀疏矩陣（sparse matrix）。

由于矩陣在程式中常使用二維陣清單示，二維陣列的大小  稀疏矩陣與使用的存儲器空間成正比，如果多數的元素沒有資料，則會造成存儲器空間的浪費，為此，必須設計稀疏矩陣的陣列儲存方式，利用較少的存儲器空間儲存完整的矩陣資料。

　　二維數組Amn中有N個非零元素，若N<<m*n（N/m*n<=0.2),則稱A為稀疏矩陣。

　　由于稀疏矩陣中含有很多的0元素,在計算機中存儲會浪費很多的空間,是以我們通常采用壓縮存儲的方法。

　稀疏矩陣的計算速度更快,因為M AT L A B隻對非零元素進行操作,這是稀疏矩陣的一個突出的優點.

　　假設矩陣A,B中的矩陣一樣.計算2*A需要一百萬次的浮點運算,而計算2*B隻

　　需要2 0 0 0次浮點運算.

　　因為M AT L A B不能自動建立稀疏矩陣,是以要用特殊的指令來得到稀疏矩陣,在下一節

　　中将給出這些指令.前面章節中的算術和邏輯運算都适用于稀疏矩陣.

　　對于一個用二維數組存儲的稀疏矩陣Amn,如果假設存儲每個數組元素需要L個位元組,那麼存儲整個矩陣需要m*n*L個位元組.但是,這些存儲空間的大部分存放的是0元素,進而造成大量的空間浪費.為了節省存儲空間,可以隻存儲其中的非0元素.

　　  對于矩陣Amn的每個元素aij,知道其行号i和列号j就可以确定其位置.是以對于稀疏矩陣可以用一個結點來存儲一個非0元素.該結點可以定義如下:

　　[i,j,aij]

　　該結點由3個域組成,i:行号,j:列号;aij元素值.這樣的結點被稱為三元組結點.矩陣的每一個元素Qij,由一個三元組結點(i,j,aij)唯一确定.

　　例如稀疏矩陣A:

　　50 0 0 0

　　10 0 20 0

　　0 0 0 0

　　-30 0 -60 5

　　其對應的三元組表為：

　　1 1 50

　　2 1 10

　　2 3 20

　　4 1 -30

　　4 3 -60

　　4 4 5

打開IDE 

我們建立一個工程

類的聲名如下

類的實作如下

類的調用如下

效果如下

代碼下載下傳位址

http://download.csdn.net/detail/yincheng01/4788652