數(shù)組與廣義表相關(guān)知識(shí)

1、數(shù)組與廣義表相關(guān)知識(shí)學(xué)習(xí)提要：學(xué)習(xí)提要： 1.了解數(shù)組的兩種存儲(chǔ)表示方法，并掌握數(shù)組在了解數(shù)組的兩種存儲(chǔ)表示方法，并掌握數(shù)組在以行為主的存儲(chǔ)結(jié)構(gòu)中的地址計(jì)算方法。以行為主的存儲(chǔ)結(jié)構(gòu)中的地址計(jì)算方法。 2.掌握對(duì)特殊矩陣進(jìn)行壓縮存儲(chǔ)時(shí)的下標(biāo)變掌握對(duì)特殊矩陣進(jìn)行壓縮存儲(chǔ)時(shí)的下標(biāo)變換公式。換公式。 3.了解稀疏矩陣的兩種壓縮存儲(chǔ)方法的特點(diǎn)和適了解稀疏矩陣的兩種壓縮存儲(chǔ)方法的特點(diǎn)和適用范圍，領(lǐng)會(huì)以三元組表示稀疏矩陣時(shí)進(jìn)行矩陣運(yùn)用范圍，領(lǐng)會(huì)以三元組表示稀疏矩陣時(shí)進(jìn)行矩陣運(yùn)算采用的處理方法。算采用的處理方法。 4.掌握廣義表的結(jié)構(gòu)特點(diǎn)及其存儲(chǔ)表示方法。掌握廣義表的結(jié)構(gòu)特點(diǎn)及其存儲(chǔ)表示方法。ADT Arra

2、y 數(shù)據(jù)對(duì)象數(shù)據(jù)對(duì)象： 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ù)組的類型定義基本操作基本操作：InitArray(&A, n, bound1, ., boundn)DestroyArray(&A)Value(A, &e, index1, ., indexn)Assign(&A, e, index1, ., indexn)InitArray(&

3、A, n, bound1, ., boundn) 操作結(jié)果：若維數(shù)操作結(jié)果：若維數(shù) n 和各維長(zhǎng)度合法，和各維長(zhǎng)度合法， 則構(gòu)造相應(yīng)的數(shù)組則構(gòu)造相應(yīng)的數(shù)組A，并，并 返回返回OK。DestroyArray(&A) 操作結(jié)果：銷毀數(shù)組操作結(jié)果：銷毀數(shù)組A。 Value(A, &e, index1, ., indexn) 初始條件：初始條件：A是是n維數(shù)組，維數(shù)組，e為元素變量，為元素變量， 隨后是隨后是n 個(gè)下標(biāo)值。個(gè)下標(biāo)值。 操作結(jié)果：若各下標(biāo)不超界，則操作結(jié)果：若各下標(biāo)不超界，則e賦值為賦值為 所指定的所指定的A 的元素值，并返的元素值，并返 回回OK。 Assign(&A, e, inde

4、x1, ., indexn) 初始條件：初始條件：A是是n維數(shù)組，維數(shù)組，e為元素為元素 變量，隨后是變量，隨后是n 個(gè)下標(biāo)值。個(gè)下標(biāo)值。 操作結(jié)果：若下標(biāo)不超界，則將操作結(jié)果：若下標(biāo)不超界，則將e的的 值賦給所指定的值賦給所指定的A的元的元 素，并返素，并返OK。二維數(shù)組的定義二維數(shù)組的定義:數(shù)據(jù)對(duì)象數(shù)據(jù)對(duì)象: : 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.nmmmnnnmaa

