第4章專題3矩陣的壓縮存儲(chǔ)

1、數(shù)據(jù)結(jié)構(gòu)（數(shù)據(jù)結(jié)構(gòu)（C+版）第版）第2版版清華大學(xué)出版社清華大學(xué)出版社專題專題3：矩陣的壓縮存儲(chǔ)：矩陣的壓縮存儲(chǔ)123對(duì)稱矩陣的壓縮存儲(chǔ)對(duì)稱矩陣的壓縮存儲(chǔ)及尋址及尋址三角矩陣的壓縮存儲(chǔ)及尋址三角矩陣的壓縮存儲(chǔ)及尋址對(duì)角矩陣的壓縮存儲(chǔ)及尋址對(duì)角矩陣的壓縮存儲(chǔ)及尋址4稀疏矩陣的壓縮存儲(chǔ)稀疏矩陣的壓縮存儲(chǔ)5矩陣壓縮存儲(chǔ)的基本思想矩陣壓縮存儲(chǔ)的基本思想數(shù)據(jù)結(jié)構(gòu)（數(shù)據(jù)結(jié)構(gòu)（C+版）第版）第2版版清華大學(xué)出版社清華大學(xué)出版社4.3 矩陣的壓縮存儲(chǔ)矩陣的壓縮存儲(chǔ)p 特殊矩陣：特殊矩陣：矩陣中很多值相同的元素并且它們的矩陣中很多值相同的元素并且它們的分布有一定的規(guī)律。分布有一定的規(guī)律。p 稀疏矩陣：稀疏矩陣：

2、矩陣中有很多零元素。矩陣中有很多零元素。p 壓縮存儲(chǔ)的基本思想是：壓縮存儲(chǔ)的基本思想是： 為多個(gè)值為多個(gè)值相同相同的元素只分配的元素只分配一個(gè)一個(gè)存儲(chǔ)空間；存儲(chǔ)空間； 對(duì)對(duì)零零元素元素不分配不分配存儲(chǔ)空間。存儲(chǔ)空間。 特殊矩陣和稀疏矩陣特殊矩陣和稀疏矩陣數(shù)據(jù)結(jié)構(gòu)（數(shù)據(jù)結(jié)構(gòu)（C+版）第版）第2版版清華大學(xué)出版社清華大學(xué)出版社特殊矩陣的壓縮存儲(chǔ)特殊矩陣的壓縮存儲(chǔ)對(duì)稱矩陣對(duì)稱矩陣 3647862842481697460582957A對(duì)稱矩陣特點(diǎn)：對(duì)稱矩陣特點(diǎn)：aij=aji如何壓縮存儲(chǔ)？如何壓縮存儲(chǔ)？只存儲(chǔ)下三角部分的元素。只存儲(chǔ)下三角部分的元素。4.3 矩陣的壓縮存儲(chǔ)矩陣的壓縮存儲(chǔ)數(shù)據(jù)結(jié)構(gòu)（數(shù)據(jù)結(jié)

3、構(gòu)（C+版）第版）第2版版清華大學(xué)出版社清華大學(xué)出版社(a) 下三角矩陣下三角矩陣 (b) 存儲(chǔ)說(shuō)明存儲(chǔ)說(shuō)明 (c) 計(jì)算方法計(jì)算方法aij在一維數(shù)組中的序號(hào)在一維數(shù)組中的序號(hào)=陰影部分的面積陰影部分的面積= i( (i+1) )/2+ j一維數(shù)組下標(biāo)從一維數(shù)組下標(biāo)從0開(kāi)始開(kāi)始aij在一維數(shù)組中的下標(biāo)在一維數(shù)組中的下標(biāo)k= i( (i+1) )/2+ j-1 1 i n1 j n aij每行元素個(gè)數(shù)每行元素個(gè)數(shù)12i-1aij在本行中的序號(hào)在本行中的序號(hào)aij第第1行行第第2行行第第i-1行行對(duì)稱矩陣的壓縮存儲(chǔ)對(duì)稱矩陣的壓縮存儲(chǔ) 4.3 矩陣的壓縮存儲(chǔ)矩陣的壓縮存儲(chǔ)數(shù)據(jù)結(jié)構(gòu)（數(shù)據(jù)結(jié)構(gòu)（C+版）

