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

1、1/55第第5章章 數(shù)組和廣義表數(shù)組和廣義表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)2/55l數(shù)組和廣義表可看成是一種特殊的線性表數(shù)組和廣義表可看成是一種特殊的線性表，其特殊在于，表，其特殊在于，表中的所有或部分元素本身也是一種線性表。中的所有或部分元素本身也是一種線性表。mnmmnnnmaaaaaaaaaA212222111211l由于數(shù)組中各元素具有統(tǒng)一的類型，并且數(shù)組元素的下標(biāo)具由于數(shù)組中各

2、元素具有統(tǒng)一的類型，并且數(shù)組元素的下標(biāo)具有固定的上界和下界，因此，數(shù)組的處理比其它復(fù)雜的數(shù)據(jù)有固定的上界和下界，因此，數(shù)組的處理比其它復(fù)雜的數(shù)據(jù)結(jié)構(gòu)較為簡(jiǎn)單。結(jié)構(gòu)較為簡(jiǎn)單。l多維數(shù)組是向量的推廣。例如，二維數(shù)組：多維數(shù)組是向量的推廣。例如，二維數(shù)組：5.1 數(shù)組的定義數(shù)組的定義3/55l二維數(shù)組可以看成是二維數(shù)組可以看成是由行向量組成的向量由行向量組成的向量，也可以看成是，也可以看成是由列向量組成的向量由列向量組成的向量。l同樣，可把三維數(shù)組看成是一個(gè)線性表，表中每一個(gè)數(shù)據(jù)同樣，可把三維數(shù)組看成是一個(gè)線性表，表中每一個(gè)數(shù)據(jù)元素為一個(gè)二維數(shù)組。依次類推，可把元素為一個(gè)二維數(shù)組。依次類推，可把n維

3、維數(shù)組看成是一個(gè)數(shù)組看成是一個(gè)線性表，表中每一個(gè)數(shù)據(jù)元素是一個(gè)線性表，表中每一個(gè)數(shù)據(jù)元素是一個(gè)n-1維數(shù)組。維數(shù)組。l數(shù)組的運(yùn)算：數(shù)組一旦被定義，它的維數(shù)和維界就不再改數(shù)組的運(yùn)算：數(shù)組一旦被定義，它的維數(shù)和維界就不再改變。因此，除了結(jié)構(gòu)的初始化和銷毀之外，變。因此，除了結(jié)構(gòu)的初始化和銷毀之外，數(shù)組只有存取數(shù)組只有存取元素和修改元素值的操作，元素和修改元素值的操作，即給定一組下標(biāo)，存取或修改即給定一組下標(biāo)，存取或修改相應(yīng)的數(shù)組元素。相應(yīng)的數(shù)組元素。5.1 數(shù)組的定義數(shù)組的定義4/551、順序存儲(chǔ)結(jié)構(gòu)、順序存儲(chǔ)結(jié)構(gòu)5.2 數(shù)組的順序表示和實(shí)現(xiàn)數(shù)組的順序表示和實(shí)現(xiàn)l用一組地址連續(xù)的存儲(chǔ)單元依次存放數(shù)

4、組的數(shù)據(jù)元素，稱為用一組地址連續(xù)的存儲(chǔ)單元依次存放數(shù)組的數(shù)據(jù)元素，稱為數(shù)組的順序存儲(chǔ)結(jié)構(gòu)數(shù)組的順序存儲(chǔ)結(jié)構(gòu)。l由于計(jì)算機(jī)的內(nèi)存結(jié)構(gòu)是一維的，因此用一維內(nèi)存來表示多由于計(jì)算機(jī)的內(nèi)存結(jié)構(gòu)是一維的，因此用一維內(nèi)存來表示多維數(shù)組，就必須按維數(shù)組，就必須按某種次序某種次序?qū)?shù)組元素排成一列序列，然后將數(shù)組元素排成一列序列，然后將這個(gè)線性序列存放在存儲(chǔ)器中。將這個(gè)線性序列存放在存儲(chǔ)器中。l由于對(duì)數(shù)組一般不做插入和刪除操作，也就是說，數(shù)組一旦由于對(duì)數(shù)組一般不做插入和刪除操作，也就是說，數(shù)組一旦建立，結(jié)構(gòu)中的元素個(gè)數(shù)和元素間的關(guān)系就不再發(fā)生變化。建立，結(jié)構(gòu)中的元素個(gè)數(shù)和元素間的關(guān)系就不再發(fā)生變化。因此，因此，

5、一般都是采用順序存儲(chǔ)結(jié)構(gòu)來表示數(shù)組一般都是采用順序存儲(chǔ)結(jié)構(gòu)來表示數(shù)組。 5/55 通常有兩種順序存儲(chǔ)方式：通常有兩種順序存儲(chǔ)方式：2、順序存儲(chǔ)方式、順序存儲(chǔ)方式l行行優(yōu)先順序優(yōu)先順序?qū)?shù)組元素按行向量排列，第將數(shù)組元素按行向量排列，第i+1個(gè)行向量緊個(gè)行向量緊接在第接在第i個(gè)行向量之后。以二維數(shù)組為例，按行優(yōu)先順序存儲(chǔ)的個(gè)行向量之后。以二維數(shù)組為例，按行優(yōu)先順序存儲(chǔ)的線性序列為：線性序列為：a11,a12,a1n,a21,a22,a2n, ,am1,am2,amn 在在PASCAL、C語言中，數(shù)組就是按行優(yōu)先順序存儲(chǔ)的。語言中，數(shù)組就是按行優(yōu)先順序存儲(chǔ)的。l列優(yōu)先順序列優(yōu)先順序?qū)?shù)組元素按列向