5、aaaaaaaA5.2 數(shù)組的順序表示和實(shí)現(xiàn)數(shù)組的順序表示和實(shí)現(xiàn)類型特點(diǎn)類型特點(diǎn): （1） 只有引用型操作，沒(méi)有加工型操作；只有引用型操作，沒(méi)有加工型操作； （2） 數(shù)組是多維的結(jié)構(gòu)，而存儲(chǔ)空間是數(shù)組是多維的結(jié)構(gòu)，而存儲(chǔ)空間是 一個(gè)一維的結(jié)構(gòu)。一個(gè)一維的結(jié)構(gòu)。有兩種順序映象的方式有兩種順序映象的方式: （1）以行序?yàn)橹餍颍┮孕行驗(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

6、. 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 . a1n-1 am-10 am-11 am-1n-1 .LOC(i,j) = LOC(0,0) + (mji)L稱為基地址基地址或基址以以“行序?yàn)橹餍蛐行驗(yàn)橹餍颉钡拇鎯?chǔ)映象的存儲(chǔ)映象:二維數(shù)組二維數(shù)組A中任一元素中任一元素ai,j 的存儲(chǔ)位置的存儲(chǔ)位置 LOC(i,j) = LOC(

7、0,0) + (nij) L 以以“列序?yàn)橹餍蛄行驗(yàn)橹餍颉钡拇鎯?chǔ)映象的存儲(chǔ)映象:二維數(shù)組二維數(shù)組A中任一元素中任一元素ai,j 的存儲(chǔ)位置的存儲(chǔ)位置 LOC(i,j) = LOC(0,0) + (mji) L 例例5.1: 5.1: 若若 L=2, LOC1,1 = 1000L=2, LOC1,1 = 1000 LOC3,4 = LOC1,1 + (5 LOC3,4 = LOC1,1 + (5* *(3-1)+4-1)(3-1)+4-1)* *L L = 1000 + 13 = 1000 + 13 * * 2 2 = 1026 = 1026一般地，若一般地，若LOC0,0 LOC0,0 為基地

8、址為基地址: : LOCi,j = LOC0,0 + (nLOCi,j = LOC0,0 + (n* *i+j)i+j)* *L L (0=im, 0=jn, (0=im, 0=jn, 每個(gè)數(shù)據(jù)元素占每個(gè)數(shù)據(jù)元素占L L個(gè)存儲(chǔ)單元個(gè)存儲(chǔ)單元) )LOCi,j,k = LOC0,0,0 + (nLOCi,j,k = LOC0,0,0 + (n* *h h* *i+ hi+ h* *j + k)j + k)* *L L(0=im, 0=jn, 0=kh, (0=im, 0=jn, 0=kh, 每個(gè)數(shù)據(jù)元素占每個(gè)數(shù)據(jù)元素占L L個(gè)存儲(chǔ)單元個(gè)存儲(chǔ)單元) ) a a11 a a12 a a13 a a1

9、4 a a15A A4x54x5 = a = a21 a a22 a a23 a a24 a a25 a a31 a a32 a a33 a a34 a a35 a a41 a a42 a a43 a a44 a a45推廣到一般情況n維數(shù)組的行序?yàn)橹餍虼鎯?chǔ)地址計(jì)算公式b b1 1,b,b2 2,.,b,.,bn n是是n n維的維界維的維界, ,數(shù)組元素?cái)?shù)組元素A(jA(j1 1,j,j2 2,.,j,.,jn n) )的存儲(chǔ)位置為的存儲(chǔ)位置為L(zhǎng)OCjLOCj1 1,j,j2 2,.j,.jn n= LOC0,0,.,0 + (b= LOC0,0,.,0 + (b2 2* *b b3 3*

10、* *b bn n* *j j1 1 + b + b3 3* * *b bn n* *j j2 2 + . + . + b + bn n* *j jn n-1-1 + j + jn )n )* *L L n-1 nn-1 n = LOC0,0,.,0 + ( = LOC0,0,.,0 + ( j ji i b bk + k + j jn n) )* *L L i=1 k=i+1i=1 k=i+1 例例: : 在在C C語(yǔ)言中語(yǔ)言中, ,設(shè)設(shè) 數(shù)組數(shù)組A5678A5678的首地址為的首地址為 2000, 2000, 每個(gè)元素占每個(gè)元素占2 2個(gè)字節(jié)個(gè)字節(jié); ; 求元素求元素A3454A3454的

