數(shù)據(jù)結(jié)構(gòu)講義5

1、2022-3-221柳 青Email: School of Software , Yunnan University 數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)(Data Structure)2022-3-222第五章第五章 數(shù)組和廣義表數(shù)組和廣義表v5.1 數(shù)組的定義數(shù)組的定義v5.2 數(shù)組的順序表示和實現(xiàn)數(shù)組的順序表示和實現(xiàn)v5.3 矩陣的壓縮存儲矩陣的壓縮存儲 5.3.1 特殊矩陣特殊矩陣 5.3.2 稀疏矩陣稀疏矩陣v5.4 廣義表的定義廣義表的定義v5.5 廣義表的存儲結(jié)構(gòu)廣義表的存儲結(jié)構(gòu)2022-3-223v數(shù)組和廣義表數(shù)組和廣義表可看成是一種特殊的線性表，其特殊在于，表中可看成是一種特殊的線性表，其特殊在

2、于，表中的數(shù)據(jù)元素本身也是一種線性表。的數(shù)據(jù)元素本身也是一種線性表。v數(shù)組數(shù)組是是n(nn(n1)1)個相同類型數(shù)據(jù)元素構(gòu)成的有限序列，且該有限個相同類型數(shù)據(jù)元素構(gòu)成的有限序列，且該有限序列存儲在一塊地址連續(xù)的內(nèi)存單元中。序列存儲在一塊地址連續(xù)的內(nèi)存單元中。 v數(shù)組數(shù)組的抽象數(shù)據(jù)類型的抽象數(shù)據(jù)類型 ADT ArrayADT Array定義見定義見P90P90。v由于數(shù)組中各元素具有統(tǒng)一的類型，并且數(shù)組元素的下標(biāo)一般由于數(shù)組中各元素具有統(tǒng)一的類型，并且數(shù)組元素的下標(biāo)一般具有固定的上界和下界，因此，數(shù)組的處理比其它復(fù)雜的結(jié)構(gòu)具有固定的上界和下界，因此，數(shù)組的處理比其它復(fù)雜的結(jié)構(gòu)更為簡單。多維數(shù)組是

3、一維數(shù)組的推廣。例如，二維數(shù)組：更為簡單。多維數(shù)組是一維數(shù)組的推廣。例如，二維數(shù)組：5.1 5.1 數(shù)組的定義數(shù)組的定義nmmmnnn11211101122212021121110110201000aaamaaaaaaaaaaaaaA2022-3-224v可看作可看作A=A=（a0, a1, ., am-1a0, a1, ., am-1），即由），即由m m個行向個行向量組成的向量，其中量組成的向量，其中 aiai = =（ai0, ai1 ., ai0, ai1 ., ain-1ain-1）。）。 v在在C C語言中，一個二維數(shù)組類型可以定義為其分量類型為語言中，一個二維數(shù)組類型可以定義為其

4、分量類型為一維數(shù)組類型的一維數(shù)組類型，也就是說，一維數(shù)組類型的一維數(shù)組類型，也就是說， typedeftypedef elemtypeelemtype array2mn; array2mn; 等價于：等價于： typedeftypedef elemtypeelemtype array1n; array1n; typedeftypedef array1 array2m; array1 array2m; v數(shù)組一旦被定義，它的維數(shù)和維界就不再改變。因此，數(shù)組一旦被定義，它的維數(shù)和維界就不再改變。因此，除了結(jié)構(gòu)的初始化和銷毀之外，數(shù)組只有存取元素和修除了結(jié)構(gòu)的初始化和銷毀之外，數(shù)組只有存取元素和修改

5、元素值的操作。改元素值的操作。5.1 5.1 數(shù)組的定義數(shù)組的定義2022-3-225 由于計算機的內(nèi)存結(jié)構(gòu)是一維的，因此用一維內(nèi)存來表示由于計算機的內(nèi)存結(jié)構(gòu)是一維的，因此用一維內(nèi)存來表示多維數(shù)組，就必須按某種次序?qū)?shù)組元素排成一列序列，然后將多維數(shù)組，就必須按某種次序?qū)?shù)組元素排成一列序列，然后將這個線性序列存放在存儲器中。這個線性序列存放在存儲器中。 又由于對數(shù)組一般不做插入和刪除操作，也就是說，數(shù)組一又由于對數(shù)組一般不做插入和刪除操作，也就是說，數(shù)組一旦建立，結(jié)構(gòu)中的元素個數(shù)和元素間的關(guān)系就不再發(fā)生變化。因旦建立，結(jié)構(gòu)中的元素個數(shù)和元素間的關(guān)系就不再發(fā)生變化。因此，一般都是采用順序存儲的

