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

特殊矩陣

2013-11-15 15:40:09  來源: 數據結構 

特殊矩陣

  所謂特殊矩陣是指非零元素或零元素的分布有一定規律的矩陣常見的有對稱矩陣三角矩陣和對角矩陣等
.對稱矩陣
)對稱矩陣
  在一個n階方陣A中若元素滿足下述性質
       aij=aji ≤ij≤n
則稱A為對稱矩陣
【例】下圖便是一個階對稱矩陣


                  
)對稱矩陣的壓縮存儲
  對稱矩陣中的元素關於主對角線對稱故只要存儲矩陣中上三角或下三角中的元素讓每兩個對稱的元素共享一個存儲空間這樣能節約近一半的存儲空間
①按行優先順序存儲主對角線(包括對角線)以下的元素

 
  即按aaa……ananann次序存放在一個向量sa[..n(n+)/]中(下三角矩陣中元素總數為n(n+)/
    其中
         sa[]= a
         sa[] = a
         ……
         sa[n(n+)/]= ann
②元素aij的存放位置
    aij元素前有i行(從第行到第i行)一共有
         ++…+i=i×(i+)/個元素
    在第i行上aij之前恰有j個元素(即aiailaij)因此有
           sa[i×(i+)/+j]= aij
③aij和sa[k]之間的對應關系
    若i≥jk=i×(i+)/+j   ≤k<n(n+)/
    若i<jk=j×(j+)/+i   ≤k<n(n+)/
    令I=max(ij)J=min(ij)則k和ij的對應關系可統一為
         k=i×(i+)/+j ≤k<n(n+)/

)對稱矩陣的地址計算公式
  LOC(aij)=LOC(sa[k])
          =LOC(sa[])+k×d=LOC(sa[])+[I×(I+)/+J]×d
  通過下標變換公式能立即找到矩陣元素aij在其壓縮存儲表示sa中的對應位置k因此是隨機存取結構
  【例】a和a均存儲在sa[]中這是因為
           k=I×(I+)/+J=×(+)/+=

三角矩陣 
)三角矩陣的劃分
     以主對角線劃分三角矩陣有上三角矩陣和下三角矩陣兩種
①上三角矩陣
     如下圖(a)所示它的下三角(不包括主角線)中的元素均為常數c
②下三角矩陣
     與上三角矩陣相反它的主對角線上方均為常數c如下圖(b)所示
  注意
     在多數情況下三角矩陣的常數c為零

)三角矩陣的壓縮存儲
  三角矩陣中的重復元素c可共享一個存儲空間其余的元素正好有n×(n+)/因此三角矩陣可壓縮存儲到向量sa[..n(n+)/]中其中c存放在向量的最後一個分量中
① 上三角矩陣中aij和sa[k]之間的對應關系
  上三角矩陣中主對角線之上的第p行(≤p<n)恰有np個元素按行優先順序存放上三角矩陣中的元素aij時
     aij元素前有i行(從第行到第i行)一共有
        (n)+(n)+(n)+…+(ni)=i×(ni+)/個元素
  在第i行上aij之前恰有ji個元素(即aijaij+laij)因此有
          sa[i×(ni+)/+ji]= aij
所以
     ┌i×(ni+)/+ji 當i≤j
   k=│
      └n×(n+)/ 當i>j

②下三角矩陣中aij和sa[k]之間的對應關系
      ┌i×(i+)/+j 當i≥j
    k=│
      └n×(n+)/ 當i<j
 注意
  三角矩陣的壓縮存儲結構是隨機存取結構

.對角矩陣
  所有的非零元素集中在以主對角線為中心的帶狀區域中即除了主對角線和主對角線相鄰兩側的若干條對角線上的元素之外其余元素皆為零的矩陣為對角矩陣
  【例】下圖給出了一個三對角矩陣


  其中
  非零元素僅出現在主對角上(aii≤i≤n)緊鄰主對角線上面的那條對角線上(aii+ ≤i≤n)和緊鄰主對角線下面的那條對角線上(a i+i≤i≤n)當|ij|>元素aij=
  由此可知一個k對角線矩陣(k為奇數)A是滿足下述條件的矩陣
            若|ij|>(k)/則元素aij=
  對角矩陣可按行優先順序或對角線的順序將其壓縮存儲到一個向量中並且也能找到每個非零元素和向量下標的對應關系具體【參見練習】

 


From:http://tw.wingwit.com/Article/program/sjjg/201311/23770.html
    推薦文章
    Copyright © 2005-2013 電腦知識網 Computer Knowledge   All rights reserved.