數(shù)據(jù)結(jié)構(gòu)演示文稿

數(shù)據(jù)結(jié)構(gòu)演示文稿第1頁，共53頁，2023年，2月20日，星期六數(shù)據(jù)結(jié)構(gòu)主講：王阿川第2頁，共53頁，2023年，2月20日，星期六§5.1數(shù)組的定義§5.2數(shù)組的順序表示和實現(xiàn)§5.3矩陣的壓縮存儲5.3.1特殊矩陣5.3.2稀疏矩陣

§

5.4廣義表的定義。

§

5.5廣義表的存儲結(jié)構(gòu)第3頁，共53頁，2023年，2月20日，星期六§5.1數(shù)組的定義

例如，二維數(shù)組：|a11a12…a1n|AmXn=|a21a22…a2n||…………||am1am2…amn|可以看成是由m個行向量組成的向量，也可以看成是n個列向量組成的向量。由于數(shù)組中各元素具有統(tǒng)一的類型，并且數(shù)組元素的下標(biāo)一般具有固定的上界和下界，因此，數(shù)組的處理比其它復(fù)雜的結(jié)構(gòu)更為簡單。多維數(shù)組是向量的推廣。1、類型相同的有限個元素的序列，叫數(shù)組。第4頁，共53頁，2023年，2月20日，星期六在C語言中，一個二維數(shù)組類型可以定義為其分量類型為一維數(shù)組類型的一維數(shù)組類型，也就是說，typedefelemtypearray2[m][n];等價于：typedefelemtypearray1[n];typedefarray1array2[m];同理，一個維數(shù)組類型可以定義為其數(shù)據(jù)元素為維數(shù)組類型的一維序組類型。數(shù)組一旦被定義，它的維數(shù)和維界就不再改變。因此，除了結(jié)構(gòu)的初始化和銷毀之外，數(shù)組只有存取元素和修改元素值的操作。第5頁，共53頁，2023年，2月20日，星期六§5.2數(shù)組的順序表式和實現(xiàn)1、數(shù)組是采用順序方式存貯設(shè)第0號元組的地址為a，元素的長度為L······l012···i···n-2n-1(長度為n)一維數(shù)組任一元素的地址LOC(i)＝a＋i﹡l行號：············01···j···n-1l列號：012···k···m-1二維數(shù)組任一元素的地址LOC(j,k)＝a＋(j﹡m＋k)l通常有兩種順序存儲方式：1、行優(yōu)先順序2、列優(yōu)先順序第6頁，共53頁，2023年，2月20日，星期六1、行優(yōu)先順序?qū)?shù)組元素按行排列，第i+1個行向量緊接在第i個行向量后面。以二維數(shù)組為例，按行優(yōu)先順序存儲的線性序列為：a11,a12,…,a1n,a21,a22,…a2n,……,am1,am2,…,amn在PASCAL、C語言中，數(shù)組就是按行優(yōu)先順序存儲的。⑵列優(yōu)先順序——將數(shù)組元素按列向量排列，第j+1個列向量緊接在第j個列向量之后，A的m*n個元素按列優(yōu)先順序存儲的線性序列為：a11,a21,…,am1,a12,a22,…am2,……,an1,an2,…,anm在FORTRAN語言中，數(shù)組就是按列優(yōu)先順序存儲的。第7頁，共53頁，2023年，2月20日，星期六5.3矩陣的壓縮存儲1.壓縮存儲：為多個值相同的元素只分配一個存儲空間；對0元素不分配空間。2.特殊矩陣假若值相同的元素或者0元素在矩陣中的分布有一定的規(guī)律，既為特殊矩陣。反之，稱為稀疏矩陣。第8頁，共53頁，2023年，2月20日，星期六1、對稱矩陣在一個n階方陣A中，若元素滿足下述性質(zhì)：aij=aji0≦i,j≦n-1則稱A為對稱矩陣。5.3矩陣的壓縮存儲5.3.1特殊矩陣若所有元素都保存，則需要n2個存儲空間。若采用壓縮存儲只需n(n+1)/2個元素的存儲空間。15137a0050800a10a1118926a20a21a2330251………………..70613an-10an-11an-12…an-1n-1圖5.1對稱矩陣第9頁，共53頁，2023年，2月20日，星期六an-10an-11an-12…an-1n-1

480963lastn=8n(n-1)/2…..n(n+1)/2a00a10a11a20a21a22a30…

