什么是壓縮存儲？

把多個(gè)相同的元素分配一個(gè)存儲空間，元素為0的不分配空間。

什么樣的矩陣能夠壓縮？

特殊矩陣，如：對稱矩陣，對角矩陣，三角矩陣，稀疏矩陣等。

什么叫稀疏矩陣？

矩陣中非零元素的個(gè)數(shù)較少，一般認(rèn)為非零元素的個(gè)數(shù)小于5%的矩陣為稀疏矩陣。

1.對稱矩陣

對稱矩陣比較特殊，其數(shù)據(jù)元素沿著對角線對稱。

對稱矩陣根據(jù)其對稱性，只存儲其下三角或者上三角就可以了

如果按行序存儲下三角，怎么找到aij的存儲位置呢？

把這個(gè)矩陣存在一維數(shù)組里：

而上三角的元素（i>j），根據(jù)對稱性，aij = aji，可以直接讀取下三角中的aji就可以了，因此按行序存儲下三角時(shí)，aij的下標(biāo)為：

存儲下標(biāo)計(jì)算秘籍：若果用一維數(shù)組s[]存儲（下標(biāo)從0開始），則aij的存儲下標(biāo)k等于aij前面的元素個(gè)數(shù)：

????????????????????????k = aij 前面的元素個(gè)數(shù)

????????????????????????計(jì)算地址：

????????????????????????LOC(aij) = LOC(a11)+k*L (L:每個(gè)元素所占的字節(jié)數(shù))

2.三角矩陣

三角矩陣比較特殊，分為下三角矩陣和上三角矩陣，下三角矩陣是指矩陣的下三角有數(shù)據(jù)，而其余的都是常數(shù)c或者為0.

下三角矩陣按行存儲在一維數(shù)組 s[] 中：

一維數(shù)組存儲：

下三角矩陣按行序存儲時(shí)，aij 的下標(biāo)為：

上三角矩陣按行序存儲時(shí)：

上三角矩陣按行序存儲時(shí)， aij 的下標(biāo)為：

3.對角矩陣

對角矩陣又稱為帶狀矩陣，是指在n*n 的矩陣中，非零元素集中在對角線及其兩側(cè)，共L（奇數(shù)）條對角線的帶狀區(qū)域內(nèi)，稱為L對角矩陣。

為了節(jié)省空間，第一行前面和最后一行后面的d個(gè)0可以不存儲。"掐頭去尾"，需要 L*n - 2*d個(gè)空間。