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

關(guān)于數(shù)據(jù)結(jié)構(gòu)數(shù)組與廣義表第一頁(yè)，共四十六頁(yè)，2022年，8月28日第五章數(shù)組和廣義表本章前討論的線性結(jié)構(gòu)數(shù)據(jù)元素都是非結(jié)構(gòu)的原子類型，元素值不可再分。本章討論了兩種數(shù)據(jù)結(jié)構(gòu)—數(shù)組和廣義表。作為線性表的擴(kuò)展，表中的數(shù)據(jù)元素也是一種數(shù)據(jù)結(jié)構(gòu)。數(shù)組這種數(shù)據(jù)結(jié)構(gòu)可以看成是線性表的推廣。廣義表是另一種推廣形式的線性表，是一種靈活的數(shù)據(jù)結(jié)構(gòu)，在許多方面有廣泛的應(yīng)用。第二頁(yè)，共四十六頁(yè)，2022年，8月28日2知識(shí)結(jié)構(gòu)圖數(shù)組與廣義表數(shù)組廣義表類型定義表示方法稀疏矩陣特殊矩陣存儲(chǔ)結(jié)構(gòu)邏輯結(jié)構(gòu)

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

…

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

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

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

αi=(ai1，ai2，…，ain)1≦i≦m如圖5-1所示。第五頁(yè)，共四十六頁(yè)，2022年，8月28日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ù)組形式第六頁(yè)，共四十六頁(yè)，2022年，8月28日6n維數(shù)組的特點(diǎn)每個(gè)數(shù)據(jù)元素都受著n個(gè)關(guān)系的約束；在每個(gè)關(guān)系中，元素(0<=ji<=bi-2)都有一個(gè)直接后繼;數(shù)據(jù)元素都必須屬于同一數(shù)據(jù)類型;n=1時(shí)，退化為定長(zhǎng)的線性表；n維數(shù)組可以看成是線性表的推廣。數(shù)組一旦被定義，則維數(shù)已定，對(duì)于數(shù)組的操作只有存取元素和修改元素。(一旦建立了數(shù)組，數(shù)組中的元素個(gè)數(shù)和元素之間的關(guān)系就不再發(fā)生變動(dòng))數(shù)組是多維的結(jié)構(gòu)，而存儲(chǔ)空間是一個(gè)一維的結(jié)構(gòu)。（存儲(chǔ)時(shí)需要一個(gè)次序約定）第七頁(yè)，共四十六頁(yè)，2022年，8月28日7

數(shù)組的順序存儲(chǔ)結(jié)構(gòu)數(shù)組的實(shí)現(xiàn)機(jī)制a０的內(nèi)存單元地址每個(gè)元素所需的字節(jié)個(gè)數(shù)第八頁(yè)，共四十六頁(yè)，2022年，8月28日8行向量下標(biāo)

i

頁(yè)向量下標(biāo)

i列向量下標(biāo)

j

行向量下標(biāo)

j

列向量下標(biāo)k二維數(shù)組三維數(shù)組第九頁(yè)，共四十六頁(yè)，2022年，8月28日9數(shù)組的順序表示-小結(jié)n維數(shù)組的特點(diǎn):數(shù)據(jù)元素同屬于一種數(shù)據(jù)類型；數(shù)組一旦被定義，則維數(shù)和各維長(zhǎng)度不能改變；數(shù)組操作只有引用型操作，沒有加工型操作；數(shù)組是多維結(jié)構(gòu)，但存儲(chǔ)空間是一維結(jié)構(gòu)。數(shù)組順序表示的特點(diǎn)存儲(chǔ)單元地址連續(xù)（需要一段連續(xù)空間）存儲(chǔ)規(guī)則（以行（列）為主序）決定元素實(shí)際存儲(chǔ)位置隨機(jī)存取存儲(chǔ)密度最大（100%）第十頁(yè)，共四十六頁(yè)，2022年，8月28日105.2

矩陣的壓縮存儲(chǔ)

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

對(duì)于高階矩陣，若其中非零元素呈某種規(guī)律分布或者矩陣中有大量的零元素，若仍然用常規(guī)方法存儲(chǔ)，可能存儲(chǔ)重復(fù)的非零元素或零元素，將造成存儲(chǔ)空間的大量浪費(fèi)。對(duì)這類矩陣進(jìn)行壓縮存儲(chǔ)：◆多個(gè)相同的非零元素只分配一個(gè)存儲(chǔ)空間；◆零元素不分配空間。第十一頁(yè)，共四十六頁(yè)，2022年，8月28日115.2.1特殊矩陣的壓縮存儲(chǔ)1.對(duì)稱矩陣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-1第十二頁(yè)，共四十六頁(yè)，2022年，8月28日12k的含義：按行優(yōu)先，是第k個(gè)（從0開始）15675289683079041526837904i=3j=2k=4公式的推導(dǎo)（下三角）i=3，j=2則前面有一個(gè)i-1行的完整三角形，共有元素