6、方法來表示數(shù)組。此，一般都是采用順序存儲的方法來表示數(shù)組。 通常有通常有兩種順序存儲兩種順序存儲方式：方式：行優(yōu)先順序行優(yōu)先順序?qū)?shù)組元素按行排列，第將數(shù)組元素按行排列，第i+1i+1個行向量緊接在個行向量緊接在第第i i個行向量后面。在個行向量后面。在PASCALPASCAL、C C語言中，數(shù)組就是按行優(yōu)先順序語言中，數(shù)組就是按行優(yōu)先順序存儲的。存儲的。列優(yōu)先順序列優(yōu)先順序?qū)?shù)組元素按列向量排列，第將數(shù)組元素按列向量排列，第j+1j+1個列向量緊個列向量緊接在第接在第j j個列向量之后。在個列向量之后。在FORTRANFORTRAN語言中，數(shù)組就是按列優(yōu)先順語言中，數(shù)組就是按列優(yōu)先順序存儲的

7、。序存儲的。5.2 5.2 數(shù)組的順序表示數(shù)組的順序表示2022-3-226v二維數(shù)組二維數(shù)組A Amnmn的地址公式：的地址公式： LOC(aLOC(aijij)=LOC(a)=LOC(a0000)+(i)+(i* *n+jn+j) )* *d dv三維數(shù)組三維數(shù)組A Amnpmnp的地址公式為：的地址公式為：LOC(aLOC(aijkijk)=LOC(a)=LOC(a000000)+(i)+(i* *n n* *p+jp+j* *p+kp+k) )* *d dn 一維數(shù)組一維數(shù)組A Am m的地址公式：的地址公式：LOC(aLOC(ai i)=LOC(a)=LOC(a0 0)+i)+i*

8、*d d （設(shè)每個元素占用（設(shè)每個元素占用 d d個存儲單元）。個存儲單元）。5.2 5.2 數(shù)組的順序表示數(shù)組的順序表示2022-3-227v上述討論均假設(shè)數(shù)組各維的下界是上述討論均假設(shè)數(shù)組各維的下界是0 0，更一般的二維數(shù)組，更一般的二維數(shù)組是是AcAc1 1.d.d1 1,c,c2 2.d.d2 2 ，這里，這里c c1 1,c,c2 2不一定是不一定是0 0。a aijij前一共有前一共有i-ci-c1 1行，二維數(shù)組一共有行，二維數(shù)組一共有d d2 2-c-c2 2+1+1列，故這列，故這i-ci-c1 1行共有行共有(i-(i-c c1 1) )* *(d(d2 2-c-c2 2+

9、1)+1)個元素，第個元素，第i i行上行上a aijij前一共有前一共有j-cj-c2 2個元素，個元素，因此，因此，二維數(shù)組二維數(shù)組a aijij的地址計算函數(shù)為：的地址計算函數(shù)為： LOC(aLOC(aijij)=LOC(a)=LOC(ac c1 1c c2 2)+(i-c)+(i-c1 1) )* *(d(d2 2-c-c2 2+1)+j-c+1)+j-c2 2)* *d ddimiLOCdimimmmimmmiLOCiiiLOCnnjnjkkjnnnnnn*)()0 , 0 , 0( *)( )0 , 0 , 0(),(111143232121n n n維數(shù)組維數(shù)組A Am m1 1

10、m m2 2m mn n的地址公式：的地址公式：5.2 5.2 數(shù)組的順序表示數(shù)組的順序表示2022-3-228 在程序設(shè)計中時，矩陣通常采用二維數(shù)組表示，可以對其元素在程序設(shè)計中時，矩陣通常采用二維數(shù)組表示，可以對其元素進(jìn)行隨機存取，各種矩陣運算也非常簡單。進(jìn)行隨機存取，各種矩陣運算也非常簡單。 在矩陣中非零元素呈某種規(guī)律分布或者矩陣中出現(xiàn)大量的零元在矩陣中非零元素呈某種規(guī)律分布或者矩陣中出現(xiàn)大量的零元素時，為了節(jié)省存儲空間，可以對這類矩陣進(jìn)行壓縮存儲：素時，為了節(jié)省存儲空間，可以對這類矩陣進(jìn)行壓縮存儲： 為相為相同的非零元素只分配一個存儲空間；對零元素不分配空間。同的非零元素只分配一個存儲

11、空間；對零元素不分配空間。5.3.1 5.3.1 特殊矩陣特殊矩陣 特殊矩陣是指非零元素或零元素的分布有一定規(guī)律的矩陣。特殊矩陣是指非零元素或零元素的分布有一定規(guī)律的矩陣。1 1、對稱矩陣、對稱矩陣 在一個在一個n n階方陣階方陣A A中，若元素滿足下述性質(zhì)：中，若元素滿足下述性質(zhì)：a aijij= =a ajiji ，0i,jn-10i,jn-1，則稱，則稱A A為對稱矩陣。為對稱矩陣。5.3 5.3 矩陣的壓縮存儲矩陣的壓縮存儲2022-3-229 對稱矩陣中的元素關(guān)于主對角線對稱，所以只要存儲矩陣中對稱矩陣中的元素關(guān)于主對角線對稱，所以只要存儲矩陣中上三角或下三角中的元素即可。按上三角或

12、下三角中的元素即可。按“行優(yōu)先順序行優(yōu)先順序”存儲主對角存儲主對角線（包括對角線）以下的元素時，其存儲形式如下所示：線（包括對角線）以下的元素時，其存儲形式如下所示： 1 5 1 3 7 1 5 1 3 7 a a0000 5 0 8 0 0 5 0 8 0 0 a a10 10 a a 11 11 1 8 9 2 6 1 8 9 2 6 a a2020 a a2121 a a2323 3 0 2 5 1 3 0 2 5 1 . 7 0 6 1 3 7 0 6 1 3 a an-1 0n-1 0 a an-1 1 n-1 1 a an-1 2n-1 2 a an-1 n-1n-1 n-1 在這

13、個下三角矩陣中，第在這個下三角矩陣中，第i i行恰有行恰有i+1i+1個元素，元素總數(shù)為：個元素，元素總數(shù)為：n(n+1)/2n(n+1)/2。因此，可以按行優(yōu)先順序?qū)ΨQ矩陣。因此，可以按行優(yōu)先順序?qū)ΨQ矩陣A A中的中的n n2 2個元素個元素壓縮存放在一個向量壓縮存放在一個向量sa0.n(n+1)/2-1sa0.n(n+1)/2-1中。為了便于訪問對稱中。為了便于訪問對稱矩陣矩陣A A中的元素，必須在中的元素，必須在a aijij和和saksak 之間找一個對應(yīng)關(guān)系。之間找一個對應(yīng)關(guān)系。5.3 5.3 矩陣的壓縮存儲矩陣的壓縮存儲2022-3-2210 若若ijij，則，則a aijij

