華中科技大學(xué)計算機(jī)學(xué)院

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

第五章數(shù)組和廣義表引言：

線性表：L=(a1,a2,...,an)，ai是同類型的元素，1≤i≤n

數(shù)組:

A=(a1,a2,...,an)

若ai是同類型的元素，A是一維數(shù)組，1≤i≤n

若ai是同類型的定長線性表，A是多維數(shù)組，1≤i≤n

廣義表：Ls=(a1,a2,...,an)ai可以是同類型的元素或廣義表，1≤i≤n5.1數(shù)組的基本概念及其操作

數(shù)組是相同類型的數(shù)據(jù)的有限的、有序的組合。5.1.1

數(shù)組的遞歸定義

1.一維數(shù)組：

是一個定長線性表(a1,a2,...,an)。

其中：ai為數(shù)據(jù)元素，i為下標(biāo)/序號，1≤i≤n(a1,a2,...,an)又稱為向量。2.二維數(shù)組是一個定長線性表(1,2,...,m)，

其中:i=(ai1,ai2,...,ain)為行向量，1≤i≤m

由m個行向量組成，記作：(a11a12...a1n)(a21a22...a2n)............(am1am2...amn)Am*n=即Am*n=((a11a12...a1n),(a21a22...a2n),...,(am1am2...amn))或由n個列向量組成，記作：))

a11a12a1na21a22a2n

am1am2amn))))Amxn=3.三維數(shù)組是一個定長線性表(1,2,...,p)。

其中:k=(1,2,...,m)為定長二維數(shù)組，1≤k≤p例三維數(shù)組A[1..3,1..4,1..2],p=3,m=4,n=2a111a112a121a122a131a132a141a142a211a212a221a222a231a232a241a242a311a312a321a322a331a332a341a342第1頁第2頁第3頁A3*4*2=5.1.2數(shù)組的類型定義和變量說明：例1inta[10]；//10個整數(shù)的一維數(shù)組

charb[4][5]；//4行5列個字符的二維數(shù)組

floatc[3][4][2]；//3*4*2個實數(shù)的三維數(shù)組例2#definem4//定義符號常量m#definen5//定義符號常量ninta[m]；//m個整數(shù)的一維數(shù)組

charb[m][n]；//m行n列個字符的二維數(shù)組例3#definem4//定義符號常量m#definen5//定義符號常量ntypedefintara[m]；//一維數(shù)組類型aratypedefchararb[m][n]；//二維數(shù)組類型arbaraa；//ara類型的變量aarbb；//arb類型的變量bC語言中定義靜態(tài)數(shù)組時，元素數(shù)目必須是常量錯例1

intm=4,n=5；

inta[m][n]；//m,n是變量錯例2intp；

scanf(”%d”,&p)；

intc[p]；//p是變量5.1.3數(shù)組的操作1.生成一個數(shù)組：

inta[7]；//生成靜態(tài)一維數(shù)組

2.賦值/修改

a[1]=15；(a[1])++；

3.取元素的值：

a[0]=a[1]*2；

4.銷毀一個數(shù)組a

0

1

2

3

4

5

