[ 資料結構 小學堂 ] 陣列結構 : 右上三角矩陣 (Right Upper Triangular Matrix)

前言 :
上三角矩陣 (Upper Triangular Matrix) 就是一種對角線以下元素皆為 0 的 nxn 矩陣. 其中又可分為右上三角矩陣 (Right Upper Triangular Matrix) 與 左上三角形矩陣 (Left Upper Triangular Matrix). 由於上三角形矩陣仍有許多元素為0. 為避免浪費空間, 可以把三角形矩陣的二維模式存在一維陣列中.

右上三角矩陣 :
即對 nxn 的矩陣 A, 假如 i>j, 那麼 A(i,j) = 0. 參考下圖 :


考慮右三角行二維矩陣的非零項目可依序對映成一為矩陣, 取需要一個一為矩陣B(1:n(n+1)/2) 來儲存. 對映方式也可以區分成以列為主以及以行為主兩種陣列記憶體配置方式.
- 以列為主


- 以行為主


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

view plaincopy to clipboardprint?

1. #include   
2. using namespace std;  
3.   
4. /*  
5. * As ch02_05.cpp 
6. * 將右上三角矩陣壓:rumatrix[MxM] 縮存放到一維矩陣:odmatrix. 
7. */  
8. void dealRightUpperTriMatrix(int* rumatrix, int* odmatrix, int M);  

* ch02.cpp 代碼 :

view plaincopy to clipboardprint?

1. #include "ch02.h"  
2.   
3. void dealRightUpperTriMatrix(int* rumatrix, int* odmatrix, int M) {  
4.     int index=0;  
5.     for(int i=0; i
6.         for(int j=i; j
7.             odmatrix[index++] = rumatrix[i*M +j];  
8.         }  
9. }  

* 呼叫演算法範例代碼 :

view plaincopy to clipboardprint?

1. #include "ch02.h"  
2.   
3. /* 
4. * 顯示矩陣 matrix[MxN] 並有前置訊息(message)顯示 
5. */  
6. void _showMatrix(char* message, int* matrix, int M, int N) {  
7.     cout << message << endl;  
8.     for(int i=0; i
9.         for(int j=0; j
10.             cout << matrix[i*N + j] << "\t";  
11.         cout << endl;  
12.     }  
13. }  
14.   
15. /* 
16. * 計算某個矩陣非零值的個數 
17. */  
18. int _notZeroCount(int* matrix, int M, int N){  
19.     int count =0;  
20.     for(int i=0; i
21.         for(int j=0; j
22.             if(matrix[i*N + j]!=0)  
23.                 count++;  
24.         }  
25.     return count;  
26. }  
27.   
28. void ch02_05(bool b) {  
29.     if(b){  
30.         int mA[5][5] = {  
31.             {7,8,12,21,9},  
32.             {0,5,14,17,6},  
33.             {0,0,7,23,24},  
34.             {0,0,0,32,19},  
35.             {0,0,0,0,8}  
36.         };  
37.         _showMatrix("[ 右上三角矩陣內容為 ]",mA[0], 5, 5);  
38.         int iNotZero = _notZeroCount(mA[0], 5, 5);  
39.         printf("[ 非零數值個數 ]\n%d\n", iNotZero);  
40.         int* odMatrix = new int[iNotZero];  
41.         dealRightUpperTriMatrix(mA[0], odMatrix, 5);  
42.         _showMatrix("[ 壓縮後一維矩陣內容 ]",odMatrix , 1, iNotZero);  
43.     }  
44. }  

執行結果 :

[ 右上三角矩陣內容為 ]
7 8 12 21 9
0 5 14 17 6
0 0 7 23 24
0 0 0 32 19
0 0 0 0 8
[ 非零數值個數 ]
15
[ 壓縮後一維矩陣內容 ]
7 8 12 21 9 5 14 17 6 7 23 24 32 19 8

This message was edited 3 times. Last update was at 20/03/2010 16:00:45