14、在下三角形中。在下三角形中。a aijij之前的之前的i i行（從第行（從第0 0行到第行到第i-i-1 1行）一共有行）一共有1+2+1+2+i=i(i+1)/2+i=i(i+1)/2個元素，在第個元素，在第i i行上行上a aijij之前有之前有j j個個元素（即元素（即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是在上三角矩陣中。因為是在上三角矩陣中。因為a aijij= =a ajiji，所以只要

15、交換，所以只要交換上述對應(yīng)關(guān)系式中的上述對應(yīng)關(guān)系式中的i i和和j j即可得到：即可得到： k=jk=j* *(j+1)/2+i 0 kn(n+1)/2 (j+1)/2+i 0 kn(n+1)/2 即：即： 5.3 5.3 矩陣的壓縮存儲矩陣的壓縮存儲jiijjjijiik,2) 1(,2) 1(思考：如何由思考：如何由k值求值求i，j？ an-1,n-1an-1 0a20a11a10a00k=0 1 2 3 n(n-1)/2 n(n+1)/2-12022-3-22112 2、三角矩陣、三角矩陣 以主對角線劃分，三角矩陣有上三角和下三角兩種。上三角矩以主對角線劃分，三角矩陣有上三角和下三角兩種

16、。上三角矩陣如圖所示，它的下三角（不包括主對角線）中的元素均為常數(shù)。陣如圖所示，它的下三角（不包括主對角線）中的元素均為常數(shù)。下三角矩陣正好相反，它的主對角線上方均為常數(shù)，如圖所示。在下三角矩陣正好相反，它的主對角線上方均為常數(shù)，如圖所示。在大多數(shù)情況下，三角矩陣常數(shù)為零。大多數(shù)情況下，三角矩陣常數(shù)為零。 a a0000 a a0101 a a0 n-10 n-1 a a0000 c c c c c a c a1111 a a1 n-11 n-1 a a1010 a a1111 c c . . . c c c c a an-1 n-1n-1 n-1 a an-1 0n-1 0 a an-1 1

17、n-1 1 a an-1 n-1 n-1 n-1 (a)(a)上三角矩陣上三角矩陣 (b)(b)下三角矩陣下三角矩陣5.3 5.3 矩陣的壓縮存儲矩陣的壓縮存儲2022-3-2212 三角矩陣中的重復(fù)元素三角矩陣中的重復(fù)元素c c可共享一個存儲空間，其余元素共有可共享一個存儲空間，其余元素共有n(n+1)/2n(n+1)/2個，因此三角矩陣可壓縮存儲到向量個，因此三角矩陣可壓縮存儲到向量sa0.n(n+1)/2sa0.n(n+1)/2中，其中中，其中c c存放在向量的最后一個分量中，上三角矩陣中，主對角線之上的第存放在向量的最后一個分量中，上三角矩陣中，主對角線之上的第p p行行(0pn)(0

18、p11時，元素時，元素a aijij=0=0。 在三對角矩陣?yán)锍凉M足條件在三對角矩陣?yán)锍凉M足條件i=0i=0，j=0j=0、1 1，或，或i=n-1j=n-2i=n-1j=n-2、n-1n-1或或1in-1,j=i-11in-1,j=i-1、i i、i+1i+1的元素的元素a aijij外，其余元素都是零。外，其余元素都是零。 對這種矩陣，也可按行優(yōu)先順序壓縮存儲到一個向量中。除第對這種矩陣，也可按行優(yōu)先順序壓縮存儲到一個向量中。除第0 0行和第行和第n-n-1 1行是行是2 2個元素外，每行的非零元素都要是個元素外，每行的非零元素都要是3 3個，因此，需存儲的元素個數(shù)為個，因此，需存儲的元素

