目錄
1.一維數(shù)組的存儲(chǔ)結(jié)構(gòu)
2.二維數(shù)組的存儲(chǔ)結(jié)構(gòu)
3.普通矩陣的存儲(chǔ)
4.特殊矩陣的壓縮存儲(chǔ)
（1）對(duì)稱矩陣
（2）三角矩陣
（3）三對(duì)角矩陣
（4）稀疏矩陣的壓縮存儲(chǔ)
1.一維數(shù)組的存儲(chǔ)結(jié)構(gòu)
一維數(shù)組的定義如下：
ElemType a[10];
各數(shù)組元素大小相同，且物理上連續(xù)存放。
數(shù)組元素a[i]的存放地址=LOC+i*sizeof(ElemType)。
注:除非題目特別說明，否則數(shù)組下標(biāo)默認(rèn)從0開始，若題目提醒下標(biāo)從1開始，則存放地址為
LOC+（i-1）*sizeof(ElemType)。
2.二維數(shù)組的存儲(chǔ)結(jié)構(gòu)
二維數(shù)組定義如下：
ElemType b[2][4];
由于內(nèi)存的存儲(chǔ)空間是連續(xù)的，線性的，所以把二維數(shù)組放到內(nèi)存中，有兩種存放方式，行優(yōu)先存放（一行一行地存）和列優(yōu)先存放（一列一列地存）。
M行N列的二維數(shù)組 b[M][N]中，若按行優(yōu)先存儲(chǔ)，則
b[i][j]的存儲(chǔ)地址 = LOC+(i*N+j)*sizeof(ElemType)
若按列優(yōu)先存儲(chǔ)，則
存儲(chǔ)地址 = LOC+(j*M+i)*sizeof(ElemType)
3.普通矩陣的存儲(chǔ)
普通矩陣可用二維數(shù)組存儲(chǔ)，描述矩陣元素時(shí)，行、列號(hào)通常從1開始；而描述數(shù)組時(shí)通常下標(biāo)從0開始。
4.特殊矩陣的壓縮存儲(chǔ)
（1）對(duì)稱矩陣
若n階方陣中任意一個(gè)元素 都有 ?，則該矩陣為對(duì)稱矩陣。
對(duì)稱矩陣進(jìn)行普通存儲(chǔ)：n*n二維數(shù)組，壓縮存儲(chǔ)：只存儲(chǔ)主對(duì)角線+下三角區(qū)。
按行優(yōu)先原則將各元素存入一維數(shù)組中。
存儲(chǔ)結(jié)構(gòu)如下:
可以看到，第一行有1個(gè)元素，第二行有2個(gè)元素，第三行有3個(gè)元素，以此類推，第n行有n個(gè)元素，所以總共有1+2+3.....+n個(gè)元素，數(shù)組大小為
那么怎么通過矩陣下標(biāo)映射到一維數(shù)組的下標(biāo)呢？
例如，按行優(yōu)先的原則，是第幾個(gè)元素？
?第一行有1個(gè)元素，第二行有2個(gè)元素，以此類推，第i-1行就有i-1個(gè)元素，所以是第
個(gè)元素，即
個(gè)元素，由于數(shù)組下標(biāo)是從0開始，所以
的數(shù)組下標(biāo)為k=
。
若要得到上三角某個(gè)元素，那么可以根據(jù)，轉(zhuǎn)換為,進(jìn)而得到與下三角相同的存放規(guī)律。
進(jìn)而其一維數(shù)組下標(biāo)為：
總結(jié)：
按照列優(yōu)先原則進(jìn)行存儲(chǔ)，是第幾個(gè)元素？
如上圖所示，第1列有n個(gè)元素，第2列有n-1個(gè)元素，第j-1列有n-j+2個(gè)元素。
技巧：1+n=n+1，2+(n-1)=n+1,(n-1)+(n-j+2)=n+1
第j列有多少元素，用（行號(hào) - 列號(hào)+1）即可，可以自己驗(yàn)算一下。
所以是第
個(gè)元素
默認(rèn)從0開始的話，數(shù)組下標(biāo)在上面的基礎(chǔ)上減1即可：
由等差數(shù)列易得：
所以的下標(biāo)為：
（2）三角矩陣
下三角矩陣：除了主對(duì)角線和下三角區(qū)，其余的元素都相同。
壓縮存儲(chǔ)：按行優(yōu)先原則將橙色區(qū)元素存入一維數(shù)組中。并在最后一個(gè)位置存儲(chǔ)常量c。
所以一維數(shù)組的長(zhǎng)度：(1+2+3.....n)+1
若按照行優(yōu)先的原則，是第幾個(gè)元素：
下三角和對(duì)稱矩陣的運(yùn)算一樣，對(duì)于上三角，由于上三角每個(gè)元素都是一樣的，所以映射到一維數(shù)組的最后一個(gè)元素，即B[
]
上三角矩陣：除了主對(duì)角線和上三角區(qū)，其余的元素都相同。
按照行優(yōu)先原則，是第幾個(gè)元素？
第1行到第i-1行有
第i行有j-i+1個(gè)元素：列號(hào)(j)-行號(hào)(i)得到該元素在第i行的前面有多少元素。
所以是第
個(gè)元素。
其數(shù)組下標(biāo)為：
由等差數(shù)列的求和公式易得：
要訪問下三角區(qū)的話同理，直接映射到一維數(shù)組的最后一個(gè)位置。
總結(jié):
（3）三對(duì)角矩陣
三對(duì)角矩陣，又稱帶狀矩陣：當(dāng)|i-j|>1時(shí)，有=0(1≤i，j≤n)，通俗點(diǎn)來講就是，主對(duì)角線元素及其上下左右的元素不為0，其余元素的值全為0。
壓縮存儲(chǔ)：按行優(yōu)先(或列優(yōu)先)原則，只存儲(chǔ)帶狀部分。
可以觀察到，帶狀矩陣除了第一行和最后一行是兩個(gè)元素，其余行都是三個(gè)元素。所以要存儲(chǔ)的元素個(gè)數(shù)為：3*n-2
若默認(rèn)數(shù)組下標(biāo)從0開始，那么最后一個(gè)元素的數(shù)組下標(biāo)就為：B[3n-3]
那么按行優(yōu)先的原則，是第幾個(gè)元素?
前 i-1 行共 3(i-1)-1 個(gè)元素。
是第i行的 j-i+2 個(gè)元素。
那么將兩個(gè)數(shù)加起來：是第 2i+j-2個(gè)元素
為什么有j-i+2呢？
由上三角矩陣我們可以分析得，的元素在第i行的前面有j-i個(gè)元素，例如,前面就有：
2-1=1個(gè)元素。
對(duì)比這里，把三角形往前挪一個(gè)位置，可以得到相同的在第i行的前面的元素的個(gè)數(shù)，所以在第i行，前面有j-i+1個(gè)元素，那么加上它本身是第i行第j-i+2個(gè)元素。
我是這么理解的，不管怎么理解，只要自己理解就可以啦~
有些人也會(huì)有疑問，是第i行的 j-i+2 個(gè)元素針對(duì)第一行就不對(duì)呀？其實(shí)結(jié)合前 i-1 行共 3(i-1)-1 個(gè)元素，針對(duì)第一行計(jì)算得到-1，再加上j-i+2 也是對(duì)的結(jié)果。
例如：
根據(jù)式子3(i-1)-1，?前i-1(0)行有-1個(gè)元素，再根據(jù)式子：是第i行的 j-i+2 個(gè)元素，得到
2-1+2=3個(gè)元素，那么最后兩者相加3+(-1)=2，得到的也是正確的結(jié)果，也就是是第2個(gè)元素。
?那么第k+1個(gè)元素，在第幾行?第幾列?
前 i-1 行共 3(i-1)-1個(gè)元素
前 i 行共 3 i-1 個(gè)元素
顯然，3(i-1)-1<?k+1 ≤ 3i-1
不等式解出來為：
，且
因?yàn)閕是行號(hào)，一定是正整數(shù)，將這個(gè)式子向上取整，即 i=
，就可以滿足i"剛好"大于等于某一行。
王道書中的邏輯：第k+1個(gè)元素前有k個(gè)元素，并且k滿足3(i-1)-1 ≤?k?＜?3i-1
不等式解出來為：
，且
將這個(gè)式子向下取整，即 i=?
，即可滿足i“剛好”小于等于某一行。
由于我們之前講到過是第 2i+j-2個(gè)元素，其下標(biāo)默認(rèn)從0開始，就是2i+j-3，所以：k=2i+j-3，所以我們就可以從 k 和 i 推出j的值了。
（4）稀疏矩陣的壓縮存儲(chǔ)
稀疏矩陣就是非零元素遠(yuǎn)遠(yuǎn)少于矩陣元素的個(gè)數(shù)。
壓縮存儲(chǔ)：
1.順序存儲(chǔ)---三元組<行，列，值>，這里存儲(chǔ)的值都是稀疏矩陣中的非0元素。
注：此處行、列標(biāo)從1開始
若用這種方式存儲(chǔ)稀疏矩陣，想要訪問其中的某個(gè)元素，只能順序依次掃描三元組，會(huì)失去隨機(jī)存取的特性。
2.鏈?zhǔn)酱鎯?chǔ)---十字鏈表法。如圖所示，向下域down指向第j列的第一個(gè)元素，向右域 right,指向第i行的第一個(gè)元素。
每個(gè)非0元素會(huì)對(duì)應(yīng)一個(gè)結(jié)點(diǎn)，這個(gè)結(jié)點(diǎn)包括該非0元素所在的行，列以及對(duì)應(yīng)的值；還會(huì)包含兩個(gè)指針，第一個(gè)指針指向同列的下一個(gè)元素，第二個(gè)指針指向同行的下一個(gè)元素?？梢钥磮D自己分析一下。
例如：該結(jié)點(diǎn)第一個(gè)指針為空，表示該列沒有非0元素了；第二個(gè)結(jié)點(diǎn)指向了同行的下一個(gè)元素，即5。
以上公式不建議死記硬背，充分理解之后，考場(chǎng)上也可以推出來的。文章來源：http://www.zghlxwxcb.cn/news/detail-860973.html
公式是沒有錯(cuò)的，附上了自己的理解，如果哪個(gè)公式不懂可以評(píng)論區(qū)或私信我，如果哪里理解錯(cuò)誤，可以評(píng)論區(qū)糾正，若有更好的方法，可以在評(píng)論區(qū)分享出來！謝謝佬們??????文章來源地址http://www.zghlxwxcb.cn/news/detail-860973.html
到了這里，關(guān)于數(shù)據(jù)結(jié)構(gòu)（五）----特殊矩陣的壓縮存儲(chǔ)的文章就介紹完了。如果您還想了解更多內(nèi)容，請(qǐng)?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！
