1、數(shù)數(shù) 據(jù)據(jù) 結(jié)結(jié) 構(gòu)構(gòu) http:/數(shù)數(shù) 據(jù)據(jù) 結(jié)結(jié) 構(gòu)構(gòu) http:/ 5.1 數(shù)組的定義數(shù)組的定義 5.2 數(shù)組的順序表示和實(shí)現(xiàn)數(shù)組的順序表示和實(shí)現(xiàn) 5.3 矩陣的壓縮存儲(chǔ)矩陣的壓縮存儲(chǔ) 5.3.1 特殊矩陣特殊矩陣 5.3.2 稀疏矩陣稀疏矩陣 5.4 廣義表的定義廣義表的定義 5.5 廣義表的存儲(chǔ)結(jié)構(gòu)廣義表的存儲(chǔ)結(jié)構(gòu)數(shù)數(shù) 據(jù)據(jù) 結(jié)結(jié) 構(gòu)構(gòu) http:/ 數(shù)組和廣義表可看成是一種特殊的線性表，其特殊在于，表中的數(shù)據(jù)元素本身也是一種線性表。 5.1 數(shù)組的定義 由于數(shù)組中各元素具有統(tǒng)一的類型，并且數(shù)組元素的下標(biāo)一般具有固定的上界和下界，因此，數(shù)組的處理比其它復(fù)雜的結(jié)構(gòu)更為簡(jiǎn)單。多維數(shù)組是向

2、量的推廣。例如，二維數(shù)組： mnmmnnnmaaaaaaaaaA.212222111211( )( )( )( )( )( )( )( )( )數(shù)數(shù) 據(jù)據(jù) 結(jié)結(jié) 構(gòu)構(gòu) http:/可以看成是由一個(gè)行向量組成的向量，也可以看成是由一個(gè)列向量組成的向量。 在C語(yǔ)言中，一個(gè)二維數(shù)組類型可以定義為其分量類型為一維數(shù)組類型的一維數(shù)組類型，也就是說(shuō)， typedef elemtype array2mn; 等價(jià)于： typedef elemtype array1n; typedef array1 array2m; 數(shù)組一旦被定義，它的維數(shù)和維界就不再改變。因此，除了結(jié)構(gòu)的初始化和銷毀之外，數(shù)組只有存取元素和

3、修改元素值的操作。數(shù)數(shù) 據(jù)據(jù) 結(jié)結(jié) 構(gòu)構(gòu) http:/ 由于計(jì)算機(jī)的內(nèi)存結(jié)構(gòu)是一維的，因此用一維內(nèi)存來(lái)表示多維數(shù)組，就必須按某種次序?qū)?shù)組元素排成一列序列，然后將這個(gè)線性序列存放在存儲(chǔ)器中。 又由于對(duì)數(shù)組一般不做插入和刪除操作，也就是說(shuō)，數(shù)組一旦建立，結(jié)構(gòu)中的元素個(gè)數(shù)和元素間的關(guān)系就不再發(fā)生變化。因此，一般都是采用順序存儲(chǔ)的方法來(lái)表示數(shù)組。 數(shù)數(shù) 據(jù)據(jù) 結(jié)結(jié) 構(gòu)構(gòu) http:/通常有兩種順序存儲(chǔ)方式： 以行序?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)橹餍?/p>

4、存放按行序?yàn)橹餍虼娣?amn . am2 am1 . 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 數(shù)數(shù) 據(jù)據(jù) 結(jié)結(jié) 構(gòu)構(gòu) http:/無(wú)論規(guī)定行優(yōu)先或列優(yōu)先，只要知道以下三要素便可隨時(shí)求出無(wú)論規(guī)定行優(yōu)先或列優(yōu)先，只要知道以下三要素便可隨時(shí)求出任一元素的地址（這樣數(shù)組中的

5、任一元素便可以隨機(jī)存?。。喝我辉氐牡刂罚ㄟ@樣數(shù)組中的任一元素便可以隨機(jī)存?。。憾S數(shù)組二維數(shù)組列優(yōu)先列優(yōu)先存儲(chǔ)的通式為：存儲(chǔ)的通式為：LOC(aij)=LOC(ac1，c2)+(j-c2)*(d1-c1+1)+i-c1)*L ac1,c2 ac1,d2 aij ad1,c2 ad1,d2 Amn=單個(gè)元素單個(gè)元素長(zhǎng)度長(zhǎng)度aijaij之前的之前的行數(shù)行數(shù)數(shù)組基址數(shù)組基址總列數(shù)，即總列數(shù)，即第第2 2維長(zhǎng)度維長(zhǎng)度aijaij本行前面本行前面的元素個(gè)數(shù)的元素個(gè)數(shù)開始結(jié)點(diǎn)的存放地址（即基地址）開始結(jié)點(diǎn)的存放地址（即基地址）維數(shù)和每維的上、下界；維數(shù)和每維的上、下界；每個(gè)數(shù)組元素所占用的單元數(shù)每個(gè)

