數(shù)據(jù)結(jié)構(gòu)五章節(jié)數(shù)組與廣義表ppt課件

1、 數(shù)據(jù)結(jié)構(gòu)課程本章內(nèi)容5.1 數(shù)組的定義5.2 數(shù)組的順序表示和實(shí)現(xiàn)5.3 矩陣的緊縮存儲(chǔ)5.4 廣義表的定義5.5 廣義表的存儲(chǔ)構(gòu)造中國(guó)科大數(shù)據(jù)結(jié)構(gòu)數(shù)組和廣義表簡(jiǎn)單描畫中國(guó)科大數(shù)據(jù)結(jié)構(gòu) 數(shù)組是我們最熟習(xí)的數(shù)據(jù)類型，在早期的高級(jí)言語數(shù)組是我們最熟習(xí)的數(shù)據(jù)類型，在早期的高級(jí)言語中，數(shù)組是獨(dú)一可供運(yùn)用的數(shù)據(jù)類型。由于數(shù)組中各中，數(shù)組是獨(dú)一可供運(yùn)用的數(shù)據(jù)類型。由于數(shù)組中各元素具有一致的類型，并且數(shù)組元素的下標(biāo)普通具有元素具有一致的類型，并且數(shù)組元素的下標(biāo)普通具有固定的上界和下界，因此，數(shù)組的處置比其它復(fù)雜的固定的上界和下界，因此，數(shù)組的處置比其它復(fù)雜的構(gòu)造更為簡(jiǎn)單。多維數(shù)組是向量的推行。例如，二維構(gòu)

2、造更為簡(jiǎn)單。多維數(shù)組是向量的推行。例如，二維數(shù)組：數(shù)組： 5.1 數(shù)組的定義Amn=a11 a12 a1na21 a22 a2n am1 am2 amn中國(guó)科大數(shù)據(jù)結(jié)構(gòu)5.1 數(shù)組的定義p二維數(shù)組二維數(shù)組p二維數(shù)組可以看成是由假設(shè)干個(gè)行向量組成的向量，也可以看成是假設(shè)干二維數(shù)組可以看成是由假設(shè)干個(gè)行向量組成的向量，也可以看成是假設(shè)干個(gè)列向量組成的向量。個(gè)列向量組成的向量。p在在C C言語中，一個(gè)二維數(shù)組類型可以定義為其分量類型為一維數(shù)組類型的一言語中，一個(gè)二維數(shù)組類型可以定義為其分量類型為一維數(shù)組類型的一維數(shù)組類型，也就是說，維數(shù)組類型，也就是說，typedef elemtype array2

3、mn; typedef elemtype array2mn; 等價(jià)于：等價(jià)于：p typedef elemtype array1n;typedef elemtype array1n;p typedef array1 array2m; typedef array1 array2m;p多維數(shù)組：用一維順序構(gòu)造線性表實(shí)現(xiàn)多維數(shù)組多維數(shù)組：用一維順序構(gòu)造線性表實(shí)現(xiàn)多維數(shù)組pstruct Arraystruct Arrayp ElemType ElemType * *buffer;buffer;/ / 數(shù)據(jù)區(qū)數(shù)據(jù)區(qū)p int dims;int dims;/ / 維數(shù)維數(shù)p int int * *L;L;

4、/ / 各維長(zhǎng)度各維長(zhǎng)度p;中國(guó)科大數(shù)據(jù)結(jié)構(gòu)5.2 數(shù)組的順序表示和實(shí)現(xiàn)p設(shè)一3維數(shù)組A423，存貯在一個(gè)順序線性表S中，構(gòu)造如下所示：A312A311A310A302A301A300A212A211A210A202A201A200A112A111A110A102A101A100A012A011A010A002A001A000A312A311A310A302A301A300A212A211A210A202A201A200A112A111A110A102A101A100A012A011A010A002A001A00001234567.2223A000A001A002A010A011A012A10

5、0A101.A311A312中國(guó)科大數(shù)據(jù)結(jié)構(gòu)5.2 數(shù)組的順序表示和實(shí)現(xiàn)p兩種順序存儲(chǔ)方式：兩種順序存儲(chǔ)方式：p行優(yōu)先順序行優(yōu)先順序?qū)?shù)組元素按行陳列，第將數(shù)組元素按行陳列，第i+1i+1個(gè)行向量緊接在第個(gè)行向量緊接在第i i個(gè)個(gè)行向量后面。以二維數(shù)組為例，按行優(yōu)先順序存儲(chǔ)的線性序列為：行向量后面。以二維數(shù)組為例，按行優(yōu)先順序存儲(chǔ)的線性序列為：a11,a12,a1n,a21,a22,a2n,am1,am2,amna11,a12,a1n,a21,a22,a2n,am1,am2,amn。在。在PASCALPASCAL、C C言語中，數(shù)組就是按行優(yōu)先順序存儲(chǔ)的。行優(yōu)先順序推行到多維言語中，數(shù)組就是按