19、個數(shù)為3n-23n-2。 數(shù)組數(shù)組sasa中的元素中的元素saksak 與三對角帶狀矩陣中的元素與三對角帶狀矩陣中的元素a aijij存在一一對應(yīng)關(guān)系，存在一一對應(yīng)關(guān)系，在在a aijij之前有之前有i i行行, ,共有共有2+32+3* *(i-1)(i-1)個非零元素，在第個非零元素，在第i i行行a aijij之前有之前有j-i+1j-i+1個非零個非零元素，這樣，非零元素元素，這樣，非零元素a aijij的地址為：的地址為： k=2+3k=2+3* *(i-1)+j-i+1=2(i-1)+j-i+1=2* *i+ji+j5.3 5.3 矩陣的壓縮存儲矩陣的壓縮存儲2022-3-2215

20、 設(shè)在的矩陣設(shè)在的矩陣A A中，有中，有s s個非零元素。令個非零元素。令 e=e=s/(ms/(m* *n)n)，稱，稱e e為矩陣的為矩陣的稀疏因子。通常認(rèn)為稀疏因子。通常認(rèn)為e0.05e0.05時稱之為稀疏矩陣。時稱之為稀疏矩陣。 在存儲稀疏矩陣時，為了節(jié)省存儲單元，很自然地想到使用壓縮存儲在存儲稀疏矩陣時，為了節(jié)省存儲單元，很自然地想到使用壓縮存儲方法。但由于非零元素的分布一般是沒有規(guī)律的，因此在存儲非零元方法。但由于非零元素的分布一般是沒有規(guī)律的，因此在存儲非零元素的同時，還必須同時記下它所在的行和列的位置（素的同時，還必須同時記下它所在的行和列的位置（i,ji,j) )。反之，一。

21、反之，一個三元組個三元組( (i,j,ai,j,aijij) )唯一確定了矩陣唯一確定了矩陣A A的一個非零元。因此，稀疏矩陣可的一個非零元。因此，稀疏矩陣可由表示非零元的三元組及其行列數(shù)唯一確定。由表示非零元的三元組及其行列數(shù)唯一確定。5.3.2 5.3.2 稀疏矩陣稀疏矩陣5.3 5.3 矩陣的壓縮存儲矩陣的壓縮存儲i i（行行行行）j j（列列列列）v v（值值值值）2022-3-2216 0 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 -3 0 0 0 0 14 0 9 0 0 24 0 0 0 0 24 0 0 0 0

22、 0 0 0 0 0 7 0 18 0 0 0 0 0 0 0 14 0 0 0 15 0 0 7 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 M=T=5.3 5.3 矩陣的壓縮存儲矩陣的壓縮存儲 例如，三元組表例如，三元組表:(1,2,12),(1,3,9),(3,1,-:(1,2,12),(1,3,9),(3,1,-3),(3,6,14),(4,3,24),(5,2,18),(6,1,15),(6,4,-7) 3),(3,6,14),(4,3,24),(5,2,18),(6,1,15),(6,4,-7) 加上加上(6,7)(6,7)這一對行、列值便可作為下列矩陣這一對行、列

