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

數(shù)據(jù)結(jié)構(gòu)5.1數(shù)組的定義和運算第5章數(shù)組和廣義表5.2數(shù)組的順序存儲和實現(xiàn)5.3特殊矩陣的壓縮存儲5.4廣義表1數(shù)據(jù)結(jié)構(gòu)5.1數(shù)組的定義和運算定義第5章數(shù)組和廣義表mnmmnnnmAa....aa................a....aaa....aa212222111211=×nm×也可以看成是m個行向量可以看成是個列向量n可看成是一種特殊的線性表，其特殊在于表中的數(shù)據(jù)元素本身也是一個線性表。數(shù)組是一組有固定個數(shù)的元素的集合。2數(shù)據(jù)結(jié)構(gòu)5.1數(shù)組的定義和運算抽象數(shù)據(jù)類型定義第5章數(shù)組和廣義表ADTArray{}ADTArray數(shù)據(jù)對象：D={aj1j2…jn|n>0,稱為數(shù)組的維數(shù)，ji是數(shù)組的第i維下標，1≤ji≤bi,bi為數(shù)組第i維的長度，aj1j2…jn∈ElementSet}數(shù)據(jù)關(guān)系：R={R1,R2,…,Rn}Ri={<aj1…ji…jn,aj1…ji+1…jn

>|1≤jk≤bk,1≤k≤n,且k≠i,1≤ji≤bi-1,aj1…ji…jn,aj1…ji+1…jn∈D,i=1,…,n

}基本操作：1.InitArray(A,n,bond1,…,bondn)2.Destroy(A)3.GetValue(A,e,index1,…,indexn)4.SetValue(A,e,index1,…,indexn)3數(shù)據(jù)結(jié)構(gòu)5.2數(shù)組的順序存儲和實現(xiàn)類型特點:第5章數(shù)組和廣義表1）不考慮插入和刪除操作；2）數(shù)組是多維的結(jié)構(gòu)，而存儲空間是一個一維的結(jié)構(gòu)。4數(shù)據(jù)結(jié)構(gòu)5.1數(shù)組的定義和運算運算第5章數(shù)組和廣義表獲得特定位置的元素值；修改特定位置的元素值。主要操作是數(shù)據(jù)元素的定位，即給定元素的下標，得到該元素在計算機中的存放位置。其本質(zhì)是地址計算問題。有兩種順序映象的方式:以行序為主序；以列序為主序。5數(shù)據(jù)結(jié)構(gòu)5.2數(shù)組的順序存儲和實現(xiàn)以行序為主序第5章數(shù)組和廣義表例如：

a1,2a1,1a1,3a2,1a2,2a2,3a1,2a1,1a1,3a2,1a2,2a2,3L二維數(shù)組Amxn中任一元素ai,j的存儲位置

LOC(i,j)=LOC(1,1)+(n×(i-1)＋(j-1))×稱為基地址或基址。

L6數(shù)據(jù)結(jié)構(gòu)5.2數(shù)組的順序存儲和實現(xiàn)第5章數(shù)組和廣義表推廣到一般情況，可得到n維數(shù)組數(shù)據(jù)元素存儲位置的映象關(guān)系：Loc(A[j1][j2]…[jn]=Loc(A[c1][c2]…[cn])+αi×(ji-ci),1≤i≤n∑ni=1其中：αi=size×(dk-ck+1),1≤i≤n)∏nk=i+19數(shù)據(jù)結(jié)構(gòu)5.2數(shù)組的順序存儲和實現(xiàn)第5章數(shù)組和廣義表例如：