11、地址的地址. . LOC3,4,5,4 = 2000 + (6 LOC3,4,5,4 = 2000 + (6* *7 7* *8 8* *3 + 73 + 7* *8 8* *4 + 84 + 8* *5 + 4)5 + 4)* *2 2 = 2000 + ( 336 = 2000 + ( 336* *3 + 563 + 56* *4 + 84 + 8* *5 + 15 + 1* *4)4)* *2 2 = 2000 + (1008 + 224 + 40 + 4) = 2000 + (1008 + 224 + 40 + 4)* *2 = 45522 = 4552推廣到一般情況，可得到推廣到一般

12、情況，可得到 n 維數(shù)組數(shù)據(jù)元素存儲(chǔ)位置的映象維數(shù)組數(shù)據(jù)元素存儲(chǔ)位置的映象關(guān)系關(guān)系 稱為稱為 n 維數(shù)組的映象函數(shù)。數(shù)組元素的存儲(chǔ)位置是其維數(shù)組的映象函數(shù)。數(shù)組元素的存儲(chǔ)位置是其下標(biāo)的線性函數(shù)。下標(biāo)的線性函數(shù)。其中其中 cn = L，ci-1 = bi ci , 1 i n。LOC(j1, j2, ., jn ) = LOC(0,0,.,0) + ci ji i=1n列序?yàn)橹餍蛄行驗(yàn)橹餍? (FORTRAN): (FORTRAN)A Amxn= =(a(a11,a,a21,a,a31,.a,.am1),(a),(a12,a,a22,a,a32,.a,.am 2),.(a),.(a1n,a,a2

13、n,a,a3n,.a,.amn) LOC1,1 LOC1,1 為基地址為基地址: : LOCi,j = LOC1,1 + (m LOCi,j = LOC1,1 + (m* *(j-1)+i-1)(j-1)+i-1)* *L L (1=i=m, 1=j=n, (1=i=m, 1=j=n, 每個(gè)數(shù)據(jù)元素占每個(gè)數(shù)據(jù)元素占L L個(gè)存儲(chǔ)單元個(gè)存儲(chǔ)單元) )例例5.2: 5.2: 若若 L=2, LOC1,1 = 1000L=2, LOC1,1 = 1000LOC3,4 = LOC1,1 + (4LOC3,4 = LOC1,1 + (4* *(4-1)+3-1)(4-1)+3-1)* *L L = 100

14、0 + 14 = 1000 + 14 * * 2 = 1028 2 = 1028LOC0,0 LOC0,0 為基地址為基地址: :LOCi,j = LOC0,0 + (mLOCi,j = LOC0,0 + (m* *j+i)j+i)* *L L (0=i=m, 0=j=n, (0=i=m, 0=j=n, 每個(gè)數(shù)據(jù)元素占每個(gè)數(shù)據(jù)元素占L L個(gè)存儲(chǔ)單元個(gè)存儲(chǔ)單元) ) LOCi,j,k = LOC0,0,0 + (m LOCi,j,k = LOC0,0,0 + (m* *(n(n* *k)+j)+i) k)+j)+i) * *L La a11 a a12 a a13 a a14 a a15 a a

15、21 a a22 a a23 a a24 a a25 a a31 a a32 a a33 a a34 a a35 a a41 a a42 a a43 a a44 a a45數(shù)組順序存儲(chǔ)的表示和實(shí)現(xiàn)數(shù)組順序存儲(chǔ)的表示和實(shí)現(xiàn) InitArray(Array &A, int dim, .); / 若維數(shù)若維數(shù)dim和隨后的各維長(zhǎng)度數(shù)合法和隨后的各維長(zhǎng)度數(shù)合法,構(gòu)造相應(yīng)的數(shù)組構(gòu)造相應(yīng)的數(shù)組,并返回并返回OK DestroyArray (Array &A);/銷毀數(shù)組銷毀數(shù)組AValue(Array A, ElemType &e, .); 若各下標(biāo)不超界若各下標(biāo)不超界,則則e賦值為所指定的賦值為所指定的