6、量排列，第將數(shù)組元素按列向量排列，第j+1個(gè)列向量緊個(gè)列向量緊接在第接在第j個(gè)列向量之后。以二維數(shù)組為例，按列優(yōu)先順序存儲(chǔ)的個(gè)列向量之后。以二維數(shù)組為例，按列優(yōu)先順序存儲(chǔ)的線性序列為：線性序列為：a11,a21,am1,a12,a22,am2, ,a1n,a2n,amn 在在FORTRAN語言中，數(shù)組就是按列優(yōu)先順序存儲(chǔ)的。語言中，數(shù)組就是按列優(yōu)先順序存儲(chǔ)的。6/55 a11 a12 . a1n a21 a22 . a2n am1 am2 . amn .Loc( aij)=Loc(a11)+(i-1)n+(j-1)*l 以行序?yàn)橹餍虼娣乓孕行驗(yàn)橹餍虼娣?amn am2 am1 a2n a22

7、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 7/55l以上規(guī)則推廣到多維數(shù)組的情況：以上規(guī)則推廣到多維數(shù)組的情況：行優(yōu)先順序可規(guī)定為先排行優(yōu)先順序可規(guī)定為先排最右的下標(biāo)，從右到左，最后排最左的下標(biāo)最右的下標(biāo)，從右到左，最后排最左的下標(biāo)；3、n維數(shù)組維數(shù)組l按上述兩種方式順序存儲(chǔ)的數(shù)組，只要知道開始元素的存放按上

8、述兩種方式順序存儲(chǔ)的數(shù)組，只要知道開始元素的存放地址（即基地址）、維數(shù)和每維的上、下界，以及每個(gè)數(shù)組地址（即基地址）、維數(shù)和每維的上、下界，以及每個(gè)數(shù)組元素所占用的單元數(shù)，就可以將數(shù)組元素的存放地址表示為元素所占用的單元數(shù)，就可以將數(shù)組元素的存放地址表示為其下標(biāo)的線性函數(shù)。因此，其下標(biāo)的線性函數(shù)。因此，數(shù)組中的任一元素可以在相同的數(shù)組中的任一元素可以在相同的時(shí)間內(nèi)存取，即順序存儲(chǔ)的數(shù)組是一個(gè)隨機(jī)存取結(jié)構(gòu)。時(shí)間內(nèi)存取，即順序存儲(chǔ)的數(shù)組是一個(gè)隨機(jī)存取結(jié)構(gòu)。l列優(yōu)先順序與此相反，先排最左的下標(biāo)，從左到右，最后排列優(yōu)先順序與此相反，先排最左的下標(biāo)，從左到右，最后排最右的下標(biāo)。最右的下標(biāo)。8/55l例如

9、，二維數(shù)組例如，二維數(shù)組Amn按按“行優(yōu)先順序行優(yōu)先順序”存儲(chǔ)在內(nèi)存中，假設(shè)存儲(chǔ)在內(nèi)存中，假設(shè)每個(gè)元素占用每個(gè)元素占用d個(gè)存儲(chǔ)單元。個(gè)存儲(chǔ)單元。4、地址公式、地址公式 元素元素aij的存儲(chǔ)地址應(yīng)是的存儲(chǔ)地址應(yīng)是數(shù)組的基地址加上排在數(shù)組的基地址加上排在aij前面的元前面的元素所占用的單元數(shù)素所占用的單元數(shù)。因?yàn)?。因?yàn)閍ij位于第位于第i行、第行、第j列，前面列，前面i-1行一共行一共有有(i-1) n個(gè)元素，在第個(gè)元素，在第i行上行上aij前面還有前面還有j-1個(gè)元素，故它前面?zhèn)€元素，故它前面一共有一共有(i-1) n+j-1個(gè)元素，因此，個(gè)元素，因此，aij的地址計(jì)算函數(shù)為：的地址計(jì)算函數(shù)為：

10、LOC(aij)=LOC(a11)+(i-1)*n+j-1*dl同樣，三維數(shù)組同樣，三維數(shù)組Amnp按按“行優(yōu)先順序行優(yōu)先順序”存儲(chǔ)，其地址計(jì)算函數(shù)存儲(chǔ)，其地址計(jì)算函數(shù)為：為： LOC(aijk)=LOC(a111)+(i-1)*n*p+(j-1)*p +(k-1)*d9/55l上述討論均是假設(shè)數(shù)組各維的下界是上述討論均是假設(shè)數(shù)組各維的下界是1，更一般的二維數(shù)組，更一般的二維數(shù)組是是Ac1.d1 , c2.d2，這里，這里c1,c2不一定是不一定是1。aij前一共有前一共有i-c1行，二維數(shù)組一共有行，二維數(shù)組一共有d2-c2+1列，故這列，故這i-c1行共有行共有(i-c1)*(d2-c2+

11、1)個(gè)元素，在第個(gè)元素，在第i行上行上aij前一共有前一共有j-c2個(gè)元素，因此，個(gè)元素，因此，aij的的地址計(jì)算函數(shù)為：地址計(jì)算函數(shù)為： LOC(aij)=LOC(ac1c2)+(i-c1)*(d2-c2+1)+j-c2)*dl例如，在例如，在C語言中，數(shù)組各維下標(biāo)的下界是語言中，數(shù)組各維下標(biāo)的下界是0，因此在，因此在C語言語言中，二維數(shù)組的地址計(jì)算公式為：中，二維數(shù)組的地址計(jì)算公式為： LOC(aij)=LOC(a00)+(i*(d2+1)+j)*d4、地址公式、地址公式10/55l在高級(jí)語言編制程序時(shí)，將一個(gè)矩陣描述為一個(gè)二維數(shù)組。在高級(jí)語言編制程序時(shí)，將一個(gè)矩陣描述為一個(gè)二維數(shù)組。但是