設(shè)有二維數(shù)組A[10][20]，其每個元素占2個字節(jié)，第一個元素A1,1的存儲地址為100，則按行優(yōu)先順序存儲時元素A6,6的存儲地址為?若按列優(yōu)先順序存儲時元素A6,6的存儲地址為?A6,6=100+[(6-1)*20+(6-1)]*2=310按行優(yōu)先按列優(yōu)先A6,6=100+[((6-1)*10+(6-1)]*2=21010數(shù)據(jù)結(jié)構(gòu)5.3特殊矩陣的壓縮存儲第5章數(shù)組和廣義表特殊矩陣①三角矩陣②帶狀矩陣稀疏矩陣①三元組順序表②十字鏈表11數(shù)據(jù)結(jié)構(gòu)5.3特殊矩陣的壓縮存儲第5章數(shù)組和廣義表特殊矩陣：①三角矩陣下三角矩陣nnnnncccccccccaaaaaaaaaa………………321333231222111LOC(i,j)=LOC(1,1)

+

前i-1行非零元素個數(shù)＋第i行中aij前非零元素的個數(shù)=LOC(1,1)+

i(i-1)/2+j-112數(shù)據(jù)結(jié)構(gòu)5.3特殊矩陣的壓縮存儲第5章數(shù)組和廣義表特殊矩陣：①三角矩陣上三角矩陣LOC(i,j)=LOC(1,1)

+

前i-1行非零元素個數(shù)＋第i行中aij前非零元素的個數(shù)=LOC(1,1)+(i-1)(2n-i+2)/2+j-i

nnnnccccc0aaaaaaaaaa...........................333223221131211n13數(shù)據(jù)結(jié)構(gòu)5.3特殊矩陣的壓縮存儲第5章數(shù)組和廣義表特殊矩陣：②帶狀矩陣LOC(i,j)=LOC(1,1)

+3(i-1)-1+j-i+1=LOC(1,1)+2(i-1)+j-1nn×..................4544433433322322211211aaaaaaaaaaa14數(shù)據(jù)結(jié)構(gòu)5.3特殊矩陣的壓縮存儲第5章數(shù)組和廣義表稀殊矩陣：稀疏因子：設(shè)在m*n的矩陣中，有t個非零元素，令稱

為矩陣的稀疏因子。通常認為<=0.3時為稀疏矩陣。nmt×=d15數(shù)據(jù)結(jié)構(gòu)5.3特殊矩陣的壓縮存儲第5章數(shù)組和廣義表稀殊矩陣：①三元組順序表三元組也是采取按行進行存儲！

30000000000–4005200000006010007

jvi11332-435541254661165716數(shù)據(jù)結(jié)構(gòu)5.3特殊矩陣的壓縮存儲第5章數(shù)組和廣義表稀殊矩陣：①三元組順序表數(shù)據(jù)類型定義#defineMAXSIZE1000typedefstruct{introw,col; ElementTypee; }Triple;typedefstruct{Triple

data[MAXSIZE+1]; intm,n,len; }TSMatrix;17數(shù)據(jù)結(jié)構(gòu)5.3特殊矩陣的壓縮存儲第5章數(shù)組和廣義表稀殊矩陣：①三元組順序表的轉(zhuǎn)置運算--028003600070500140--005280000007143600for(row=1;row<=m;++row)for(col=1;col<=n;++col)

dest[col][row]=source[row][col];其時間復(fù)雜度為:

O(m×n)用常規(guī)的二維數(shù)組表示時的算法18數(shù)據(jù)結(jié)構(gòu)5.3特殊矩陣的壓縮存儲第5章數(shù)組和廣義表稀殊矩陣：①三元組順序表的轉(zhuǎn)置運算--028003600070500140--005280000007143600不是按行序有序存儲!重新排序121422-73136342815-5ijv211422-71336432851-5ijv19數(shù)據(jù)結(jié)構(gòu)5.3特殊矩陣的壓縮存儲第5章數(shù)組和廣義表稀殊矩陣：①三元組順序表的轉(zhuǎn)置運算重排三元組之間的次序有兩種方法：

按照A的列序進行轉(zhuǎn)置；按照A的行序轉(zhuǎn)置，但轉(zhuǎn)置后的元素按B的行序直接填到向量B.data中恰當(dāng)?shù)奈恢谩?0數(shù)據(jù)結(jié)構(gòu)5.3特殊矩陣的壓縮存儲第5章數(shù)組和廣義表稀殊矩陣：①三元組順序表的轉(zhuǎn)置運算“列序”遞增轉(zhuǎn)置法

算法實現(xiàn)

voidTransposeTSMatrix(TSMatrixA,TSMatrix*B){inti,j,k;B->m=A.n;B->n=A.m;B->len=A.len;if(B->len>0){ j=1;

for(k=1;k<=A.n;k++)

for(i=1;i<=A.len;i++)

if(A.data[i].col==k) {B->data[j].row=A.data[i].col; B->data[j].col=A.data[i].row; B->data[j].e=A.data[i].e;

j++;

}

}}{

if(j>A.len)break;}21數(shù)據(jù)結(jié)構(gòu)

