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

1、第四章 數(shù)組數(shù)組可以看成是一種特殊的線性表，即線性表中數(shù)據(jù)元素本身也是一個線性表4.1 數(shù)組的定義和特點定義mnmmnnnmaaaaaaaaaa.212222111211數(shù)組特點v數(shù)組結(jié)構(gòu)固定v數(shù)據(jù)元素同構(gòu)數(shù)組運算v給定一組下標(biāo)，存取相應(yīng)的數(shù)據(jù)元素v給定一組下標(biāo)，修改數(shù)據(jù)元素的值( )( )( )( )( )( )( )( )( )4.2 數(shù)組的順序存儲結(jié)構(gòu)次序約定v以行序為主序v以列序為主序 a11 a12 . a1n a21 a22 . a2n am1 am2 . amn .loc( aij)=loc(a11)+(i-1)n+(j-1)*l 按行序為主序存放按行序為主序存放 amn . a

2、m2 am1 . a2n . a22 a21 a1n . a12 a1101n-1m*n-1n 按列序為主序存放按列序為主序存放01m-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 矩陣的壓縮存儲對稱矩陣jiijjjijiik, 12/ ) 1(12/ ) 1(， a11 a12 . . a1n a21 a22 . . a2n an1 an2 . ann . a11 a21 a2

3、2 a31 a32 an1 ann .k=0 1 2 3 4 n(n-1)/2 n(n+1)/2-1 按行序為主序：三角矩陣 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 按行序為主序：對角矩陣 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 a

4、33 a34 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 按行序為主序：7600070015000001800000240001400003000000000009120mm由(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）唯一確定稀疏矩陣v定義：非零元較零元少，且分布沒有一定規(guī)律的矩陣v壓縮存儲原則：只存矩陣的行列維

5、數(shù)和每個非零元的行列下標(biāo)及其值v稀疏矩陣的壓縮存儲方法l順序存儲結(jié)構(gòu)u三元組表#define m 20typedef struct node int i,j; int v;jd;jd mam;三元組表所需存儲單元個數(shù)為3(t+1)其中t為非零元個數(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ù)和非零元個數(shù)行列下標(biāo)非零元值7600070015000001800000240001400003000000000009120m

6、u帶輔助行向量的二元組表增加一個輔助數(shù)組nram+1,其物理意義是第i行第一個非零元在二元組表中的起始地址（m為行數(shù)）顯然有：nra1=1nrai=nrai-1+第i-1行非零元個數(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ù)和非零元個數(shù)列下標(biāo)和非零元值nra0不用或存矩陣行數(shù)二元組表需存儲單元個數(shù)為2(t+1)+m+17600070015000001800000240001400003000000000009120mu偽地址表示法偽地址：本元

7、素在矩陣中（包括零元素再內(nèi)） 按行優(yōu)先順序的相對位置 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偽地址表示法需存儲單元個數(shù)為2(t+1)7600070015000001800000240001400003000000000009120mu求轉(zhuǎn)置矩陣y問題描述：已知一個稀疏矩陣的三元組表，求該矩陣轉(zhuǎn)置矩陣的三元組表y問題分析一般矩陣轉(zhuǎn)置算法：for(col=0;coln;col+) for(row=0;rowp-col時，p和q右移（2）插入：a、若p=null且q=null，即本行空，則rhr-1=s;b、若p=null,q!=null，即走到行末，則q-right=sc、若c=p-col，則修改p-vald、若ccol且q=null，則在p之前插入s，即s是行鏈表中 第一個結(jié)點，令rhr-1=