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

數(shù)據(jù)結(jié)構(gòu)演示文稿第一頁，共五十三頁，2022年，8月28日數(shù)據(jù)結(jié)構(gòu)主講：王阿川第二頁，共五十三頁，2022年，8月28日§5.1數(shù)組的定義§5.2數(shù)組的順序表示和實(shí)現(xiàn)§5.3矩陣的壓縮存儲(chǔ)5.3.1特殊矩陣5.3.2稀疏矩陣

§

5.4廣義表的定義。

§

5.5廣義表的存儲(chǔ)結(jié)構(gòu)第三頁，共五十三頁，2022年，8月28日§5.1數(shù)組的定義

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

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

0123456在這個(gè)下三角矩陣中，第i行恰有i+1個(gè)元素，元素總數(shù)為：1+2+3+…+(i+1)+…+n=n(n+1)/2因此，我們可以按圖中箭頭所指的次序?qū)⑦@些元素存放在一個(gè)向量sa[0..n(n+1)/2-1]中。為了便于訪問對稱矩陣A中的元素，我們必須在aij和sa[k]之間找一個(gè)對應(yīng)關(guān)系。若i≧j，則aij在下三角形中。aij之前的i行（從第0行到第i-1行）一共有1+2+…+i=i(i+1)/2個(gè)元素，在第i行上，aij之前恰有j個(gè)元素（即ai0,ai1,ai2,…,aij-1），因此有：k=i*(i+1)/2+j0≦k<n(n+1)/2第十頁，共五十三頁，2022年，8月28日若i<j，則aij是在上三角矩陣中。因?yàn)閍ij=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的地址可用下列式計(jì)算：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的壓縮存儲(chǔ)，第十一頁，共五十三頁，2022年，8月28日例如a21和a12均存儲(chǔ)在sa[4]中，這是因?yàn)閗=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可共享一個(gè)存儲(chǔ)空間第十二頁，共五十三頁，2022年，8月28日其余的元素正好有n(n+1)/2個(gè)，因此，三角矩陣可壓縮存儲(chǔ)到向量sa[0..n(n+1)/2]中，其中c存放在向量的最后一個(gè)分量中.上三角矩陣中，主對角線之上的第p行(0≦p<n)恰有n-p個(gè)元素.按行優(yōu)先順序存放上三角矩陣中的元素aij時(shí)，aij之前的I行一共有(n-p)=i(2n-i+1)/2個(gè)元素，在第i行上，aij前恰好有j-i個(gè)元素：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第十三頁，共五十三頁，2022年，8月28日下三角矩陣的存儲(chǔ)和對稱矩陣類似，sa[k]和aij對應(yīng)關(guān)系是：k=i(i+1)/2+ji≧jk=n(n+1)/2i>j3、對角矩陣對角矩陣中，所有的非零元素集中在以主對角線為了中心的帶狀區(qū)域中，即除了主對角線和主對角線相鄰兩側(cè)的若干條對角線上的元素之外，其余元素皆為零。下圖給出了一個(gè)三對角矩陣，

a00a01a10a11a12a21a22a23….…..….圖5.3對角矩陣an-2n-3an-2n-2an-2n-1an-1n-2an-1n-1第十四頁，共五十三頁，2022年，8月28日非零元素僅出現(xiàn)在主對角(aii,0≦i≦n-1上，緊鄰主對角線上面的那條對角線上(aii+1,0≦i≦n-2)和緊鄰主對角線下面的那條對角線上(ai+1i,0≦i≦n-2)。顯然，當(dāng)∣i-j∣>1時(shí)，元素aij=0。由此可知，一個(gè)k對角矩陣(k為奇數(shù))A是滿足下述條件的矩陣：若∣i-j∣>(k-1)/2，則元素aij=0。對角矩陣可按行優(yōu)先順序或?qū)蔷€的順序，將其壓縮存儲(chǔ)到一個(gè)向量中，并且也能找到每個(gè)非零元素和向量下標(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外，其余元素都是零。第十五頁，共五十三頁，2022年，8月28日對這種矩陣，我們也可按行優(yōu)序?yàn)橹餍騺泶鎯?chǔ)。除第0行和第n-1行是2個(gè)元素外，每行的非零元素都要是3個(gè)，因此，需存儲(chǔ)的元素個(gè)數(shù)為3n-2。K=012345……3n-23n-1數(shù)組sa中的元素sa[k]與三對角帶狀矩陣中的元素aij存在一一對應(yīng)關(guān)系，在aij之前有i行,共有3*i-1個(gè)非零元素，在第i行，有j-i+1個(gè)非零元素，這樣，非零元素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第十六頁，共五十三頁，2022年，8月28日a21對應(yīng)著sa[5]k=2*2+1=5由此，我們稱sa[0..3*n-2]是階三對角帶狀矩陣A的壓縮存儲(chǔ)表示。

5.3.2稀疏矩陣設(shè)在的矩陣A中，有s個(gè)非零元素。令e=s/(m*n)，稱e為矩陣的稀疏因子。通常認(rèn)為e≦0.05時(shí)稱之為稀疏矩陣。必須同時(shí)記下它所在的行和列的位置（i,j)。反之，一個(gè)三元組(i,j,aij)唯一確定了矩陣A的一個(gè)非零元。第十七頁，共五十三頁，2022年，8月28日例如，下列三元組表((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第十八頁，共五十三頁，2022年，8月28日例如，下列三元組表((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的另一種描述。而由上述三元組表的不同表示方法可引出稀疏矩陣不同的壓縮存儲(chǔ)方法。

0129000000-30015000000012000180-3000014090024000024000000000–70180000000140001500–7000000000000000

圖5.4稀疏矩陣M和T第十九頁，共五十三頁，2022年，8月28日5.3.2.1三元組順序表假設(shè)以順序存儲(chǔ)結(jié)構(gòu)來表示三元組表，則可得到稀疏矩陣的一種壓縮存儲(chǔ)方法——三元順序表。

#definemaxsize10000

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

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

下面討論兩個(gè)稀疏矩陣相乘的例子，容易看出這種表示方法的優(yōu)越性。第三十一頁，共五十三頁，2022年，8月28日兩個(gè)矩陣相乘的經(jīng)典算法也是大家所熟悉的。若設(shè)Q=M*N其中，M是m1*n1矩陣，N是m2*n2矩陣。當(dāng)n1=m2時(shí)有：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)。第三十二頁，共五十三頁，2022年，8月28日當(dāng)M和N是稀疏矩陣并用三元組表存儲(chǔ)結(jié)構(gòu)時(shí)，就不能套用上述算法。假設(shè)M和N分別為：