16、A的元素值的元素值,并返回并返回OK Assign(Array &A, ElemType e, .) 若各下標(biāo)不超界若各下標(biāo)不超界,則將則將e的值賦給所指定的的值賦給所指定的A的元素的元素,并返回并返回OK basedimboundsconstantsa0a1aiat.0 1 . dim-1.#include #include #define MAX_ARRAY_DIM 8/#define MAX_ARRAY_DIM 8/維數(shù)最大值維數(shù)最大值typedef struct typedef struct ElemType ElemType * *base;/base;/數(shù)組元素基址數(shù)組元素基址 i

17、nt dim;/int dim;/維數(shù)維數(shù) int int * *bounds; /bounds; /維界基址維界基址 int int * *constants;/constants;/映像函數(shù)常量基映像函數(shù)常量基址，除址，除dimdim外，均由外，均由InitArray分配分配Array;Array;練習(xí)假設(shè)有二維數(shù)組假設(shè)有二維數(shù)組A 68，每個(gè)元素用相鄰的，每個(gè)元素用相鄰的6個(gè)字節(jié)存?zhèn)€字節(jié)存儲(chǔ)，存儲(chǔ)器按字節(jié)編址。已知儲(chǔ)，存儲(chǔ)器按字節(jié)編址。已知A的起始存儲(chǔ)位置（基地的起始存儲(chǔ)位置（基地址）為址）為1000，計(jì)算：，計(jì)算：（1）數(shù)組）數(shù)組A的體積（即存儲(chǔ)量）；的體積（即存儲(chǔ)量）；（2）數(shù)組）數(shù)

18、組A的最后一個(gè)元素的最后一個(gè)元素a57的第一個(gè)字節(jié)的地址；的第一個(gè)字節(jié)的地址；（3）按行存儲(chǔ)時(shí)，元素）按行存儲(chǔ)時(shí)，元素a14的第一個(gè)字節(jié)的地址；的第一個(gè)字節(jié)的地址；（4）按列存儲(chǔ)時(shí)，元素）按列存儲(chǔ)時(shí)，元素a47的第一個(gè)字節(jié)的地址。的第一個(gè)字節(jié)的地址。 5.3.1 特殊矩陣特殊矩陣5.3 矩陣的壓縮存儲(chǔ)矩陣的壓縮存儲(chǔ) 5.3.2 稀疏矩陣稀疏矩陣7600070015000001800000240001400003000000000009120M 以常規(guī)方法，即以二維數(shù)組表示以常規(guī)方法，即以二維數(shù)組表示高階的稀疏矩陣時(shí)產(chǎn)生的問(wèn)題高階的稀疏矩陣時(shí)產(chǎn)生的問(wèn)題:(1) 零值元素占了很大空間零值元素占了很

19、大空間;(2) 計(jì)算中進(jìn)行了很多和零值的運(yùn)算。計(jì)算中進(jìn)行了很多和零值的運(yùn)算。(1) 盡可能少存或不存零值元素；盡可能少存或不存零值元素；解決問(wèn)題的原則解決問(wèn)題的原則:(2) 盡可能減少?zèng)]有實(shí)際意義的運(yùn)算；盡可能減少?zèng)]有實(shí)際意義的運(yùn)算；(3) 操作方便。操作方便。 即：即： 能盡可能快地找到與下標(biāo)值能盡可能快地找到與下標(biāo)值(i，j)對(duì)應(yīng)的對(duì)應(yīng)的元素，元素， 能盡可能快地找到同一行或同一列的能盡可能快地找到同一行或同一列的非零值元。非零值元。5.3.1 特殊矩陣特殊矩陣 特殊矩陣是指非零元素或零元素在矩特殊矩陣是指非零元素或零元素在矩陣中的分布有一定規(guī)律的矩陣。陣中的分布有一定規(guī)律的矩陣。 對(duì)稱矩

