3-5矩陣的壓縮存儲(chǔ)v第三章棧、隊(duì)列和數(shù)組對(duì)稱矩陣的壓縮存儲(chǔ)三角矩陣的壓縮存儲(chǔ)對(duì)角矩陣的壓縮存儲(chǔ)學(xué)什么？稀疏矩陣的壓縮存儲(chǔ)特殊矩陣的壓縮存儲(chǔ)3-5-1特殊矩陣的壓縮存儲(chǔ)v第三章棧、隊(duì)列和數(shù)組特殊矩陣什么是特殊矩陣？

特殊矩陣：矩陣中很多值相同的元素并且它們的分布有一定的規(guī)律特殊矩陣如何壓縮存儲(chǔ)？為值相同的元素分配一個(gè)存儲(chǔ)空間特殊矩陣壓縮存儲(chǔ)后有什么要求嗎？保證隨機(jī)存取，即在O(1)時(shí)間內(nèi)尋址3647862842481697460582957A＝對(duì)稱矩陣特點(diǎn)：aij=aji如何壓縮存儲(chǔ)對(duì)稱矩陣呢？只存儲(chǔ)下三角部分的元素對(duì)稱矩陣aij在一維數(shù)組中的序號(hào)=

i×(i-1)/2+j∵一維數(shù)組下標(biāo)從0開(kāi)始∴aij在一維數(shù)組中的下標(biāo)k=i×(i-1)/2+j-1

1…

i

n1…j…n

aij第2行第n行第1行第3行

a11

a21

a22

a31

a32

a33

aij…

an1

an2…ann…012345kn(n+1)/2-1對(duì)稱矩陣下三角中的元素aij（i≥j）：k＝i×(i-1)/2＋j-1壓縮存儲(chǔ)后的尋址方法上三角中的元素aij（i＜j），k＝j(luò)×(j-1)/2＋i

-1如何壓縮存儲(chǔ)三角矩陣呢？3c

c

c

c62c

c

c481c

c7460c82957(a)下三角矩陣34810c2946c

c１57c

c

c

08c

c

c

c7(b)上三角矩陣相同的常數(shù)只存儲(chǔ)一個(gè)下（上）三角部分的元素三角矩陣下三角矩陣的壓縮存儲(chǔ)第2行第n行第1行第3行

a11

a21

a22

a31

a32

a33

aij…

an1

an2…ann…012345kn(n+1)/2c下三角中的元素aij（i≥j）：k＝i×(i

-1)/2+j-1上三角中的元素aij（i＜j）：k＝n×(n+1)/2下三角矩陣壓縮存儲(chǔ)后的尋址方法上三角矩陣的壓縮存儲(chǔ)請(qǐng)仿此給出三角矩陣對(duì)角矩陣對(duì)角矩陣：所有非零元素都集中在以主對(duì)角線為中心的帶狀區(qū)域中，所有其他元素都為零。

a11a120

00a21a22

a23000a32

a33a34000

a43

a44

a45000a54

a55A=如何壓縮存儲(chǔ)對(duì)角矩陣呢？只存儲(chǔ)非零元素

元素aij在一維數(shù)組中的序號(hào)=2+3(i-2)+(j-i+2)=2i+j-2∵一維數(shù)組下標(biāo)從0開(kāi)始∴元素aij在一維數(shù)組中的下標(biāo)=

2i+j-3a11a12000a21a22

a23000a32a33

a34000

a43a44

a45

000a54a55A=

a11a12a21a22a23a32a33a34a43a44a45a54a550123456789101112第1行第2行第3行對(duì)角矩陣3-5-2稀疏矩陣的壓縮存儲(chǔ)v第三章棧、隊(duì)列和數(shù)組稀疏矩陣什么是稀疏矩陣？

稀疏矩陣：矩陣中有很多零元素，并且分布沒(méi)有規(guī)律稀疏矩陣如何壓縮存儲(chǔ)？只存儲(chǔ)非零元素，零元素不分配存儲(chǔ)空間如何只存儲(chǔ)非零元素？

三元組：（行號(hào)，列號(hào)，非零元素值）300700

10200000000008A=如何存儲(chǔ)三元組表？

三元組表：將稀疏矩陣的非零元素對(duì)應(yīng)的三元組所構(gòu)成的集合，按行優(yōu)先的順序排列成一個(gè)線性表((1,1,3),(1,4,7),(2,3,1),(3,1,2),(5,4,8))template<typenameDataType>structelement{

introw,col;

DataTypeitem};

三元組：（行號(hào)，列號(hào)，非零元素值）稀疏矩陣300700

10200000000008A=

三元組順序表：采用順序存儲(chǔ)結(jié)構(gòu)存儲(chǔ)三元組表三元組順序表三元組順序表需要預(yù)留存儲(chǔ)單元嗎？300700

10200000000008A=稀疏矩陣的修改操作三元組表的插入/刪除操作((1,1,3),(1,4,7),(2,3,1),(3,1,2),(5,4,8))

113147231312548空空空閑閑閑rowcolitem01234MaxTerm-1

5（非零元個(gè)數(shù)）

5（矩陣的行數(shù)）

6（矩陣的列數(shù)）能唯一表示稀疏矩陣嗎？constintMaxTerm=100;structSparseMatrix{elementdata[MaxTerm];intmu,nu,tu;};三元組順序表

113147231312548空空空閑閑閑rowcolitem01234MaxTerm-1

5（非零元個(gè)數(shù)）

5（矩陣的行數(shù)）

6（矩陣的列數(shù)）十字鏈表十字鏈表：采用鏈接存儲(chǔ)結(jié)構(gòu)存儲(chǔ)三元組表三元組順序表不適合什么情況？稀疏矩陣的加法、乘法等操作，非零元素的個(gè)數(shù)及位置都會(huì)發(fā)生變化，則在三元組順序表中就要進(jìn)行插入和刪除操作，順序存儲(chǔ)就十分不便rowcolitemdown