6、行優(yōu)先順序存儲(chǔ)的。行優(yōu)先順序推行到多維數(shù)組，可規(guī)定為先排最右的下標(biāo)。數(shù)組，可規(guī)定為先排最右的下標(biāo)。 p列優(yōu)先順序列優(yōu)先順序?qū)?shù)組元素按列向量陳列，第將數(shù)組元素按列向量陳列，第j+1j+1個(gè)列向量緊接在個(gè)列向量緊接在第第j j個(gè)列向量之后，個(gè)列向量之后，A A的的m m* *n n個(gè)元素按列優(yōu)先順序存儲(chǔ)的線性序列為：個(gè)元素按列優(yōu)先順序存儲(chǔ)的線性序列為：a11,a21,am1,a12,a22,am2,an1,an2,anm a11,a21,am1,a12,a22,am2,an1,an2,anm 。在。在FORTRANFORTRAN言語中，數(shù)組就是按列優(yōu)先順序存儲(chǔ)的。列優(yōu)先順序推行言語中，數(shù)組就是按

7、列優(yōu)先順序存儲(chǔ)的。列優(yōu)先順序推行到多維數(shù)組，可規(guī)定為先排最左的下標(biāo)。到多維數(shù)組，可規(guī)定為先排最左的下標(biāo)。 中國(guó)科大數(shù)據(jù)結(jié)構(gòu)5.2 數(shù)組的順序表示和實(shí)現(xiàn)p二維數(shù)組元素的存取二維數(shù)組元素的存取p二維數(shù)組二維數(shù)組AmnAmn按按“行優(yōu)先順序存儲(chǔ)在內(nèi)存中，假設(shè)每個(gè)元素占用行優(yōu)先順序存儲(chǔ)在內(nèi)存中，假設(shè)每個(gè)元素占用L L個(gè)存儲(chǔ)單元。個(gè)存儲(chǔ)單元。p元素元素aijaij的存儲(chǔ)地址應(yīng)是數(shù)組的基地址加上排在的存儲(chǔ)地址應(yīng)是數(shù)組的基地址加上排在aijaij前面的元素所占前面的元素所占用的單元數(shù)。由于用的單元數(shù)。由于aijaij位于第位于第i i行、第行、第j j列，前面列，前面 i-1 i-1 行一共有行一共有(i-

8、1) (i-1) n n 個(gè)元素，第個(gè)元素，第i i行上行上aijaij前面又有前面又有j-1j-1個(gè)元素，故它前面一共有個(gè)元素，故它前面一共有(i-1) (i-1) n+j-1n+j-1個(gè)元素，因此，個(gè)元素，因此，aijaij的地址計(jì)算函數(shù)為：的地址計(jì)算函數(shù)為：p LOC(aij) = LOC(a11)+(i-1) LOC(aij) = LOC(a11)+(i-1)* *n+j-1n+j-1* *L L中國(guó)科大數(shù)據(jù)結(jié)構(gòu)5.2 數(shù)組的順序表示和實(shí)現(xiàn)p例：二維數(shù)組例：二維數(shù)組Ac1.d1,c2.d2Ac1.d1,c2.d2的存取的存取p分析：分析：aijaij前一共有前一共有i-c1i-c1行，

9、二維數(shù)組一共有行，二維數(shù)組一共有d2-c2+1d2-c2+1列，故這列，故這i-c1i-c1行共有行共有(i-c1)(i-c1)* *(d2-c2+1)(d2-c2+1)個(gè)元素，第個(gè)元素，第i i行上行上aijaij前一共有前一共有j-c2j-c2個(gè)元素，個(gè)元素，因此，因此，aijaij的地址計(jì)算函數(shù)為：的地址計(jì)算函數(shù)為：p LOC(aij) = LOC(ac1c2)+(i-c1)LOC(aij) = LOC(ac1c2)+(i-c1)* *(d2-c2+1)+j-c2)(d2-c2+1)+j-c2)* *L Lp在在C C言語中，數(shù)組各維下標(biāo)的下界是言語中，數(shù)組各維下標(biāo)的下界是0 0，因此二

