數據結構演示文稿

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

§

5.4廣義表的定義。

§

5.5廣義表的存儲結構第三頁，共五十三頁，2022年，8月28日§5.1數組的定義

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

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

0123456在這個下三角矩陣中，第i行恰有i+1個元素，元素總數為：1+2+3+…+(i+1)+…+n=n(n+1)/2因此，我們可以按圖中箭頭所指的次序將這些元素存放在一個向量sa[0..n(n+1)/2-1]中。為了便于訪問對稱矩陣A中的元素，我們必須在aij和sa[k]之間找一個對應關系。若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第十頁，共五十三頁，2022年，8月28日若i<j，則aij是在上三角矩陣中。因為aij=aji，所以只要交換上述對應關系式中的i和j即可得到：k=j*(j+1)/2+i0≦k<n(n+1)/2令i=max(i,j)，j=min(i,j)，則k和i,j的對應關系可統(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有了上述的下標交換關系，對于任意給定一組下標(i，j)，均可在sa[k]中找到矩陣元素aij，反之，對所有的k=0,1,2,…n(n-1)/2-1，都能確定sa[k]中的元素在矩陣中的位置(I,j)。由此，稱sa[n(n+1)/2]為階對稱矩陣A的壓縮存儲，第十一頁，共五十三頁，2022年，8月28日例如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三角矩陣三角矩陣中的重復元素c可共享一個存儲空間第十二頁，共五十三頁，2022年，8月28日其余的元素正好有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的對應關系是：k=i(2n-i+1)/2+j-i當i≦jk=n(n+1)/2當i>j第十三頁，共五十三頁，2022年，8月28日下三角矩陣的存儲和對稱矩陣類似，sa[k]和aij對應關系是：k=i(i+1)/2+ji≧jk=n(n+1)/2i>j3、對角矩陣對角矩陣中，所有的非零元素集中在以主對角線為了中心的帶狀區(qū)域中，即除了主對角線和主對角線相鄰兩側的若干條對角線上的元素之外，其余元素皆為零。下圖給出了一個三對角矩陣，

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)。顯然，當∣i-j∣>1時，元素aij=0。由此可知，一個k對角矩陣(k為奇數)A是滿足下述條件的矩陣：若∣i-j∣>(k-1)/2，則元素aij=0。對角矩陣可按行優(yōu)先順序或對角線的順序，將其壓縮存儲到一個向量中，并且也能找到每個非零元素和向量下標的對應關系。在三對角矩陣里附滿足條件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)序為主序來存儲。除第0行和第n-1行是2個元素外，每行的非零元素都要是3個，因此，需存儲的元素個數為3n-2。K=012345……3n-23n-1數組sa中的元素sa[k]與三對角帶狀矩陣中的元素aij存在一一對應關系，在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對應著sa[10]。k=2*i+j=2*3+4=10a00a01

a10a11a12a21

……an-1n-2an-1n-1第十六頁，共五十三頁，2022年，8月28日a21對應著sa[5]k=2*2+1=5由此，我們稱sa[0..3*n-2]是階三對角帶狀矩陣A的壓縮存儲表示。

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

0129000000-30015000000012000180-3000014090024000024000000000–70180000000140001500–7000000000000000

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

#definemaxsize10000

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

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