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

數據結構數組和廣義表之矩陣的壓縮存儲

2013-11-15 15:21:13  來源: 數據結構 

  壓縮存儲即為多個相同的非零元素只分配一個存儲空間對零元素不分配空間
  所謂特殊矩陣(Special Matrices)是指非零元素或零元素的分布有一定規律的矩陣

 
 幾種特殊矩陣的壓縮存儲
 對稱矩陣
  在一個n階方陣A中若元素滿足下述性質
    aij=aji    ≤ij≤n
  則稱A為對稱矩陣如圖所示
存儲元素為{}
令I=max(ij)J=min(ij)則k和ij的對應關系為
   k=I×(I+)/+J    ≤k<n(n+)/
aij的地址計算公式
   LOC(aij)=LOC(sa[])+[I×(I+)/+J]×d

  三角矩陣
 以主對角線劃分三角矩陣有上三角和下三角兩種上三角矩陣的下三角(不包括主角線)中的元素均為常數c下三角矩陣正好相反它的主對角線上方均為常數c在多數情況下三角矩陣的常數c為零


上三角矩陣中sa[k]和aij的對應關系是 

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


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


From:http://tw.wingwit.com/Article/program/sjjg/201311/23283.html
  • 上一篇文章:

  • 下一篇文章:
  • 推薦文章
    Copyright © 2005-2013 電腦知識網 Computer Knowledge   All rights reserved.