目錄

11.特殊矩陣的壓縮存儲(chǔ)

（1）.一維數(shù)組的儲(chǔ)存結(jié)構(gòu)

（2）.二維數(shù)組的存儲(chǔ)結(jié)構(gòu)

（3）.普通矩陣的存儲(chǔ)

（4）.特殊矩陣的壓縮存儲(chǔ)

? ? ? ? i.對(duì)稱(chēng)矩陣

? ? ? ? ii.三角矩陣

? ? ? ? iii.三對(duì)角矩陣

? ? ? ? iiii.稀疏矩陣

---

11.特殊矩陣的壓縮存儲(chǔ)

（1）.一維數(shù)組的儲(chǔ)存結(jié)構(gòu)

? ? ? ? int a[10];

? ? ? ? 一維數(shù)組的地址是連續(xù)的，只要知道了起始地址（LOC，默認(rèn)是a[0]的地址），就可以知道所有元素的地址。

????????

? ? ? ? a[i] 地址的計(jì)算 ：LOC + i * sizeof(int) .

? ? ? ? 注意：有時(shí)候給出的LOC可能不是a[0] 的，此時(shí)，就要在上式子的i 中減去，如給出的是a[1]的，則計(jì)算公式變?yōu)?LOC + (i - 1) * sizeof(int).

（2）.二維數(shù)組的存儲(chǔ)結(jié)構(gòu)

? ? ? ? int b[2][4]

? ? ? ? 二維數(shù)組在內(nèi)存中有兩種存儲(chǔ)方法，行優(yōu)先和列優(yōu)先。

? ? ? ? 當(dāng)然，從邏輯視角上看，將數(shù)據(jù)配列成矩陣的樣式，更方便進(jìn)行操作。

? ? ? ? 有int b[M][N]，b[0][0] 的地址為L(zhǎng)OC，則b[i][j]

? ? ? ? 行優(yōu)先：LOC + (i*N?+ j)*sizeof(int)

? ? ? ? 列優(yōu)先：LOC + (j*M?+ i)*sizeof(int)?

（3）.普通矩陣的存儲(chǔ)

? ? ? ? 一般是用二維數(shù)組，

? ? ? ? 需要注意的是，矩陣的下標(biāo)是從(1, 1) 開(kāi)始的，數(shù)組是從(0, 0) 開(kāi)始的。

（4）.特殊矩陣的壓縮存儲(chǔ)

? ? ? ? i.對(duì)稱(chēng)矩陣

? ? ? ? · 是方陣（n階），

? ? ? ? · 恒有 aij == aji，

? ? ? ? 因?yàn)閷?duì)稱(chēng)，所以可以只存儲(chǔ)下三角區(qū)和對(duì)稱(chēng)軸（或上三角區(qū)和對(duì)稱(chēng)軸）（這樣就是所謂的壓縮存儲(chǔ)）

????????

????????按行優(yōu)先將各元素存入一維數(shù)組（也可以列優(yōu)先），

????????如此便要思考，

????????數(shù)組的大小，顯然，第一行一個(gè)元素，第二行兩個(gè)元素...第N行N個(gè)元素，總數(shù)就是n*(n+1)/2.

????????數(shù)據(jù)的調(diào)用，因?yàn)榫仃嚨南聵?biāo)與數(shù)組的下標(biāo)規(guī)則不同，可以寫(xiě)一個(gè)簡(jiǎn)單的映射函數(shù)進(jìn)行轉(zhuǎn)換

? ? ? ? aij => b[k]

? ? ? ? 總結(jié)上圖，可知

????????k = (i+1)*i/2 + j - 1 ,

????????即當(dāng)前元素行數(shù)往上為等差數(shù)列求和，再加上列數(shù)，就是在數(shù)組中的第幾個(gè)元素，再減一，就成了數(shù)組下標(biāo)。（如果，題干給出的數(shù)組起始下標(biāo)為1，k就不需要減去那個(gè)1）

? ? ? ? ii.三角矩陣

????????

? ? ? ? 壓縮存儲(chǔ)策略：儲(chǔ)存aij的三角區(qū)，將常數(shù)儲(chǔ)存在數(shù)組最后一位。（以下三角為例）

? ? ? ? 數(shù)組大小，n*(n+1)/2 + 1.

? ? ? ? aij的ij 與數(shù)組下標(biāo)之間的相互轉(zhuǎn)換與上文相同。

? ? ? ? 獲取常數(shù)項(xiàng)，數(shù)組下標(biāo)就是 n*(n+1)/2。

? ? ? ? ?值得一提的，在上三角中，求aij是數(shù)組中的第幾個(gè)元素，觀察圖可知，每行的元素?cái)?shù)由N個(gè)依次遞減。所以，aij 前面有 [n + ... + (n - i + 2)] + (j - i)個(gè)元素，中括號(hào)里的是此行往上的，那個(gè)j-i是當(dāng)前行內(nèi)aij 之前的元素。

? ? ? ? iii.三對(duì)角矩陣

? ? ? ?以行優(yōu)先為例，

????????數(shù)組大小，3n - 2。

? ? ? ? 數(shù)組下標(biāo)（對(duì)于aij），前(i - 1)行，有3(i - 1) - 1個(gè)元素(每行有三個(gè)元素，但第一行只有兩個(gè))；第i 行中，aij是第j?- i?+ 2個(gè)元素，所以aij 就是第2i + j - 2(前后相加)。

? ? ? ? k = 2i + j - 3

? ? ? ? 由數(shù)組下標(biāo)逆推矩陣下標(biāo)ij

? ? ? ? 已知b[k]

? ? ? ? 是第k + 1個(gè)元素，在前i-1行，與前i行之間，3(i - 1) - 1 < k + 1 <= 3i - 1

? ? ? ? i >= (k + 2)/3，左式算出結(jié)果后向上取整就是i 值

? ? ? ? （向上取整：如1.2，向上取整就是2，向下就是1）?

? ? ? ? iiii.稀疏矩陣

? ? ? ? 壓縮策略：

? ? ? ? ?① 順序存儲(chǔ)------設(shè)置一個(gè)類(lèi)，其中包含三個(gè)數(shù)組，分別存儲(chǔ)i、j、非零數(shù)據(jù)。

? ? ? ? ② 十字鏈表法----此為鏈?zhǔn)酱鎯?chǔ)，

? ? ? ? 結(jié)點(diǎn)中，包含行、列、值以及兩個(gè)指針。

? ? ? ? 兩個(gè)指針?lè)謩e指向同一列的下一個(gè)結(jié)點(diǎn)和同一行的下一個(gè)結(jié)點(diǎn)。