23、值便可作為下列矩陣M M的另一種描的另一種描述。而由上述三元組表的不同表示方法可引出稀疏矩陣不述。而由上述三元組表的不同表示方法可引出稀疏矩陣不同的壓縮存儲方法。同的壓縮存儲方法。2022-3-2217 假設(shè)以順序存儲結(jié)構(gòu)來表示三元組表，則可得到稀疏矩假設(shè)以順序存儲結(jié)構(gòu)來表示三元組表，則可得到稀疏矩陣的一種壓縮存儲方法陣的一種壓縮存儲方法三元組順序表。三元組順序表。5.3 5.3 矩陣的壓縮存儲矩陣的壓縮存儲 #define maxsize 10000 typedef int datatype; typedef struct int i,j; datatype v; triple; typed

24、ef struct triple datamaxsize+1; int m,n,t; /行、列、非零個數(shù) tripletable;一、三元組順序表三元組順序表2022-3-2218矩陣的轉(zhuǎn)置運算矩陣的轉(zhuǎn)置運算 設(shè)有一個設(shè)有一個m mn n的矩陣的矩陣A A，則它的轉(zhuǎn)置，則它的轉(zhuǎn)置B B是一個是一個n nm m的矩陣的矩陣且：且：aijaij=bjibji ，1im1im，1jn1jn， 即即A A的行是的行是B B的列，的列，A A的列是的列是B B的行。的行。 將將A A轉(zhuǎn)置為轉(zhuǎn)置為B B，就是將，就是將A A的三元組表的三元組表a.dataa.data置換為表置換為表B B的三的三元組表元

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

26、按行優(yōu)先存放的。5.3 5.3 矩陣的壓縮存儲矩陣的壓縮存儲2022-3-2219算法思想：算法思想：對對A A中的每一列中的每一列col(1coln)col(1coln)，通過從頭至尾掃描三元表，通過從頭至尾掃描三元表a.dataa.data，找出所有列號等于，找出所有列號等于colcol的那些三元組，將其行號和列號互換后依的那些三元組，將其行號和列號互換后依次放入次放入b.datab.data中，即可得到中，即可得到B B的按行優(yōu)先的壓縮存儲表示。的按行優(yōu)先的壓縮存儲表示。5.3 矩陣的壓縮存儲ijv121213931-3361443245218611564-7ijv13-31615211

27、22518319342446-76314矩陣矩陣A A矩陣矩陣B B2022-3-2220void transmatrix( tripletable a, tripletable &b ) int p, q, col; b.m=a.n; b.n=a.m; b.t=a.t; if( b.t = 0 ) printf(“A=0n”); q=1; for( col=1; col=a.n; col+ ) for( p=1; p=a.t; p+ ) if( a.datap.j = col ) b.dataq.i = a.datap.j; b.dataq.j = a.datap.i; b.data

28、q.v = a.datap.v; q+; 5.3 5.3 矩陣的壓縮存儲矩陣的壓縮存儲演示2022-3-2221 分析這個算法，主要的工作是在分析這個算法，主要的工作是在p p和和colcol的兩個循環(huán)中完成的兩個循環(huán)中完成的，故算法的時間復(fù)雜度為的，故算法的時間復(fù)雜度為O(nO(n* *t)t)，即矩陣的列數(shù)和非零元的，即矩陣的列數(shù)和非零元的個數(shù)的乘積成正比。而一般傳統(tǒng)矩陣的轉(zhuǎn)置算法為：個數(shù)的乘積成正比。而一般傳統(tǒng)矩陣的轉(zhuǎn)置算法為： for(colfor(col=0;col=n-1;+col)=0;col=n-1;+col) for(rowfor(row=0;row=0;row=m;+row

29、m;+row) ) tcolrowtcolrow=mrowcolmrowcol; 其時間復(fù)雜度為其時間復(fù)雜度為O(nO(n* *m)m)。當(dāng)非零元素的個數(shù)。當(dāng)非零元素的個數(shù)t t和和m m* *n n同數(shù)量同數(shù)量級時，算法級時，算法transmatrixtransmatrix的時間復(fù)雜度為的時間復(fù)雜度為O(mO(m* *n n2 2) )。 三元組順序表雖然節(jié)省了存儲空間，但時間復(fù)雜度比一般三元組順序表雖然節(jié)省了存儲空間，但時間復(fù)雜度比一般矩陣轉(zhuǎn)置的算法還要復(fù)雜，同時還有可能增加算法的難度。矩陣轉(zhuǎn)置的算法還要復(fù)雜，同時還有可能增加算法的難度。 因此，此算法僅適用于因此，此算法僅適用于t mt