61516325.1.4程序設(shè)計舉例例1main(){inti,a[10]；//生成一維數(shù)組afor(i=0；i<10；i++)scanf(”%d”,&a[i])；//輸入元素

for(i=0；i<10；i++)printf(”%d”,a[i]*a[i])；//輸出元素的平方}退出時釋放a例2生成動態(tài)的10個整數(shù)的一維數(shù)組

int*pa；//指針變量papa=(int*)malloc(10*sizeof(int))；//動態(tài)數(shù)組papa0123456789pa[0]pa[1]pa[9]…main(){inti,n,*pa；

scanf(”%d”,&n)；//動態(tài)輸入npa=(int*)malloc(n*sizeof(int))；//生成動態(tài)數(shù)組*pafor(i=0；i<n；i++)*(pa+i)=2*i；//指針法引用數(shù)組元素,賦值

for(i=0；i<n；i++)printf(“%d,”,*(pa+i))；//輸出數(shù)組元素0,2,4,6,...

for(i=0；i<n；i++)scanf(“%d”,&pa[i])；//下標(biāo)法引用數(shù)組元素,輸入

for(i=0；i<n；i++)printf("%d,",pa[i])；//輸出數(shù)組元素

free(pa)；//釋放(銷毀)數(shù)組空間}5.2數(shù)組的順序表示和實現(xiàn)

5.2.1順序表示(順序存儲結(jié)構(gòu)）1.以行序為主序的順序存儲方式左邊的下標(biāo)后變化，右邊的下標(biāo)先變化2.以列序為主序的順序存儲方式左邊的下標(biāo)先變化，右邊的下標(biāo)后變化例1二維數(shù)組a[1..3,1..2],b是首地址,s是元素所占的單元數(shù)a11a12a21a22a31a32a11a12a21a22a31a32a11a21a31a12a22a32序號內(nèi)存地址123456123456序號內(nèi)存地址bb+sb+2*sb+3*sb+4*sb+5*sbb+sb+2*sb+3*sb+4*sb+5*s以行序為主序以列序為主序邏輯結(jié)構(gòu)例2三維數(shù)組a[1..2,1..3,1..2]a111a112a121a122a131a132a111a112a121a122a131a132a211a212a221a222a231a232序號內(nèi)存地址123456789101112序號內(nèi)存地址bb+sb+2*sb+3*sb+4*sb+5*sb+6*sb+11*sbb+sb+2*sb+3*sb+4*sb+5*sb+6*sb+11*s以行序為主序以列序為主序邏輯結(jié)構(gòu)a211a212a221a222a231a232第1頁第2頁123456789101112a111a211a121a221a131a231a112a212a122a222a132a2325.2.2數(shù)組的映象函數(shù)數(shù)組元素的存儲地址例1一維數(shù)組a[0..n-1]

設(shè):b為首地址,s為每個元素所占的存儲單元數(shù)則:元素a[i]的存儲地址：

Loc(i)=Loc(0)+i*s=b+i*s0≤i≤n-1a(n-1)...ai...a2a1a0下標(biāo)012in-1地址bb+sb+2*sb+i*sb+(n-1)*sa1a2a3...ai...an下標(biāo)1

2

3

in地址bb+sb+2sb+(i-1)sb+(n-1)s例2一維數(shù)組a[1..n]元素a[i]的存儲地址

Loc(i)=Loc(1)+(i-1)*s=b+(i-1)*s1≤i≤n

例3

二維數(shù)組a[1..m,1..n],假定無零行零列a11...a1j...a1n.................ai1...aij...ain.................am1...amj...amnAmxn=(1)以行序為主序，a[i][j]的地址為

Loc(i,j)=Loc(1,1)+(n*(i-1)+j-1)*s=b+(n*(i-1)+j-1)*s1≤i≤m,1≤j≤n其中：b為首地址，s為每個元素所占的存儲單元數(shù)

n:列數(shù)m:行數(shù)共i-1行共j-1列例3

二維數(shù)組a[1..m,1..n],假定無零行零列a11a12...a1j...a1n..................ai1ai2...aij...ain..................am1am2...amj...amnAmxn=(2)以列序為主序，a[i][j]的地址為

Loc(i,j)=Loc(1,1)+(m*(j-1)+i-1)*s=b+(m*(j-1)+i-1)*s1≤i≤m,1≤j≤n其中：b為首地址，s為每個元素所占的存儲單元數(shù)

n:列數(shù)m:行數(shù)共i-1行共j-1列例4

二維數(shù)組a[0..m-1,0..n-1]（有零行零列）a00...a0j...a0n-1a10...a1j...a1n-1....................ai0...aij...ain-1....................am-10...am-1j...am-1n-1Amxn=(1)以行序為主序，a[i][j]的地址為

Loc(i,j)=Loc(0,0)+(n*i+j)*s=b+(n*i+j)*s0≤i≤m-1,0≤j≤n-1其中：b為首地址，s為每個元素所占的存儲單元數(shù)

n:列數(shù)m:行數(shù)共i行共j列例4

二維數(shù)組a[0..m-1,0..n-1]（有零行零列）a00a01...a0j...a0n-1a10a11...a1j...a1n-1.....................

ai0ai1...aij...ain-1....................am-10am-11...am-1j...am-1n-1Amxn=(2)以列序為主序，a[i][j]的地址為

Loc(i,j)=Loc(0,0)+(m*j+i)*s=b+(m*j+i)*s0≤i≤m-1,0≤j≤n-1其中：b為首地址，s為每個元素所占的存儲單元數(shù)

n:列數(shù)m:行數(shù)共i行共j列例5三維數(shù)組a[1..p,1..m,1..n],假定無0頁0行0列1)以行序為主序，a[k][i][j]的地址為

Loc(k,i,j)=Loc(1,1,1)+(m*n*(k-1)+n(i-1)+j-1)*s=b+(m*n*(k-1)+n(i-1)+j-1)*s1≤k≤p,1≤i≤m,1≤j≤n其中：

b為首地址，s為每個元素所占的存儲單元數(shù)

p---頁數(shù)n--列數(shù)m-行數(shù)(2)以列序為主序，a[k][i][j]的地址為

Loc(k,i,j)=Loc(1,1,1)+(p*m*(j-1)+p*(i-1)+k-1)*s=b+(p*m*(j-1)+p*(i-1)+k-1)*s1≤k≤p,1≤i≤m,1≤j≤n其中：

b為首地址，s為每個元素所占的存儲單元數(shù)

p---頁數(shù)n--列數(shù)m-行數(shù)例5三維數(shù)組a[0..p-1,0..m-1,0..n-1],(1)以行序為主序，a[k][i][j]的地址為

Loc(k,i,j)=Loc(0,0,0)+(m*n*k+n*i+j)*s=b+(m*n*k+n*i+j)*s0≤k≤p-1,0≤i≤m-1,0≤j≤n-1其中：

b為首地址，s為每個元素所占的存儲單元數(shù)

p---頁數(shù)n--列數(shù)m-行數(shù)(2)以列序為主序，a[k][i][j]的地址為

Loc(k,i,j)=Loc(0,0,0)+(p*m*j+p*i+k)*s=b+(p*m*j+p*i+k)*s0≤k≤p-1,0≤i≤m-1,0≤j≤n-1其中：

b為首地址，s為每個元素所占的存儲單元數(shù)

p---頁數(shù)n--列數(shù)m-行數(shù)5.3矩陣的壓縮存儲

5.3.1特殊矩陣的壓縮存儲

1.n階對稱矩陣a11a1n

aji

aij

an1annAnxn=上三角下三角aij==aji1≤i,j≤n(1)設(shè)aij在下三角，i≥j

∵

第1i-1行共有元素

1+2+3+…(i-1)=i(i-1)/2(個)ai1aij共有j個元素∴aij的序號為:k=i(i-1)/2+j假定以行序為主，順序存儲下三角元素到SA[1..maxleng]a11a21a22a31...ai1...aij...aii...an1...annk=1234...i(i-1)/2+j...n(n+1)/2如何求aij在SA中的位置，即序號k？(2)設(shè)aij在上三角,i<j∵上三角的aij=下三角的aji

下三角的aji的序號為

k=j(j-1)/2+ii<j∴上三角的aij的序號為

k=j(j-1)/2+ii<j

由(1)和(2)，任意aij在SA中的序號，為

i(i-1)/2+ji≥jj(j-1)/2+ii<j

稱為在SA中的映象函數(shù)，下標(biāo)轉(zhuǎn)換公式k(i,j)=2.三對角矩陣a11a12a21a22a23

a32a33a34

...aij.....an-1n-1an-1n

ann-1annAnxn=全0全0假定以行序為主，順序存儲非0元素到SA[1..maxleng]：a11a21a22a23a32a33...aij...ann-1annk=123456...?...3n-2任意aij≠0,在SA中的序號:k=(3*(i-1)-1)+(j-i+2)=2(i-1)+j5.3.2

稀疏矩陣的壓縮存儲1.三元組表例稀疏矩陣M及其轉(zhuǎn)置矩陣T013900000000000-300001400024000001800000000-700000-300013000180900240000000-70000000014000000000M=T=121313931-336144324521864-7ijv=aij13-321132518319342446-76314ijv=aijM的三元組表

T的三元組表表A表B問題:如何由矩陣M求矩陣T,即由表A求表B？

行數(shù)(mu)：6列數(shù)(nu)：7非零元(tu)：7M的三元表存儲結(jié)構(gòu)用C語言定義三元組表#defineMAXSIZE100typedefstruct{inti,j;//非零元行、列下標(biāo)

ElemTypee;}Triple;//定義三元組typedefstruct{Tripledata[MAXSIZE+1];intmu,nu,tu;}TSMatrix;//定義三元組表TSMatrixM;-746182524341463-3139311321