6、數(shù)組元素所占用的單元數(shù)則則行優(yōu)先行優(yōu)先存儲(chǔ)時(shí)的地址公式為：存儲(chǔ)時(shí)的地址公式為：LOC(aij)=LOC(ac1，c2)+(i-c1)*(d2-c2+1)+(j-c2)*L數(shù)數(shù) 據(jù)據(jù) 結(jié)結(jié) 構(gòu)構(gòu) http:/ Loc(aij)=Loc(a11)+(j-1)*m+(i-1)*K （盡管是方陣，但公式不同）（盡管是方陣，但公式不同）例例1一個(gè)二維數(shù)組一個(gè)二維數(shù)組A，行下標(biāo)的范圍是，行下標(biāo)的范圍是1到到6，列下標(biāo)的范圍，列下標(biāo)的范圍是是0到到7，每個(gè)數(shù)組元素用相鄰的，每個(gè)數(shù)組元素用相鄰的6個(gè)字節(jié)存儲(chǔ)，存儲(chǔ)器按字個(gè)字節(jié)存儲(chǔ)，存儲(chǔ)器按字節(jié)編址。那么，這個(gè)數(shù)組的體積是節(jié)編址。那么，這個(gè)數(shù)組的體積是 個(gè)字節(jié)。

7、個(gè)字節(jié)。 288例例3：設(shè)數(shù)組設(shè)數(shù)組a160, 170的基地址為的基地址為2048，每個(gè)元素，每個(gè)元素占占2個(gè)存儲(chǔ)單元，若以列序?yàn)橹餍蝽樞虼鎯?chǔ)，則元素個(gè)存儲(chǔ)單元，若以列序?yàn)橹餍蝽樞虼鎯?chǔ)，則元素a32,58的存儲(chǔ)地址為的存儲(chǔ)地址為 。8950LOC(aij)=LOC(ac1，c2)+(j-c2)*(d1-c1+1)+i-c1)*L得：得：LOC(a32,58)=2048+(58-1)*(60-1+1)+32-1)*28950答：請(qǐng)注意審題！答：請(qǐng)注意審題！利用列優(yōu)先通式：利用列優(yōu)先通式：答：答： Volume=m*n*L=(6-1+1)*(7- 0 +1)*6=48*6=288數(shù)數(shù) 據(jù)據(jù) 結(jié)結(jié)

8、構(gòu)構(gòu) http:/ 5.3 5.3 矩陣的壓縮存儲(chǔ)矩陣的壓縮存儲(chǔ) 在科學(xué)與工程計(jì)算問(wèn)題中，矩陣是一種常用的數(shù)在科學(xué)與工程計(jì)算問(wèn)題中，矩陣是一種常用的數(shù)學(xué)對(duì)象，在高級(jí)語(yǔ)言編制程序時(shí)，簡(jiǎn)單而又自然的方學(xué)對(duì)象，在高級(jí)語(yǔ)言編制程序時(shí)，簡(jiǎn)單而又自然的方法，就是將一個(gè)矩陣描述為一個(gè)二維數(shù)組。矩陣在這法，就是將一個(gè)矩陣描述為一個(gè)二維數(shù)組。矩陣在這種存儲(chǔ)表示之下，可以對(duì)其元素進(jìn)行隨機(jī)存取，各種種存儲(chǔ)表示之下，可以對(duì)其元素進(jìn)行隨機(jī)存取，各種矩陣運(yùn)算也非常簡(jiǎn)單，并且存儲(chǔ)的密度為矩陣運(yùn)算也非常簡(jiǎn)單，并且存儲(chǔ)的密度為1 1。但是在矩。但是在矩陣中非零元素呈某種規(guī)律分布或者矩陣中出現(xiàn)陣中非零元素呈某種規(guī)律分布或者矩陣中

9、出現(xiàn)大量的大量的零元素零元素的情況下，看起來(lái)存儲(chǔ)密度仍為的情況下，看起來(lái)存儲(chǔ)密度仍為1 1，但實(shí)際上占，但實(shí)際上占用了許多單元去存儲(chǔ)重復(fù)的非零元素或零元素，這對(duì)用了許多單元去存儲(chǔ)重復(fù)的非零元素或零元素，這對(duì)高階矩陣會(huì)造成極大的浪費(fèi)，為了節(jié)省存儲(chǔ)空間，高階矩陣會(huì)造成極大的浪費(fèi)，為了節(jié)省存儲(chǔ)空間， 我我們可以對(duì)這類矩陣進(jìn)行們可以對(duì)這類矩陣進(jìn)行壓縮存儲(chǔ)壓縮存儲(chǔ)：即為多個(gè)相同的非即為多個(gè)相同的非零元素只分配一個(gè)存儲(chǔ)空間；對(duì)零元素不分配空間。零元素只分配一個(gè)存儲(chǔ)空間；對(duì)零元素不分配空間。數(shù)數(shù) 據(jù)據(jù) 結(jié)結(jié) 構(gòu)構(gòu) http:/5.3.1 5.3.1 特殊矩陣特殊矩陣 所謂特殊矩陣是指非零元素或零元素的分布有

