數(shù)據(jù)結(jié)構(gòu)數(shù)組及廣義表課件

第五章數(shù)組和廣義表1第五章數(shù)組和廣義表本章前討論的線性結(jié)構(gòu)數(shù)據(jù)元素都是非結(jié)構(gòu)的原子類型，元素值不可再分。本章討論了兩種數(shù)據(jù)結(jié)構(gòu)—數(shù)組和廣義表。作為線性表的擴展，表中的數(shù)據(jù)元素也是一種數(shù)據(jù)結(jié)構(gòu)。數(shù)組這種數(shù)據(jù)結(jié)構(gòu)可以看成是線性表的推廣。廣義表是另一種推廣形式的線性表，是一種靈活的數(shù)據(jù)結(jié)構(gòu)，在許多方面有廣泛的應用。2知識結(jié)構(gòu)圖數(shù)組與廣義表數(shù)組廣義表類型定義表示方法稀疏矩陣特殊矩陣存儲結(jié)構(gòu)邏輯結(jié)構(gòu)

應用壓縮存儲各種運算35.1數(shù)組數(shù)組是n(n＞1)個相同數(shù)據(jù)類型的數(shù)據(jù)元素a0,a1,a2,...,an-1構(gòu)成的占用一塊地址連續(xù)的內(nèi)存單元的有限序列。數(shù)組中任意一個元素可以用該元素在數(shù)組中的位置來表示，數(shù)組元素的位置通常稱作數(shù)組的下標。45.1.1數(shù)組的概念及其與線性表的關(guān)系由定義知，n維數(shù)組中有b1b2

…

bn個數(shù)據(jù)元素，每個數(shù)據(jù)元素都受到n維關(guān)系的約束。直觀的n維數(shù)組以二維數(shù)組為例討論。將二維數(shù)組看成是一個定長的線性表，其每個元素又是一個定長的線性表。設(shè)二維數(shù)組A=(aij)mn，則

A=(α1，α2，…，αp)(p=m或n)其中每個數(shù)據(jù)元素αj是一個列向量(線性表)：

αj=(a1j，a2j，…，amj)1≦j≦n或是一個行向量：

αi=(ai1，ai2，…，ain)1≦i≦m如圖5-1所示。5a11a12…a1na21a22…a2n……………am1am2…amnA=……………A=a11a12…a1na21a22…a2nam1am2…amna11

a21┆

am1a12

a22┆am2a1n

a2n┆amn┆┆┆A=圖5-1

二維數(shù)組圖例形式(a)

矩陣表示形式(b)行向量的一維數(shù)組形式(c)列向量的一維數(shù)組形式6n維數(shù)組的特點每個數(shù)據(jù)元素都受著n個關(guān)系的約束；在每個關(guān)系中，元素(0<=ji<=bi-2)都有一個直接后繼;數(shù)據(jù)元素都必須屬于同一數(shù)據(jù)類型;n=1時，退化為定長的線性表；n維數(shù)組可以看成是線性表的推廣。數(shù)組一旦被定義，則維數(shù)已定，對于數(shù)組的操作只有存取元素和修改元素。(一旦建立了數(shù)組，數(shù)組中的元素個數(shù)和元素之間的關(guān)系就不再發(fā)生變動)數(shù)組是多維的結(jié)構(gòu)，而存儲空間是一個一維的結(jié)構(gòu)。（存儲時需要一個次序約定）75.1.2

數(shù)組的順序存儲結(jié)構(gòu)數(shù)組的實現(xiàn)機制a０的內(nèi)存單元地址每個元素所需的字節(jié)個數(shù)8行向量下標

i

頁向量下標

i列向量下標

j

行向量下標

j

列向量下標k二維數(shù)組

三維數(shù)組9數(shù)組的順序表示-小結(jié)n維數(shù)組的特點:數(shù)據(jù)元素同屬于一種數(shù)據(jù)類型；數(shù)組一旦被定義，則維數(shù)和各維長度不能改變；數(shù)組操作只有引用型操作，沒有加工型操作；數(shù)組是多維結(jié)構(gòu)，但存儲空間是一維結(jié)構(gòu)。數(shù)組順序表示的特點存儲單元地址連續(xù)（需要一段連續(xù)空間）存儲規(guī)則（以行（列）為主序）決定元素實際存儲位置隨機存取存儲密度最大（100%）105.2