20、陣對(duì)稱矩陣元素滿足條件元素滿足條件 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/ ) 1(，例5.2 對(duì)稱矩陣n = 5, 1+2+3+4+5 = 5n = 5, 1+2+3+4+5 = 5* *(5+1)/2 = 15(5+1)/2 = 15一維數(shù)組一維數(shù)組SA1.15SA1.15作為數(shù)

21、組作為數(shù)組A A的存儲(chǔ)結(jié)構(gòu)的存儲(chǔ)結(jié)構(gòu): :SA=(4 5 2 3 1 3 2 5 2 8 1 6 7 9 5)SA=(4 5 2 3 1 3 2 5 2 8 1 6 7 9 5)如如: a5,3 = a3,5 = 7: a5,3 = a3,5 = 7 k = 5(5-1)/2 + 3-1= 12 k = 5(5-1)/2 + 3-1= 12故故:sa12 = 7 :sa12 = 7 4 5 3 2 14 5 3 2 15 2 1 5 65 2 1 5 63 1 3 2 73 1 3 2 72 5 2 8 92 5 2 8 91 6 7 9 51 6 7 9 5A =A =4 4 5 2 5 2

22、 0 03 1 3 3 1 3 2 5 2 8 2 5 2 8 1 6 7 9 51 6 7 9 5A A = =三角矩陣三角矩陣按行序?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 例5.3 下三角矩陣 4 0 0 0 0 4 0 0 0 0 5 2 0 0 0 5 2 0 0 0 A A = 3 1 3 0 0 = 3 1 3

23、 0 0 2 5 2 8 0 2 5 2 8 0 1 6 7 9 5 1 6 7 9 5如如: a5,3 = 7: a5,3 = 7 k = 5(5-1)/2 + 3-1 = 12 k = 5(5-1)/2 + 3-1 = 12故故:sa12 = 7 :sa12 = 7 但但 a3,5 = 0a3,5 = 0對(duì)角矩陣對(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 0 0 Loc(aij)=Loc(a11)+2(i-1)+(j-1)*L 按行序?yàn)橹餍颍喊葱行驗(yàn)?/p>

24、主序：a11 a12 a21 a22 a23 ann-1 ann . k=0 1 2 3 4 3*n-3 saksak和和ai,jai,j的一一對(duì)應(yīng)關(guān)系的一一對(duì)應(yīng)關(guān)系: : sak, k = 3sak, k = 3* *(i-1) + j-i, (i-1) + j-i, ai, j = ai, j = 當(dāng)當(dāng) |i - j|=1|i - j|1|i - j|1 a a1111 a a1212 0 0 . 0 0 0 . 0 a a2121 a a2222 a a2323 0 . 0 0 . 0Anxn = 0 aAnxn = 0 a3232 a a3333 a a3434 . 0 . 0 . .

25、 0 0 0 . a 0 0 0 . ann-1nn-1 a annnn例5.4 對(duì)角矩陣 4 3 0 0 0 4 3 0 0 0 5 2 2 0 0 5 2 2 0 0 A = 0 1 0 4 0 A = 0 1 0 4 0 0 0 2 8 7 0 0 2 8 7 0 0 0 9 5 0 0 0 9 5一維數(shù)組一維數(shù)組SA0.3SA0.3* *5-35-3作為數(shù)組作為數(shù)組A A的存儲(chǔ)結(jié)構(gòu)的存儲(chǔ)結(jié)構(gòu): SA=(4 : SA=(4 3 5 2 2 1 0 4 2 8 7 9 5)3 5 2 2 1 0 4 2 8 7 9 5)如如: a5,4 = 9: a5,4 = 9 k = 3 k = 3*

26、 *(5-1) + 4-5= 11(5-1) + 4-5= 11故故:sa11 = 9:sa11 = 95.3.2 稀疏矩陣稀疏矩陣 假設(shè)假設(shè) m 行行 n 列的矩陣含列的矩陣含 t 個(gè)非零個(gè)非零元素，則稱元素，則稱 為稀疏因子。為稀疏因子。 通常認(rèn)為通常認(rèn)為 0.05 的矩陣為稀疏的矩陣為稀疏矩陣。矩陣。nmt稀疏矩陣的壓縮存儲(chǔ)方法稀疏矩陣的壓縮存儲(chǔ)方法:一、三元組順序表一、三元組順序表二、行邏輯鏈接的順序表二、行邏輯鏈接的順序表三、三、 十字鏈表十字鏈表 #define MAXSIZE 12500 typedef struct int i, j; /該非零元的行下標(biāo)和列下標(biāo) ElemTyp

27、e e; / 該非零元的值 Triple; / 三元組類型三元組類型一、三元組順序表一、三元組順序表typedef struct Triple dataMAXSIZE + 1; int mu, nu, tu; TSMatrix; / 稀疏矩陣類型稀疏矩陣類型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 87600070015000001800000240001400003000000000009120M76000700150000018000002400014000030000

28、00000009120M6700000000014000000007000000024009018000121500300NT如何求轉(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 5 6 7 8i j e7 6 8 1 3 -3 1 6 15 2 1

29、12 2 5 18 3 1 9 3 4 24 4 6 -7 6 3 14 0 1 2 3 4 5 6 7 8?M.dataT.data解決思路：解決思路： 只要做到只要做到 將矩陣行、列值互換；將矩陣行、列值互換； 將每個(gè)三元組中的將每個(gè)三元組中的i和和j相互調(diào)換；相互調(diào)換； 重排三元組次序，使重排三元組次序，使T.data中元中元素以素以N的行的行(M的列的列)為主序?yàn)橹餍蚍椒ㄒ唬喊捶椒ㄒ唬喊碝的列序轉(zhuǎn)置的列序轉(zhuǎn)置 按按T.data中三元組次序依次在中三元組次序依次在M.data中找到相應(yīng)的三元組進(jìn)行轉(zhuǎn)置，即按照矩中找到相應(yīng)的三元組進(jìn)行轉(zhuǎn)置，即按照矩陣陣M的列序來(lái)進(jìn)行置換。的列序來(lái)進(jìn)行置換。

30、 為找到為找到M中每一列所有非零元素，中每一列所有非零元素，需對(duì)其三元組表需對(duì)其三元組表M.data從第一行起掃描從第一行起掃描一遍。由于一遍。由于M.data中以中以M行序?yàn)橹餍?，所行序?yàn)橹餍?，所以由此得到的恰是以由此得到的恰是T.data中應(yīng)有的順序中應(yīng)有的順序。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.data7 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 i j e0 1 2 3 4 5