0123456在這個下三角矩陣中，第i行恰有i+1個元素，元素總數(shù)為：1+2+3+…+(i+1)+…+n=n(n+1)/2因此，我們可以按圖中箭頭所指的次序?qū)⑦@些元素存放在一個向量sa[0..n(n+1)/2-1]中。為了便于訪問對稱矩陣A中的元素，我們必須在aij和sa[k]之間找一個對應(yīng)關(guān)系。若i≧j，則aij在下三角形中。aij之前的i行（從第0行到第i-1行）一共有1+2+…+i=i(i+1)/2個元素，在第i行上，aij之前恰有j個元素（即ai0,ai1,ai2,…,aij-1），因此有：k=i*(i+1)/2+j0≦k<n(n+1)/2第10頁，共53頁，2023年，2月20日，星期六若i<j，則aij是在上三角矩陣中。因為aij=aji，所以只要交換上述對應(yīng)關(guān)系式中的i和j即可得到：k=j*(j+1)/2+i0≦k<n(n+1)/2令i=max(i,j)，j=min(i,j)，則k和i,j的對應(yīng)關(guān)系可統(tǒng)一為：k=i*(i+1)/2+j0≦k<n(n+1)/2

因此，aij的地址可用下列式計算：LOC(aij)=LOC(sa[k])=LOC(sa[0])+k*d=LOC(sa[0]+[I*(I+1)/2+J]*d有了上述的下標(biāo)交換關(guān)系，對于任意給定一組下標(biāo)(i，j)，均可在sa[k]中找到矩陣元素aij，反之，對所有的k=0,1,2,…n(n-1)/2-1，都能確定sa[k]中的元素在矩陣中的位置(I,j)。由此，稱sa[n(n+1)/2]為階對稱矩陣A的壓縮存儲，第11頁，共53頁，2023年，2月20日，星期六例如a21和a12均存儲在sa[4]中，這是因為k=I*(I+1)/2+J=2*(2+1)/2+1=42、三角矩陣|a00a01…a0n-1||a00c…c||ca11…a1n-1||a10a11…c||…..||……………..||cc…an-1n-1||an-10an-11…an-1n-1|

(a)上三角矩陣(b)下三角矩陣圖5.2三角矩陣三角矩陣中的重復(fù)元素c可共享一個存儲空間第12頁，共53頁，2023年，2月20日，星期六其余的元素正好有n(n+1)/2個，因此，三角矩陣可壓縮存儲到向量sa[0..n(n+1)/2]中，其中c存放在向量的最后一個分量中.上三角矩陣中，主對角線之上的第p行(0≦p<n)恰有n-p個元素.按行優(yōu)先順序存放上三角矩陣中的元素aij時，aij之前的I行一共有(n-p)=i(2n-i+1)/2個元素，在第i行上，aij前恰好有j-i個元素：aij,aij+1,…aij-1。因此，sa[k]和aij的對應(yīng)關(guān)系是：k=i(2n-i+1)/2+j-i當(dāng)i≦jk=n(n+1)/2當(dāng)i>j第13頁，共53頁，2023年，2月20日，星期六下三角矩陣的存儲和對稱矩陣類似，sa[k]和aij對應(yīng)關(guān)系是：k=i(i+1)/2+ji≧jk=n(n+1)/2i>j3、對角矩陣對角矩陣中，所有的非零元素集中在以主對角線為了中心的帶狀區(qū)域中，即除了主對角線和主對角線相鄰兩側(cè)的若干條對角線上的元素之外，其余元素皆為零。下圖給出了一個三對角矩陣，

a00a01a10a11a12a21a22a23….…..….圖5.3對角矩陣an-2n-3an-2n-2an-2n-1an-1n-2an-1n-1第14頁，共53頁，2023年，2月20日，星期六非零元素僅出現(xiàn)在主對角(aii,0≦i≦n-1上，緊鄰主對角線上面的那條對角線上(aii+1,0≦i≦n-2)和緊鄰主對角線下面的那條對角線上(ai+1i,0≦i≦n-2)。顯然，當(dāng)∣i-j∣>1時，元素aij=0。由此可知，一個k對角矩陣(k為奇數(shù))A是滿足下述條件的矩陣：若∣i-j∣>(k-1)/2，則元素aij=0。對角矩陣可按行優(yōu)先順序或?qū)蔷€的順序，將其壓縮存儲到一個向量中，并且也能找到每個非零元素和向量下標(biāo)的對應(yīng)關(guān)系。在三對角矩陣?yán)锔綕M足條件i=0，j=0、1，或i=n-1j=n-2、n-1或1<i<n-1,j=i-1、i、i+1的元素aij外，其余元素都是零。第15頁，共53頁，2023年，2月20日，星期六對這種矩陣，我們也可按行優(yōu)序為主序來存儲。除第0行和第n-1行是2個元素外，每行的非零元素都要是3個，因此，需存儲的元素個數(shù)為3n-2。K=012345……3n-23n-1數(shù)組sa中的元素sa[k]與三對角帶狀矩陣中的元素aij存在一一對應(yīng)關(guān)系，在aij之前有i行,共有3*i-1個非零元素，在第i行，有j-i+1個非零元素，這樣，非零元素aij的地址為：LOC(i,j)=LOC(0,0)+[3*i-1+(j-i+1)]*d=LOC(0,0)+(2i+j)*d上例中，a34對應(yīng)著sa[10]。k=2*i+j=2*3+4=10a00a01