12、在矩陣中非零元素呈某種規(guī)律重復(fù)分布或者矩陣中出現(xiàn)但是在矩陣中非零元素呈某種規(guī)律重復(fù)分布或者矩陣中出現(xiàn)大量的零元素的情況下，大量的零元素的情況下，實(shí)際上占用了許多單元去存儲(chǔ)重復(fù)實(shí)際上占用了許多單元去存儲(chǔ)重復(fù)的非零元素或零元素的非零元素或零元素，這對(duì)高階矩陣的存儲(chǔ)會(huì)造成極大的浪，這對(duì)高階矩陣的存儲(chǔ)會(huì)造成極大的浪費(fèi)。為了節(jié)省存儲(chǔ)空間，費(fèi)。為了節(jié)省存儲(chǔ)空間， 可以對(duì)這類矩陣進(jìn)行壓縮存儲(chǔ)?？梢詫?duì)這類矩陣進(jìn)行壓縮存儲(chǔ)。5.3 矩陣的壓縮存儲(chǔ)矩陣的壓縮存儲(chǔ)l壓縮存儲(chǔ)：壓縮存儲(chǔ)：為多個(gè)值相同的非零元素只分配一個(gè)存儲(chǔ)空間；為多個(gè)值相同的非零元素只分配一個(gè)存儲(chǔ)空間； 對(duì)零元素不分配空間。對(duì)零元素不分配空間。l假若

13、值相同的元素或零元素在矩陣中的分布有一定規(guī)律，則假若值相同的元素或零元素在矩陣中的分布有一定規(guī)律，則稱此類矩陣為稱此類矩陣為特殊矩陣特殊矩陣；反之，稱為；反之，稱為稀疏矩陣稀疏矩陣。11/551、對(duì)稱矩陣、對(duì)稱矩陣 5.3.1 特殊矩陣特殊矩陣l在一個(gè)在一個(gè)n階方陣階方陣A中，中，若元素滿足下述性質(zhì)：若元素滿足下述性質(zhì)： aij=aji 0i , jn-1 則稱則稱A為對(duì)稱矩陣為對(duì)稱矩陣。 對(duì)稱矩陣中的元素關(guān)于主對(duì)角線對(duì)稱，對(duì)稱矩陣中的元素關(guān)于主對(duì)角線對(duì)稱，故只要存儲(chǔ)矩陣中上三角或下三角中的元素，讓每?jī)蓚€(gè)對(duì)稱故只要存儲(chǔ)矩陣中上三角或下三角中的元素，讓每?jī)蓚€(gè)對(duì)稱的元素共享一個(gè)存儲(chǔ)空間，這樣，能節(jié)

14、約近一半的存儲(chǔ)空的元素共享一個(gè)存儲(chǔ)空間，這樣，能節(jié)約近一半的存儲(chǔ)空間。不失一般性，按間。不失一般性，按“行優(yōu)先順序行優(yōu)先順序”存儲(chǔ)主對(duì)角線（包括對(duì)存儲(chǔ)主對(duì)角線（包括對(duì)角線）以下的元素，其存儲(chǔ)形式如圖所示：角線）以下的元素，其存儲(chǔ)形式如圖所示： a00 a01 . a0n-1 a10 a11 . a1n-1 an-10 an-11 . an-1n-1 . 12/55a00a10 a11a20 a21 a22 .an-1 0 an-1 1 an-1 2 a n-1 n-1 a00 a01 . . a0n-1 a10 a11 . . a1n-1 an-10 an-11 . an-1n-1 . 對(duì)稱矩

15、陣的下三角l在這個(gè)下三角矩陣中，第在這個(gè)下三角矩陣中，第i行恰有行恰有i+1個(gè)元素，元素總數(shù)為：個(gè)元素，元素總數(shù)為：n(n+1)/2。這樣可將這樣可將n2個(gè)壓縮到個(gè)壓縮到n(n+1)/2個(gè)元的空間中。個(gè)元的空間中。l因此，可以按將這些元素存放在一個(gè)向量因此，可以按將這些元素存放在一個(gè)向量sa0.n(n+1)/2-1中。為了便于訪問對(duì)稱矩陣中。為了便于訪問對(duì)稱矩陣A中的元素，必須在中的元素，必須在aij和和sak之之間找一個(gè)對(duì)應(yīng)關(guān)系。間找一個(gè)對(duì)應(yīng)關(guān)系。1、對(duì)稱矩陣、對(duì)稱矩陣13/55l若若ij，則，則aij在下三角形中。在下三角形中。 aij之前的之前的i行（從第行（從第0行到第行到第i-1行）