矩陣的壓縮存儲

在科學與工程計算問題中，矩陣是一種常用的數(shù)學對象，在高級語言編程時，通常將一個矩陣描述為一個二維數(shù)組。這樣，可以對其元素進行隨機存取，各種矩陣運算也非常簡單。

對于高階矩陣，若其中非零元素呈某種規(guī)律分布或者矩陣中有大量的零元素，若仍然用常規(guī)方法存儲，可能存儲重復的非零元素或零元素，將造成存儲空間的大量浪費。對這類矩陣進行壓縮存儲：◆多個相同的非零元素只分配一個存儲空間；◆零元素不分配空間。115.2.1特殊矩陣的壓縮存儲1.對稱矩陣n階矩陣A中元素滿足性質(zhì)a[i][j]=a[j][i](1≤i,j≤n)。（即aij=aji,1<=i,j<=n）a11a21a22……aij……annLTA[0..n(n+1)/2-1]k=012……n(n+1)/2-11213k的含義：按行優(yōu)先，是第k個（從0開始）15675289683079041526837904i=3j=2k=4公式的推導（下三角）i=3，j=2則前面有一個i-1行的完整三角形，共有元素

(1+i-1)(i-1)/2=i(i-1)/2個另外，同一行，前面還有j-1個元素所以，k=i(i-1)/2+j-114/502、三角矩陣

以主對角線劃分，n階三角矩陣有n階上三角矩陣和n階下三角矩陣兩種。

n階上三角矩陣的下三角（不包括主對角線）中的元素均為0（或常數(shù)）。n階下三角矩陣正好相反，它的主對角線上方均為0（或常數(shù)）。

注：在大多數(shù)情況下，n階三角矩陣常數(shù)為零。

下三角矩陣元素aij保存在向量sa中時的下標值k與（i,j）之間的對應關(guān)系是：i(i-1)/2+j當i≧j時n(n+1)/2當i<j時K=1≦i,j≦n(5-5)155.2.2

稀疏矩陣的壓縮存儲稀疏矩陣：設(shè)m行n列的矩陣含t個非零元素，則δ=t/(m*n)稱為稀疏因子，通常認為

0.05的矩陣為稀疏矩陣。(1)、稀疏矩陣矩陣中非零元素的個數(shù)遠遠小于矩陣元素個數(shù)。(2)

、稠密矩陣

一個不稀疏的矩陣。(3)

、稀疏矩陣壓縮存儲方法只存儲稀疏矩陣中的非零元素，實現(xiàn)方法是:將每個非零元素用一個三元組（i，j，aij）來表示，則每個稀疏矩陣可用一個三元組線性表來表示。161、三元組順序表稀疏矩陣和對應的三元組線性表

若把稀疏矩陣的三元組線性表按順序存儲結(jié)構(gòu)存儲，則稱為稀疏矩陣的三元組順序表。17三元組表表示的稀疏矩陣轉(zhuǎn)置1818稀疏矩陣的轉(zhuǎn)置Tij=Mji01290000

00000-3000014002400001800000

0-30012

0001890024000

0

00018000001400566121213931-336144324521865613-3211225183193424631419稀疏矩陣用三元組表示的轉(zhuǎn)置行數(shù)和列數(shù)交換i、j的值相互交換重排三元組之間的次序566121213931-336144324521865613-32112251831934246314656211231913-363143424251820用三元組表示，求稀疏矩陣M的轉(zhuǎn)置矩陣TM566121213931-3361443245218T1.行數(shù)和列數(shù)交換，總個數(shù)不變:

T.m=M.n;T.n=M.m;T.t=M.t;2.讓q定位T中的第一條記錄:

q=1;656q21M566121213931-3361443245218T3.讓col取M的每一列:

for(col=1;col<=M.n;col++)