10、維數(shù)組，因此二維數(shù)組AmAmn n的地址的地址計(jì)算公式為：計(jì)算公式為：p LOC(aij) = LOC(a00)+(iLOC(aij) = LOC(a00)+(i* *n+j)n+j)* *L L中國(guó)科大數(shù)據(jù)結(jié)構(gòu)5.3 矩陣的緊縮存儲(chǔ)p在高級(jí)言語編制程序時(shí)，將一個(gè)矩陣描畫為一個(gè)二維數(shù)組。在高級(jí)言語編制程序時(shí)，將一個(gè)矩陣描畫為一個(gè)二維數(shù)組。p矩陣在這種存儲(chǔ)表示之下，可以對(duì)其元素進(jìn)展隨機(jī)存取，各種矩陣矩陣在這種存儲(chǔ)表示之下，可以對(duì)其元素進(jìn)展隨機(jī)存取，各種矩陣運(yùn)算也非常簡(jiǎn)單，并且存儲(chǔ)的密度為運(yùn)算也非常簡(jiǎn)單，并且存儲(chǔ)的密度為1 1。但是在矩陣中非零元素呈。但是在矩陣中非零元素呈某種規(guī)律分布或者矩陣中出

11、現(xiàn)大量的零元素的情況下，看起來存儲(chǔ)某種規(guī)律分布或者矩陣中出現(xiàn)大量的零元素的情況下，看起來存儲(chǔ)密度仍為密度仍為1 1，但實(shí)踐上占用了許多單元去存儲(chǔ)反復(fù)的非零元素或零，但實(shí)踐上占用了許多單元去存儲(chǔ)反復(fù)的非零元素或零元素，這對(duì)高階矩陣會(huì)呵斥極大的浪費(fèi)元素，這對(duì)高階矩陣會(huì)呵斥極大的浪費(fèi). .p為了節(jié)省存儲(chǔ)空間，為了節(jié)省存儲(chǔ)空間， 對(duì)這類矩陣進(jìn)展緊縮存儲(chǔ)：即為多個(gè)一樣的對(duì)這類矩陣進(jìn)展緊縮存儲(chǔ)：即為多個(gè)一樣的非零元素只分配一個(gè)存儲(chǔ)空間；對(duì)零元素不分配空間。非零元素只分配一個(gè)存儲(chǔ)空間；對(duì)零元素不分配空間。中國(guó)科大數(shù)據(jù)結(jié)構(gòu)5.3 矩陣的緊縮存儲(chǔ)5.3.1 特殊矩陣特殊矩陣所謂特殊矩陣是指非零元素或零元素的分布

12、有一定規(guī)律的矩陣，所謂特殊矩陣是指非零元素或零元素的分布有一定規(guī)律的矩陣，下面我們討論幾種特殊矩陣的緊縮存儲(chǔ)。下面我們討論幾種特殊矩陣的緊縮存儲(chǔ)。 1、對(duì)稱矩陣、對(duì)稱矩陣 2、對(duì)角矩陣、對(duì)角矩陣中國(guó)科大數(shù)據(jù)結(jié)構(gòu)5.3 矩陣的緊縮存儲(chǔ)p對(duì)稱矩陣對(duì)稱矩陣p在一個(gè)在一個(gè)n n階方陣階方陣A A中，假設(shè)元素滿足下述性質(zhì)：中，假設(shè)元素滿足下述性質(zhì)：aij=aji aij=aji 0i,jn-10i,jn-1p 那么稱那么稱A A為對(duì)稱矩陣。如以下圖是一個(gè)為對(duì)稱矩陣。如以下圖是一個(gè)5 5階對(duì)稱矩陣。階對(duì)稱矩陣。p對(duì)稱矩陣中的元素關(guān)于主對(duì)角線對(duì)稱，故只需存儲(chǔ)矩對(duì)稱矩陣中的元素關(guān)于主對(duì)角線對(duì)稱，故只需存儲(chǔ)矩陣