16、一共有行）一共有1+2+i=i(i+1)/2個(gè)元素，在第個(gè)元素，在第i行上，行上， aij之之前恰有前恰有j個(gè)元素（即個(gè)元素（即ai0,ai1,ai2,aij-1），因此有：），因此有：1、對(duì)稱矩陣、對(duì)稱矩陣 k=i*(i+1)/2+j 0kn(n+1)/2l若若i j，則，則aij是在上三角矩陣中。因?yàn)槭窃谏先蔷仃囍?。因?yàn)閍ij=aji，所以只要交，所以只要交換上述對(duì)應(yīng)關(guān)系式中的換上述對(duì)應(yīng)關(guān)系式中的i和和j即可得到：即可得到： k=j*(j+1)/2+i 0 kn(n+1)/2 l令令 I=max(i,j)， J=min(i,j)，則，則k和和 i, j的對(duì)應(yīng)關(guān)系可統(tǒng)一為：的對(duì)應(yīng)關(guān)系可統(tǒng)一

17、為： k=I*(I+1)/2+J 0 kd時(shí)，元時(shí)，元素素aij=0。l對(duì)帶狀矩陣可按對(duì)帶狀矩陣可按行優(yōu)先順序行優(yōu)先順序或或?qū)蔷€的順序?qū)蔷€的順序，將其壓縮存儲(chǔ)到一，將其壓縮存儲(chǔ)到一個(gè)向量中，并且也能找到每個(gè)非零元素和向量下標(biāo)的對(duì)應(yīng)關(guān)系。個(gè)向量中，并且也能找到每個(gè)非零元素和向量下標(biāo)的對(duì)應(yīng)關(guān)系。18/55l上述的各種特殊矩陣，其非零元素的分布都是有規(guī)律的，因上述的各種特殊矩陣，其非零元素的分布都是有規(guī)律的，因此總能找到一種方法將它們壓縮存儲(chǔ)到一個(gè)一維數(shù)組中，并此總能找到一種方法將它們壓縮存儲(chǔ)到一個(gè)一維數(shù)組中，并且一般都能找到矩陣中的元素與該一維數(shù)組元素的對(duì)應(yīng)關(guān)且一般都能找到矩陣中的元素與該一維

18、數(shù)組元素的對(duì)應(yīng)關(guān)系，通過這個(gè)關(guān)系，能對(duì)矩陣的元素進(jìn)行隨機(jī)存取。系，通過這個(gè)關(guān)系，能對(duì)矩陣的元素進(jìn)行隨機(jī)存取。5.3.2 稀疏矩陣稀疏矩陣什么是稀疏矩陣？什么是稀疏矩陣？l精確地，設(shè)在精確地，設(shè)在mn的矩陣的矩陣A中，有中，有t個(gè)非零元素。個(gè)非零元素。令令 =t/(m*n)，稱稱為為矩陣的稀疏因子矩陣的稀疏因子。通常認(rèn)為。通常認(rèn)為0.05時(shí)時(shí)可稱之為可稱之為稀疏矩陣稀疏矩陣。l簡(jiǎn)單說，設(shè)矩陣簡(jiǎn)單說，設(shè)矩陣A中有中有s個(gè)非零元素，若個(gè)非零元素，若s遠(yuǎn)遠(yuǎn)小于矩陣元素遠(yuǎn)遠(yuǎn)小于矩陣元素的總數(shù)（即的總數(shù)（即smn），），則稱則稱A為為稀疏矩陣稀疏矩陣。19/55l在存儲(chǔ)稀疏矩陣時(shí)，為了節(jié)省存儲(chǔ)單元，很自然

19、地想在存儲(chǔ)稀疏矩陣時(shí)，為了節(jié)省存儲(chǔ)單元，很自然地想到使用壓縮存儲(chǔ)方法。但由于其非零元素的分布一般到使用壓縮存儲(chǔ)方法。但由于其非零元素的分布一般是沒有規(guī)律的，因此在存儲(chǔ)非零元素的同時(shí)，還必須是沒有規(guī)律的，因此在存儲(chǔ)非零元素的同時(shí)，還必須同時(shí)記下它所在的行和列的位置（同時(shí)記下它所在的行和列的位置（i ，j)。1、三元組順序表、三元組順序表 l反之，一個(gè)三元組反之，一個(gè)三元組(i ，j ，aij)唯一確定了矩陣唯一確定了矩陣A的一個(gè)的一個(gè)非零元。非零元。l因此，因此，稀疏矩陣可由表示非零元的三元組及其行列數(shù)稀疏矩陣可由表示非零元的三元組及其行列數(shù)唯一確定唯一確定。20/55l例如，下列三元組表例如，

20、下列三元組表 (1,2,12), (1,3,9), (3,1,- 3), (3,6,14), (4,3,24), (5,2,18), (6,1,15), (6,4,-7) 加上加上(6,7)這一對(duì)行、列值這一對(duì)行、列值便可作為下列矩陣便可作為下列矩陣M的另一種描述。而由上述三元組表的不同的另一種描述。而由上述三元組表的不同表示方法可引出稀疏矩陣的不同壓縮存儲(chǔ)方法。表示方法可引出稀疏矩陣的不同壓縮存儲(chǔ)方法。00000000014000000007000000024009018000121500300T00070015000001800000240001400003000000000009120M