4、第版）第2版版清華大學(xué)出版社清華大學(xué)出版社對(duì)于下三角中的元素對(duì)于下三角中的元素aij（ij），在數(shù)組，在數(shù)組SA中的下標(biāo)中的下標(biāo)k與與i、j的關(guān)系為：的關(guān)系為：ki(i1)/2j -1。上三角中的元素上三角中的元素aij（ij），），因?yàn)橐驗(yàn)閍ijaji，則訪問(wèn)和則訪問(wèn)和它對(duì)應(yīng)的元素它對(duì)應(yīng)的元素aji即可，即：即可，即：kj(j1)/2i -1 。對(duì)稱矩陣的壓縮存儲(chǔ)對(duì)稱矩陣的壓縮存儲(chǔ) 第第1行行第第n-1行行第第0行行 a11 a21 a22 a31 a32 a33 aij a n1 an2 ann 第第2行行0 1 2 3 4 5 k n(n+1)/2-14.3 矩陣的壓縮存儲(chǔ)矩陣的壓縮存儲(chǔ)

5、數(shù)據(jù)結(jié)構(gòu)（數(shù)據(jù)結(jié)構(gòu)（C+版）第版）第2版版清華大學(xué)出版社清華大學(xué)出版社特殊矩陣的壓縮存儲(chǔ)特殊矩陣的壓縮存儲(chǔ)三角矩陣三角矩陣 3 cc c c6 2c c c4 81 c c7 46 0 c8 29 5 7(a)下三角矩陣下三角矩陣3 4 8 1 0c2 9 4 6cc 5 7cc c 0 8cc c c 7(b)上三角矩陣上三角矩陣如何壓縮存儲(chǔ)？如何壓縮存儲(chǔ)？只存儲(chǔ)上三角（或下三角）部分的元素。只存儲(chǔ)上三角（或下三角）部分的元素。4.3 矩陣的壓縮存儲(chǔ)矩陣的壓縮存儲(chǔ)數(shù)據(jù)結(jié)構(gòu)（數(shù)據(jù)結(jié)構(gòu)（C+版）第版）第2版版清華大學(xué)出版社清華大學(xué)出版社矩陣中任一元素矩陣中任一元素aij在在數(shù)組數(shù)組中的下標(biāo)中的下

6、標(biāo)k與與i、j的對(duì)應(yīng)關(guān)系：的對(duì)應(yīng)關(guān)系：i( (i1) )/2j-1 當(dāng)當(dāng)ijn( (n1) )/2 當(dāng)當(dāng)ijk=下三角矩陣的壓縮存儲(chǔ)下三角矩陣的壓縮存儲(chǔ)0 1 2 3 4 5 k n(n+1)/2第第1行行第第0行行 a11 a21 a22 a31 a32 aij ann 第第2行行 c a33存儲(chǔ)存儲(chǔ)下三角下三角元素元素對(duì)角線上方的常數(shù)對(duì)角線上方的常數(shù)只存一個(gè)只存一個(gè)4.3 矩陣的壓縮存儲(chǔ)矩陣的壓縮存儲(chǔ)數(shù)據(jù)結(jié)構(gòu)（數(shù)據(jù)結(jié)構(gòu)（C+版）第版）第2版版清華大學(xué)出版社清華大學(xué)出版社矩陣中任一元素矩陣中任一元素aij在在數(shù)組數(shù)組中的下標(biāo)中的下標(biāo)k與與i、j的對(duì)應(yīng)關(guān)系：的對(duì)應(yīng)關(guān)系： (i-1)(2n-i+

7、2)/2+j-i 當(dāng)當(dāng)ijn( (n1) ) /2 當(dāng)當(dāng)ijk=上三角矩陣的壓縮存儲(chǔ)上三角矩陣的壓縮存儲(chǔ)存儲(chǔ)存儲(chǔ)上三角上三角元素元素對(duì)角線上方的常數(shù)對(duì)角線上方的常數(shù)只存一個(gè)只存一個(gè)4.3 矩陣的壓縮存儲(chǔ)矩陣的壓縮存儲(chǔ)數(shù)據(jù)結(jié)構(gòu)（數(shù)據(jù)結(jié)構(gòu)（C+版）第版）第2版版清華大學(xué)出版社清華大學(xué)出版社特殊矩陣的壓縮存儲(chǔ)特殊矩陣的壓縮存儲(chǔ)對(duì)角矩陣對(duì)角矩陣 對(duì)角矩陣：對(duì)角矩陣：所有非零元素都集中在以主對(duì)角線為中心所有非零元素都集中在以主對(duì)角線為中心的帶狀區(qū)域中，除了主的帶狀區(qū)域中，除了主對(duì)角線和它的上下方若干條對(duì)對(duì)角線和它的上下方若干條對(duì)角線的元素外，所有其他元素都為零。角線的元素外，所有其他元素都為零。 a11

