12講第五章數(shù)組廣義表

第五章數(shù)組和廣義表本章內(nèi)容與要點(diǎn)本章內(nèi)容數(shù)組的類(lèi)型定義和表示方法；稀疏矩陣的壓縮存儲(chǔ)方法及矩陣運(yùn)算的實(shí)現(xiàn)；廣義表定義的遞歸性及廣義表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)。本章要點(diǎn)了解數(shù)組的兩種存儲(chǔ)表示方法，并掌握數(shù)組在以行為主的存儲(chǔ)結(jié)構(gòu)中的地址計(jì)算方法；領(lǐng)會(huì)以三元組表示稀疏矩陣時(shí)進(jìn)行矩陣運(yùn)算采用的處理方法；掌握廣義表的結(jié)構(gòu)特點(diǎn)及鏈?zhǔn)酱鎯?chǔ)表示方法；掌握數(shù)組和廣義表可看成是一種特殊的線性表，其特殊性在于，表中的數(shù)據(jù)元素本身也是一種線性表。5.1數(shù)組的定義數(shù)組數(shù)組是數(shù)據(jù)元素為結(jié)構(gòu)類(lèi)型的一種特殊的線性表。數(shù)組的每一個(gè)元素的結(jié)構(gòu)都是相同的；數(shù)組中各元素具有統(tǒng)一的類(lèi)型，并且數(shù)組元素的下標(biāo)一般具有固定的上界和下界；數(shù)組通常分為一維數(shù)組、二維數(shù)組、三維數(shù)組…和n維數(shù)組。數(shù)組一旦被定義，它的維數(shù)和維界就不再改變。除了結(jié)構(gòu)的初始化和銷(xiāo)毀之外，數(shù)組只有存取元素和修改元素值的操作。

二維數(shù)組的定義二維數(shù)組既可以看成是由行向量組成的向量；也可以看成是列向量組成的向量；C語(yǔ)言中二維數(shù)組的定義定義為分量類(lèi)型為一維數(shù)組類(lèi)型的一維數(shù)組類(lèi)型

typedefelemtypearray2[m][n];

等價(jià)于：

typedefelemtypearray1[n];typedefarray1array2[m];Amn=a11a12

…a1na21a22

…a2n

…

…

…

…am1am2

…amn5.2數(shù)組的順序表示和實(shí)現(xiàn)數(shù)組的順序存儲(chǔ)方式行優(yōu)先順序?qū)?shù)組元素按行排列，第i+1個(gè)行向量緊接在第i個(gè)行向量后面；以二維數(shù)組為例，按行優(yōu)先順序存儲(chǔ)的線性序列為：a11,a12,…,a1n,a21,a22,…a2n,……,am1,am2,…,amn

PASCAL、C語(yǔ)言中，數(shù)組就是按行優(yōu)先順序存儲(chǔ)的。列優(yōu)先順序?qū)?shù)組元素按列向量排列，第j+1個(gè)列向量緊接在第j個(gè)列向量之后，數(shù)組的m*n個(gè)元素按列優(yōu)先順序存儲(chǔ)的線性序列為：a11,a21,…,am1,a12,a22,…am2,……,an1,an2,…,anm在FORTRAN語(yǔ)言中，數(shù)組就是按列優(yōu)先順序存儲(chǔ)的。數(shù)組的順序存儲(chǔ)方式（續(xù)）多維數(shù)組行優(yōu)先順序規(guī)定為先排最右的下標(biāo)，從右到左，最后排最左下標(biāo)：列優(yōu)先順序規(guī)定為先排最左下標(biāo)，從左向右，最后排最右下標(biāo)。數(shù)組的順序存儲(chǔ)特點(diǎn)只要已知開(kāi)始結(jié)點(diǎn)的存放地址（即基地址）、數(shù)組維數(shù)、每維的上、下界，和每個(gè)數(shù)組元素所占用的單元數(shù)，就可以將數(shù)組元素的存放地址表示為其下標(biāo)的線性函數(shù)；數(shù)組中的任一元素可以在相同的時(shí)間內(nèi)存取，即順序存儲(chǔ)的數(shù)組是一個(gè)隨機(jī)存取結(jié)構(gòu)。數(shù)組的順序表示和實(shí)現(xiàn)（續(xù)）求數(shù)組A[c1..d1,c2..d2,……,cn..dn]每個(gè)給定下標(biāo)的數(shù)據(jù)元素的存儲(chǔ)地址：LOC(j1,j2,…,jn)=