31、 6 7 8T.dataqppppppppqqqqppppppppcol=1col=2Status TransposeSMatix(TSMatrix M,TSMatrix &T) /采用三元組表存儲(chǔ)表示，求稀疏矩陣采用三元組表存儲(chǔ)表示，求稀疏矩陣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

32、; T.dataq.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ù)。實(shí)現(xiàn)：設(shè)兩個(gè)數(shù)組實(shí)現(xiàn)：設(shè)兩個(gè)數(shù)組numcol：表示矩陣：表示矩陣M中第中第col列中非零元個(gè)數(shù)

33、列中非零元個(gè)數(shù)cpotcol：指示指示M中第中第col列第一個(gè)非零元在列第一個(gè)非零元在T.data中位置中位置顯然有：顯然有：cpot1=1;cpotcol=cpotcol-1+numcol-1; (2 col M.nu)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

34、 1 9 3 4 24 4 6 -7 6 3 14 pppppppp46297537600070015000001800000240001400003000000000009120M6 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 8for (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 = cp

35、otcol-1 + numcol-1; Col 1 2 3 4 5 6 7Numcolcpotcolt1t1t1t1t2t2t2t10 01357889Status FastTransposeSMatrix(TSMatrix 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) cpotco

36、l = 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; T.dataq.j =M.datap.i; T.dataq.e =M.datap.e; +cpotcol; / for / if return OK; / FastTransposeSMatrixT(n)=O(nu+tu)T(n)=O(mu*nu) 三元組順序表又稱有序的雙下三元組順序表又稱有序的雙下標(biāo)法，它的特點(diǎn)是，非零元在表中標(biāo)法，它的特點(diǎn)是，非零元在表中按行序有序存儲(chǔ)，因此

37、便于進(jìn)行依按行序有序存儲(chǔ)，因此便于進(jìn)行依行順序處理的矩陣運(yùn)算。然而，若行順序處理的矩陣運(yùn)算。然而，若需需隨機(jī)隨機(jī)存取某一行中的非零元，則需存取某一行中的非零元，則需從頭開(kāi)始進(jìn)行查找。從頭開(kāi)始進(jìn)行查找。 #define MAXMN 500 typedef struct Triple dataMAXSIZE + 1; /非零元三元組表 int rposMAXMN + 1; /各行第一個(gè)非零元的位置表各行第一個(gè)非零元的位置表 int mu, nu, tu; RLSMatrix; / 行邏輯鏈接順序表類型二、行邏輯鏈接的順序表二、行邏輯鏈接的順序表000200105003M=00420120N=400

38、160Q=Q = M N 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 -2N.data 2 1 -1 i j e1 2 3 4 Q.dataparow 1 2 3 rposarow 1 3 4brow 1 2 3 4rposbrow 1 2 3 5ccol 1 2ctempt1tpq6p 1 2 6tpp2tq-1tp =5p1tq4 3 2 4三、三、 十字鏈表十字鏈表M.cheadM.rhead3 0 0 50 -1 0 02 0 0 01 1 314 522-1312 Typ

39、e struct OLNodeType struct OLNode int i,j; int i,j; int e; int e; struct OLNode struct OLNode * *right,right,* *down;down; OLNode; OLNode; * *OLink;OLink;Type struct Type struct OLink OLink * *rhead,rhead,* *chead;chead; int mu,nu,tu; int mu,nu,tu; CrossList; CrossList;5.4 廣義表的類型定義廣義表的類型定義ADT Glist

40、數(shù)據(jù)對(duì)象數(shù)據(jù)對(duì)象：Dei | i=1,2,.,n; n0; eiAtomSet 或 eiGList, AtomSet為某個(gè)數(shù)據(jù)對(duì)象 數(shù)據(jù)關(guān)系：數(shù)據(jù)關(guān)系： LR| ei-1 ,eiD, 2in ADT Glist 基本操作基本操作:廣義表是遞歸定義的線性結(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, , ) ) )廣義表是一個(gè)多層次多層次的線性結(jié)構(gòu)線性結(jié)構(gòu)