10、一定規(guī)所謂特殊矩陣是指非零元素或零元素的分布有一定規(guī)律的矩陣，下面我們討論幾種特殊矩陣的壓縮存儲(chǔ)。律的矩陣，下面我們討論幾種特殊矩陣的壓縮存儲(chǔ)。1 1、對(duì)稱矩陣、對(duì)稱矩陣 在一個(gè)在一個(gè)n n階方陣階方陣A A中，若元素滿足下述性質(zhì)：中，若元素滿足下述性質(zhì)： a aijij=a=ajiji 0 0i,ji,jn-1n-1則稱則稱A A為對(duì)稱矩陣。如圖為對(duì)稱矩陣。如圖5.15.1便是一個(gè)便是一個(gè)5 5階對(duì)稱矩陣。階對(duì)稱矩陣。 對(duì)稱矩陣中的元素關(guān)于主對(duì)角線對(duì)稱，故只要存儲(chǔ)對(duì)稱矩陣中的元素關(guān)于主對(duì)角線對(duì)稱，故只要存儲(chǔ)矩陣中上三角或下三角中的元素，讓每?jī)蓚€(gè)對(duì)稱的元素矩陣中上三角或下三角中的元素，讓每?jī)蓚€(gè)

11、對(duì)稱的元素共享一個(gè)存儲(chǔ)空間，這樣，能節(jié)約近一半的存儲(chǔ)空間。共享一個(gè)存儲(chǔ)空間，這樣，能節(jié)約近一半的存儲(chǔ)空間。不失一般性，我們按不失一般性，我們按“行優(yōu)先順序行優(yōu)先順序”存儲(chǔ)主對(duì)角線（包存儲(chǔ)主對(duì)角線（包括對(duì)角線）以下的元素，其存儲(chǔ)形式如圖所示：括對(duì)角線）以下的元素，其存儲(chǔ)形式如圖所示：數(shù)數(shù) 據(jù)據(jù) 結(jié)結(jié) 構(gòu)構(gòu) http:/ 1 5 1 3 7 a00 5 0 8 0 0 a10 a 11 1 8 9 2 6 a20 a21 a23 3 0 2 5 1 . 7 0 6 1 3 an-1 0 a n-1 1 a n-1 2 a n-1 n-1 圖圖 5.1 對(duì)稱矩陣對(duì)稱矩陣 在這個(gè)下三角矩陣中，在這個(gè)下

12、三角矩陣中，i i行（行（0=in0=in）恰有）恰有i+1i+1個(gè)元個(gè)元素，元素總數(shù)為：素，元素總數(shù)為：n(n+1)/2n(n+1)/2。 因此，我們可以按從上到下、從左到右將這些元素因此，我們可以按從上到下、從左到右將這些元素存放在一個(gè)向量存放在一個(gè)向量san(n+1)/2san(n+1)/2中。為了便于訪問(wèn)對(duì)稱矩中。為了便于訪問(wèn)對(duì)稱矩陣陣A A中的元素，我們必須在中的元素，我們必須在a aijij和和saksak之間找一個(gè)對(duì)應(yīng)之間找一個(gè)對(duì)應(yīng)關(guān)系。關(guān)系。 數(shù)數(shù) 據(jù)據(jù) 結(jié)結(jié) 構(gòu)構(gòu) http:/ 若若ijij，則，則a aijij在下三角形中。在下三角形中。 a aijij之前的之前的i i行

13、行（從第（從第0 0行到第行到第i-1i-1行）一共有行）一共有1+2+i=i(i+1)/21+2+i=i(i+1)/2個(gè)元個(gè)元素，在第素，在第i+1i+1行上，行上， a aijij之前恰有之前恰有j j個(gè)元素（即個(gè)元素（即a ai0i0,a,ai1i1,a,ai2i2,a,aij-1ij-1），因此有：），因此有： k=ik=i* *(i+1)/2+j 0kn(n+1)/2 (i+1)/2+j 0kn(n+1)/2 若若ijij，則，則a aijij是在上三角矩陣中。因?yàn)槭窃谏先蔷仃囍小Ｒ驗(yàn)閍 aijij=a=ajiji，所以只要交換上述對(duì)應(yīng)關(guān)系式中的所以只要交換上述對(duì)應(yīng)關(guān)系式中的i i

14、和和j j即可得到：即可得到： k=jk=j* *(j+1)/2+i 0 kn(n+1)/2 (j+1)/2+i 0 kn(n+1)/2 數(shù)數(shù) 據(jù)據(jù) 結(jié)結(jié) 構(gòu)構(gòu) http:/2、三角矩陣、三角矩陣 以主對(duì)角線劃分，三角矩陣有上三角和下三角兩種。以主對(duì)角線劃分，三角矩陣有上三角和下三角兩種。上三角矩陣如圖所示，它的下三角（不包括主對(duì)角線）上三角矩陣如圖所示，它的下三角（不包括主對(duì)角線）中的元素均為常數(shù)。下三角矩陣正好相反，它的主對(duì)中的元素均為常數(shù)。下三角矩陣正好相反，它的主對(duì)角線上方均為常數(shù)，如圖所示。在大多數(shù)情況下，角線上方均為常數(shù)，如圖所示。在大多數(shù)情況下，三角矩陣常數(shù)為零。三角矩陣常數(shù)為零