a10a11a12a21

……an-1n-2an-1n-1第16頁，共53頁，2023年，2月20日，星期六a21對應(yīng)著sa[5]k=2*2+1=5由此，我們稱sa[0..3*n-2]是階三對角帶狀矩陣A的壓縮存儲表示。

5.3.2稀疏矩陣設(shè)在的矩陣A中，有s個非零元素。令e=s/(m*n)，稱e為矩陣的稀疏因子。通常認為e≦0.05時稱之為稀疏矩陣。必須同時記下它所在的行和列的位置（i,j)。反之，一個三元組(i,j,aij)唯一確定了矩陣A的一個非零元。第17頁，共53頁，2023年，2月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))

0129000000-30015000000012000180-3000014090024000024000000000–70180000000140001500–7000000000000000圖5.4稀疏矩陣M和T第18頁，共53頁，2023年，2月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)這一對行、列值便可作為下列矩陣M的另一種描述。而由上述三元組表的不同表示方法可引出稀疏矩陣不同的壓縮存儲方法。

0129000000-30015000000012000180-3000014090024000024000000000–70180000000140001500–7000000000000000

圖5.4稀疏矩陣M和T第19頁，共53頁，2023年，2月20日，星期六5.3.2.1三元組順序表假設(shè)以順序存儲結(jié)構(gòu)來表示三元組表，則可得到稀疏矩陣的一種壓縮存儲方法——三元順序表。

#definemaxsize10000

