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

1、第五章 數(shù)組和廣義表5.1 數(shù)組的類型定義數(shù)組的類型定義5.3 矩陣的壓縮存儲矩陣的壓縮存儲 5.2 數(shù)組的順序表示和實(shí)現(xiàn)數(shù)組的順序表示和實(shí)現(xiàn)5.4 廣義表的類型定義廣義表的類型定義5.5 廣義表的存儲結(jié)構(gòu)廣義表的存儲結(jié)構(gòu)ADT Array 數(shù)據(jù)對象數(shù)據(jù)對象： Daj1,j2, .,ji,jn| ji =0,.,bi -1, i=1,2,.,n 數(shù)據(jù)關(guān)系數(shù)據(jù)關(guān)系： RR1, R2, ., Rn Ri | 0 jk bk -1, 1 k n 且k i, 0 ji bi -2, i=2,.,n ADT Array 基本操作基本操作:5.1 數(shù)組的類型定義數(shù)組的類型定義基本操作基本操作：InitAr

2、ray(&A, n, bound1, ., boundn)DestroyArray(&A)Value(A, &e, index1, ., indexn)Assign(&A, e, index1, ., indexn)InitArray(&A, n, bound1, ., boundn) 操作結(jié)果：操作結(jié)果：若維數(shù)若維數(shù) n 和各維長度合法，和各維長度合法， 則構(gòu)造相應(yīng)的數(shù)組則構(gòu)造相應(yīng)的數(shù)組A，并，并 返回返回OK。DestroyArray(&A) 操作結(jié)果：操作結(jié)果：銷毀數(shù)組銷毀數(shù)組A。 Value(A, &e, index1, ., i

3、ndexn) 初始條件：初始條件：A是是n維數(shù)組，維數(shù)組，e為元素變量，為元素變量， 隨后是隨后是n 個(gè)下標(biāo)值。個(gè)下標(biāo)值。 操作結(jié)果：操作結(jié)果：若各下標(biāo)不超界，則若各下標(biāo)不超界，則e賦值為賦值為 所指定的所指定的A 的元素值，并返的元素值，并返 回回OK。 Assign(&A, e, index1, ., indexn) 初始條件：初始條件：A是是n維數(shù)組，維數(shù)組，e為元素為元素 變量，隨后是變量，隨后是n 個(gè)下標(biāo)值。個(gè)下標(biāo)值。 操作結(jié)果：操作結(jié)果：若下標(biāo)不超界，則將若下標(biāo)不超界，則將e的的 值賦給所指定的值賦給所指定的A的元的元 素，并返素，并返OK。二維數(shù)組的定義二維數(shù)組的定義:數(shù)

4、據(jù)對象數(shù)據(jù)對象: : D = aij | 0ib1-1, 0 jb2-1數(shù)據(jù)關(guān)系數(shù)據(jù)關(guān)系: : R = ROW, COL ROW = | 0ib1-2, 0jb2-1 COL = | 0ib1-1, 0 jb2-2二維數(shù)組的定義二維數(shù)組的定義:111110111110100100.nmmmnnnmaaaaaaaaaA5.2 數(shù)組的順序表示和實(shí)現(xiàn)類型特點(diǎn)類型特點(diǎn): （1） 只有引用型操作，沒有加工型操作；只有引用型操作，沒有加工型操作； （2） 數(shù)組是多維的結(jié)構(gòu)，而存儲空間是數(shù)組是多維的結(jié)構(gòu)，而存儲空間是 一個(gè)一維的結(jié)構(gòu)。一個(gè)一維的結(jié)構(gòu)。有兩種順序映象的方式有兩種順序映象的方式: （1）以行序?yàn)?/p>

5、主序以行序?yàn)橹餍?（2）以列序?yàn)橹餍蛞粤行驗(yàn)橹餍?a00 a01 a0n-1 a10 a11 a1n-1 am-10 am-11 am-1n-1 . 按行序?yàn)橹餍虼娣虐葱行驗(yàn)橹餍虼娣?am-1n-1 . am-11 am-10 . a1n -1 . a11 a10 a0n-1 . a01 a0001n-1m*n-1nLOC(i,j) = LOC(0,0) + (nij)L 按列序?yàn)橹餍虼娣虐戳行驗(yàn)橹餍虼娣?1m-1m*n-1m am-1n-1 . a1n-1 a0n-1 . am-11 . a11 a01 am-10 . a10 a00 a00 a01 . a0n-1 a10 a11 . a1

