考研-數(shù)據(jù)結(jié)構(gòu)

數(shù)據(jù)結(jié)構(gòu)---第五章數(shù)組和廣義表1第五章數(shù)組和廣義表

本質(zhì)上為非線性結(jié)構(gòu)5.1數(shù)組和線性表的關(guān)系以及數(shù)組的運(yùn)算5.2數(shù)組的順序存儲結(jié)構(gòu)5.3特殊矩陣和稀疏矩陣的壓縮存儲5.4廣義表的定義和表示方法5.5廣義表的存儲結(jié)構(gòu)5.6廣義表的遞歸算法5.7例題解析數(shù)據(jù)結(jié)構(gòu)---第五章數(shù)組和廣義表25.1數(shù)組和線性表的關(guān)系以及數(shù)組的運(yùn)算[數(shù)組和線性表的關(guān)系]

任何數(shù)組A都可以看作一個線性表

A=(a1,a2,…,aj,…an)

n維數(shù)組時，表中每一個元素是一個(n-1)維數(shù)組[數(shù)組的特點(diǎn)]數(shù)組中各元素都具有統(tǒng)一的類型可以認(rèn)為，d維數(shù)組的非邊界元素具有d個直接前趨和d個直接后繼數(shù)組維數(shù)確定后，數(shù)據(jù)元素個數(shù)和元素之間的關(guān)系不再發(fā)生改變，適合于順序存儲每組有定義的下標(biāo)都存在一個與其相對應(yīng)的值[在數(shù)組上的基本操作]給定一組下標(biāo)，取得相應(yīng)的數(shù)據(jù)元素值讀取給定一組下標(biāo)，修改相應(yīng)的數(shù)據(jù)元素值修改數(shù)據(jù)結(jié)構(gòu)---第五章數(shù)組和廣義表35.2數(shù)組的順序存儲結(jié)構(gòu)[一維數(shù)組]b基地址c個單元a[1]a[2]a[i]loc(a[i])=b+(i-1)c=b-c+i*c=C0+C1*iC1=cC0=b-C1VARa:ARRAY[1..n]OFelemtp；數(shù)據(jù)結(jié)構(gòu)---第五章數(shù)組和廣義表4[二維數(shù)組]

a11a12a13...a1na21a22a23...a2n

::::am1am2am3...amna=mna[1,1]a[1,n]a[2,1]a[i,j]a[m,n]ba1loc(a[i,j])=b+[(i-1)*n+(j-1)]*c=C0+C1*i+C2*jC2=cC1=n*C2C0=b-C1-C2注：Pascal、C語言以行序?yàn)橹餍?/p>

Fortran語言以列序?yàn)橹餍騐ARa:ARRAY[1..m,1..n]OFelemtp;數(shù)據(jù)結(jié)構(gòu)---第五章數(shù)組和廣義表5[d維數(shù)組]loc(a[i1,i2,...,id])=C0+C1*i1+C2*i2+...+Cd*id

Cd=c;Ct-1=Ct*nt(1<td)C0=b-C1-C2-...-Cdb=loc(a[1,1,...,1])VARa:ARRAY[1..n1,1..n2,...,1..nd]OFelemtp;數(shù)據(jù)結(jié)構(gòu)---第五章數(shù)組和廣義表65.3特殊矩陣和稀疏矩陣的壓縮存儲

數(shù)組下標(biāo)(i,j)存儲地址5.3.1對稱矩陣[特點(diǎn)]

在nn的矩陣a中，滿足如下性質(zhì)：aij=aji(1i,jn)[存儲方法]

只存儲下(或者上)三角(包括主對角線)的數(shù)據(jù)元素。共占用n(n+1)/2個元素空間。k=i(i-1)/2+j當(dāng)ijj(j-1)/2+i當(dāng)i<ja11a21a22a31aij(aji)annk1234n(n+1)/2saaji確定aij數(shù)據(jù)結(jié)構(gòu)---第五章數(shù)組和廣義表75.3.2三角矩陣[特點(diǎn)]