15、。 a00 a01 a 0 n-1 a00 c c c a11 a 1 n-1 a10 a11 c . . c c a n-1 n-1 an-1 0 an-1 1 an-1 n-1 (a)(a)上三角矩陣上三角矩陣 (b)(b)下三角矩陣下三角矩陣 數(shù)數(shù) 據(jù)據(jù) 結(jié)結(jié) 構(gòu)構(gòu) http:/ 三角矩陣中的重復(fù)元素三角矩陣中的重復(fù)元素c c可共享一個(gè)存儲(chǔ)空間，其可共享一個(gè)存儲(chǔ)空間，其余的元素正好有余的元素正好有n(n+1)/2n(n+1)/2個(gè)，因此，三角矩陣可壓縮個(gè)，因此，三角矩陣可壓縮存儲(chǔ)到向量存儲(chǔ)到向量san(n+1)/2+1san(n+1)/2+1中，其中中，其中c c存放在向量的最存放在向量

16、的最后一個(gè)分量中，后一個(gè)分量中， 上三角矩陣中，主對(duì)角線之上的第上三角矩陣中，主對(duì)角線之上的第i i行行(0(0in)i j數(shù)數(shù) 據(jù)據(jù) 結(jié)結(jié) 構(gòu)構(gòu) http:/ 下三角矩陣的存儲(chǔ)和對(duì)稱矩陣類似，下三角矩陣的存儲(chǔ)和對(duì)稱矩陣類似，saksak和和a aijij對(duì)應(yīng)關(guān)系是：對(duì)應(yīng)關(guān)系是： i(i+1)/2+j ii(i+1)/2+j ij j n(n+1)/2 ij n(n+1)/2 i11時(shí)，元素時(shí)，元素a aijij=0=0。 由此可知，一個(gè)由此可知，一個(gè)k k對(duì)角矩陣對(duì)角矩陣(k(k為奇數(shù)為奇數(shù))A)A是滿足下述是滿足下述條件的矩陣：若條件的矩陣：若 i-ji-j (k-1)/2 (k-1)/2

17、 ，則元素，則元素 a aijij=0=0。 對(duì)角矩陣可按行優(yōu)先順序或?qū)蔷€的順序，將其壓對(duì)角矩陣可按行優(yōu)先順序或?qū)蔷€的順序，將其壓縮存儲(chǔ)到一個(gè)向量中，并且也能找到每個(gè)非零元素和縮存儲(chǔ)到一個(gè)向量中，并且也能找到每個(gè)非零元素和向量下標(biāo)的對(duì)應(yīng)關(guān)系。向量下標(biāo)的對(duì)應(yīng)關(guān)系。數(shù)數(shù) 據(jù)據(jù) 結(jié)結(jié) 構(gòu)構(gòu) http:/ 在三對(duì)角矩陣?yán)锍凉M足條件在三對(duì)角矩陣?yán)锍凉M足條件i=0i=0，j=0j=0、1 1，或，或i=n-i=n-1j=n-21j=n-2、n-1n-1或或1in-1,j=i-11in-1,j=i-1、i i、i+1i+1的元素的元素a aijij外，外，其余元素都是零。其余元素都是零。 對(duì)這種矩陣，我

18、們也可按行優(yōu)序?yàn)橹餍騺?lái)存儲(chǔ)。除對(duì)這種矩陣，我們也可按行優(yōu)序?yàn)橹餍騺?lái)存儲(chǔ)。除第第0 0行和第行和第n-1n-1行是行是2 2個(gè)元素外，每行的非零元素都要是個(gè)元素外，每行的非零元素都要是3 3個(gè)，因此，需存儲(chǔ)的元素個(gè)數(shù)為個(gè)，因此，需存儲(chǔ)的元素個(gè)數(shù)為3n-23n-2。 a00 a01 a10 a11 a12 a21 a n-1 n-2 a n-1 n-1 K=0 1 2 3 4 5 3n-4 3n-3 數(shù)組數(shù)組sa中的元素中的元素sak與三對(duì)角帶狀矩陣中的元素與三對(duì)角帶狀矩陣中的元素aij存在一一對(duì)應(yīng)關(guān)系，在存在一一對(duì)應(yīng)關(guān)系，在aij之前有之前有i行行,共有共有3*i-1個(gè)非零元個(gè)非零元素，在第素，

19、在第i+1行，行， aij 之前有之前有j-i+1個(gè)非零元素，這樣，個(gè)非零元素，這樣，非零元素非零元素aij的地址為：的地址為： 數(shù)數(shù) 據(jù)據(jù) 結(jié)結(jié) 構(gòu)構(gòu) http:/ LOC(i,j)=LOC(0,0)+3*i-1+(j-i+1)*d =LOC(0,0)+(2i+j)*d 上例中，上例中， a a3434對(duì)應(yīng)著對(duì)應(yīng)著sa10sa10。k=2k=2* *i+j=2i+j=2* *3+4=103+4=10。 a a2121對(duì)應(yīng)著對(duì)應(yīng)著sa5sa5。k=2k=2* *2+1=52+1=5。 由此，我們稱由此，我們稱sa3sa3* *n-2n-2是階三對(duì)角帶狀矩陣是階三對(duì)角帶狀矩陣A A的壓的壓縮存儲(chǔ)