行數(shù)(mu)：6列數(shù)(nu)：7非零元(tu)：7-746182524341463-3139311321

行數(shù)(mu)：7列數(shù)(nu)：6非零元(nu)：7-764185224431436-3319131312行、列互換不符合以行為主的存放M的三元表存儲結(jié)構(gòu)T的三元表存儲結(jié)構(gòu)

行數(shù)(mu)：6列數(shù)(nu)：7非零元(tu)：7-746182524341463-3139311321M的三元表存儲結(jié)構(gòu)T.mu=M.nu;T.nu=M.Mu;T.tu=M.tu;if(T.tu){q=1;/*指示向T寫時的位置*/for(col=1;col<=M.nu;++col)for(p=1;p<=M.tu;++p)/*掃描M三元表*/if(M.data[p].j==col)/*當(dāng)前行*/{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++;}}returnOK;算法1：時間復(fù)雜度:O(nu*tu)col1234567num[col]1221010cpot[col]1246778cpot[1]=1;cpot[col]=cpot[col-1]+num[col-1]2≤col≤a.nufor(p=1;p<=M.tu;++p)/*掃描M三元表*/{col=M.data[p].j;/*確定當(dāng)前元素列號*/q=cpot[col];/*確定當(dāng)前元素M.data[p]

在T的當(dāng)前存放位置*/T.data[q].j=M.data[p].i;T.data[q].i=M.data[p].j;T.data[q].e=M.data[p].e;++cpot[col];/*T的當(dāng)前列指示下一空位置*/}算法2：時間復(fù)雜度:O(nu+tu)2.十字鏈接表例稀疏矩陣2500640-80020000M=3120