對角線以下(或者以上)的數(shù)據(jù)元素(不包括對角線)全部為常數(shù)c。[存儲方法]

重復(fù)元素c共享一個元素存儲空間，共占用n(n+1)/2+1個元素空間:sa[1..n(n+1)/2+1]

上三角矩陣下三角矩陣

k=(i-1)(2n-i+2)/2+j-i+1ijk=i(i-1)/2+jijn(n+1)/2+1i>j

n(n+1)/2+1i<jCC上三角矩陣下三角矩陣數(shù)據(jù)結(jié)構(gòu)---第五章數(shù)組和廣義表85.3.3帶狀矩陣（對角矩陣）[特點(diǎn)]

在nn的方陣中，非零元素集中在主對角線及其兩側(cè)共L(奇數(shù))條對角線的帶狀區(qū)域內(nèi)—L對角矩陣。[存儲方法]以對角線的順序存儲

823000

420300

577680096915006142000283五對角矩陣

338520612827943476185962s[-2..2;1..6]-2-1012123456i1=i-jj1=j|i-j|(L-1)/2k1n*Lsak=(i1+2)*n+j1=(i-j+2)*n+j|i-j|(L-1)/2數(shù)據(jù)結(jié)構(gòu)---第五章數(shù)組和廣義表9只存儲帶狀區(qū)內(nèi)的元素除首行和末行，按每行L個元素，共(n-2)L+(L+1)個元素。sa[1..(n-1)L+1]

k=(i-1)L+1+(j-i)|i-j|(L-1)/2

823000

420300

577680096915006142000283823420357768969156142283sak1234567891011121314151617181920212223242526數(shù)據(jù)結(jié)構(gòu)---第五章數(shù)組和廣義表105.3.4稀疏矩陣[特點(diǎn)]

大多數(shù)元素為零。[常用存儲方法]

只記錄每一非零元素(i,j,aij)

節(jié)省空間，但喪失隨機(jī)存取功能順序存儲：三元組表鏈?zhǔn)酱鎯Γ菏?正交)鏈表

1500220-15011

3000000-600000000

9100000002800066數(shù)據(jù)結(jié)構(gòu)---第五章數(shù)組和廣義表115.3.4.1三元組表[類型定義]

CONSTu={矩陣中非零元素最大個數(shù)};TYPEtuple3p=RECORDi,j:integer;v:elemtp;END;

sparmattp=RECORDm,n,t:integer;

{m:行數(shù);n:列數(shù);t:非零元素數(shù)目}data:ARRAY[1..u]OFtuple3tp;END;ijv1115142216651916328數(shù)據(jù)結(jié)構(gòu)---第五章數(shù)組和廣義表12三元組表的結(jié)點(diǎn)次序一般按矩陣的行優(yōu)先順序排列矩陣轉(zhuǎn)置算法示例說明在某些時候利用必要的輔助空間可以提高算法的時間效率其它的順序存儲壓縮方法

帶輔助行向量的二元組表示法

偽地址法

jv1154226-15222334-6191328

14677812345612345678addrv1154226-158229316-62591332812345678addr=(i-1)*n+j數(shù)據(jù)結(jié)構(gòu)---第五章數(shù)組和廣義表135.3.4.2十字（正交）鏈表[特點(diǎn)]

在行、列兩個方向上，將非零元素鏈接在一起?？朔M表在矩陣的非零元素位置或個數(shù)經(jīng)常變動時的使用不便。[類型定義]TYPElink=^matnode;feature=(headnode,element);matnode=RECORDrow,col:integer;right,down:link;CASEfeatureOFheadnode:(next:link);element:(val:elemtp)END;rowcolval/nextdownright數(shù)據(jù)結(jié)構(gòu)---第五章數(shù)組和廣義表14結(jié)點(diǎn)總數(shù)：非零元素個數(shù)+max{行數(shù)，列數(shù)}+1數(shù)據(jù)結(jié)構(gòu)---第五章數(shù)組和廣義表15稀疏矩陣的鏈?zhǔn)酱鎯€可以采用帶行指針向量的單鏈表表示法行指針向量123456