6、n-1 am-10 am-11 am-1n-1 .LOC(i,j) = LOC(0,0) + (mji)L稱為基地址基地址或基址以以“行序?yàn)橹餍蛐行驗(yàn)橹餍颉钡拇鎯τ诚蟮拇鎯τ诚?二維數(shù)組二維數(shù)組A中任一元素中任一元素ai,j 的存儲位置的存儲位置 LOC(i,j) = LOC(0,0) + (nij) L 以以“列序?yàn)橹餍蛄行驗(yàn)橹餍颉钡拇鎯τ诚蟮拇鎯τ诚?二維數(shù)組二維數(shù)組A中任一元素中任一元素ai,j 的存儲位置的存儲位置 LOC(i,j) = LOC(0,0) + (mji) L 5.3.1 特殊矩陣特殊矩陣5.3 矩陣的壓縮存儲矩陣的壓縮存儲 5.3.2 稀疏矩陣稀疏矩陣760007001

7、5000001800000240001400003000000000009120M 以常規(guī)方法，即以二維數(shù)組表示以常規(guī)方法，即以二維數(shù)組表示高階的稀疏矩陣時(shí)產(chǎn)生的高階的稀疏矩陣時(shí)產(chǎn)生的問題問題:(1) 零值元素占了很大空間零值元素占了很大空間;(2) 計(jì)算中進(jìn)行了很多和零值的運(yùn)算。計(jì)算中進(jìn)行了很多和零值的運(yùn)算。(1) 盡可能少存或不存零值元素；盡可能少存或不存零值元素；解決問題的原則解決問題的原則:(2) 盡可能減少?zèng)]有實(shí)際意義的運(yùn)算；盡可能減少?zèng)]有實(shí)際意義的運(yùn)算；(3) 操作方便。操作方便。 即：即： 能盡可能快地找到與下標(biāo)值能盡可能快地找到與下標(biāo)值(i，j)對對應(yīng)的元素，應(yīng)的元素， 能盡可

8、能快地找到同一行或同一列能盡可能快地找到同一行或同一列的非零值元。的非零值元。5.3.1 特殊矩陣 特殊矩陣是指非零元素或零元素的特殊矩陣是指非零元素或零元素的分布有一定規(guī)律的矩陣。分布有一定規(guī)律的矩陣。 對稱矩陣對稱矩陣元素滿足條件元素滿足條件 aij=aji 1=i , j=n的的n階矩陣。階矩陣。按行序?yàn)橹餍颍喊葱行驗(yàn)橹餍颍?a11 a12 . . a1n a21 a22 . . a2n an1 an2 . ann . a11 a21 a22 a31 a32 an1 ann . k=0 1 2 3 4 n(n-1)/2 n(n+1)/2-1 jiijjjijiik, 12/ ) 1(12

9、/ ) 1(，三角矩陣按行序?yàn)橹餍颍喊葱行驗(yàn)橹餍颍篖oc( aij)=Loc(a11)+ i*(i-1)/2 +(j-1)*L a11 0 0 . 0 a21 a22 0 . 0 an1 an2 an3. ann . 0a11 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 a33 a34 0 0 Loc(aij)=Loc(a11)+2(i-1)+(j

10、-1) 按行序?yàn)橹餍颍喊葱行驗(yàn)橹餍颍篴11 a12 a21 a22 a23 ann-1 ann . k=0 1 2 3 4 n(n+1)/2-1 5.3.2 稀疏矩陣稀疏矩陣 假設(shè)假設(shè) m 行行 n 列列的矩陣含的矩陣含 t 個(gè)非個(gè)非零元素零元素，則稱，則稱 為為稀疏因子稀疏因子。 通常認(rèn)為通常認(rèn)為 0.05 的矩陣為稀的矩陣為稀疏矩陣。疏矩陣。nmt稀疏矩陣的壓縮存儲方法稀疏矩陣的壓縮存儲方法:一、三元組順序表一、三元組順序表二、行邏輯鏈接的順序表二、行邏輯鏈接的順序表三、三、 十字鏈表十字鏈表6 7 8 1 2 12 1 3 9 3 1 -3 3 6 14 4 3 24 5 2 18 6