20、表示?？s存儲(chǔ)表示。數(shù)數(shù) 據(jù)據(jù) 結(jié)結(jié) 構(gòu)構(gòu) http:/ 上述的各種特殊矩陣，其非零元素的分布都是有規(guī)上述的各種特殊矩陣，其非零元素的分布都是有規(guī)律的，因此總能找到一種方法將它們壓縮存儲(chǔ)到一個(gè)律的，因此總能找到一種方法將它們壓縮存儲(chǔ)到一個(gè)向量中，并且一般都能找到矩陣中的元素與該向量的向量中，并且一般都能找到矩陣中的元素與該向量的對(duì)應(yīng)關(guān)系，對(duì)應(yīng)關(guān)系，通過(guò)這個(gè)關(guān)系，仍能對(duì)矩陣的元素進(jìn)行隨通過(guò)這個(gè)關(guān)系，仍能對(duì)矩陣的元素進(jìn)行隨機(jī)存取。機(jī)存取。 5.3.2 5.3.2 稀疏矩陣稀疏矩陣 什么是稀疏矩陣？簡(jiǎn)單說(shuō)，設(shè)矩陣什么是稀疏矩陣？簡(jiǎn)單說(shuō)，設(shè)矩陣A A中有中有s s個(gè)非零元個(gè)非零元素，若素，若s s遠(yuǎn)遠(yuǎn)小

21、于矩陣元素的總數(shù)（即遠(yuǎn)遠(yuǎn)小于矩陣元素的總數(shù)（即smsmn n），則），則稱稱A A為稀疏矩陣。為稀疏矩陣。數(shù)數(shù) 據(jù)據(jù) 結(jié)結(jié) 構(gòu)構(gòu) http:/ 精確地說(shuō)，設(shè)在的矩陣精確地說(shuō)，設(shè)在的矩陣A A中，有中，有s s個(gè)非零元素。令個(gè)非零元素。令 e=s/(me=s/(m* *n)n)，稱，稱e e為矩陣的稀疏因子。通常認(rèn)為為矩陣的稀疏因子。通常認(rèn)為e e0.050.05時(shí)稱之為稀疏矩陣。在存儲(chǔ)稀疏矩陣時(shí)，為時(shí)稱之為稀疏矩陣。在存儲(chǔ)稀疏矩陣時(shí)，為了節(jié)省存儲(chǔ)單元，很自然地想到使用壓縮存儲(chǔ)方法。了節(jié)省存儲(chǔ)單元，很自然地想到使用壓縮存儲(chǔ)方法。但由于非零元素的分布一般是沒(méi)有規(guī)律的，因此在存但由于非零元素的分布一

22、般是沒(méi)有規(guī)律的，因此在存儲(chǔ)非零元素的同時(shí)，還必須同時(shí)記下它所在的行和列儲(chǔ)非零元素的同時(shí)，還必須同時(shí)記下它所在的行和列的位置（的位置（i,j)i,j)。反之，一個(gè)三元組。反之，一個(gè)三元組(i,j,a(i,j,aijij) )唯一確定唯一確定了矩陣了矩陣A A的一個(gè)非零元。因此，的一個(gè)非零元。因此，稀疏矩陣可由表示稀疏矩陣可由表示非非零元的三元組及其行列數(shù)零元的三元組及其行列數(shù)唯一確定。唯一確定。數(shù)數(shù) 據(jù)據(jù) 結(jié)結(jié) 構(gòu)構(gòu) http:/例如，下列三元組表：例如，下列三元組表：(1,2,12)(1,3,9),(3,1,- 3),(3,6,14),(4,3,24), (5,2,18),(6,1,15),(

23、6,4,-7)加上加上(6,7(6,7，8)8)這一對(duì)行、列值以及非零元素的個(gè)數(shù)便可作為下這一對(duì)行、列值以及非零元素的個(gè)數(shù)便可作為下列矩陣列矩陣M M的另一種描述。而由上述三元組表的不同表示方法可引的另一種描述。而由上述三元組表的不同表示方法可引出稀疏矩陣不同的壓縮存儲(chǔ)方法。出稀疏矩陣不同的壓縮存儲(chǔ)方法。 0 12 9 0 0 0 0 0 0 -3 0 0 150 12 9 0 0 0 0 0 0 -3 0 0 15 0 0 0 0 0 0 0 12 0 0 0 18 0 0 0 0 0 0 0 0 12 0 0 0 18 0 -3 0 0 0 0 14 0 9 0 0 24 0 0 -3 0

24、 0 0 0 14 0 9 0 0 24 0 0 0 0 24 0 0 0 0 0 0 0 0 0 0 0 24 0 0 0 0 0 0 0 0 0 7 7 0 18 0 0 0 0 0 0 0 14 0 0 0 0 18 0 0 0 0 0 0 0 14 0 0 0 15 0 0 15 0 0 7 0 0 0 0 0 0 0 0 07 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 圖圖5.4 5.4 稀疏矩陣稀疏矩陣M M和和T TM=T=數(shù)數(shù) 據(jù)據(jù) 結(jié)結(jié) 構(gòu)構(gòu) http:/一、三元組順序表一、三元組順序表 假設(shè)以順序存儲(chǔ)結(jié)構(gòu)來(lái)表示三元組表，則可得到稀假

