第五章數(shù)組和廣義表ppt課件

1、第四章 數(shù)組數(shù)組可以看成是一種特殊的線性表，即線性表中數(shù)據(jù)元素本身也是一個(gè)線性表4.1 數(shù)組的定義和特點(diǎn)定義mnmmnnnmaaaaaaaaaA.212222111211數(shù)組特點(diǎn)數(shù)組構(gòu)造固定數(shù)據(jù)元素同構(gòu)數(shù)組運(yùn)算給定一組下標(biāo)，存取相應(yīng)的數(shù)據(jù)元素給定一組下標(biāo)，修正數(shù)據(jù)元素的值( )( )( )( )( )( )( )( )( )4.2 數(shù)組的順序存儲(chǔ)構(gòu)造次序商定以行序?yàn)橹餍蛞粤行驗(yàn)橹餍?a11 a12 . a1n a21 a22 . a2n am1 am2 . amn .Loc( aij)=Loc(a11)+(i-1)n+(j-1)*l 按行序?yàn)橹餍虼娣虐葱行驗(yàn)橹餍虼娣?amn . am2 am1

2、 . a2n . a22 a21 a1n . a12 a1101n-1m*n-1n 按列序?yàn)橹餍虼娣虐戳行驗(yàn)橹餍虼娣?1m-1m*n-1m amn . a2n a1n . am2 . a22 a12 am1 . a21 a11 a11 a12 . a1n a21 a22 . a2n am1 am2 . amn .Loc(aij)=Loc(a11)+(j-1)m+(i-1)*l 4.3 矩陣的緊縮存儲(chǔ)對(duì)稱(chēng)矩陣jiijjjijiik, 12/ ) 1(12/ ) 1(， a11 a12 . . a1n a21 a22 . . a2n an1 an2 . ann . a11 a21 a22 a31

3、a32 an1 ann .k=0 1 2 3 4 n(n-1)/2 n(n+1)/2-1 按行序?yàn)橹餍颍喝蔷仃?a11 0 0 . 0 a21 a22 0 . 0 an1 an2 an3. ann . 0Loc(aij)=Loc(a11)+( +(j-1)*l i(i-1)2a11 a21 a22 a31 a32 an1 ann .k=0 1 2 3 4 n(n-1)/2 n(n+1)/2-1 按行序?yàn)橹餍颍簩?duì)角矩陣 a11 a12 0 . 0 a21 a22 a23 0 0 0 0 an-1,n-2 an-1,n-1 an-1,n 0 0 an,n-1 ann. 0 a32 a33 a34

4、 0 0 Loc(aij)=Loc(a11)+2(i-1)+(j-1) a11 a12 a21 a22 a23 ann-1 ann .k=0 1 2 3 4 n(n-1)/2 n(n+1)/2-1 按行序?yàn)橹餍颍?600070015000001800000240001400003000000000009120MM由(1,2,12), (1,3,9), (3,1,-3), (3,6,14), (4,3,24), (5,2,18), (6,1,15), (6,4,-7) 和矩陣維數(shù)6,7獨(dú)一確定稀疏矩陣定義：非零元較零元少，且分布沒(méi)有一定規(guī)律的矩陣緊縮存儲(chǔ)原那么：只存矩陣的行列維數(shù)和每個(gè)非零元的行

5、列下標(biāo)及其值v稀疏矩陣的緊縮存儲(chǔ)方法v順序存儲(chǔ)構(gòu)造v三元組表#define M 20typedef struct node int i,j; int v;JD;JD maM;三元組表所需存儲(chǔ)單元個(gè)數(shù)為3(t+1)其中t為非零元個(gè)數(shù)6 7 8 1 2 12 1 3 9 3 1 -3 3 6 14 4 3 24 5 2 18 6 1 15 6 4 -7 mai j v0 1 2 3 4 5 6 7 8ma0.i,ma0.j,ma0.v分別存放矩陣行列維數(shù)和非零元個(gè)數(shù)行列下標(biāo)非零元值7600070015000001800000240001400003000000000009120Mu帶輔助行向量的二

6、元組表添加一個(gè)輔助數(shù)組NRAm+1,其物理意義是第i行第一個(gè)非零元在二元組表中的起始地址m為行數(shù)顯然有：NRA1=1NRAi=NRAi-1+第i-1行非零元個(gè)數(shù)(i2)0 1 2 3 4 5 6 NRA1335676 7 8 2 12 3 9 1 -3 6 14 3 24 2 18 1 15 4 -7 maj v0 1 2 3 4 5 6 7 8矩陣列數(shù)和非零元個(gè)數(shù)列下標(biāo)和非零元值NRA0不用或存矩陣行數(shù)二元組表需存儲(chǔ)單元個(gè)數(shù)為2(t+1)+m+17600070015000001800000240001400003000000000009120Mu偽地址表示法偽地址：本元素在矩陣中包括零元素再

7、內(nèi) 按行優(yōu)先順序的相對(duì)位置 6 7 2 12 3 9 15 -3 20 14 24 24 30 18 36 15 39 -7 maaddr v偽地址非零元值矩陣行列維數(shù)0 1 2 3 4 5 6 7 8偽地址表示法需存儲(chǔ)單元個(gè)數(shù)為2(t+1)7600070015000001800000240001400003000000000009120Mu求轉(zhuǎn)置矩陣u問(wèn)題描畫(huà)：知一個(gè)稀疏矩陣的三元組表，求該矩陣轉(zhuǎn)置矩陣的三元組表u問(wèn)題分析u普通矩陣轉(zhuǎn)置算法：for(col=0;coln;col+) for(row=0;rowp-col時(shí)，p和q右移2插入：a、假設(shè)p=NULL且q=NULL，即本行空，那么rhr-1=s;b、假設(shè)p=NULL,q!=NULL，即走到行末，那么q-right=sc、假設(shè)c=p-col，那么修正p-vald、假設(shè)ccol且q=NULL，那么在p之前插入s，即s是行鏈表中 第一個(gè)結(jié)點(diǎn)，令rhr-1=s;