11、1 15 6 4 -7 i j e0 1 2 3 4 5 6 7 87600070015000001800000240001400003000000000009120M一、三元組順序表一、三元組順序表 #define MAXSIZE 12500 typedef struct int i, j; /該非零元的行下標(biāo)和列下標(biāo) ElemType e; / 該非零元的值 Triple; / 三元組類型三元組類型一、三元組順序表一、三元組順序表typedef struct Triple dataMAXSIZE + 1; int mu, nu, tu; TSMatrix; / 稀疏矩陣類型稀疏矩陣類型76

12、00070015000001800000240001400003000000000009120M6700000000014000000007000000024009018000121500300NT如何求轉(zhuǎn)置矩陣？如何求轉(zhuǎn)置矩陣？用常規(guī)的二維數(shù)組表示時(shí)的算法 其時(shí)間復(fù)雜度為其時(shí)間復(fù)雜度為: O(munu) for (col=1; col=nu; +col) for (row=1; row=mu; +row) Tcolrow = Mrowcol;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 i j e0 1 2 3 4

13、5 6 7 8i j e7 6 8 1 3 -3 1 6 15 2 1 12 2 5 18 3 1 9 3 4 24 4 6 -7 6 3 14 0 1 2 3 4 5 6 7 8M.dataT.data解決思路：解決思路： 只要做到只要做到 將矩陣行、列值互換；將矩陣行、列值互換； 將每個(gè)三元組中的將每個(gè)三元組中的i和和j相互調(diào)換；相互調(diào)換； 重排三元組次序，使重排三元組次序，使T.data中中元素以元素以N的行的行(M的列的列)為主序?yàn)橹餍蛉绾瓮瓿芍嘏湃绾瓮瓿芍嘏挪僮鳎坎僮?？方法一：按方法一：按M的列序的列序轉(zhuǎn)置轉(zhuǎn)置6 7 8 1 2 12 1 3 9 3 1 -3 3 6 14 4 3

14、24 5 2 18 6 1 15 6 4 -7 i j e0 1 2 3 4 5 6 7 8M.data7 6 8 i j e0 1 2 3 4 5 6 7 8T.data方法一：按方法一：按M的列序轉(zhuǎn)置的列序轉(zhuǎn)置 按按T.data中三元組次序依次在中三元組次序依次在M.data中找到相應(yīng)的三元組進(jìn)行轉(zhuǎn)置，中找到相應(yīng)的三元組進(jìn)行轉(zhuǎn)置，即按照矩陣即按照矩陣M的列序的列序來進(jìn)行置換。來進(jìn)行置換。 為找到為找到M中每一列所有非零元素，中每一列所有非零元素，需對其三元組表需對其三元組表M.data從第一行起掃從第一行起掃描一遍。由于描一遍。由于M.data中以中以M行序?yàn)橹餍行驗(yàn)橹餍?，所以由此得到的?/p>

15、是序，所以由此得到的恰是T.data中應(yīng)中應(yīng)有的順序有的順序。Status TransposeSMatix(TSMatrix M,TSMatrix &T) /采用三元組表存儲表示，求稀疏矩陣采用三元組表存儲表示，求稀疏矩陣M的轉(zhuǎn)置矩陣的轉(zhuǎn)置矩陣T。 T.mu=M.nu; T.nu=M.mu; T.tu=M.tu; If (T.tu) q=1; for (col=1; col=M.nu; +col) for (p=1; p=M.tu; +p) If (M.datap.j = col) T.dataq.i = M.datap.j; T.dataq.j = M.datap.i; T.data

16、q.e = M.datap.e; +q; return OK;/TransposeSMatrixT(n)=O(nu*tu)方法二：快速轉(zhuǎn)置方法二：快速轉(zhuǎn)置 按按M.data中三元組次序轉(zhuǎn)置，轉(zhuǎn)置結(jié)果中三元組次序轉(zhuǎn)置，轉(zhuǎn)置結(jié)果放入放入T.data中恰當(dāng)位置。中恰當(dāng)位置。 此法關(guān)鍵是要預(yù)先確定此法關(guān)鍵是要預(yù)先確定M中每一列第一中每一列第一個(gè)非零元在個(gè)非零元在T.data中位置，為確定這些位置，中位置，為確定這些位置，轉(zhuǎn)置前應(yīng)先求得轉(zhuǎn)置前應(yīng)先求得M的每一列中非零元個(gè)數(shù)。的每一列中非零元個(gè)數(shù)。cpot1=1;cpotcol=cpotcol-1+numcol-1; (2 col M.nu)7600070

