[ 資料結構 小學堂 ] 陣列結構 : 左下三角矩陣 (Left Lower Triangular Matrix)

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

左下三角矩陣 : 
即對 nxn 的矩陣 A, 假如 i


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


- 以行為主


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

view plaincopy to clipboardprint?

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

* ch02.cpp 代碼 :

view plaincopy to clipboardprint?

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

* 呼叫演算法代碼 :

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. int _notZeroCount(int* matrix, int M, int N){  
18.     int count =0;  
19.     for(int i=0; i
20.         for(int j=0; j
21.             if(matrix[i*N + j]!=0)  
22.                 count++;  
23.         }  
24.     return count;  
25. }  
26.   
27. void ch02_06(bool b) {  
28.     if(b) {  
29.         int mA[5][5] = {  
30.             {7,0,0,0,0},  
31.             {1,21,0,0,0},  
32.             {19,5,8,0,0},  
33.             {4,12,51,81,0},  
34.             {15,33,52,23,62}  
35.         };  
36.         _showMatrix("[ 左下三角矩陣內容為 ]",mA[0], 5, 5);  
37.         int iNotZero = _notZeroCount(mA[0], 5, 5);  
38.         printf("[ 非零數值個數 ]\n%d\n", iNotZero);  
39.         int* odMatrix = new int[iNotZero];  
40.         dealLeftDownTriMatrix(mA[0], odMatrix, 5);  
41.         _showMatrix("[ 壓縮後一維矩陣內容 ]",odMatrix , 1, iNotZero);  
42.     }  
43. }  

執行結果 :

[ 左下三角矩陣內容為 ]
7 0 0 0 0
1 21 0 0 0
19 5 8 0 0
4 12 51 81 0
15 33 52 23 62
[ 非零數值個數 ]
15
[ 壓縮後一維矩陣內容 ]
7 1 21 19 5 8 4 12 51 81 15 33 52 23 62

This message was edited 4 times. Last update was at 20/03/2010 21:34:42