25、設(shè)以順序存儲(chǔ)結(jié)構(gòu)來(lái)表示三元組表，則可得到稀疏矩陣的一種壓縮存儲(chǔ)方法疏矩陣的一種壓縮存儲(chǔ)方法三元順序表。三元順序表。 #define maxsize 10000#define maxsize 10000 typedef int datatype; typedef int datatype; typedef struct typedef struct int int i,ji,j; /; /* * 行列號(hào)行列號(hào) * */ / datatype datatype v v; /; /* * 元素值元素值 * */ / triplet; triplet; 數(shù)數(shù) 據(jù)據(jù) 結(jié)結(jié) 構(gòu)構(gòu) http:/ typed

26、ef structtypedef struct triplet datamaxsize; / triplet datamaxsize; /* * 三元組表三元組表 * */ / int m,n,t; / int m,n,t; /* * 行數(shù)、列數(shù)、非零元素個(gè)數(shù)行數(shù)、列數(shù)、非零元素個(gè)數(shù) * */ / tripletable; / tripletable; /* * 稀疏矩陣類型稀疏矩陣類型 * */ / 設(shè)設(shè)A A為為tripletabletripletable型的結(jié)構(gòu)變量，圖型的結(jié)構(gòu)變量，圖5.45.4中所示的稀疏矩陣中所示的稀疏矩陣的三元組的表示如下：的三元組的表示如下： i j vi j

27、v 0 1 12 0 1 12 0 2 9 0 2 9 2 0 -3 2 0 -3 2 5 14 2 5 14 3 2 24 3 2 24 4 1 18 4 1 18 5 0 15 5 0 15 5 3 -7 5 3 -7 數(shù)數(shù) 據(jù)據(jù) 結(jié)結(jié) 構(gòu)構(gòu) http:/ 下面以矩陣的轉(zhuǎn)置為例，說(shuō)明在這種壓縮存儲(chǔ)結(jié)構(gòu)下面以矩陣的轉(zhuǎn)置為例，說(shuō)明在這種壓縮存儲(chǔ)結(jié)構(gòu)上如何實(shí)現(xiàn)矩陣的運(yùn)算。上如何實(shí)現(xiàn)矩陣的運(yùn)算。 一個(gè)一個(gè)m mn n的矩陣的矩陣A A，它的轉(zhuǎn)置，它的轉(zhuǎn)置B B是一個(gè)是一個(gè)n nm m的矩陣，的矩陣，且且aij=bjiaij=bji，0 0i im m，0 0j jn n，即，即A A的行是的行是B

28、 B的列，的列，A A的列是的列是B B的行。的行。 將將A A轉(zhuǎn)置為轉(zhuǎn)置為B B，就是將，就是將A A的三元組表的三元組表a.dataa.data置換為表置換為表B B的三元組表的三元組表b.datab.data，如果只是簡(jiǎn)單地交換，如果只是簡(jiǎn)單地交換a.dataa.data中中i i和和j j的內(nèi)容，那么得到的的內(nèi)容，那么得到的b.datab.data將是一個(gè)按列優(yōu)先順序存將是一個(gè)按列優(yōu)先順序存儲(chǔ)的稀疏矩陣儲(chǔ)的稀疏矩陣B B，要得到按行優(yōu)先順序存儲(chǔ)的，要得到按行優(yōu)先順序存儲(chǔ)的b.datab.data，就必須重新排列三元組的順序。就必須重新排列三元組的順序。 由于由于A A的列是的列是B B

29、的行，因此，按的行，因此，按a.dataa.data的列序轉(zhuǎn)置，的列序轉(zhuǎn)置，所得到的轉(zhuǎn)置矩陣所得到的轉(zhuǎn)置矩陣B B的三元組表的三元組表b.datab.data必定是按行優(yōu)先必定是按行優(yōu)先存放的。存放的。數(shù)數(shù) 據(jù)據(jù) 結(jié)結(jié) 構(gòu)構(gòu) http:/7600070015000001800000240001400003000000000009120M6700000000014000000007000000024009018000121500300N6 7 8 0 1 12 0 2 9 2 0 -3 2 5 14 3 2 24 4 1 18 5 0 15 5 3 -7 i j v0 1 2 3 4 5 6 7

30、 8ai j v7 6 8 0 2 -3 0 5 15 1 0 12 1 4 18 2 0 9 2 3 24 3 5 -7 5 2 14 0 1 2 3 4 5 6 7 8b?數(shù)數(shù) 據(jù)據(jù) 結(jié)結(jié) 構(gòu)構(gòu) http:/Y解決思路：只要做到解決思路：只要做到 將矩陣行、列維數(shù)互換將矩陣行、列維數(shù)互換 將每個(gè)三元組中的將每個(gè)三元組中的i和和j相互調(diào)換相互調(diào)換 重排三元組次序，使重排三元組次序，使b中元素以中元素以N的行的行(M的列的列)為主序?yàn)橹餍蚍椒ㄒ唬悍椒ㄒ唬喊窗碝的列序的列序轉(zhuǎn)置轉(zhuǎn)置 即按即按b中三元組次序依次在中三元組次序依次在a中找到相應(yīng)的三元組進(jìn)行轉(zhuǎn)置。中找到相應(yīng)的三元組進(jìn)行轉(zhuǎn)置。為找到為找