voidTransposeTSMatrix(TSMatrixA,TSMatrix*B){inti,j,min;B->m=A.n;B->n=A.m;B->len=A.len;

i=1; while(i<=A.len) {min=1; for(j=2;j<=A.len;j++) if(A.data[j].col<A.data[min].col)min=j;

B->data[i].row=A.data[min].col; B->data[i].col=A.data[min].row; B->data[i].e=A.data[min].e;

i++;

A.data[min].col=A.n+1; }}22數(shù)據(jù)結(jié)構(gòu)5.3特殊矩陣的壓縮存儲第5章數(shù)組和廣義表稀殊矩陣：①三元組順序表的轉(zhuǎn)置運算M第j列在轉(zhuǎn)置后，形成轉(zhuǎn)置矩陣T的第j行。設(shè)M的第j列有k個非零元素，如圖所示·····r1,j,v1·····r2,j,v2·····rk,j,vk·····M··········j,r1,v1j,r2,v2·····j,rk,vk·····T一次定位快速轉(zhuǎn)置23數(shù)據(jù)結(jié)構(gòu)5.3特殊矩陣的壓縮存儲第5章數(shù)組和廣義表稀殊矩陣：①三元組順序表的轉(zhuǎn)置運算--028003600070500140--005280000007143600121421-73136332815-5ijvijv1336211412-7332851-524數(shù)據(jù)結(jié)構(gòu)5.3特殊矩陣的壓縮存儲第5章數(shù)組和廣義表稀殊矩陣：①三元組順序表的轉(zhuǎn)置運算一次定位快速轉(zhuǎn)置算法步驟：a.掃描矩陣A的三元組表，統(tǒng)計出A的每一列的非零元素的個數(shù)，存放到數(shù)組num[col]中（num[col]存放M第col列的非零元素個數(shù)）。b.計算轉(zhuǎn)置矩陣B的每一行在三元組表中的開始位置，并存放到數(shù)組position[col]中，（position[col]存放T第col行開始位置）。c.再次掃描矩陣A的三元組表，根據(jù)非零元素的列號col，確定它轉(zhuǎn)置后的行號，查position表，按查到的位置直接將該項存入轉(zhuǎn)置三元組表B中,并修改position[col],將其指向該行下一個元素的存儲位置(position[col]++

)。25數(shù)據(jù)結(jié)構(gòu)5.3特殊矩陣的壓縮存儲第5章數(shù)組和廣義表稀殊矩陣：①三元組順序表的轉(zhuǎn)置運算一次定位快速轉(zhuǎn)置算法實現(xiàn)：a.for(col=1;col<=A.n;col++)num[col]=0; for(t=1;t<=A.len;t++)

num[A.data[t].col]++;

121422-73136342815-5ijvcol12345num[col]000001121126數(shù)據(jù)結(jié)構(gòu)5.3特殊矩陣的壓縮存儲第5章數(shù)組和廣義表稀殊矩陣：①三元組順序表的轉(zhuǎn)置運算一次定位快速轉(zhuǎn)置算法實現(xiàn)：b.position[1]=1;for(col=2;col<=A.n;col++)position[col]=position[col-1]+num[col-1];

col12345num[col]0000011211position[col]12445121422-73136342815-5ijvijv211422-71336432851-527數(shù)據(jù)結(jié)構(gòu)5.3特殊矩陣的壓縮存儲第5章數(shù)組和廣義表稀殊矩陣：①三元組順序表的轉(zhuǎn)置運算一次定位快速轉(zhuǎn)置算法實現(xiàn)：for(p=1;p<=A.len;p++){

col=A.data[p].col;q=position[col];B->data[q].row=A.data[p].col;B->data[q].col=A.data[p].row;B->data[q].e=A.data[p].e;

position[col]++;}col12345num[col]0000011211position[col]12445121422-73136342815-5ijvijv2114351-522-7413362432865完整P13528數(shù)據(jù)結(jié)構(gòu)5.3特殊矩陣的壓縮存儲第5章數(shù)組和廣義表稀殊矩陣：①三元組順序表的轉(zhuǎn)置運算一次定位快速轉(zhuǎn)置算法實現(xiàn)：該算法的總的循環(huán)次數(shù)為：A.n+A.len+A.n-1+A.len=2(A.n+A.len)-1時間復(fù)雜度為：O(A.n+A.len)即使非零元個數(shù)A.len與A.m*A.n同數(shù)量級，其時間復(fù)雜度為O(A.m*A.n)，與經(jīng)典算法時間復(fù)雜度相同。29數(shù)據(jù)結(jié)構(gòu)5.3特殊矩陣的壓縮存儲第5章數(shù)組和廣義表稀殊矩陣：②十字鏈表的存儲表示一個結(jié)點除了數(shù)據(jù)域(i,j,elem)之外，還應(yīng)該用兩個方向的指針（right,down)，分別指向行和列。right：用于鏈接同一行中的下一個元素；down：用于鏈接同一列中的下一個元素。整個矩陣構(gòu)成了一個十字交叉的鏈表，因此稱十字鏈表。rowcolvaluedownright每一行和每一列的頭指針，用兩個一維指針數(shù)組來存放。30數(shù)據(jù)結(jié)構(gòu)5.3特殊矩陣的壓縮存儲第5章數(shù)組和廣義表稀殊矩陣：②十字鏈表的類型定義typedefstructOLNode{introw,col;intvalue;structOLNode*right,*down;}OLNode,*OLink;typedefstruct{ OLink*row_head,*col_head; intm,n,len; }CrossList;rowcolvaluerightdown31數(shù)據(jù)結(jié)構(gòu)5.3特殊矩陣的壓縮存儲第5章數(shù)組和廣義表稀殊矩陣：②十字鏈表的舉例rowcolvaluedownright-300-50-1008007M=11-314522-1∧∧318∧∧347∧∧32數(shù)據(jù)結(jié)構(gòu)5.4廣義表第5章數(shù)組和廣義表概念：是n>=0個元素的有限序列，記作