21、 圖圖5.4 稀疏矩陣稀疏矩陣M和和T1、三元組順序表、三元組順序表 21/55#define M 20typedef struct node int i, j; int v;JD;JD maM;l三元組表所需存儲(chǔ)單元個(gè)數(shù)為三元組表所需存儲(chǔ)單元個(gè)數(shù)為3(t+1)，其中，其中t為非零元個(gè)數(shù)為非零元個(gè)數(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 8lma0.i,ma0.j,ma0.v分別存放分別存放 矩陣行數(shù)、列數(shù)和非零元個(gè)數(shù)矩陣行數(shù)、列數(shù)和非零元個(gè)數(shù)行列下標(biāo)行列下標(biāo)非零元值

22、非零元值7600070015000001800000240001400003000000000009120M2、稀疏矩陣的壓縮存儲(chǔ)方法、稀疏矩陣的壓縮存儲(chǔ)方法22/553、求轉(zhuǎn)置矩陣、求轉(zhuǎn)置矩陣l問題描述：?jiǎn)栴}描述：已知一個(gè)稀疏矩陣已知一個(gè)稀疏矩陣M的三元組表的三元組表ma，求該矩陣的轉(zhuǎn)置矩陣求該矩陣的轉(zhuǎn)置矩陣T的三元組表的三元組表mb。l解決思路：解決思路： （1）將矩陣行、列數(shù)互換將矩陣行、列數(shù)互換 （2）將每個(gè)三元組中的）將每個(gè)三元組中的i和和j相互調(diào)換相互調(diào)換 （3）重排三元組次序，使）重排三元組次序，使mb中元素以中元素以T的行的行(M的的 列列)為主序?yàn)橹餍?3/557600070

23、015000001800000240001400003000000000009120M6700000000014000000007000000024009018000121500300T6 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 v0 1 2 3 4 5 6 7 8mai j v7 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 8mb?24/55l一個(gè)一個(gè)mn的矩陣的矩陣A，它的轉(zhuǎn)置，它的轉(zhuǎn)置B是一個(gè)是一個(gè)

24、nm的矩陣，且的矩陣，且aij=bji，0im-1，0jn-1，即，即A的行是的行是B的列，的列，A的列是的列是B的行。的行。方法一方法一l將將A轉(zhuǎn)置為轉(zhuǎn)置為B，就是將就是將A的三元組表的三元組表a.data置換為表置換為表B的三的三元組表元組表b.data，如果只是簡(jiǎn)單地交換如果只是簡(jiǎn)單地交換a.data中中i和和j的內(nèi)的內(nèi)容，那么得到的容，那么得到的b.data將是一個(gè)按將是一個(gè)按列優(yōu)先順序列優(yōu)先順序存儲(chǔ)的稀疏存儲(chǔ)的稀疏矩陣矩陣B。l要得到按行優(yōu)先順序存儲(chǔ)的要得到按行優(yōu)先順序存儲(chǔ)的b.data，就必須重新排列三元就必須重新排列三元組的順序。組的順序。 25/55l由于由于A的列是的列是B的

25、行，因此，按的行，因此，按a.data的列序轉(zhuǎn)置，所得的列序轉(zhuǎn)置，所得到的轉(zhuǎn)置矩陣到的轉(zhuǎn)置矩陣B的三元組表的三元組表b.data必定是按必定是按行優(yōu)先順序行優(yōu)先順序存存放的。放的。l按這種方法設(shè)計(jì)的算法，按這種方法設(shè)計(jì)的算法，其基本思想是其基本思想是：對(duì)：對(duì)A中的每一列中的每一列 col(0coln-1)，通過從頭至尾掃描三元表通過從頭至尾掃描三元表a.data，找出找出所有列號(hào)等于所有列號(hào)等于col的那些三元組，將它們的行號(hào)和列號(hào)互的那些三元組，將它們的行號(hào)和列號(hào)互換后依次放入換后依次放入b.data中，即可得到中，即可得到B的按的按行優(yōu)先順序行優(yōu)先順序的壓的壓縮存儲(chǔ)表示?？s存儲(chǔ)表示。方法一

26、方法一26/55l#define MAXSIZE 12500 ltypedef struct int i, j; ElemType e; Triple;ltypedef struct Triple dataMAXSIZE+1; int mu, nu, tu; TSMatrix; 27/55Status TransposeSMatrix ( TSMatrix M, TSMatrix &T) T.mu=M.nu; T.nu=M.mu; T.tu=M.tu; l if (T.tu) q=1; for ( col=1;col=M.nu;+col) for (p=1; p=M.tu; +p) i

27、f (M.datap.j=col) T.dataq.i=M.datap.j; T.dataq.j=M.datap.i; T.dataq.e=M.datap.e; +q; l return OK; 28/556 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 v0 1 2 3 4 5 6 7 8ma7 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 v0 1 2 3 4 5 6 7 8mbqppppppppqqqqppppppppcol=1c

28、ol=2方法一方法一29/55l這個(gè)算法，主要的工作是在這個(gè)算法，主要的工作是在p和和col的兩個(gè)循環(huán)中完成的，的兩個(gè)循環(huán)中完成的，故算法的時(shí)間復(fù)雜度為故算法的時(shí)間復(fù)雜度為O(nu*tu)，即矩陣的列數(shù)和非零元，即矩陣的列數(shù)和非零元的個(gè)數(shù)的乘積成正比。的個(gè)數(shù)的乘積成正比。l而一般傳統(tǒng)矩陣的轉(zhuǎn)置算法為：而一般傳統(tǒng)矩陣的轉(zhuǎn)置算法為： for(col=1;col=nu;+col) for(row=1;row=mu;+row)tcolrow=mrowcol; 其時(shí)間復(fù)雜度為其時(shí)間復(fù)雜度為O(nu*mu)。方法一方法一30/55l當(dāng)非零元素的個(gè)數(shù)當(dāng)非零元素的個(gè)數(shù)tu和和mu*nu同數(shù)量級(jí)時(shí)，方法一的時(shí)間