∧

∧22-8

∧

∧1464

∧

∧1125

∧ijedownright行號列號值下一行的非0元素下一列的非0元素列頭指針數(shù)組行

頭指針數(shù)組5.4廣義表(generalizedlist),列表(lists)5.4.1廣義表的定義和術(shù)語

n(n≥0)個數(shù)據(jù)元素或廣義表的一個有限序列叫做廣義表。記作:LS=(e1,e2,...,en)。n為LS的長度。其中:LS----廣義表名

ei----單元素、原子,約定用小寫,1≤i≤nei----廣義表，約定用大寫,1≤i≤n(1)空表LS=(),n=0(2)非空表LS=(e1,e2,...,en)n>0

其中:e1---LS的表頭/首部，記作:Head(LS)=e1(e2,...,en)---LS的表尾/尾部,記作：

Tail(LS)=(e2,...,en)例：(1)A=()//空表(2)B=(e)Head(B)=eTail(B)=()(3)C=(a,b,c)Head(C)=aTail(C)=(b,c)Head(Tail(C))=bTail(Tail(C))=(c)(4)D=(a,(b,c))Head(D)=aTail(D)=((b,c))D2=((a,b),c)Head(D2)=(a,b)Tail(D2)=(c)(5)E=((a,b),c,(d,e))Head(E)=(a,b)Tail(E)=(c,(d,e))Head(Tail(E))=cTail(Tail(E))=((d,e))(6)F=(A,B,C,d)=((),(e),(a,b,c),d)Head(F)=()Tail(F)=((e),(a,b,c),d)(7)G=(a,G)//遞歸廣義表

=(a,(a,G))=(a,(a,(a,G)))=(a,(a,(a,(a,...G))))Head(G)=aTail(G)=(G)=((a,G))(8)H=((),((),()))Head(H)=()Tail(H)=(((),()))5.4.2廣義表的圖型表示----樹型結(jié)構(gòu)約定□----單元素/原子○----列表,若有表名,附表名例(1)A=()(2)B=(a)ABa(3)C=(a,b,c)(4)D=(a,(b,c))CbDacabc(5)E=((a,b),c,(d,e))(6)F=(A,B,C,d)=((),(e),(a,b,c),d)EbcaedadecbFBAC(7)G=(a,G)(8)H=((),((),()))HGaaGaG...5.4.3廣義表的操作

1.求長度：Leng(LS)a=()Leng(A)=0G=(a,G)Leng(G)=2H=((),((),()))Leng(H)=2F=(A,B,C,d)Leng(F)=42.求表頭：Head(LS)G=(a,G)Head(G)=aE=((a,b),c,(d,e))Head(E)=(a,b)3.求表尾：Tail(LS)G=(a,G)Tail(G)=(G)=((a,G))E=((a,b),c,(d,e))Tail(E)=(c,(d,e))4.求第i個元素：GetElem(LS,i)=ei1≤i≤nI=((a,b),c,(),(d))GetElem(I,1)=(a,b)Get(I,2)=CGetElem(E,3)=()Get(I,4)=(d)5.求深度：Depth(LS)---LS所含括號的層數(shù)

(1)A=()Depth(A)=1(2)E=((a,b),c,(d,e))Depth(E)=2(3)H=((),((),()))Depth(H)=36.插入：InsertFirst(LS,e)---e插入LS的第一個位置設(shè)A=()

執(zhí)行：InsertFirst(A,a)；得：A=(a)

執(zhí)行：InsertFirst(A,(b,(c)))；得：A=((b,(c)),a)

執(zhí)行：InsertFirst(A,())；得：A=((),(b,(c)),a)7.其它：......5.5廣義表的存儲結(jié)構(gòu)廣義表的的元素具有不同結(jié)構(gòu)，一般用鏈?zhǔn)酱鎯Y(jié)構(gòu)。tag=1hp(表頭）tp(表尾)tag=0atom(元素)原子結(jié)點:列表結(jié)點:typedefstructGLNode{ElemTagtag;union{AtomTypeatom;struct{structGLNode*hp,*tp;}ptr;}}*GList;(1)A=()(2)B=(e)(3)C=(a,b,c)A=NULL1^0eB10aC10b1^0c5.6m元多項式的表示一元多項式:P(x)

=6+3x3-3x5