09年自考《數據結構》各章要點一[10]

　　矩陣的壓縮存儲為多個相同的非零元素分配一個存儲空間;對零元素不分配空間

　　特殊矩陣的概念所謂特殊矩陣是指非零元素或零元素分布有一定規律的矩陣

　　稀疏矩陣的概念一個矩陣中若其非零元素的個數遠遠小於零元素的個數則該矩陣稱為稀疏矩陣

　　特殊矩陣的類型

　　·對稱矩陣滿足a(ij)=a(ji)元素總數n(n+)/I=max(ij)J=min(ij)LOCa(ij)=LOC(sa[])+(I*(I+)/+J)*d

　　·三角矩陣

　　 ·上三角陣k=i*(ni+)/+jiLOCa(ij)=LOC(sa[])+k*d

　　·下三角陣k=i*(i+)/+jLOCa(ij)=LOC(sa[])+k*d

　　·對角矩陣k=i+jLOCa(ij)=LOC(sa[])+k*d

　　稀疏矩陣的壓縮存儲方式用三元組表把非零元素的值和它所在的行號列號做為一個結點存放在一起用這些結點組成的一個線性表來表示但這種壓縮存儲方式將失去隨機存儲功能加入行表記錄每行的非零元素在三元組表中的起始位置即帶行表的三元組表

[]  []  []  []  []  []  []  []  []  []  []  

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