29、同數(shù)量級(jí)時(shí)，方法一的時(shí)間復(fù)雜度為復(fù)雜度為O(mu*nu2)。l三元組順序表雖然節(jié)省了存儲(chǔ)空間，但時(shí)間復(fù)雜度比一般三元組順序表雖然節(jié)省了存儲(chǔ)空間，但時(shí)間復(fù)雜度比一般矩陣轉(zhuǎn)置的算法還要復(fù)雜，同時(shí)還有可能增加算法的難矩陣轉(zhuǎn)置的算法還要復(fù)雜，同時(shí)還有可能增加算法的難度。度。因此，此算法僅適用于因此，此算法僅適用于tumu*nu的情況。的情況。方法一方法一31/55l按照按照a.data中三元組的次序進(jìn)行轉(zhuǎn)置，并將轉(zhuǎn)置后的三元組置中三元組的次序進(jìn)行轉(zhuǎn)置，并將轉(zhuǎn)置后的三元組置入入b.data中的恰當(dāng)位置。中的恰當(dāng)位置。方法二：快速轉(zhuǎn)置算法方法二：快速轉(zhuǎn)置算法l如果能預(yù)先確定矩陣如果能預(yù)先確定矩陣M中每一列

30、（即中每一列（即T中每一行）的第一個(gè)非中每一行）的第一個(gè)非零元素在零元素在b.data中應(yīng)有的位置，那么在對(duì)中應(yīng)有的位置，那么在對(duì)a.data中的三元組依中的三元組依次作轉(zhuǎn)置時(shí)，便可直接放到次作轉(zhuǎn)置時(shí)，便可直接放到b.data中恰當(dāng)?shù)奈恢蒙先ァＶ星‘?dāng)?shù)奈恢蒙先?。l為了確定這些位置，在轉(zhuǎn)置前，應(yīng)先求得為了確定這些位置，在轉(zhuǎn)置前，應(yīng)先求得M的每一列中非零元的的每一列中非零元的個(gè)數(shù)，進(jìn)而求得每一列的第一個(gè)非零元在個(gè)數(shù)，進(jìn)而求得每一列的第一個(gè)非零元在b.data中應(yīng)在的位置。中應(yīng)在的位置。l快速轉(zhuǎn)置算法的思想：快速轉(zhuǎn)置算法的思想：對(duì)對(duì)A掃描一次，按掃描一次，按A第二列提供的列號(hào)第二列提供的列號(hào)依次確定

31、三元組裝入依次確定三元組裝入B的位置。具體實(shí)施如下：一遍掃描先確的位置。具體實(shí)施如下：一遍掃描先確定三元組的位置關(guān)系，二次掃描由位置關(guān)系裝入三元組?？啥ㄈM的位置關(guān)系，二次掃描由位置關(guān)系裝入三元組?？梢?，見，位置關(guān)系是此種算法的關(guān)鍵位置關(guān)系是此種算法的關(guān)鍵。 32/55實(shí)現(xiàn)：需要附設(shè)實(shí)現(xiàn)：需要附設(shè)num和和cpot兩個(gè)數(shù)組。兩個(gè)數(shù)組。lnumcol：表示矩陣：表示矩陣M中第中第col列中非零元的個(gè)數(shù)；列中非零元的個(gè)數(shù)；lcpotcol：指示矩陣：指示矩陣M中第中第col列第一個(gè)非零元在列第一個(gè)非零元在mb中的位置中的位置顯然有：顯然有：lcpot1=1;lcpotcol=cpotcol-1+

32、numcol-1; (2 col a.nu)1357889colnumcolcpotcol122232415061707600070015000001800000240001400003000000000009120M方法二：快速轉(zhuǎn)置算法方法二：快速轉(zhuǎn)置算法33/55Status FastTransposeSMatrix ( TSMatrix M, TSMatrix &T) lT.mu=M.nu; T.nu=M.mu; T.tu=M.tu;lif (T.tu) for ( col=1; col=M.nu; +col) numcol=0; for (t=1;t=M.tu;+t) +num

33、M.datat.j; / 求求M中每一列含非零元個(gè)數(shù)中每一列含非零元個(gè)數(shù) cpot1=1; 方法二：快速轉(zhuǎn)置算法方法二：快速轉(zhuǎn)置算法34/55 for (col=2;col=M.nu;+col) cpotcol=cpotcol-1+numcol-1; /求第求第col列中第一個(gè)非零元在列中第一個(gè)非零元在b.data中的序號(hào)。中的序號(hào)。 for(p=1; p=1) 非空，則非空，則a1是是LS的的表表頭頭，其余元素組成的表，其余元素組成的表(a2,a3,an)稱為稱為L(zhǎng)S的的表尾表尾。l顯然廣義表是遞歸定義的，這是因?yàn)樵诙x廣義表時(shí)又用到顯然廣義表是遞歸定義的，這是因?yàn)樵诙x廣義表時(shí)又用到了廣義