8、 a12 0 0 0a21 a22 a23 0 00 a32 a33a34 00 0 a43a44 a450 0 0 a54 a55A=4.3 矩陣的壓縮存儲(chǔ)矩陣的壓縮存儲(chǔ)數(shù)據(jù)結(jié)構(gòu)（數(shù)據(jù)結(jié)構(gòu)（C+版）第版）第2版版清華大學(xué)出版社清華大學(xué)出版社按行按行存儲(chǔ)存儲(chǔ) 元素元素aij在一維數(shù)組中的序號(hào)在一維數(shù)組中的序號(hào)=2 + 3( (i2) )+( ( ji + 2) )=2i+ j -2 一維數(shù)組下標(biāo)從一維數(shù)組下標(biāo)從0開(kāi)始開(kāi)始元素元素aij在一維數(shù)組中的下標(biāo)在一維數(shù)組中的下標(biāo)= 2i+ j -3(b) 尋址的計(jì)算方法尋址的計(jì)算方法(c) 壓縮到一維數(shù)組中壓縮到一維數(shù)組中a11 a12 a21 a22

9、 a23 a32 a33 a34 a43 a44 a45 a54 a550 1 2 3 4 5 6 7 8 9 10 11 12對(duì)角矩陣的壓縮存儲(chǔ)對(duì)角矩陣的壓縮存儲(chǔ)(a) 三對(duì)角矩陣三對(duì)角矩陣 0 0 0 0 00 00 0 0 0 0 A=a11 a12a21 a22 a23a32 a33 a34a43 a44 a45a54 a554.3 矩陣的壓縮存儲(chǔ)矩陣的壓縮存儲(chǔ)數(shù)據(jù)結(jié)構(gòu)（數(shù)據(jù)結(jié)構(gòu)（C+版）第版）第2版版清華大學(xué)出版社清華大學(xué)出版社稀疏矩陣的壓縮存儲(chǔ)稀疏矩陣的壓縮存儲(chǔ) 15 0 0 0 0 0 0 11 0 0 0 0 0 0 0 6 0 0 0 0 0 0 0 0 9 0 0 0 0

10、0A=如何只存儲(chǔ)非零元素？如何只存儲(chǔ)非零元素？注意：稀疏矩陣中的非零元素的分布沒(méi)有規(guī)律。注意：稀疏矩陣中的非零元素的分布沒(méi)有規(guī)律。4.3 矩陣的壓縮存儲(chǔ)矩陣的壓縮存儲(chǔ)數(shù)據(jù)結(jié)構(gòu)（數(shù)據(jù)結(jié)構(gòu)（C+版）第版）第2版版清華大學(xué)出版社清華大學(xué)出版社template struct element int row, col; /行號(hào)，列號(hào)行號(hào)，列號(hào) DataType item /非零元素值非零元素值;將稀疏矩陣中的每個(gè)非零元素表示為將稀疏矩陣中的每個(gè)非零元素表示為：( (行號(hào)，列號(hào)，非零元素值行號(hào)，列號(hào)，非零元素值) )三元組三元組稀疏矩陣的壓縮存儲(chǔ)稀疏矩陣的壓縮存儲(chǔ) 定義三元組定義三元組：4.3 矩陣的壓縮

11、存儲(chǔ)矩陣的壓縮存儲(chǔ)數(shù)據(jù)結(jié)構(gòu)（數(shù)據(jù)結(jié)構(gòu)（C+版）第版）第2版版清華大學(xué)出版社清華大學(xué)出版社三元組表三元組表：將稀疏矩陣的非零元素對(duì)應(yīng)的三元組所將稀疏矩陣的非零元素對(duì)應(yīng)的三元組所構(gòu)成的集合，構(gòu)成的集合，按行優(yōu)先的順序排列成一個(gè)線性表。按行優(yōu)先的順序排列成一個(gè)線性表。稀疏矩陣的壓縮存儲(chǔ)稀疏矩陣的壓縮存儲(chǔ) 三元組表三元組表( (0,0,15), (1,1,11), (2,3,6), (4,0,9) )15 0 0 0 0 0 0 11 0 0 0 0 0 0 0 6 0 0 0 0 0 0 0 0 9 0 0 0 0 0A=如何存儲(chǔ)三元組表？如何存儲(chǔ)三元組表？4.3 矩陣的壓縮存儲(chǔ)矩陣的壓縮存儲(chǔ)數(shù)據(jù)結(jié)