LS=(d1,d2,

,dn)其中：di或為原子項(原子，一般用小寫字母表示)或為廣義表(子表，一般用大寫字母表示)，n為廣義表的長度。原子：是作為結(jié)構(gòu)上不可分割的成分，它可以是一個數(shù)或一個結(jié)構(gòu)。表頭與表尾：LS不為空時，稱d1為表頭(head)，稱其余元素組成的子表(d2,d3，

,dn)為表尾(tail)。33數(shù)據(jù)結(jié)構(gòu)5.4廣義表第5章數(shù)組和廣義表舉例：1） A=()2） F=(d,(e))n=3） D=((a,(b,c)),F)4） C=(A,D,F)5） B=(a,B)=(a,(a,(a,

,)))n=2n=n=head(F)=head(D)=tail(D)=head(C)=head(B)=tail(F)=0d((e))2(a,(bc))(F)3Atail(C)=(D,F)atail(B)=(B)任何一個非空廣義表其表頭可能是原子或廣義表，而其表尾必定為廣義表。34數(shù)據(jù)結(jié)構(gòu)5.4廣義表第5章數(shù)組和廣義表結(jié)構(gòu)特點：1）廣義表中的數(shù)據(jù)元素有相對次序；2）廣義表的長度定義為最外層包含元素個數(shù)；3）廣義表的深度定義為所含括弧的重數(shù)；4）廣義表可以共享；5）廣義表可以是一個遞歸的表。遞歸表的深度是無窮值，長度是有限值。注意：“原子”的深度為0“空表”的深度為135數(shù)據(jù)結(jié)構(gòu)5.4廣義表第5章數(shù)組和廣義表存儲方式：由于廣義表(a1,a2,a3,…an)中的數(shù)據(jù)元素可以具有不同的結(jié)構(gòu)，（或是原子，或是廣義表），因此，難以用順序存儲結(jié)構(gòu)表示，通常采用鏈式存儲結(jié)構(gòu)來表示。①頭、尾鏈表存儲結(jié)構(gòu)；②擴展線性鏈表存儲結(jié)構(gòu)。36數(shù)據(jù)結(jié)構(gòu)5.4廣義表第5章數(shù)組和廣義表存儲方式：①

頭、尾鏈表存儲結(jié)構(gòu)每個元素用一個結(jié)點表示,需要用兩種結(jié)構(gòu)的結(jié)點:表結(jié)點原子結(jié)點標志域表頭指針表尾指針tag=1hptp標志域值域tag=0atomtypedefenum{ATOM,LIST}ElemTag;typedefstructGLNode{ElemTagtag;union{ AtomTypeatom; struct {structGLNode*hp,*tp; }htp;}atom_htp;}GLNode,*GList;37數(shù)據(jù)結(jié)構(gòu)5.4廣義表第5章數(shù)組和廣義表存儲方式：①

頭、尾鏈表存儲結(jié)構(gòu)分析方法：表頭、表尾分析若表頭為原子，則用原子結(jié)點:空表L=NIL(L為頭指針)非空表L指向表頭指向表尾否則用表結(jié)點;表尾總是用表結(jié)點或空;子表結(jié)構(gòu)依次類推。tag=1tag=0atom38數(shù)據(jù)結(jié)構(gòu)5.4廣義表第5章數(shù)組和廣義表存儲方式：①

頭、尾鏈表存儲結(jié)構(gòu)分析方法：表頭、表尾分析例如:A=()B=(e)C=(a,(b,c,d))D=(A,