(1+i-1)(i-1)/2=i(i-1)/2個(gè)另外，同一行，前面還有j-1個(gè)元素所以，k=i(i-1)/2+j-1第十三頁(yè)，共四十六頁(yè)，2022年，8月28日132、三角矩陣

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

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

注：在大多數(shù)情況下，n階三角矩陣常數(shù)為零。第十四頁(yè)，共四十六頁(yè)，2022年，8月28日14

下三角矩陣元素aij保存在向量sa中時(shí)的下標(biāo)值k與（i,j）之間的對(duì)應(yīng)關(guān)系是：i(i-1)/2+j當(dāng)i≧j時(shí)n(n+1)/2當(dāng)i<j時(shí)K=1≦i,j≦n(5-5)第十五頁(yè)，共四十六頁(yè)，2022年，8月28日15

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

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

、稠密矩陣

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

、稀疏矩陣壓縮存儲(chǔ)方法只存儲(chǔ)稀疏矩陣中的非零元素，實(shí)現(xiàn)方法是:將每個(gè)非零元素用一個(gè)三元組（i，j，aij）來(lái)表示，則每個(gè)稀疏矩陣可用一個(gè)三元組線性表來(lái)表示。第十六頁(yè)，共四十六頁(yè)，2022年，8月28日161、三元組順序表稀疏矩陣和對(duì)應(yīng)的三元組線性表

若把稀疏矩陣的三元組線性表按順序存儲(chǔ)結(jié)構(gòu)存儲(chǔ)，則稱為稀疏矩陣的三元組順序表。第十七頁(yè)，共四十六頁(yè)，2022年，8月28日17三元組表表示的稀疏矩陣轉(zhuǎn)置18稀疏矩陣的轉(zhuǎn)置Tij=Mji01290000

00000-3000014002400001800000

0-30012

0001890024000

0

00018000001400566121213931-336144324521865613-32112251831934246314第十八頁(yè)，共四十六頁(yè)，2022年，8月28日18稀疏矩陣用三元組表示的轉(zhuǎn)置行數(shù)和列數(shù)交換i、j的值相互交換重排三元組之間的次序566121213931-336144324521865613-32112251831934246314656211231913-3631434242518第十九頁(yè)，共四十六頁(yè)，2022年，8月28日19用三元組表示，求稀疏矩陣M的轉(zhuǎn)置矩陣TM566121213931-3361443245218T1.行數(shù)和列數(shù)交換，總個(gè)數(shù)不變:

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

q=1;656q第二十頁(yè)，共四十六頁(yè)，2022年，8月28日20M566121213931-3361443245218T3.讓col取M的每一列:

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

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

for(p=1;p<=M.t;p++)656qcol=1p第二十一頁(yè)，共四十六頁(yè)，2022年，8月28日21M566121213931-3361443245218T656qcol=1p5.如果p指向的記錄的j下標(biāo)與col相等:

if(M.data[p].j==col)ije第二十二頁(yè)，共四十六頁(yè)，2022年，8月28日22M566121213931-3361443245218T656qcol=1p6.把M中的記錄p復(fù)制到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-3第二十三頁(yè)，共四十六頁(yè)，2022年，8月28日23M566121213931-3361443245218T656qcol=2p13-321122518第二十四頁(yè)，共四十六頁(yè)，2022年，8月28日24M566121213931-3361443245218T656qcol=3p13-3211225183193424……第二十五頁(yè)，共四十六頁(yè)，2022年，8月28日25M566121213931-3361443245218T656qcol=6p13-32112251831934246314第二十六頁(yè)，共四十六頁(yè)，2022年，8月28日26（1）稀疏矩陣的轉(zhuǎn)置：“按需查找”法簡(jiǎn)單算法的分析稀疏矩陣轉(zhuǎn)置算法復(fù)雜度=O(n*t)比較一般矩陣的轉(zhuǎn)置算法：其復(fù)雜度=O(m*n)如果t和m*n一個(gè)數(shù)量級(jí)，則稀疏矩陣轉(zhuǎn)置算法復(fù)雜度=O(m*n2)所以此算法只適用于t<<m*n時(shí)for(col=1;col<=nu;col++)for(row=1;row<=mu;row++)T[col][row]=M[row][col];第二十七頁(yè)，共四十六頁(yè)，2022年，8月28日27算法的實(shí)現(xiàn)附設(shè)兩個(gè)輔助向量num[]和cpot[]。◆

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