115422

6-15^jvnext數(shù)據(jù)結(jié)構(gòu)---第五章數(shù)組和廣義表165.4廣義表（列表）的定義和表示方法[概念]

廣義表是由零個或多個原子或者子表組成的有限序列。可以記作：LS=(d1,d2,…,dn

)

原子：邏輯上不能再分解的元素。

子表：作為廣義表中元素的廣義表。[與線性表的關(guān)系]

廣義表中的元素全部為原子時即為線性表。線性表是廣義表的特例，廣義表是線性表的推廣。數(shù)據(jù)結(jié)構(gòu)---第五章數(shù)組和廣義表17[廣義表的表示方法和相關(guān)術(shù)語]

表長表深表頭表尾

A=()01--B=(a,A)=(a,())22a(())C=((a,b),c,d)32(a,b)(c,d)D=(a,D)=(a,(a,(a,…)))2a(D)表的長度：表中的元素（第一層）個數(shù)。表的深度：表中元素的最深嵌套層數(shù)。表頭：表中的第一個元素。表尾：除第一個元素外，剩余元素構(gòu)成的廣義表。數(shù)據(jù)結(jié)構(gòu)---第五章數(shù)組和廣義表18[廣義表的圖形表達(dá)方法]

A=(a,b)abAB=(A,c)BD=(a,D)aDL=(A,B)LABabcAabc表原子數(shù)據(jù)結(jié)構(gòu)---第五章數(shù)組和廣義表19[規(guī)定所有表都有名字時廣義表的表示方法]例A(a,b)B(A(a,b),c)L(A(a,b),B(A(a,b),c))D(a,D(a,D(…)))[廣義表結(jié)構(gòu)的分類]

純表：與樹型結(jié)構(gòu)對應(yīng)的廣義表。再入表：允許結(jié)點(diǎn)共享的廣義表。遞歸表：允許遞歸的廣義表。遞歸表再入表純表線性表數(shù)據(jù)結(jié)構(gòu)---第五章數(shù)組和廣義表205.5廣義表的存儲結(jié)構(gòu)5.5.1方法１—頭尾鏈表形式

[類型定義]

TYPEnodeptr=^nodetype;nodetype=RECORDtag:0..1;CASEtagOF0:(data:atomtp);1:(hp,tp:nodeptr)END;

lists1=nodeptr;tag=1hptp表結(jié)點(diǎn)tag=0data原子結(jié)點(diǎn)hp:指示表頭的指針tp:指示表尾的指針數(shù)據(jù)結(jié)構(gòu)---第五章數(shù)組和廣義表21[示例]A=()A-NILBC11^^0a111^0c0d11^0a0b11^D0aB=(a,A)C=((a,b),c,d)D=(a,D)(A)(D)(a,b)(c,d)(d)(b)數(shù)據(jù)結(jié)構(gòu)---第五章數(shù)組和廣義表225.5.2方法2—擴(kuò)展的線性鏈表形式

[類型定義]

TYPEpoint=^node;node=RECORDtag:0..1;tp:point;CASEtagOF0:(data:atomtp);1:(hp:point)END;

lists2=point;tag=1hptp表結(jié)點(diǎn)tag=0datatp原子結(jié)點(diǎn)hp:指向表頭的指針tp:指向同一層的下一個結(jié)點(diǎn)數(shù)據(jù)結(jié)構(gòu)---第五章數(shù)組和廣義表23[示例]A1^^1^0aA=()1^^BB=(a,A)C=((a,b),c,d)C1^10c0d^0a0b^1^DD=(a,D)0a1^aDaA(a,b)cdab數(shù)據(jù)結(jié)構(gòu)---第五章數(shù)組和廣義表245.6廣義表的遞歸算法[廣義表的特點(diǎn)]

