熱點推薦:
您现在的位置: 電腦知識網 >> 編程 >> 數據結構 >> 正文

多維數組-矩陣的壓縮存儲- 特殊矩陣(二)

2013-11-15 15:45:24  來源: 數據結構 

  三角矩陣

  ()三角矩陣的劃分

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

  ①上三角矩陣

  如下圖(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
    推薦文章
    Copyright © 2005-2013 電腦知識網 Computer Knowledge   All rights reserved.