4.讓p掃描三元組M的每一條記錄:

for(p=1;p<=M.t;p++)656qcol=1p22M566121213931-3361443245218T656qcol=1p5.如果p指向的記錄的j下標與col相等:

if(M.data[p].j==col)ije23M566121213931-3361443245218T656qcol=1p6.把M中的記錄p復制到T中的記錄q:T.data[q].i=M.data[p].j;T.data[q].j=M.data[p].i;T.data[q].v=M.data[p].v;7.讓q下移:q++;13-324M566121213931-3361443245218T656qcol=2p13-32112251825M566121213931-3361443245218T656qcol=3p13-3211225183193424……26M566121213931-3361443245218T656qcol=6p13-3211225183193424631427（1）稀疏矩陣的轉(zhuǎn)置：“按需查找”法簡單算法的分析稀疏矩陣轉(zhuǎn)置算法復雜度=O(n*t)比較一般矩陣的轉(zhuǎn)置算法：其復雜度=O(m*n)如果t和m*n一個數(shù)量級，則稀疏矩陣轉(zhuǎn)置算法復雜度=O(m*n2)所以此算法只適用于t<<m*n時for(col=1;col<=nu;col++)for(row=1;row<=mu;row++)T[col][row]=M[row][col];28算法的實現(xiàn)附設(shè)兩個輔助向量num[]和cpot[]?！?/p>

num[col]：統(tǒng)計A中第col列中非0元素的個數(shù)；◆

cpot[col]：指示A中第一個非0元素在b.data中的恰當位置。數(shù)組num[col]：原矩陣第col列中，非零元素的個數(shù)數(shù)組cpot[col]：原矩陣第col列中，第1個非零元素在結(jié)果三元組表中的位置顯然有：cpot[1]=1cpot[col]=cpot[col-1]+num[col-1]（2）稀疏矩陣的轉(zhuǎn)置：“按位就坐”算法29ijv0566112122139331-3436145432465218ijv0656113-3221123251843195342466314col123456num[col]122001cpot[col]124666（2）稀疏矩陣的轉(zhuǎn)置：“按位就坐”算法2.十字鏈表十字鏈表的定義

稀疏矩陣的每個非零元素用一個含五個域的結(jié)點表示:i:非零元素所在行;j:非零元素所在列

e:非零元素值;right域:鏈接同一行下一非零元素

down域:鏈接同一列下一非零元素；存儲結(jié)構(gòu)的C語言描述

typedefstructOLNode{inti,j;ElemTypee;StructOLNode*right,*down;}OLNode,*OLink;typedefstruct{OLink*rhead,*chead;intmu,nu,tu;}CrossLink;ijedownright結(jié)點結(jié)構(gòu)：30十字鏈表表示的稀疏矩陣舉例ijedownright結(jié)點結(jié)構(gòu)：稀疏矩陣M：M的十字鏈表：M.cheadM.rhead113145^^22-1^^^^312采用十字鏈表存儲稀疏矩陣，創(chuàng)建稀疏矩陣、稀疏矩陣的運算見教材P104－106315.3廣義表(GeneralLists)廣義表(列表):n(0)個表元素組成的有限序列，記作

LS=(a1,a2,…,an)表頭(head):n>0時,表的第一個表元素表尾(tail):其它表元素組成的表空表:n=0的廣義表。廣義表的特性：有長度：n有深度：廣義表中括號的重數(shù)可遞歸可共享表名表元素

表長非空列表表頭可是原子或列表,表尾必定是列表32廣義表的圖形表示1、A=(/)2、B=(e)3、C=(a,(b,c,d))4、D=(A，B，C)注：○：表□：原子335.3.1廣義表的定義GetHead(L):在廣義表L存在的條件下，取L的表頭。GetTail(L):在廣義表L存在的條件下，取L的表尾。舉例：1A=()

GetHead(A)=NULL,GetTail(A)=NULL2B=(e)

GetHead(B)=e,GetTail(B)=()3C=(a,(b,c,d))GetHead(C)=a,GetTail(C)=(b,c,d)

GetHead((b,c,d))=b,GetTail((b,c,d))=(c,d)