30、m* *n n的情況的情況( (稀疏矩陣稀疏矩陣) )。5.3 5.3 矩陣的壓縮存儲矩陣的壓縮存儲2022-3-2222快速轉(zhuǎn)置的算法快速轉(zhuǎn)置的算法： 對對A A掃描一次，按掃描一次，按A A的列號一次確定位置裝入的列號一次確定位置裝入B B的一個三元組。的一個三元組。具體實施如下：具體實施如下：一遍掃描先確定三元組的位置關(guān)系，二次掃描由位置關(guān)系裝入一遍掃描先確定三元組的位置關(guān)系，二次掃描由位置關(guān)系裝入三元組。可見，位置關(guān)系是此種算法的關(guān)鍵。三元組。可見，位置關(guān)系是此種算法的關(guān)鍵。 為了預(yù)先確定矩陣為了預(yù)先確定矩陣A A中的每一列的第一個非零元素在數(shù)組中的每一列的第一個非零元素在數(shù)組B B中

31、應(yīng)有的位置，中應(yīng)有的位置，需要先求得矩陣需要先求得矩陣A A中的每一列中非零元素的個數(shù)。中的每一列中非零元素的個數(shù)。 矩陣矩陣A A中每一列的第一個非零元素在數(shù)組中每一列的第一個非零元素在數(shù)組B B中應(yīng)有的位置等于前一列第一個中應(yīng)有的位置等于前一列第一個非零元素的位置加上前列非零元素的個數(shù)。非零元素的位置加上前列非零元素的個數(shù)。 為此，需要設(shè)置兩個一維數(shù)組為此，需要設(shè)置兩個一維數(shù)組num1.A.nnum1.A.n和和cpot1.A.ncpot1.A.n num1.A.n num1.A.n ：統(tǒng)計：統(tǒng)計A A中每列非零元素的個數(shù)，中每列非零元素的個數(shù)，numcolnumcol 的值可以由的值可以

32、由A A的非的非零元的列號求得。零元的列號求得。 cpot1.A.ncpot1.A.n：由遞推關(guān)系得出：由遞推關(guān)系得出A A中的每列第一個非零元素在中的每列第一個非零元素在B B中的位置。中的位置。5.3 5.3 矩陣的壓縮存儲矩陣的壓縮存儲2022-3-2223算法通過算法通過cpotcpot數(shù)組建立位置對應(yīng)關(guān)系：數(shù)組建立位置對應(yīng)關(guān)系： cpot1=1cpot1=1 cpotcolcpotcol=cpotcol-1+numcol-1 2=cpotcol-1+numcol-1 2=colcol=a.na.n 例如：前例中的矩陣?yán)纾呵袄械木仃嘇 A可以求得可以求得numcolnumcol 和

33、和cpotcolcpotcol 的值的值如下：如下：colcolnumcolnumcol cpotcolcpotcol 1 2 3 4 5 6 7 1 2 3 4 5 6 7 2 2 2 1 0 1 0 2 2 2 1 0 1 0 1 3 5 7 8 8 9 1 3 5 7 8 8 95.3 5.3 矩陣的壓縮存儲矩陣的壓縮存儲2022-3-2224Status fasttranstri(tritupletable b,tritupletable a) b.m=a.n; b.n=a.m; b.t=a.t; if(b.t) for(col=1;col=a.n;+col) numcol=0; fo

34、r(k=1;k=a.t;+k) +numa.datak.j; cpot1=1; for(col=2;col=a.n;+col) cpotcol=cpotcol-1+numcol-1; for(p=1;p=a.t;+p) col=a.datap.j; q=cpotcol; b.dataq.i=a.datap.j; b.dataq.j=a.datap.i; b.dataq.v=a.datap.v; +cpotcol; /for /if return OK;時間復(fù)雜度為時間復(fù)雜度為O(n+tO(n+t),),最壞情況最壞情況 O(mO(m* *n)n)。5.3 5.3 矩陣的壓縮存儲矩陣的壓縮存儲演

35、示2022-3-2225二、帶行表的三元組二、帶行表的三元組 有時為了方便某些矩陣運算，我們在按行優(yōu)先存儲的三元組有時為了方便某些矩陣運算，我們在按行優(yōu)先存儲的三元組中，加入一個行表來記錄稀疏矩陣中每行的非零元素在三元組表中，加入一個行表來記錄稀疏矩陣中每行的非零元素在三元組表中的起始位置。當(dāng)將行表作為三元組表的一個新增屬性加以描述中的起始位置。當(dāng)將行表作為三元組表的一個新增屬性加以描述時，我們就得到了稀疏矩陣的另一種順序存儲結(jié)構(gòu)：帶行表的三時，我們就得到了稀疏矩陣的另一種順序存儲結(jié)構(gòu)：帶行表的三元組表。其類型描述如下：元組表。其類型描述如下： #define maxrow 100 typed