31、到M中每一列所有非零元素，需對(duì)其三元組表中每一列所有非零元素，需對(duì)其三元組表a從第一行從第一行起掃描起掃描一遍。由于一遍。由于a中以中以M行序?yàn)橹餍蛐行驗(yàn)橹餍?所以由此得到的恰是所以由此得到的恰是b中應(yīng)有的順序。中應(yīng)有的順序。算法描述：算法描述：P76 算法算法算法分析：算法分析：T(n)=O(M的列數(shù)的列數(shù)n 非零元個(gè)數(shù)非零元個(gè)數(shù)t)若若 t 與與m n同數(shù)量級(jí)，則同數(shù)量級(jí)，則)()(2nmOnT數(shù)數(shù) 據(jù)據(jù) 結(jié)結(jié) 構(gòu)構(gòu) http:/6 7 8 0 1 12 0 2 9 2 0 -3 2 5 14 3 2 24 4 1 18 5 0 15 5 3 -7 i j v0 1 2 3 4 5 6 7

32、 8a7 6 8 0 2 -3 0 5 15 1 0 12 1 4 18 2 0 9 2 3 24 3 5 -7 5 2 14 i j v0 1 2 3 4 5 6 7 8bqppppppppqqqqppppppppcol=0col=6數(shù)數(shù) 據(jù)據(jù) 結(jié)結(jié) 構(gòu)構(gòu) http:/方法二：快速轉(zhuǎn)置方法二：快速轉(zhuǎn)置即按即按a中三元組次序轉(zhuǎn)置，轉(zhuǎn)置結(jié)果放入中三元組次序轉(zhuǎn)置，轉(zhuǎn)置結(jié)果放入b中恰當(dāng)位置中恰當(dāng)位置此法關(guān)鍵是要預(yù)先確定此法關(guān)鍵是要預(yù)先確定M中每一列第一個(gè)非零元在中每一列第一個(gè)非零元在b中位置，中位置，為確定這些位置，轉(zhuǎn)置前應(yīng)先求得為確定這些位置，轉(zhuǎn)置前應(yīng)先求得M的每一列中非零元個(gè)數(shù)的每一列中非零元個(gè)

33、數(shù)實(shí)現(xiàn)：設(shè)兩個(gè)數(shù)組實(shí)現(xiàn)：設(shè)兩個(gè)數(shù)組numcol：表示矩陣：表示矩陣M中第中第col列中非零元個(gè)數(shù)列中非零元個(gè)數(shù)cpotcol：指示：指示M中第中第col列第一個(gè)非零元在列第一個(gè)非零元在b中的下標(biāo)中的下標(biāo)顯然有：顯然有：cpot0=0;cpotcol=cpotcol-1+numcol-1; (2 col ma0.j)0246778colnumcolcpotcol021222314051607600070015000001800000240001400003000000000009120M數(shù)數(shù) 據(jù)據(jù) 結(jié)結(jié) 構(gòu)構(gòu) http:/6 7 8 0 1 12 0 2 9 2 0 -3 2 5 14 3 2

34、24 4 1 18 5 0 15 5 3 -7 i j v0 1 2 3 4 5 6 7 8ai j v0 0 1 2 3 4 5 6 7 bcolnumcolcpotcol002122242361470571680 7 6 8 0 2 -3 0 5 15 1 0 12 1 4 18 2 0 9 2 3 24 3 5 -7 5 2 14 pppppppp24 075316數(shù)數(shù) 據(jù)據(jù) 結(jié)結(jié) 構(gòu)構(gòu) http:/ 鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu) 帶行指針向量的單鏈表表示帶行指針向量的單鏈表表示Y每行的非零元用一個(gè)單鏈表存放每行的非零元用一個(gè)單鏈表存放 Y設(shè)置一個(gè)行指針數(shù)組，指向本行第一個(gè)設(shè)置一個(gè)行指針數(shù)組

35、，指向本行第一個(gè)非零元結(jié)點(diǎn)；若本行無(wú)非零元，則指針?lè)橇阍Y(jié)點(diǎn)；若本行無(wú)非零元，則指針為空為空Y表頭結(jié)點(diǎn)與單鏈表結(jié)點(diǎn)類型定義表頭結(jié)點(diǎn)與單鏈表結(jié)點(diǎn)類型定義typedef struct node int col; int val; struct node *link;JD;typedef struct node *TD;0200000000000210010070003A1 35 73 -11 -12 -24 2數(shù)數(shù) 據(jù)據(jù) 結(jié)結(jié) 構(gòu)構(gòu) http:/ 十字鏈表十字鏈表Y設(shè)行指針數(shù)組和列指針數(shù)組，分別指向每行、列第一個(gè)非零元設(shè)行指針數(shù)組和列指針數(shù)組，分別指向每行、列第一個(gè)非零元Y結(jié)點(diǎn)定義結(jié)點(diǎn)定義tped