13、中上三角或下三角中的元素，讓每?jī)蓚€(gè)對(duì)稱的元素共享一個(gè)存儲(chǔ)陣中上三角或下三角中的元素，讓每?jī)蓚€(gè)對(duì)稱的元素共享一個(gè)存儲(chǔ)空間，這樣，能節(jié)約近一半的存儲(chǔ)空間。不失普通性，我們按空間，這樣，能節(jié)約近一半的存儲(chǔ)空間。不失普通性，我們按“行行優(yōu)先順序存儲(chǔ)主對(duì)角線包括對(duì)角線以下的元素，其存儲(chǔ)方式優(yōu)先順序存儲(chǔ)主對(duì)角線包括對(duì)角線以下的元素，其存儲(chǔ)方式如上圖示。如上圖示。1 5 1 3 7 a005 0 8 0 0 a10 a 111 8 9 2 6 a20 a21 a233 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中國(guó)科大數(shù)據(jù)結(jié)構(gòu)5.3 矩陣的緊縮存儲(chǔ)

14、p對(duì)稱矩陣的存儲(chǔ)表示對(duì)稱矩陣的存儲(chǔ)表示p在這個(gè)下三角矩陣中，第在這個(gè)下三角矩陣中，第i i行恰有行恰有i+1i+1個(gè)元素，元素總數(shù)為：個(gè)元素，元素總數(shù)為：p (i+1) = n(n+1)/2 (i+1) = n(n+1)/2p因此，我們可以按行優(yōu)先的次序?qū)⑦@些元素存放在一個(gè)向量因此，我們可以按行優(yōu)先的次序?qū)⑦@些元素存放在一個(gè)向量sa0.n(n+1)/2-1sa0.n(n+1)/2-1中。中。paijaij和和sak sak 之間對(duì)應(yīng)關(guān)系之間對(duì)應(yīng)關(guān)系p假設(shè)假設(shè)ijij，那么，那么ai jai j在下三角形中。在下三角形中。 ai j ai j之前的之前的i i行從第行從第0 0行到行到第第i-1

15、i-1行一共有行一共有 1+2+i=i(i+1)/2 1+2+i=i(i+1)/2 個(gè)元素，在第個(gè)元素，在第i i行上，行上， ai j ai j之前恰有之前恰有j j個(gè)元素即個(gè)元素即 ai0,ai1,ai2,aij-1 ai0,ai1,ai2,aij-1，因此有：，因此有：pk=ik=i* *(i+1)/2+j 0kn(n+1)/2(i+1)/2+j 0kn(n+1)/2p假設(shè)假設(shè)ijij，那么，那么aijaij是在上三角矩陣中。由于是在上三角矩陣中。由于aij=ajiaij=aji，所以只需交，所以只需交換上述對(duì)應(yīng)關(guān)系式中的換上述對(duì)應(yīng)關(guān)系式中的i i和和j j即可得到：即可得到：pk=jk

16、=j* *(j+1)/2+i 0 kn(n+1)/2(j+1)/2+i 0 k1i-j1時(shí)，元素時(shí)，元素aij=0aij=0。p由此可知，一個(gè)由此可知，一個(gè)k k對(duì)角矩陣對(duì)角矩陣(k(k為奇數(shù)為奇數(shù))A)A是滿足下述條件的矩陣：假是滿足下述條件的矩陣：假設(shè)設(shè)i-j(k-1)/2 i-j(k-1)/2 ，那么元素，那么元素 aij=0 aij=0。p對(duì)角矩陣可按行優(yōu)先順序或?qū)蔷€的順序，將其緊縮存儲(chǔ)到一個(gè)向?qū)蔷仃嚳砂葱袃?yōu)先順序或?qū)蔷€的順序，將其緊縮存儲(chǔ)到一個(gè)向量中，并且也能找到每個(gè)非零元素和向量下標(biāo)的對(duì)應(yīng)關(guān)系。量中，并且也能找到每個(gè)非零元素和向量下標(biāo)的對(duì)應(yīng)關(guān)系。中國(guó)科大數(shù)據(jù)結(jié)構(gòu)5.3 矩陣的緊縮存儲(chǔ)在三對(duì)角矩陣?yán)锔綕M足條件i=0，j=0、1，或i=n-1j=n-2、n-1或1in-1,j=i-1、i、i+1的元素aij外，其他元素都是零。對(duì)這種矩陣，我們也可按行優(yōu)序?yàn)橹餍騺泶鎯?chǔ)。除第0行和第n-1行是2個(gè)元素外，每行的非零元素都是3個(gè)，因此，需存儲(chǔ)的元素個(gè)數(shù)為3n-2。數(shù)組sa中的元素sak與三對(duì)角帶狀矩陣中的元素aij存在一一對(duì)應(yīng)關(guān)系，在aij之前有i行,共有3*i-1個(gè)非零元素，在第i行，有j-i+1個(gè)非零元素.a n-1 n-1a n-1 n-2