36、ef struct triple datamaxsize; int rposmaxrow; int n,m,t; rtripletable5.3 5.3 矩陣的壓縮存儲矩陣的壓縮存儲2022-3-2226 兩個矩陣相乘的經(jīng)典算法也是大家所熟悉的。若設(shè)兩個矩陣相乘的經(jīng)典算法也是大家所熟悉的。若設(shè)Q=MQ=M* *N N其中，其中，M M是是m m1 1* *n n1 1矩陣，矩陣，N N是是m m2 2* *n n2 2矩陣。當(dāng)矩陣。當(dāng)n n1 1=m=m2 2時有：時有： for(ifor(i=1;i=m1;+i)=1;i=m1;+i) for(jfor(j=1;j=n2;+j)=1;j=n2

37、;+j) qijqij=0=0 for(kfor(k=1;k=n1;+k)=1;k=n1;+k) qijqij+=+=mikmik * *nkjnkj; 此算法的復(fù)雜度為此算法的復(fù)雜度為O(mO(m1 1* *n n1 1* *n n2 2) )。 當(dāng)當(dāng)M M和和N N是稀疏矩陣并用三元組表存儲結(jié)構(gòu)時，就不能套用是稀疏矩陣并用三元組表存儲結(jié)構(gòu)時，就不能套用上述算法。上述算法。 5.3 5.3 矩陣的壓縮存儲矩陣的壓縮存儲2022-3-2227假設(shè)假設(shè)M M和和N N分別為：分別為： 3 0 0 50 -1 0 02 0 0 0Mm1*n1= 0 2 1 0-2 4 0 0Nn1*n2=則則Q=

38、MQ=M* *N N為：為： 0 6-1 0 0 4Qm1*n2=5.3 5.3 矩陣的壓縮存儲矩陣的壓縮存儲乘積矩陣乘積矩陣Q Q中元素中元素 Q(i,j)=11),(*),(nkjkNkiM（）（）2022-3-2228 它們的三元組分別為：它們的三元組分別為： i j v i j v i j v 1 1 3 1 2 2 1 2 6 1 4 5 2 1 1 2 1 -1 3 2 -1 3 1 -2 3 2 4 3 1 2 3 2 4 q.data m.data n.data 稀疏矩陣稀疏矩陣相乘的基本思想相乘的基本思想是：對于是：對于M M中每個元素中每個元素M.datapM.datap

39、，找到，找到N N中所中所有滿足條件有滿足條件M.datap.jM.datap.j= = N.dataq.iN.dataq.i的元素的元素N.dataqN.dataq ，求得，求得M.datap.vM.datap.v和和N.dataq.vN.dataq.v的乘積，而從式（的乘積，而從式（- -）得知，乘積矩陣）得知，乘積矩陣Q Q中中每個元素的值是個累加和，這個乘積只是其中的一部分。為了便于操作，應(yīng)每個元素的值是個累加和，這個乘積只是其中的一部分。為了便于操作，應(yīng)對每個元素設(shè)一累加和的變量，其初值為零，然后掃描數(shù)組對每個元素設(shè)一累加和的變量，其初值為零，然后掃描數(shù)組M M，求得相應(yīng)元，求得相應(yīng)

40、元素的乘積并累加到適當(dāng)?shù)那罄塾嫼偷淖兞可?。素的乘積并累加到適當(dāng)?shù)那罄塾嫼偷淖兞可稀?算法見算法見P102-103P102-103。5.3 5.3 矩陣的壓縮存儲矩陣的壓縮存儲2022-3-2229Status multsmatrix( rtripletable a, rtripletable b, rtripletable c) if(a.n!=b.m) return ERROR; c.m=a.m; c.n=b.n; c.t=0; if(a.t*b.t!=0) for(arow=1;arow=a.m;+arow) ctemparow=0; c.rposarow=c.t+1; for(p=a.r

41、opsarow;pa.rposarow+1;+p) brow=a.datap.j; if(browb.m) t=b.rposbrow+1 else t=b.t+1; for(q=b.rposbrow; qt;+q) ccol=n.dataq.j; ctempccol+=a.datap.v*b.dataq.v; for(ccol=1;ccolmaxsize) return ERROR; c.datac.t=arow,ccol,ctempccol; return OK;2022-3-22305.3 5.3 矩陣的壓縮存儲矩陣的壓縮存儲三、十字鏈表三、十字鏈表稀疏矩陣稀疏矩陣M的十字鏈表的十字鏈表t