34、表的概念。廣義表的例子如下：了廣義表的概念。廣義表的例子如下： （1）A=()A是一個(gè)空表，其長(zhǎng)度為零。是一個(gè)空表，其長(zhǎng)度為零。 （2）B=(e)表表B只有一個(gè)原子只有一個(gè)原子e，B的長(zhǎng)度為的長(zhǎng)度為1。 （3）C=(a,(b,c,d)表表C的長(zhǎng)度為的長(zhǎng)度為2，兩個(gè)元素分別為原，兩個(gè)元素分別為原子子a和子表和子表(b,c,d)。 （4）D=(A，B，C)表表D的長(zhǎng)度為的長(zhǎng)度為3，三個(gè)元素都是廣義，三個(gè)元素都是廣義表。顯然，將子表的值代入后，則有表。顯然，將子表的值代入后，則有D=(),(e),(a,(b,c,d)。 5.4 廣義表的定義廣義表的定義44/55 （5）E=（a,E）這是一個(gè)遞歸的表

35、，它的長(zhǎng)度為這是一個(gè)遞歸的表，它的長(zhǎng)度為2，E相相當(dāng)于一個(gè)無限的廣義表當(dāng)于一個(gè)無限的廣義表E=(a,(a,(a,(a,). l例如：例如： D=(E, F) 其中其中: E=(a, (b, c) F=(d, (e)DEFa( ) d( )bcel從上述定義和例子可推出廣義表的三個(gè)重要結(jié)論：從上述定義和例子可推出廣義表的三個(gè)重要結(jié)論：（1）廣義表的元素可以是子表，而子表的元素還可以是子表。）廣義表的元素可以是子表，而子表的元素還可以是子表。由此，廣義表是一個(gè)多層次的結(jié)構(gòu)，可以用圖形象地表示。由此，廣義表是一個(gè)多層次的結(jié)構(gòu)，可以用圖形象地表示。5.4 廣義表的定義廣義表的定義45/55（2）廣義表

36、可為其它表所共享。）廣義表可為其它表所共享。例如在上述例（例如在上述例（4）中，廣義）中，廣義表表A，B，C為為D的子表，則在的子表，則在D中可以不必列出子表的值，中可以不必列出子表的值，而是通過子表的名稱來引用。而是通過子表的名稱來引用。（3）廣義表的遞歸性。）廣義表的遞歸性。l綜上所述，綜上所述，廣義表不僅是線性表的推廣，也是樹的推廣廣義表不僅是線性表的推廣，也是樹的推廣。l廣義表中所含括弧的重?cái)?shù)稱為廣義表中所含括弧的重?cái)?shù)稱為表的深度表的深度，表中元素的層數(shù)，表中元素的層數(shù)就是包括該元素的括弧重?cái)?shù)。例如：就是包括該元素的括弧重?cái)?shù)。例如： F（a，b，（，（c，（，（d） 其中，單元素其中，

37、單元素a、b在第一層，在第一層，d在第三層，廣義表的深度為在第三層，廣義表的深度為3。5.4 廣義表的定義廣義表的定義46/55l由于廣義表由于廣義表(a1,a2,a3,an)中的數(shù)據(jù)元素可以具有不同的結(jié)中的數(shù)據(jù)元素可以具有不同的結(jié)構(gòu)（或是原子，或是廣義表），因此，構(gòu)（或是原子，或是廣義表），因此，難以用順序存儲(chǔ)結(jié)難以用順序存儲(chǔ)結(jié)構(gòu)表示，通常采用鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)構(gòu)表示，通常采用鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)，每個(gè)數(shù)據(jù)元素可用一個(gè)，每個(gè)數(shù)據(jù)元素可用一個(gè)結(jié)點(diǎn)表示。結(jié)點(diǎn)表示。 tag=1 hp tp tag=0 atom表結(jié)點(diǎn)表結(jié)點(diǎn)原子結(jié)點(diǎn)原子結(jié)點(diǎn)l由于廣義表中有兩種數(shù)據(jù)元素：原子或廣義表，因此，需由于廣義表中有兩種數(shù)據(jù)

38、元素：原子或廣義表，因此，需要兩種結(jié)構(gòu)的結(jié)點(diǎn)：要兩種結(jié)構(gòu)的結(jié)點(diǎn)：一種是表結(jié)點(diǎn)，一種是原子結(jié)點(diǎn)一種是表結(jié)點(diǎn)，一種是原子結(jié)點(diǎn)。 l表結(jié)點(diǎn)由三個(gè)域組成：表結(jié)點(diǎn)由三個(gè)域組成：標(biāo)志域標(biāo)志域、指示表頭的指針域指示表頭的指針域和和指示指示表尾的指針域表尾的指針域；l而原子結(jié)點(diǎn)只需兩個(gè)域：而原子結(jié)點(diǎn)只需兩個(gè)域：標(biāo)志域標(biāo)志域和和值域值域。5.5 廣義表的存儲(chǔ)結(jié)構(gòu)廣義表的存儲(chǔ)結(jié)構(gòu)47/55L = ( a, ( x, y ), ( ( x ) ) )a ( x, y ) ( ) 1 L0 a 1 1 1 1 1 0 x ( )x48/55BCDE1 0 e1 1 0 a1 1 1 1 0 a1 1 0 d0 c0