GetHead((c,d))=c,GetTail((c,d))=(d)4D=(A,B,C)GetHead(D)=A,GetTail(D)=(B,C)

GetHead((B,C))=B,GetTail((B,C))=(C)5E=(())

GetHead(B)=(),GetTail(B)=()345.3.2廣義表的存儲結(jié)構(gòu)采用鏈式存儲結(jié)構(gòu)，元素包括原子和子表，結(jié)點結(jié)構(gòu)：表結(jié)點：表示列表原子結(jié)點：表示原子1、廣義表的頭尾鏈表存儲表示：

typedefenum{ATOM,LIST}ElemTag;//ATOM=0:原子,LIST=1:子表

typedefstructGLNode{ElemTagtag;//公共部分，用來區(qū)分原子結(jié)點和表結(jié)點

Union{//原子結(jié)點和表結(jié)點的聯(lián)合部分

AtomTypeatom;Struct{structGLNode*hp,*tp;}ptr;//hp指向表頭,tp指向表尾

};}*Glist;tag=1hptptag=0atom35A=(/)B=(e)C=(a,(b,c,d))D=(A，B，C)E=(a，E)5.5廣義表的存儲結(jié)構(gòu)示例B0e1^C11^0a111^0b0d0cD1^11^E11^0aA=NIL表結(jié)點：原子結(jié)點：tag=1hptptag=0atom365.5廣義表的存儲結(jié)構(gòu)示例對廣義表：C=(a,(b,c,d))，其頭尾鏈表為：1C0a1^10b10c1^0d372、廣義表的擴展線性鏈表存儲表示：

typedefenum{ATOM,LIST}ElemTag;//ATOM==0:原子，LIST==1：子表

typedefstructGLNode{ElemTagtag;//公共部分，用來區(qū)分原子結(jié)點和表結(jié)點

Union{//原子結(jié)點和表結(jié)點的聯(lián)合部分

AtomTypeatom;//原子結(jié)點的值域

StructGLNode*hp//表結(jié)點的頭指針

};GLNode*tp;//指向下一個結(jié)點

}*Glist;38廣義表的另一種存儲結(jié)構(gòu)示例A=(/)B=(e)C=(a,(b,c,d))D=(A，B，C)E=(a，E)CABD0e1^1^1^0a0b0c0d^1^1^^^E11^0a1^11^tag=1hptptag=0atomtp表結(jié)點：原子結(jié)點：3940/505.3.3廣義表的基本操作與實現(xiàn)

下面討論頭鏈和尾鏈存儲結(jié)構(gòu)下和原子和子表存儲結(jié)構(gòu)下一些典型操作的算法實現(xiàn)。//---廣義表的頭尾鏈表存儲表示typedefenum{ATOM,LIST}ElemTag;//ATOM==0原子，LIST==1子表typedefstructGLNode{ElemTagtag;//公共部分，用于區(qū)分原子結(jié)點和表結(jié)點

union{AtomTypeatom;//atom是原子結(jié)點的值域

struct{structGLNode*hp,*tp;}ptr;//ptr是表結(jié)點的指針域，ptr.hp和ptr.tp分別指向表頭和表尾

};}*GList;//廣義表類型41/50第五章數(shù)組和廣義表1、求廣義表深度算法

廣義表的深度是廣義表中所有原子數(shù)據(jù)元素到達根結(jié)點的最大值。intGListDepth(GListLS){//采用頭尾鏈表存儲結(jié)構(gòu)，求廣義表L的深度

if(!L)return1;//空表深度為1if(L->tag==ATOM)return0;//原子深度為0for(max=0,pp=L;pp;pp=pp->ptr.tp){//求以pp->ptr.hp為頭指針的子表深度

dep=GListDepth(pp->ptr.hp);if(dep>max)max=dep;}returnmax+1;}//GListDepth42/50第五章數(shù)組和廣義表2、求廣義表的長度算法

在頭鏈和尾鏈存儲結(jié)構(gòu)中，廣義表的長度就是表尾指針構(gòu)成的單鏈表的長