Loc(c1,c2,…,cn)+[(d2-c2+1)…(dn-cn+1)(j1-c1)+(d3-c3+1)…(dn-cn+1)(j2-c2)+...+(dn-cn+1)(jn-1-cn-1)+(jn-cn)]*l=Loc(c1,c2,…,cn)+[∑(ji-ci)(∏(dk-ck+1)+(jn-cn)]*li=1k=i+1n-1nLOC(j1,j2,…,jn)=

Loc(c1,c2,…,cn)+∑αi(ji-ci)i=1n其中αi

=l∏(dk-ck+1)1≤i≤nnk=i+15.3矩陣壓縮存儲(chǔ)特殊矩陣非零元素或零元素的分布有一定規(guī)律的矩陣，可以把矩陣壓縮存儲(chǔ)在一個(gè)一維數(shù)數(shù)組中。如下三角矩陣有映射k=i(i-1)/2+j(i≥j),Aij=Bk(i≥j)，Aij=0(i≤j)An×nBm，即B[k]=A[i,j]，需求出下標(biāo)映射函數(shù)k=f(i,j)。上三角矩陣0對(duì)角矩陣000下三角矩陣ajiaij對(duì)稱矩陣a11a21a22a31．．．a(chǎn)n,1．．．a(chǎn)nnk=0123n(n-1)/2n(n+1)/2-1稀疏矩陣稀疏矩陣非零元素很少，分布沒(méi)有規(guī)律；設(shè)矩陣A中有s個(gè)非零元素，若s遠(yuǎn)遠(yuǎn)小于矩陣元素的總數(shù)（即s≦m×n），則稱A為稀疏矩陣；令e=s/(m*n)，稱e為矩陣的稀疏因子。通常認(rèn)為e≦0.05時(shí)稱之為稀疏矩陣；在壓縮存儲(chǔ)時(shí)需要同時(shí)存儲(chǔ)非零元素的下標(biāo)和值；可用三元組存儲(chǔ)（行號(hào)，列號(hào)，值）。0120000100030000500000000020006ijv1212211253345522566A三元組順序表（續(xù)）稀疏矩陣的定義稀疏矩陣還可用帶行索引的二元組表、十字鏈表等表示。#defineMAXSIZE12500typedefstruct{ inti,j; ElemTypee;}Triple;typedefstruct{ Tripledata[MAXSIZE+1]; intmu,nu,tu;}TSMatrix;矩陣的操作求矩陣的轉(zhuǎn)置ijv1212211253345522566ijv1212112252435523656A’求矩陣的轉(zhuǎn)置一個(gè)m×n的矩陣M，它的轉(zhuǎn)置T是一個(gè)n×m的矩陣，且a[i][j]=b[j][i]，0≤i≤m，0≤j≤n，即M的行是T的列，M的列是T的行；算法思想對(duì)M中的每一列col(1≤col≤n)，從頭至尾掃描三元表a.data；找出所有列號(hào)等于col的那些三元組，將它們的行號(hào)和列號(hào)互換后依次放入b.data中；即可得到T的按行優(yōu)先的壓縮存儲(chǔ)表示。求矩陣轉(zhuǎn)置的算法Voidtransmatrix(TSMatrixM,TSMatrix&T){ 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].e=M.data[p].e;q++;}}}算法的時(shí)間復(fù)雜度

O(nu*tu)快速轉(zhuǎn)置算法思路對(duì)M掃描一次，預(yù)先確定矩陣M中每一列的第一個(gè)非零元在T中的位置；對(duì)M進(jìn)行第二次掃描，由位置關(guān)系裝入三元組。算法實(shí)現(xiàn)附設(shè)num和cpot兩個(gè)向量：num[col]:表示矩陣M中第col列中非零元的個(gè)數(shù)；cpot[col]:指示M中第col列的第一個(gè)非零元在b.data中的恰當(dāng)位置；cpot[1]=1;cpot[col]=cpot[col-1]+num[col-1] 2≤col≤a.nu

因三元組表是按行優(yōu)先排序的，故先確定轉(zhuǎn)置后矩陣各行的元素個(gè)數(shù)，預(yù)留出位置再進(jìn)行轉(zhuǎn)置?？焖俎D(zhuǎn)置的算法實(shí)現(xiàn)voidfasttranstri(TSMatrixM,TSMatrix&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];}}}算法的時(shí)間復(fù)雜度