定義是遞歸的。[廣義表上操作的實(shí)現(xiàn)]

多采用遞歸算法操作對象——非遞歸表且無共享子表把廣義表分解為表頭和表尾

當(dāng)以頭尾鏈表形式存儲時宜把廣義表看成是n個并列的子表組成的表當(dāng)以擴(kuò)展線性鏈表形式存儲時宜

數(shù)據(jù)結(jié)構(gòu)---第五章數(shù)組和廣義表255.7例題解析判斷題1.數(shù)組可以看成線性表，因此為線性表定義的基本操作也都適合于數(shù)組。2.三元組和散列是稀疏矩陣常用的兩種存儲方式。3.若采用三元組存儲稀疏矩陣，只要將每個元素的行號和列號互換，就完成了對該矩陣的轉(zhuǎn)置。4.特殊矩陣壓縮存儲后喪失隨機(jī)存取功能。5.稀疏矩陣壓縮存儲后喪失隨機(jī)存取功能。6.一個廣義表的表尾總是一個廣義表。7.一個廣義表的深度與其表尾的深度一致。8.空表的表頭仍是空表。9.（北郵2002）二維以上的數(shù)組其實(shí)是一種特殊的廣義表。數(shù)據(jù)結(jié)構(gòu)---第五章數(shù)組和廣義表26填空題1.（北郵2001）用一維數(shù)組B以列優(yōu)先存放帶狀矩陣A中的非零元素A[i，j]（1in，i-2ji+2），B中的第8個元素是A中第1行、第3列的元素。

五對角矩陣2.設(shè)廣義表L=((),())，則head[L]是()；tail[L]是(())?！瓟?shù)據(jù)結(jié)構(gòu)---第五章數(shù)組和廣義表27求解題1.已知三維數(shù)組A[1..6,0..7,-1..4]，每個元素占用4個字節(jié)，存儲器按字節(jié)編址。已知A的起始存儲位置是1024，計(jì)算

1）數(shù)組A占用的存儲空間大小

2）按低下標(biāo)優(yōu)先存儲時，A[3,5,2]的第一個字節(jié)的地址類似行優(yōu)先

3）按高下標(biāo)優(yōu)先存儲時，A[3,5,2]的第一個字節(jié)的地址類似列優(yōu)先[解]1）[(6-1+1)(7-0+1)(4-(-1)+1)]4=[686]4=1152字節(jié)2）1024+[(3-1)86+(5-0)6+(2-(-1))]4=15403）1024+[(3-1)+(5-0)6+(2-(-1))86]4=1728數(shù)據(jù)結(jié)構(gòu)---第五章數(shù)組和廣義表282.設(shè)有nn的上三角矩陣A，其上三角的元素逐行存于數(shù)組B[1..m]中（m充分大），使得B[k]=aij，且k=f(i)+g(j)+C。試推導(dǎo)出函數(shù)f、g和C（要求f和g中不含常數(shù)項(xiàng)）。[解]

k=[n+(n-(i-2))](i-1)/2前i-1行的總元素數(shù)+(j-i+1)第i行上到j(luò)列為止的元素數(shù)=-i2+i(n+1/2)+j-n

即f(i)=-i2+i(n+1/2)g(j)=jC=-n數(shù)據(jù)結(jié)構(gòu)---第五章數(shù)組和廣義表293.設(shè)mn階稀疏矩陣A有t個非零元素，其三元組表表示為LTMA[1:(t+1),1:3]，試問：非零元素的個數(shù)達(dá)到什么程度時用LTMA表示A才有意義？[解答]A矩陣本身直接存儲占用空間為mn，三元組表占用空間為3(t+1),

則應(yīng)有3(t+1)mn，因此tmn/3-1時，用LTMA表示A才有意義。4.利用廣義表的head和tail操作將元素e從以下廣義表中分離出來：L=((((a),b)),(((),d),(e,f)))

