多維數組-矩陣的壓縮存儲- 特殊矩陣（二）

　　三角矩陣

　　()三角矩陣的劃分

　　以主對角線劃分三角矩陣有上三角矩陣和下三角矩陣兩種

　　①上三角矩陣

　　如下圖(a)所示它的下三角(不包括主角線)中的元素均為常數c

　　②下三角矩陣

　　與上三角矩陣相反它的主對角線上方均為常數c如下圖(b)所示

　　注意

　　在多數情況下三角矩陣的常數c為零

　　

　　()三角矩陣的壓縮存儲

　　三角矩陣中的重復元素c可共享一個存儲空間其余的元素正好有n×(n+)/個因此三角矩陣可壓縮存儲到向量sa[

　　n(n+)/]中其中c存放在向量的最後一個分量中

　　① 上三角矩陣中a ij 和sa[k]之間的對應關系

　　上三角矩陣中主對角線之上的第p行(≤p

　　a ij 元素前有i行(從第0行到第i-1行)，一共有：

　　(n-0)+(n-1)+(n-2)+…+(n-i)=i×(2n-i+1)/2個元素;

　　在第i行上，a ij 之前恰有j-i個元素(即a ij ，a i,j+l ，…，a i,j-1 )，因此有：

　　sa[i×(2n-i+1)/2+j-i]= a ij

　　所以：

　　┌i×(2n-i+1)/2+j-i 當i≤j

　　k=│

　　└n×(n+1)/2 當i>j

　　②下三角矩陣中a ij 和sa[k]之間的對應關系

　　┌i×(i+1)/2+j 當i≥j

　　k=│

　　└n×(n+1)/2 當i

　　注意：

　　三角矩陣的壓縮存儲結構是隨機存取結構。tw.wingWit.CoM

　　3.對角矩陣

　　所有的非零元素集中在以主對角線為中心的帶狀區域中，即除了主對角線和主對角線相鄰兩側的若干條對角線上的元素之外，其余元

　　素皆為零的矩陣為對角矩陣。

　　【例】下圖給出了一個三對角矩陣。

　　

　　其中：

　　非零元素僅出現在主對角上(a ii ，0≤i≤n-1)，緊鄰主對角線上面的那條對角線上(a i ， i+1 ，0≤i≤n-2)和緊鄰主對角線下

　　面的那條對角線上(a i+1 ， i ，0≤i≤n-2)。當|i-j|>1時，元素a ij =0。

　　由此可知，一個k對角線矩陣(k為奇數)A是滿足下述條件的矩陣：

　　若|i-j|>(k-1)/2，則元素a ij =0。

　　對角矩陣可按行優先順序或對角線的順序，將其壓縮存儲到一個向量中，並且也能找到每個非零元素和向量下標的對應關系。具

　　體【參見練習】

From:http://tw.wingwit.com/Article/program/sjjg/201311/23898.html