39、b1 1 廣義表的存儲(chǔ)結(jié)構(gòu)示例廣義表的存儲(chǔ)結(jié)構(gòu)示例l（1）A=（）（）l（2）B=（e）l（3）C=（a, （b, c, d）l（4）D=（A，B，C）l（5）E=（a, E）49/55*5.6 m元多項(xiàng)式的表示元多項(xiàng)式的表示1、一元多項(xiàng)式、一元多項(xiàng)式l一個(gè)多項(xiàng)式可以用一個(gè)長(zhǎng)度為一個(gè)多項(xiàng)式可以用一個(gè)長(zhǎng)度為m且每個(gè)數(shù)據(jù)元素有兩個(gè)數(shù)且每個(gè)數(shù)據(jù)元素有兩個(gè)數(shù)據(jù)項(xiàng)（系數(shù)項(xiàng)和指數(shù)項(xiàng)）的線性表來表示。據(jù)項(xiàng)（系數(shù)項(xiàng)和指數(shù)項(xiàng)）的線性表來表示。2、 m元多項(xiàng)式元多項(xiàng)式l一個(gè)一個(gè)m元多項(xiàng)式的每一項(xiàng)，最多有個(gè)元多項(xiàng)式的每一項(xiàng)，最多有個(gè)m變?cè)?，如果用線性變?cè)?，如果用線性表來表示，則每個(gè)數(shù)據(jù)元素需要表來表示，則每個(gè)數(shù)據(jù)元

40、素需要m+1個(gè)數(shù)據(jù)項(xiàng)，以存儲(chǔ)一個(gè)數(shù)據(jù)項(xiàng)，以存儲(chǔ)一個(gè)系數(shù)值和個(gè)系數(shù)值和m個(gè)指數(shù)值。將產(chǎn)生兩個(gè)問題：個(gè)指數(shù)值。將產(chǎn)生兩個(gè)問題：l造成浪費(fèi)造成浪費(fèi) l線性表中結(jié)點(diǎn)大小不一樣線性表中結(jié)點(diǎn)大小不一樣50/55l因此，由于因此，由于m 元多項(xiàng)式中每一項(xiàng)的變化數(shù)目不均勻性和變?cè)囗?xiàng)式中每一項(xiàng)的變化數(shù)目不均勻性和變?cè)畔⒌闹匾?，故不適于用線性表表示。例如：元信息的重要性，故不適于用線性表表示。例如：152632),(43442252362310yzzyxzyxzyxzyxzyxzyxP15)2)6()3)2(),(4342253610zyyxxzyxyxxzyxP0215zBzAzl上式是變?cè)鲜绞亲冊(cè)猌的

41、多項(xiàng)式，即的多項(xiàng)式，即 其中：其中：A和和B本身又是一個(gè)（本身又是一個(gè)（x,y）的二元多項(xiàng)式，）的二元多項(xiàng)式，15是是Z的零的零次項(xiàng)的系數(shù)。次項(xiàng)的系數(shù)。l進(jìn)一步考察進(jìn)一步考察A(x,y)，又可把它看成是，又可把它看成是y的多項(xiàng)式。的多項(xiàng)式。lCy3+Dy2，而其中，而其中C和和D為為x的一元多項(xiàng)式。循環(huán)以往，每個(gè)多的一元多項(xiàng)式。循環(huán)以往，每個(gè)多項(xiàng)式都可看作是由一個(gè)變量加上若干個(gè)系數(shù)指數(shù)偶對(duì)組成。項(xiàng)式都可看作是由一個(gè)變量加上若干個(gè)系數(shù)指數(shù)偶對(duì)組成。*5.6 m元元多項(xiàng)式的表示多項(xiàng)式的表示51/55l任何一個(gè)任何一個(gè)m 元多項(xiàng)式都可如此做：元多項(xiàng)式都可如此做：先分解出一個(gè)主變?cè)?，隨后先分解出一個(gè)主

42、變?cè)?，隨后再分解出第二個(gè)變?cè)?，等等再分解出第二個(gè)變?cè)?，等等。由此，一個(gè)。由此，一個(gè)m元的多項(xiàng)式首先是元的多項(xiàng)式首先是它的主變?cè)亩囗?xiàng)式，而其系數(shù)又是第二變?cè)亩囗?xiàng)式，由它的主變?cè)亩囗?xiàng)式，而其系數(shù)又是第二變?cè)亩囗?xiàng)式，由此，可用廣義表來表示此，可用廣義表來表示m元多項(xiàng)式。例如上述三元多項(xiàng)式可用元多項(xiàng)式。例如上述三元多項(xiàng)式可用下式的廣義表表示，廣義表的深度即為變?cè)獋€(gè)數(shù)。下式的廣義表表示，廣義表的深度即為變?cè)獋€(gè)數(shù)。15)2)6()3)2(),(4342253610zyyxxzyxyxxzyxPlP=Z（A，2），（），（B，1），（），（15，0） 在廣義表的括號(hào)之前加一個(gè)變?cè)?，以示各層的變?cè)?。在廣義表的括號(hào)之前加一個(gè)變?cè)允靖鲗拥淖冊(cè)?。lA=y(C,3),(D,2) B=y(E,4),(F,1)lC=x(1,10),(2,6) D=x(3,5)lE=x(1,4),(6,3) F=x(2,0)*5.6 m元元多項(xiàng)式的表示多項(xiàng)式的表示52/55l可以類似廣義表的第二種存儲(chǔ)結(jié)構(gòu)來定義表示可以類似廣義表的第二種存儲(chǔ)結(jié)構(gòu)來定義表示m元多項(xiàng)式的元多項(xiàng)式的廣義表的存儲(chǔ)結(jié)構(gòu)。鏈