41、例如：例如：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) 廣義表中的數(shù)據(jù)元素有相對(duì)次序；廣義表中的數(shù)據(jù)元素有相對(duì)次序；2) 廣義表的長(zhǎng)度定義為最外層包含元素個(gè)數(shù)；廣義表的長(zhǎng)度定義為最外層包含元素個(gè)數(shù)；3) 廣義表的深度定義為所含括弧的重?cái)?shù)；廣義表的深度定義為所含括弧的重?cái)?shù)； 注意：注意：“原子原子”的深度為的深度為 0 “空表空表”的深度為的深度為 1 4) 廣義表可以共享；廣義表可以共享；5) 廣義表可以是一個(gè)遞歸的表。廣義表可以是一個(gè)遞歸的表。 遞歸表的深度是無(wú)窮

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

43、 ) = ( )GetHead( ( b, c) ) = b GetTail( ( b, c) ) = ( c )GetHead( ( c ) ) = c GetTail( ( c ) ) = ( )練習(xí)求下列廣義表操作的結(jié)果：求下列廣義表操作的結(jié)果：（1）GetHead( (p, h, w) );（2） GetTail( (a ,b) ,(c ,d) );（3） GetHead ( GetTail ( (a,b),(c,d) ) )。 結(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); DeleteFirst_GL(&L, &e); 遍歷遍歷 Traverse_GL(L, Visit();5.5 廣義表的表示方法廣義表的表示方法通常采用頭、尾指針的鏈表結(jié)構(gòu)通常采用頭、尾指針的鏈表結(jié)構(gòu)表結(jié)點(diǎn)表結(jié)點(diǎn):原子結(jié)點(diǎn)：原子結(jié)點(diǎn)：tag=1 h