12、構(gòu)（數(shù)據(jù)結(jié)構(gòu)（C+版）第版）第2版版清華大學(xué)出版社清華大學(xué)出版社稀疏矩陣的壓縮存儲(chǔ)稀疏矩陣的壓縮存儲(chǔ)三元組順序表三元組順序表采用順序存儲(chǔ)結(jié)構(gòu)存儲(chǔ)三元組表采用順序存儲(chǔ)結(jié)構(gòu)存儲(chǔ)三元組表15 0 0 22 0 - -15 0 11 3 0 0 0 0 0 0 6 0 0 0 0 0 0 0 0 91 0 0 0 0 0A=三元組順序表是否三元組順序表是否需要預(yù)留存儲(chǔ)空間？需要預(yù)留存儲(chǔ)空間？稀疏矩陣的修改操作稀疏矩陣的修改操作三元組順序表的插入三元組順序表的插入/ /刪除操作刪除操作4.3 矩陣的壓縮存儲(chǔ)矩陣的壓縮存儲(chǔ)數(shù)據(jù)結(jié)構(gòu)（數(shù)據(jù)結(jié)構(gòu)（C+版）第版）第2版版清華大學(xué)出版社清華大學(xué)出版社稀疏矩陣的壓縮

13、存儲(chǔ)稀疏矩陣的壓縮存儲(chǔ)三元組順序表三元組順序表采用順序存儲(chǔ)結(jié)構(gòu)存儲(chǔ)三元組表采用順序存儲(chǔ)結(jié)構(gòu)存儲(chǔ)三元組表 1 1 15 1 4 22 1 6 - -15 2 2 11 2 3 3 3 4 6 5 1 91 空空 空空 空空 閑閑 閑閑 閑閑row col item0123456MaxTerm- -115 0 0 22 0 - -15 0 11 3 0 0 0 0 0 0 6 0 0 0 0 0 0 0 0 91 0 0 0 0 0A=7（非零元個(gè)數(shù)）（非零元個(gè)數(shù)）是否對(duì)應(yīng)惟一的稀疏矩陣？是否對(duì)應(yīng)惟一的稀疏矩陣？5（矩陣的行數(shù)）（矩陣的行數(shù)）6（矩陣的列數(shù)）（矩陣的列數(shù)）4.3 矩陣的壓縮存儲(chǔ)矩陣

14、的壓縮存儲(chǔ)數(shù)據(jù)結(jié)構(gòu)（數(shù)據(jù)結(jié)構(gòu)（C+版）第版）第2版版清華大學(xué)出版社清華大學(xué)出版社存儲(chǔ)結(jié)構(gòu)定義：存儲(chǔ)結(jié)構(gòu)定義： const int MaxTerm=100; template struct SparseMatrix DataType dataMaxTerm; /存儲(chǔ)非零元素存儲(chǔ)非零元素 int mu, nu, tu; /行數(shù)、列數(shù)、非零元個(gè)數(shù)行數(shù)、列數(shù)、非零元個(gè)數(shù) ;稀疏矩陣的壓縮存儲(chǔ)稀疏矩陣的壓縮存儲(chǔ)三元組順序表三元組順序表4.3 矩陣的壓縮存儲(chǔ)矩陣的壓縮存儲(chǔ)數(shù)據(jù)結(jié)構(gòu)（數(shù)據(jù)結(jié)構(gòu)（C+版）第版）第2版版清華大學(xué)出版社清華大學(xué)出版社采用采用鏈接鏈接存儲(chǔ)結(jié)構(gòu)存儲(chǔ)三元組表，每個(gè)非零元素對(duì)應(yīng)存儲(chǔ)結(jié)構(gòu)存儲(chǔ)

15、三元組表，每個(gè)非零元素對(duì)應(yīng)的三元組存儲(chǔ)為一個(gè)鏈表結(jié)點(diǎn)，結(jié)構(gòu)為：的三元組存儲(chǔ)為一個(gè)鏈表結(jié)點(diǎn)，結(jié)構(gòu)為： rowcolitemdownrightrow：存儲(chǔ)非零元素的行號(hào)存儲(chǔ)非零元素的行號(hào)col：存儲(chǔ)非零元素的列號(hào)存儲(chǔ)非零元素的列號(hào)item：存儲(chǔ)非零元素的值存儲(chǔ)非零元素的值right：指針域，指向同一行中的下一個(gè)三元組指針域，指向同一行中的下一個(gè)三元組down：指針域，指向同一列中的下一個(gè)三元組指針域，指向同一列中的下一個(gè)三元組稀疏矩陣的壓縮存儲(chǔ)稀疏矩陣的壓縮存儲(chǔ)十字鏈表十字鏈表4.3 矩陣的壓縮存儲(chǔ)矩陣的壓縮存儲(chǔ)數(shù)據(jù)結(jié)構(gòu)（數(shù)據(jù)結(jié)構(gòu)（C+版）第版）第2版版清華大學(xué)出版社清華大學(xué)出版社 3 1 2M=3 0 0 50 1 0 02 0 0 0 1 1 3 1 4 5 2 2 1稀疏矩陣的壓縮存儲(chǔ)稀疏矩陣的壓縮存儲(chǔ)十字鏈表十字鏈表4.3 矩陣的壓縮存儲(chǔ)矩陣的壓縮