并求L的長度和深度[解答]e=head[head[tail[head[tail[L]]]]]

L的長度是2，深度是4。數(shù)據(jù)結(jié)構(gòu)---第五章數(shù)組和廣義表305.給出稀疏矩陣如圖，畫出

1）三元組表示法

2）偽地址表示法

3）帶行指針向量的單鏈表表示法

4）十字鏈表示法6.已知廣義表A=……，畫出其兩種存儲結(jié)構(gòu)。數(shù)據(jù)結(jié)構(gòu)---第五章數(shù)組和廣義表31算法題1.有二維數(shù)組A[1..m,1..n]，其元素為整型，每行每列均按從小到大有序，試給出一算法確定值為x的元素的行、列號，且要求總的比較次數(shù)不多于m+n次。設(shè)x為輸入?yún)?shù)，它一定存在于A中。PROCsearch(A:ARRAY[1..m,1..n]OFinteger;x:integer);i:=1;j:=n;WHILEA[i,j]xDOIFA[i,j]>xTHENj:=j-1ELSEi:=i+1;write(i,j)ENDP;{search}1n1m數(shù)據(jù)結(jié)構(gòu)---第五章數(shù)組和廣義表322.假設(shè)稀疏矩陣Amk和Bkn采用三元組表示，設(shè)計(jì)一個算法求C=A*B，要求C也采用三元組表示。PROCmadd(A,B:sparmattp;VARC:sparmattp);p=1;FORi:=1TOA.mDO[FORj:=1TOB.nDO[c:=0;FORs:=1TOA.nDOc:=c+value(A,i,s)*value(B,s,j);]IFc0THEN[C.data[p].i:=i;C.data[p].j:=j;C.data[p].v:=c;p:=p+1];]C.m=A.m;C.n=B.n;C.t:=p-1ENDP;{madd}數(shù)據(jù)結(jié)構(gòu)---第五章數(shù)組和廣義表33FUNCvalue(C:sparmattp;i,j:integer);p:=1;WHILE(p<=C.tANDNOT(C.data[p].i=iANDC.data[p].j=j))DOp:=p+1;IF(p<=C.t)THENRETURN(C.data[p].v)ELSERETURN(0)ENDF;{value}數(shù)據(jù)結(jié)構(gòu)---第五章數(shù)組和廣義表343.若廣義表以頭尾鏈表形式存儲，求廣義表的深度。方法1：廣義表由n個元素組成LS=（a1，a2，…，an）

1當(dāng)LS為空表

depth(LS)=0當(dāng)LS為單原子

1+

max{depth(ai)}n1

FUNCdepth(ls:list1):integer;IFls=nilTHENRETURN(1);IFls^.tag=0THENRETURN(0);max:=0;pp:=ls;WHILEppnilDO[dep:=depth(pp^.hp);IFdep>maxTHENmax:=dep;pp:=pp^.tp;]RETURN(max+1);ENDF;{depth}數(shù)據(jù)結(jié)構(gòu)---第五章數(shù)組和廣義表35方法2：分析表頭和表尾

1當(dāng)LS為空表

depth(LS)=0當(dāng)LS為單原子

max{depth(head(LS)+1,depth(tail(LS))}其它情況

FUNCdepth(ls:list1):integer;IFls=NILTHENRETURN(1);{空表}

IFls.tag=0THENRETURN(0);{單原子}

dep1:=depth(ls.hp)+1;dep2:=depth(ls.tp);IFdep1>dep2THENRETURN(dep1)ELSERETURN(dep2)ENDF;{depth}數(shù)據(jù)結(jié)構(gòu)---第五章數(shù)組和廣義表364.若廣義表以擴(kuò)展線性鏈表形式存儲，求廣義表的深度。廣義表由n個元素組成LS=（a1，a2，…，an）

1當(dāng)LS為空表

depth(LS)=0