42、ypedef struct OLNode int i; int j; ElemType e; struct OLNode *right; struct OLNode *down; *OLink;typedef struct OLink *rhead; OLink *chead; int mu; int nu; int tu; CrossList;11314522-1312M.cheadM.rhead2022-3-2231假設(shè)假設(shè)M M和和N N分別為：分別為： 3 0 0 50 -1 0 02 0 0 0M= 0 2 1 0-2 4 0 0N=則Q=M*N為： 0 6-1 0 0 4Q=5.3

43、 5.3 矩陣的壓縮存儲矩陣的壓縮存儲2022-3-22325.3 5.3 矩陣的壓縮存儲矩陣的壓縮存儲n n 當(dāng)矩陣的非零元個數(shù)和位置在操作過程中變化較大當(dāng)矩陣的非零元個數(shù)和位置在操作過程中變化較大時，采用鏈?zhǔn)酱鎯Y(jié)構(gòu)表示三元組的線形表更為合時，采用鏈?zhǔn)酱鎯Y(jié)構(gòu)表示三元組的線形表更為合適。適。n n 鏈表中的每個非零元可用一個含五個域的結(jié)點表鏈表中的每個非零元可用一個含五個域的結(jié)點表示，其中示，其中i，j和和e 分別表示該非零元所在的行、列和分別表示該非零元所在的行、列和值，指針值，指針right用以鏈接同一行中下一個非零元，指用以鏈接同一行中下一個非零元，指針針down用以鏈接同一列中下一

44、個非零元。用以鏈接同一列中下一個非零元。n n 同一行的非零元通過指針同一行的非零元通過指針right鏈接成一個鏈表。鏈接成一個鏈表。n n 同一列的非零元通過指針同一列的非零元通過指針down鏈接成一個鏈表。鏈接成一個鏈表。2022-3-22335.3 5.3 矩陣的壓縮存儲矩陣的壓縮存儲v每個非零元既是某個行鏈表中的一個結(jié)點，也每個非零元既是某個行鏈表中的一個結(jié)點，也是某個列鏈表中的一個結(jié)點，整個矩陣構(gòu)成一是某個列鏈表中的一個結(jié)點，整個矩陣構(gòu)成一個個十字鏈表十字鏈表。vn n 所有的行鏈表的頭指針組成一個指針數(shù)組。所有的行鏈表的頭指針組成一個指針數(shù)組。vn n 所有的列鏈表的頭指針組成一個

45、指針數(shù)組。所有的列鏈表的頭指針組成一個指針數(shù)組。vn n 稀疏矩陣的十字鏈表由行鏈表頭指針數(shù)組、稀疏矩陣的十字鏈表由行鏈表頭指針數(shù)組、列鏈表頭指針數(shù)組、行數(shù)、列數(shù)和非零元個數(shù)列鏈表頭指針數(shù)組、行數(shù)、列數(shù)和非零元個數(shù)組成。組成。v 建立十字鏈表算法見建立十字鏈表算法見 P104 算法算法5.4。2022-3-22345.4 5.4 廣義表的定義廣義表的定義n 廣義表廣義表的概念的概念: n( : n( 0 0 ) )個表元素組成的有限序列，個表元素組成的有限序列，記作：記作： LS = (aLS = (a0 0, a, a1 1, a, a2 2, , , a, an-1n-1) ) LS LS

46、是是表名表名，a ai i是是表元素表元素，它可以是表，它可以是表( (稱為子表稱為子表) )，可以是數(shù)據(jù)元素可以是數(shù)據(jù)元素( (稱為原子稱為原子) )。 a0為表頭，為表頭， ( a1, a2, , an-1)為表尾。為表尾。n n n為為表的長度表的長度。n = 0 n = 0 的廣義表為空表。的廣義表為空表。 n 例如：例如：A = ( ) B = ( 6, 2 )C = ( a, ( 5, 3, x ) )D = ( B, C, A )E = ( B, D )F = ( 4, F )2022-3-2235各種廣義表的示意圖各種廣義表的示意圖2022-3-2236 n n00時，時，廣義表的第一個元素稱為廣義表的廣義表的第一個元素稱為廣義表的表頭表頭( (headhead) )，除此之外，其它元素組成的表稱為廣義表的除此之外，其它元素組成的表稱為廣義表的表尾表尾( (tailtail) )。例如：例如：A =A =（）（） B =B =（6,26