cpot[col]：指示A中第一個(gè)非0元素在b.data中的恰當(dāng)位置。數(shù)組num[col]：原矩陣第col列中，非零元素的個(gè)數(shù)數(shù)組cpot[col]：原矩陣第col列中，第1個(gè)非零元素在結(jié)果三元組表中的位置顯然有：cpot[1]=1cpot[col]=cpot[col-1]+num[col-1]（2）稀疏矩陣的轉(zhuǎn)置：“按位就坐”算法第二十八頁(yè)，共四十六頁(yè)，2022年，8月28日28ijv0566112122139331-3436145432465218ijv0656113-3221123251843195342466314col123456num[col]122001cpot[col]124666（2）稀疏矩陣的轉(zhuǎn)置：“按位就坐”算法第二十九頁(yè)，共四十六頁(yè)，2022年，8月28日292.十字鏈表十字鏈表的定義

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

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

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

typedefstructOLNode{inti,j;ElemTypee;StructOLNode*right,*down;}OLNode,*OLink;typedefstruct{OLink*rhead,*chead;intmu,nu,tu;}CrossLink;ijedownright結(jié)點(diǎn)結(jié)構(gòu)：第三十頁(yè)，共四十六頁(yè)，2022年，8月28日30十字鏈表表示的稀疏矩陣舉例ijedownright結(jié)點(diǎn)結(jié)構(gòu)：稀疏矩陣M：M的十字鏈表：M.cheadM.rhead113145^^22-1^^^^312采用十字鏈表存儲(chǔ)稀疏矩陣，創(chuàng)建稀疏矩陣、稀疏矩陣的運(yùn)算見教材P104－106第三十一頁(yè)，共四十六頁(yè)，2022年，8月28日315.3廣義表(GeneralLists)廣義表(列表):n(0)個(gè)表元素組成的有限序列，記作

LS=(a1,a2,…,an)表頭(head):n>0時(shí),表的第一個(gè)表元素表尾(tail):其它表元素組成的表空表:n=0的廣義表。廣義表的特性：有長(zhǎng)度：n有深度：廣義表中括號(hào)的重?cái)?shù)可遞歸可共享表名表元素

表長(zhǎng)非空列表表頭可是原子或列表,表尾必定是列表第三十二頁(yè)，共四十六頁(yè)，2022年，8月28日32廣義表的圖形表示1、A=(/)2、B=(e)3、C=(a,(b,c,d))4、D=(A，B，C)注：○：表□：原子第三十三頁(yè)，共四十六頁(yè)，2022年，8月28日33廣義表的定義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)=()第三十四頁(yè)，共四十六頁(yè)，2022年，8月28日345.3.2廣義表的存儲(chǔ)結(jié)構(gòu)采用鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)，元素包括原子和子表，結(jié)點(diǎn)結(jié)構(gòu)：表結(jié)點(diǎn)：表示列表原子結(jié)點(diǎn)：表示原子1、廣義表的頭尾鏈表存儲(chǔ)表示：

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

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

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

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

};}*Glist;tag=1hptptag=0atom第三十五頁(yè)，共四十六頁(yè)，2022年，8月28日35A=(/)B=(e)C=(a,(b,c,d))D=(A，B，C)E=(a，E)5.5廣義表的存儲(chǔ)結(jié)構(gòu)示例B0e1^C11^0a111^0b0d0cD1^11^E11^0aA=NIL表結(jié)點(diǎn)：原子結(jié)點(diǎn)：tag=1hptptag=0atom第三十六頁(yè)，共四十六頁(yè)，2022年，8月28日365.5廣義表的存儲(chǔ)結(jié)構(gòu)示例對(duì)廣義表：C=(a,(b,c,d))，其頭尾鏈表為：1C0a1^10b10c1^0d第三十七頁(yè)，共四十六頁(yè)，2022年，8月28日372、廣義表的擴(kuò)展線性鏈表存儲(chǔ)表示：

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

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

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

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

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

};GLNode*tp;//指向下一個(gè)結(jié)點(diǎn)

}*Glist;第三十八頁(yè)，共四十六頁(yè)，2022年，8月28日38廣義表的另一種存儲(chǔ)結(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é)點(diǎn)：原子結(jié)點(diǎn)：第三十九頁(yè)，共四十六頁(yè)，2022年，8月28日395.3.3廣義表的基本操作與實(shí)現(xiàn)

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

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

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

};}*GList;//廣義表類型第四十頁(yè)，共四十六頁(yè)，2022年，8月28日40第五章數(shù)組和廣義表1、求廣義表深度算法

廣義表的深度是廣義表中所有原子數(shù)據(jù)元素到達(dá)根結(jié)點(diǎn)的最大值。intGListDepth(GListLS){//采用頭尾鏈表存儲(chǔ)結(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;}//GListDepth第四十一頁(yè)，共四十六頁(yè)，2022年，8月28日41第五章數(shù)組和廣義表2