36、ef struct node int row,col,val; struct node *down, *right;JD; row col valdownright34008000450003A113418225234數(shù)數(shù) 據(jù)據(jù) 結(jié)結(jié) 構(gòu)構(gòu) http:/5.4 5.4 廣義表的定義廣義表的定義 廣義表是第二章提到的線性表的推廣。線性表中的元素僅廣義表是第二章提到的線性表的推廣。線性表中的元素僅限于原子項(xiàng)限于原子項(xiàng)(單個(gè)數(shù)據(jù)元素單個(gè)數(shù)據(jù)元素)，即不可以再分，而廣義表中的元，即不可以再分，而廣義表中的元素既可以是原子項(xiàng)，也可以是子表素既可以是原子項(xiàng)，也可以是子表(另一個(gè)線性表另一個(gè)線性表)。 (如

37、果如果ai是單個(gè)數(shù)據(jù)元素是單個(gè)數(shù)據(jù)元素,則稱則稱ai為廣義表的原子為廣義表的原子 )1廣義表的定義廣義表的定義 廣義表是廣義表是n0個(gè)元素個(gè)元素a0，a1，an-1的有限序列，其中每的有限序列，其中每一個(gè)一個(gè)ai或者是原子，或者是一個(gè)子表。廣義表通常記為或者是原子，或者是一個(gè)子表。廣義表通常記為GL=(a0,a1,an-1)，其中，其中GL為廣義表的名字，為廣義表的名字，n為廣義表的長(zhǎng)為廣義表的長(zhǎng)度，度， 每一個(gè)每一個(gè)ai為廣義表的元素。但在習(xí)慣中，一般用大寫字為廣義表的元素。但在習(xí)慣中，一般用大寫字母表示廣義表，小寫字母表示原子。母表示廣義表，小寫字母表示原子。 稱第一個(gè)元素稱第一個(gè)元素a0

38、為廣義表為廣義表GL的表頭的表頭,其余部分其余部分(a1,.an-1)為為GL的表尾的表尾,分別記作分別記作head(GL)= a0和和tail(GL)= (a1,.an-1)數(shù)數(shù) 據(jù)據(jù) 結(jié)結(jié) 構(gòu)構(gòu) http:/說(shuō)明說(shuō)明:1.廣義表是線性表的一種推廣。廣義表是線性表的一種推廣。2.廣義表的定義是遞歸的。因?yàn)樵诿枋鰪V義表的時(shí)候又用廣義表的定義是遞歸的。因?yàn)樵诿枋鰪V義表的時(shí)候又用到了廣義表的概念到了廣義表的概念.3.廣義表是多層次結(jié)構(gòu)。廣義表是多層次結(jié)構(gòu)。4.一個(gè)廣義表可以為其它廣義表所共享。一個(gè)廣義表可以為其它廣義表所共享。數(shù)數(shù) 據(jù)據(jù) 結(jié)結(jié) 構(gòu)構(gòu) http:/2廣義表舉例廣義表舉例 (1) A=

39、( ), A為空表，長(zhǎng)度為為空表，長(zhǎng)度為0。(2) B=(a,（b,c) ), B是長(zhǎng)度為是長(zhǎng)度為2的廣義表，第一項(xiàng)為原子，第二的廣義表，第一項(xiàng)為原子，第二項(xiàng)為子表。項(xiàng)為子表。(3) C=(x,y,z) C是長(zhǎng)度為是長(zhǎng)度為3的廣義表，每一項(xiàng)都是原子。的廣義表，每一項(xiàng)都是原子。D=(B,C) ， D是長(zhǎng)度為是長(zhǎng)度為2的廣義表，每一項(xiàng)都是上面提到的子表。的廣義表，每一項(xiàng)都是上面提到的子表。E=(a,E) 是長(zhǎng)度為是長(zhǎng)度為2的廣義表，第一項(xiàng)為原子，第二項(xiàng)為它本身。的廣義表，第一項(xiàng)為原子，第二項(xiàng)為它本身。 數(shù)數(shù) 據(jù)據(jù) 結(jié)結(jié) 構(gòu)構(gòu) http:/3廣義表的深度廣義表的深度 一個(gè)廣義表的深度是指該廣義表展開

40、后所含括號(hào)的層數(shù)。一個(gè)廣義表的深度是指該廣義表展開后所含括號(hào)的層數(shù)。例如，例如，A=(b,c)的深度為的深度為1，B=(A,d)的深度為的深度為2，C=(f,B,h)的深度為的深度為3。數(shù)數(shù) 據(jù)據(jù) 結(jié)結(jié) 構(gòu)構(gòu) http:/4取表頭運(yùn)算取表頭運(yùn)算head 若廣義表若廣義表LS=(a1，a2，an)， 則則head(LS)=a1 。取表頭運(yùn)算得到的結(jié)果可以是原子，也可以是一個(gè)子表。取表頭運(yùn)算得到的結(jié)果可以是原子，也可以是一個(gè)子表。例如，例如，head(a1,a2,a3,a4)=a1，head(a1,a2),(a3,a4),a5)=(a1,a2)。5取表尾運(yùn)算取表尾運(yùn)算tail若廣義表若廣義表LS=(a1，a2，an)，則，則tail(LS)=(a2，a3，an)。即取表尾運(yùn)算得到的結(jié)果是除表頭以外的所有元素，取表尾即取表尾運(yùn)算得到的結(jié)果是除表頭以外的所有元素，取表尾運(yùn)算得到的結(jié)果一定是一個(gè)子表。運(yùn)算得到的結(jié)果一定是一個(gè)子表。值得注意的是廣義表值得注意的是廣義表( )和和()是不同的，前者為空表，長(zhǎng)度為是不同的，前者為空表，長(zhǎng)度為0，后者的長(zhǎng)度為，后者的長(zhǎng)度為1，可得到表頭