[ 資料結構 小學堂 ] 陣列結構 : 稀疏矩陣

前言 :
稀疏矩陣最簡單的定義就是一個矩陣中大部分的元素為0, 即可以稱為稀疏矩陣 (Sparse Matrix). 例如下列的4x4矩陣就是相當典型的稀疏矩陣 :


如果直接使用傳統二維矩陣來儲存稀疏矩陣會有許多元素都是0. 這樣就會十分浪費記憶體空間. 而改進空間浪費的方法就是利用三項式的資料結構. 我們把每一個非零項目以 (I, j, item-value) 來表示. 更詳細的形容就是如果有一稀疏矩陣有 n 個非零項目, 那麼就可以利用一個 A(0,n, 1:3) 的二維矩陣來表示. 參考如下 :


範例代碼 :
* ch02.h 代碼 :

view plaincopy to clipboardprint?

1. /** 
2. * As ch02_04.cpp 
3. * Compress matrix into 稀疏矩陣cmatrix 
4. */  
5. void genSparseMatrix(int* matrix, int* cmatrix, int M, int N);  

* ch02.cpp 代碼 :

view plaincopy to clipboardprint?

1. void genSparseMatrix(int* matrix, int* cmatrix, int M, int N) {  
2.     //Calculate how many not-zero cell in matrix  
3.     if(M<=0 || N <=0) {  
4.         cout << "[ 錯誤:矩陣維數不可以小於等於0 ]" << endl;  
5.     }  
6.     //int iNotZero = _notZeroCount(matrix, M, N);  
7.     //cmatrix = new int[(iNotZero+1)*3];      
8.     int row=1;  
9.     for(int i=0; i
10.         for(int j=0; j
11.             if(matrix[i*N + j]!=0){  
12.                 cmatrix[row*3] = i+1;  
13.                 cmatrix[row*3 + 1] = j+1;  
14.                 cmatrix[row*3 + 2] = matrix[i*N + j];  
15.                 row++;  
16.             }                 
17.         }  
18. }  

* 呼叫演算法範例代碼 :

view plaincopy to clipboardprint?

1. /* 
2. * 計算某個矩陣非零值的個數 
3. */  
4. int _notZeroCount(int* matrix, int M, int N){  
5.     int count =0;  
6.     for(int i=0; i
7.         for(int j=0; j
8.             if(matrix[i*N + j]!=0)  
9.                 count++;  
10.         }  
11.     return count;  
12. }  
13.   
14. void ch02_04(bool b) {  
15.     if(b) {  
16.         int M,N;  
17.         cout << "[ 請輸入MxN 矩陣的維度 ]" << endl;  
18.         cout << "請輸入維度M: ";  
19.         cin >> M;  
20.         cout << "請輸入維度N: ";  
21.         cin >> N;  
22.         int *arrA = new int[M*N];         
23.         _setMatrix(arrA, M, N);  
24.         _showMatrix("[ 輸入矩陣內容為 ]",arrA, M, N);  
25.         int iNotZero = _notZeroCount(arrA, M, N);  
26.         int *comprMatrix = new int[(iNotZero+1)*3];  
27.         comprMatrix[0] = M;  
28.         comprMatrix[1] = N;  
29.         comprMatrix[2] = iNotZero;  
30.         genSparseMatrix(arrA, comprMatrix, M, N);   
31.         _showMatrix("[ 壓縮矩陣內容為 ]", comprMatrix, comprMatrix[2]+1, 3);  
32.     }  
33. }  

執行結果 :

[ 請輸入MxN 矩陣的維度 ]
請輸入維度M: 4
請輸入維度N: 4
[ 請輸入矩陣內容 ]
m11=0
m12=0
m13=0
m14=6
m21=0
m22=4
m23=0
m24=0
m31=0
m32=0
m33=0
m34=0
m41=0
m42=0
m43=6
m44=0
[ 輸入矩陣內容為 ]
0 0 0 6
0 4 0 0
0 0 0 0
0 0 6 0
[ 壓縮矩陣內容為 ]
4 4 3
1 4 6
2 2 4
4 3 6

This message was edited 3 times. Last update was at 20/03/2010 11:40:20