17、015000001800000240001400003000000000009120M6 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 i j e0 1 2 3 4 5 6 7 8 Col 1 2 3 4 5 6 7Numcolcpotcolt1t1t1t1t2t2t2t10 01 3 5 7 8 8 9實(shí)現(xiàn)：實(shí)現(xiàn)：設(shè)兩個(gè)數(shù)組設(shè)兩個(gè)數(shù)組numcol：表示矩陣：表示矩陣M中第中第col列中非列中非零元零元個(gè)數(shù)個(gè)數(shù)。cpotcol：指示指示M中第中第col列第一個(gè)非列第一個(gè)非零元在零元在T.data中位置中位置顯然有顯然有：c

18、pot1=1;cpotcol=cpotcol-1+numcol-1; 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 i j e0 1 2 3 4 5 6 7 8M.datai j e0 1 2 3 4 5 6 7 8T.datacolnumcolcpotcol1122323524715806817907 6 8 1 3 -3 1 6 15 2 1 12 2 5 18 3 1 9 3 4 24 4 6 -7 6 3 14 pppppppp4629753Status FastTransposeSMatrix(TSMatri

19、x M, TSMatrix &T) T.mu = M.nu; T.nu = M.mu; T.tu = M.tu; if (T.tu) for (col=1; col=M.nu; +col) numcol = 0; for (t=1; t=M.tu; +t) +numM.datat.j; cpot1 = 1; for (col=2; col=M.nu; +col) cpotcol = cpotcol-1 + numcol-1; for (p=1; p=M.tu; +p) / 轉(zhuǎn)置矩陣元素 col = M.datap.j; q = cpotcol; T.dataq.i =M.datap.j

20、; T.dataq.j =M.datap.i; T.dataq.e =M.datap.e; +cpotcol; / for / if return OK; / FastTransposeSMatrix 三元組順序表又稱三元組順序表又稱有序的雙下有序的雙下標(biāo)法標(biāo)法，它的特點(diǎn)是，非零元在表中，它的特點(diǎn)是，非零元在表中按行序有序存儲，因此按行序有序存儲，因此便于進(jìn)行依便于進(jìn)行依行順序處理的矩陣運(yùn)算行順序處理的矩陣運(yùn)算。然而，若。然而，若需需隨機(jī)隨機(jī)存取某一行中的非零元，則存取某一行中的非零元，則需從頭開始進(jìn)行查找。需從頭開始進(jìn)行查找。行行邏輯鏈接的順序表邏輯鏈接的順序表 #define MAXMN

21、500 typedef struct Triple dataMAXSIZE + 1; /非零元三元組表 int rposMAXMN + 1; /各行第一個(gè)非零元的位置表各行第一個(gè)非零元的位置表 int mu, nu, tu; RLSMatrix; / 行邏輯鏈接順序表類型二、行邏輯鏈接的順序表二、行邏輯鏈接的順序表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 i j e0 1 2 3 4 5 6 7 87600070015000001800000240001400003000000000009120Mrowrposro

22、w126543133567000200105003M=00420120N=400160Q=Q = M N矩陣乘法的精典算法矩陣乘法的精典算法:Q=MNM是是m1n1矩陣矩陣，N是是m2n2矩陣矩陣,當(dāng)當(dāng)n1=m2時(shí)時(shí)for (i=1; i=m1; +i) for (j=1; j=n2; +j) Qij = 0; for (k=1; k=n1; +k) Qij += Mik * Nkj; 其時(shí)間復(fù)雜度為其時(shí)間復(fù)雜度為: O(m1n2n1) 1 1 3 1 4 5 i j e1 2 3 4 3 1 2 2 2 -1M.data 1 2 2 2 1 1 i j e1 2 3 4 3 2 4 3 1

23、-2N.data 2 1 -1 i j e1 2 3 4 Q.dataparow 1 2 3 ropsarow 1 3 4brow 1 2 3 4ropsbrow 1 2 3 5ccol 1 2ctempt1tpq6p 1 2 6tpp2tq-1tp =5p1tq4 3 2 4 矩陣本身不存在插入和刪除的矩陣本身不存在插入和刪除的操作。但當(dāng)矩陣的非零元素的個(gè)數(shù)操作。但當(dāng)矩陣的非零元素的個(gè)數(shù)和位置在操作過程中變化較大時(shí)，和位置在操作過程中變化較大時(shí)，不適合采用順序存儲結(jié)構(gòu)來表示三不適合采用順序存儲結(jié)構(gòu)來表示三元組的線性表。元組的線性表。三、三、 十字鏈表十字鏈表M.cheadM.rhead3 0