typedefstruct{inti,j;ElemTypee;}triple;typedefstruct{tripledata[maxsize];intmu,nu,tu;}tripletable;第20頁，共53頁，2023年，2月20日，星期六設(shè)A為tripletable型的結(jié)構(gòu)變量，圖5.4中所示的稀疏矩陣的三元組的表示如下：M.dataT.data第21頁，共53頁，2023年，2月20日，星期六如何實現(xiàn)：矩陣轉(zhuǎn)置和矩陣相乘。1>求矩陣轉(zhuǎn)置若MmXn轉(zhuǎn)置NnXm且N[i,j]=M[j,i]1<=i<=n1<=j<=m顯然一個稀疏矩陣的轉(zhuǎn)置仍是稀疏矩陣假設(shè)M和T是tripletable型變量，如何由M求T從分析可知：（1）將矩陣的行列值交換；（2）將每個三元組中的I和J交換；（3）重排三元組之間的次序以便可實現(xiàn)矩陣轉(zhuǎn)置；有兩種處理方法：一種按T.DATA中的三元組轉(zhuǎn)置；另一種按M.DATA中的三元組的次序轉(zhuǎn)置；第22頁，共53頁，2023年，2月20日，星期六voidtransmatrix(tripletableM,tripletableT){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.data[p].j==col){T.data[q].i=M.data[p].j;T.data[q].j=M.data[p].i;T.data[q].v=M.data[p].e;q++;}returnOK;}1.按T.DATA轉(zhuǎn)置第23頁，共53頁，2023年，2月20日，星期六分析這個算法，主要的工作是在p和col的兩個循環(huán)中完成的，故算法的時間復(fù)雜度為O(n*t)，即矩陣的列數(shù)和非零元的個數(shù)的乘積成正比。而一般傳統(tǒng)矩陣的轉(zhuǎn)置算法為：for(col=0;col<=n-1;++col)for(row=0;row<=m;++row)t[col][row]=m[row][col];其時間復(fù)雜度為O(n*m)。當(dāng)非零元素的個數(shù)t和m*n同數(shù)量級時，算法transmatrix的時間復(fù)雜度為O(n*nu2)。第24頁，共53頁，2023年，2月20日，星期六因此，此算法僅適用于t<=m*n的情況。2.另外一種稱之為快速轉(zhuǎn)置的算法其算法思想為：對A掃描一次，按A第二列提供的列號一次確定位置裝入B的一個三元組。具體實施如下：一遍掃描先確定三元組的位置關(guān)系，二次掃描由位置關(guān)系裝入三元組?？梢?，位置關(guān)系是此種算法的關(guān)鍵。第25頁，共53頁，2023年，2月20日，星期六為了預(yù)先確定矩陣M中的每一列的第一個非零元素在數(shù)組B中應(yīng)有的位置，需要先求得矩陣M中的每一列中非零元素的個數(shù)。因為：矩陣M中第一列的第一個非零元素在數(shù)組B中應(yīng)有的位置等于前一列第一個非零元素的位置加上前列非零元素的個數(shù)。為此，需要設(shè)置兩個一維數(shù)組num[0..n]和cpot[0..n]num[0..n]：統(tǒng)計M中每列非零元素的個數(shù)，num[col]的值可以由A的第二列求得。第26頁，共53頁，2023年，2月20日，星期六12vq…Aijv第一列元素個數(shù)第二列元素個數(shù)第三列元素個數(shù)numcpotq=cpot[col]21vpp第27頁，共53頁，2023年，2月20日，星期六cpot[0..n]：由遞推關(guān)系得出M中的每列第一個非零元素在B中的位置。算法通過cpot數(shù)組建立位置對應(yīng)關(guān)系：cpot[1]=1cpot[col]=cpot[col-1]+num[col-1]2<=cpl<=a.n例如：圖5.4中的矩陣M和相應(yīng)的三元組A可以求得num[col]和cpot[col]的值如下：col1234567num[col]2221010cpot[col]1357889第28頁，共53頁，2023年，2月20日，星期六快速轉(zhuǎn)置算法如下：voidfasttranstri(tritupletableM,tritupletable&T){T.mu=M.nu;T.nu=M.mu;T.tu=M.tu;if(T.tu){for(col=1;col<=M.nu;++col)num[col]=0;for(t=1;t<=M.tu;++t)++num[M.data[t].j];cpot[1]=1;for(col=2;col<=M.nu;++col)cpot[col]=cpot[col-1]+num[col-1];for(p=1;p<=M.tu;++p){col=M.data[p].j;q=cpot[col];T.data[q].i=M.data[p].j;T.data[q].j=M.data[p].i;T.data[q].e=M.data[p].e;++cpot[col];}}returnOK;}

第29頁，共53頁，2023年，2月20日，星期六二、帶行表的三元組有時為了方便某些矩陣運算，我們在按行優(yōu)先存儲的三元組中，加入一個行表來記錄稀疏矩陣中每行的非零元素在三元組表中的起始位置。當(dāng)將行表作為三元組表的一個新增屬性加以描述時，我們就得到了稀疏矩陣的另一種順序存儲結(jié)構(gòu)：帶行表的三元組表。其類型描述如下：第30頁，共53頁，2023年，2月20日，星期六#definemaxrow100typedefstruct{tripledata[maxsize+1];intrpos[maxrow+1];intnu,mu,tu;}rtripletable

下面討論兩個稀疏矩陣相乘的例子，容易看出這種表示方法的優(yōu)越性。第31頁，共53頁，2023年，2月20日，星期六兩個矩陣相乘的經(jīng)典算法也是大家所熟悉的。若設(shè)Q=M*N其中，M是m1*n1矩陣，N是m2*n2矩陣。當(dāng)n1=m2時有：for(i=1;i<=m1;++i)for(j=1;j<=n2;++j){q[i][j]=0for(k=1;k<=n1;++k)q[i][j]+=m[i][k]*n[k][j];}此算法的復(fù)雜度為O(m1*n1*n2)。第32頁，共53頁，2023年，2月20日，星期六當(dāng)M和N是稀疏矩陣并用三元組表存儲結(jié)構(gòu)時，就不能套用上述算法。假設(shè)M和N分別為：