O(mu*nu)5.4廣義表的定義廣義表又稱列表，其每一個(gè)元素的結(jié)構(gòu)都可能是不同的；是n(n≥0)個(gè)元素a1,a2,a3,…,an的有限序列，其中ai或者是原子項(xiàng)，或者是一個(gè)廣義表；通常記作LS=(a1,a2,a3,…,an)LS是廣義表的名字，n為它的長(zhǎng)度。若ai是廣義表，則稱它為L(zhǎng)S的子表。第一個(gè)元素a1稱為表LS的表頭（head），由余下元素組成的表(a2,a3,...,an)稱為L(zhǎng)S的表尾（tail）。廣義表中括號(hào)的重?cái)?shù)稱為廣義表的深度。廣義表的定義（續(xù)）廣義表舉例表長(zhǎng)表深表頭表尾A=()01--B=(a,A)=(a,())22a(())C=((a,b),c,d)32(a,b)(c,d)D=(a,D)=(a,(a,(a,…)))2

a(D)廣義表的圖形表達(dá)方法

A=(a,b)abAB=(A,c)BD=(a,D)aDL=(A,B)LABabcAabc表原子5.5廣義表的存儲(chǔ)結(jié)構(gòu)頭尾鏈表存儲(chǔ)結(jié)構(gòu)typedefenum{ATOM,LIST}ElemTag;typedefstructGLNode{ ElemTagtag; union{ AtomTypeatom; struct{ structGLNode*hp; /*表頭指針*/ structGLNode*tp; /*表尾指針*/ }ptr; };}*GList;tag=1hptp表結(jié)點(diǎn)tag=0data原子結(jié)點(diǎn)廣義表的頭尾鏈表存儲(chǔ)結(jié)構(gòu)示例A=()A-NIL11^^0a111^0c0d11^0a0b11^D0aB=(a,A)C=((a,b),c,d)D=(a,D)(A)(D)(a,b)(c,d)(d)(b)BC廣義表的存儲(chǔ)結(jié)構(gòu)（續(xù)）擴(kuò)展線性鏈表存儲(chǔ)結(jié)構(gòu)typedefenum{ATOM,LIST}ElemTag;typedefstructGLNode{ ElemTagtag; union{ AtomTagatom; structGLNode*hp; /*表頭指針*/ }; structGLNode*tp; /*同一層的下一個(gè)結(jié)點(diǎn)*/}*GList;tag=0datatp原子結(jié)點(diǎn)tag=1hptp表結(jié)點(diǎn)廣義表的擴(kuò)展線性鏈表存儲(chǔ)示例A1^^1^0aA=()1^^BB=(a,A)C=((a,b),c,d)C1^10c0d^0a0b^1^DD=(a,D)0a1^aDaA(a,b)cdab5.6m元多項(xiàng)式的表示將m元多項(xiàng)式先分解成主變?cè)亩囗?xiàng)式可將其看作一元多項(xiàng)式每個(gè)系數(shù)則是m-1元多項(xiàng)式；利用此法可將m-1元多項(xiàng)式進(jìn)一步分解，直至每個(gè)系數(shù)為常數(shù)。作業(yè)求下列廣義表運(yùn)算的結(jié)果：

1、HEAD[((a,b),(c,d))]2、TAIL[((a,b),(c,d))]3、HEAD[TAIL[((a,b),(c,d))]] 4、TAIL[HEAD[((a,b),(c,d))]]5、HEAD[TAIL[HEAD[((a,b),(c,d))]]] 6、TAIL[HEAD[TAIL[((a,b),(c,d))]]]作業(yè)利用HEAD和TAIL運(yùn)算將下列廣義表中的原子c取出來(lái)：

1、L1=(a,b,c,d)2、L2=((a,b),(c