24、 0 50 -1 0 02 0 0 01 1 31 4 52 2-13 1 2 5.4 廣義表的類型定義廣義表的類型定義廣義表是廣義表是遞歸遞歸定義的定義的線性結(jié)構(gòu)線性結(jié)構(gòu)， LS = ( 1, 2, , n )其中：其中： i 或?yàn)樵踊驗(yàn)樵?或?yàn)閺V義表或?yàn)閺V義表例如例如: A = ( ) F = (d, (e) D = (a,(b,c), F) C = (A, D, F) B = (a, B) = (a, (a, (a, , ) ) )5.4 廣義表的類型定義廣義表的類型定義ADT Glist 數(shù)據(jù)對象數(shù)據(jù)對象：Dei | i=1,2,.,n; n0; eiAtomSet 或 eiGLi

25、st, AtomSet為某個(gè)數(shù)據(jù)對象 數(shù)據(jù)關(guān)系：數(shù)據(jù)關(guān)系： LR| ei-1 ,eiD, 2in ADT Glist 基本操作基本操作: 結(jié)構(gòu)的創(chuàng)建和銷毀結(jié)構(gòu)的創(chuàng)建和銷毀 InitGList(&L); DestroyGList(&L); CreateGList(&L, S); CopyGList(&T, L);基本操作基本操作 狀態(tài)函數(shù)狀態(tài)函數(shù) GListLength(L); GListDepth(L); GListEmpty(L); GetHead(L); GetTail(L); 插入和刪除操作插入和刪除操作 InsertFirst_GL(&L, e)

26、; DeleteFirst_GL(&L, &e); 遍歷遍歷 Traverse_GL(L, Visit();廣義表是一個(gè)多層次多層次的線性結(jié)構(gòu)線性結(jié)構(gòu)例如：例如：D=(E, F)其中: E=(a, (b, c) F=(d, (e)DEFa( ) d( )bce廣義表廣義表 LS = ( 1, 2, , n )的的結(jié)構(gòu)特點(diǎn)結(jié)構(gòu)特點(diǎn):1) A=( ) A是是個(gè)空表，長度為零個(gè)空表，長度為零2) B=（e） B只有一個(gè)原子，長度為只有一個(gè)原子，長度為13) C=（e，（，（a，c，d）長度為）長度為25) 廣義表可以是一個(gè)廣義表可以是一個(gè)遞歸遞歸的表。的表。 遞歸表的深度是無窮值，長

27、度是有限值遞歸表的深度是無窮值，長度是有限值。4) E=（a，E）長度為）長度為2，是個(gè)遞歸的表，是個(gè)遞歸的表6) 任何一個(gè)非空廣義表任何一個(gè)非空廣義表 LS = ( 1, 2, , n) 均可分解為均可分解為 表頭表頭 Head(LS) = 1 和和 表尾表尾 Tail(LS) = ( 2, , n) 兩部分。兩部分。例如例如: D = ( E, F ) = (a, (b, c)，F(xiàn) )Head( D ) = E Tail( D ) = ( F )Head( E ) = a Tail( E ) = ( ( b, c) )Head( ( b, c) ) = ( b, c) Tail( ( b,

28、 c) ) = ( )Head( ( b, c) ) = b Tail( ( b, c) ) = ( c )Head( ( c ) ) = c Tail( ( c ) ) = ( )5.5 廣義表的表示方法廣義表的表示方法通常采用頭、尾指針的鏈表結(jié)構(gòu)通常采用頭、尾指針的鏈表結(jié)構(gòu)表結(jié)點(diǎn)表結(jié)點(diǎn):原子結(jié)點(diǎn)：原子結(jié)點(diǎn)：tag=1 hp tptag=0 data（1） 表頭、表尾分析法：表頭、表尾分析法：構(gòu)造存儲結(jié)構(gòu)的兩種分析方法構(gòu)造存儲結(jié)構(gòu)的兩種分析方法: :若表頭為原子，則為若表頭為原子，則為空表空表 ls=NIL非空表非空表 lstag=1 指向表頭的指針指向表尾的指針tag=0 data否則，依次類推。否則，依次類推。例如例