程式扎記: [ 資料結構 小學堂 ] 陣列結構 : 稀疏矩陣

標籤

2010年9月11日 星期六

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


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


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


範例代碼 :
* ch02.h 代碼 :
  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 代碼 :
  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. }  
* 呼叫演算法範例代碼 :
  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]+13);  
  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

沒有留言:

張貼留言

網誌存檔

關於我自己

我的相片
Where there is a will, there is a way!