數(shù)據(jù)結構實用課件第四章

第五章數(shù)組和廣義表第五章數(shù)組和廣義表1一維數(shù)組具有線性表的結構，但操作簡單，一般不進行插入和刪除操作，只定義給定下標讀取元素和修改元素的操作二維數(shù)組中，每個數(shù)據(jù)元素對應一對數(shù)組下標，在行方向上和列方向上都存在一個線性關系，即存在兩個前驅（前件）和兩個后繼（后件）。也可看作是以線性表為數(shù)據(jù)元素的線性表。n維數(shù)組中，每個數(shù)據(jù)元素對應n個下標，受n個關系的制約，其中任一個關系都是線性關系。可看作是數(shù)據(jù)元素為n-1維數(shù)組的一維數(shù)組。因此，多維數(shù)組和廣義表是對線性表的擴展：線性表中的數(shù)據(jù)元素本身又是一個多層次的線性表。一維數(shù)組具有線性表的結構，但操作簡單，一般不進行插入和刪除操25.1數(shù)組的定義5.2數(shù)組的順序表示和實現(xiàn)5.3矩陣的壓縮存儲5.1數(shù)組的定義35.1數(shù)組的定義ADTArray{數(shù)據(jù)對象：ji=0,…,bi-1,i=1,2,…,n,D={aj1j2…jn|n(>0)稱為數(shù)組的維數(shù)，bi是數(shù)組第i維的長度，ji是數(shù)組元素的第i維下標，aj1j2…jn∈ElemSet}數(shù)據(jù)關系：R={R1,R2,…,Rn} Ri={<aj1…ji…jn,aj1…ji+1…jn>|0≤jk≤bk-1,1≤k≤n且k≠i,0≤ji≤bi-2,aj1…ji…jn,aj1…ji+1…jn∈D,i=2,…n}5.1數(shù)組的定義ADTArray{4基本操作：InitArray(&A,n,bound1,…,boundn)DestroyArray(&A)Value(A,&e,index1,…,indexn)Assign(&A,e,index1,…,indexn)}ADTArray基本操作：55.2數(shù)組的順序表示多維數(shù)組用一維的存儲單元存放需約定次序。PASCAL和C語言是以行序為主序，F(xiàn)ORTRAN以列序為主序。給定維數(shù)和各維長度，數(shù)組的存儲空間確定。二維數(shù)組中任一元素aij的存儲地址:Loc(i,j)=Loc(0,0)+(b2*i+j)*Ln維數(shù)組：教材p93Loc（j1,j2,…,jn)=Loc(0,0,…,0)+∑ciji其中cn=L,ci-1=bi*ci,1<i≤n5.2數(shù)組的順序表示多維數(shù)組用一維的存儲單元存放需約定次序6類型定義#include<stdarg.h>#defineMAX_ARRAY_DIM8typedefstruct{ElemType*base;intdim;int*bounds;int*constants;}Array;類型定義#include<stdarg.h>75.3矩陣的壓縮存儲矩陣一般可用二維數(shù)組實現(xiàn)，特殊矩陣采用壓縮存儲。壓縮存儲：為多個值相同的元只分配一個存儲空間，對零元不分配空間。特殊矩陣：值相同的元素或者零元素在矩陣中的分布有一定規(guī)律稀疏矩陣：非零元較零元少，且分布沒有一定規(guī)律的矩陣5.3矩陣的壓縮存儲矩陣一般可用二維數(shù)組實現(xiàn)，特殊矩陣采用85.3.1.特殊矩陣對稱矩陣：aij=aji1≤i,j≤n壓縮存儲方法：為每一對對稱元分配一個存儲空間將下三角的元素，按行存儲到一維數(shù)組sa中共有n(n+1)/2個存儲單元，aij在一維數(shù)組中的位置k為：i(i-1)/2+j-1當i>=j否則j(j-1)/2+i-1三角矩陣：上（下）三角中的元均為常數(shù)c或0壓縮存儲方法：同上，只存儲上（下）三角元素。下三角：k=i*(i-1)/2+j-1上三角：k=(2n-i)(i-1)/2+j-1(按行)k=j(j-1)/2+i-1（按列）注意：k從零開始，i,j從1開始對角矩陣：所有非零元都集中在以主對角線為中心的帶狀區(qū)域中。壓縮方法：壓縮存儲到一維數(shù)組sa[]中，三對角矩陣有3n-2個元素。k=2*i+j-35.3.1.特殊矩陣對稱矩陣：aij=aji1≤95.3.2.稀疏矩陣1.三元組的表示稀疏矩陣可由表示非零元的三元組及其行列數(shù)唯一確定。t個非零元，t/(m*n)稱為稀疏因子<0.05用三元組(i,j,aij)存儲行和列的位置，及非零元數(shù)值。5.3.2.稀疏矩陣1.三元組的表示10（1）稀疏矩陣

(SparseMatrix)行數(shù)m=6,列數(shù)n=7,非零元素個數(shù)t=6

（1）稀疏矩陣(SparseMatrix)行數(shù)m=611稀疏矩陣轉置矩陣稀疏矩陣轉置矩陣12用三元組表表示的稀疏矩陣及其轉置用三元組表表示的稀疏矩陣及其轉置13（2）三元組順序表#defineMAXSIZE12500//非零元個數(shù)最大值typedefstruct{ inti,j;//行下標和列下標 ElemTypee;}Triple;typedefstruct{ Tripledata[MAXSIZE+1];//非零元三元組表 intmu,nu,tu;//行數(shù)、列數(shù)、非零元個數(shù)}TSMatrix;TSMatrixa,b;所需空間：3*tu+3若>mu*nu,則不必用三元組表示mu,nu,tu（2）三元組順序表#defineMAXSIZE125014(3)三元組表稀疏矩陣的轉置運算方法：按照b.data中的三元組的次序，即M的列序，依次在a.data中找到相應的三元組進行轉置。步驟：從k=1開始依次掃描找尋所有列號為k的項，將其行號變列號、列號變行號，順次存于轉置矩陣三元組表。其時間復雜度為O(a.nu*a.tu)。例：若矩陣有200行，200列，10,000個非零元素，總共有2,000,000次處理。(3)三元組表稀疏矩陣的轉置運算方法：按照b.data中的三15稀疏矩陣的轉置(算法5.1)

StatusTransposeSMatrix(TSMatrixM,TSMatrix&T){ intq,col,p; T.mu=M.nu; T.nu=M.mu; T.tu=M.tu; if(T.tu){q=1; for(col=1;col<=T.mu;++col) for(p=1;p<=M.tu;++p) if(M.data[p].j==col){ 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;}稀疏矩陣的轉置(算法5.1)16快速轉置算法方法：按a.data中三元組的次序進行轉置，并將轉置后的三元組置入b中恰當?shù)奈恢?。建立輔助數(shù)組num和cpot，num[col]表示矩陣第col列中非零元的個數(shù)，cpot[col]指示第col列的第一個非零元素在b.data中的恰當位置。按行掃描矩陣三元組表，根據(jù)某項的列號，確定它轉置后的行號，查cpot表，按查到的位置直接將該項存入轉置三元組表中。轉置時間復雜度為

O(nu+tu+nu+tu)=O(tu)。若矩陣有200列，10000個非零元素，總共需10000次處理?？焖俎D置算法方法：按a.data中三元組的次序進行轉置，并將17cpot[1]=1cpot[col]=cpot[col-1]+num[col-1]cpot[1]=118稀疏矩陣的快速轉置(算法5.2)StatusFastTransposeSMatrix(TSMatrixM,TSMatrix&T){T.mu=M.nu;T.nu=M.mu;T.tu=M.tu;if(T.tu){for(col=1;col<=M.nu;++col)num[col]=0; for(t=1;t<=M.tu;++t)++num[M.data[t].j]; cpot[1]=1; for(col=2;col<=M.nu;++col) cpot[col]=cpot[col-1]+num[col-1];for(p=1;p<=M.tu;++p){ col=M.data[p].j; q=cpot[col]; T.data[q].i=M.data[p].j; T.data[q].j=M.data[p].i; T.data[q].e=M.data[p].e; ++cpot[col];} }returnOK;}稀疏矩陣的快速轉置(算法5.2)192.十字鏈表當矩陣中非零元素的個數(shù)和位置經(jīng)過運算后變化較大時，就不宜采用順序存儲結構，而應采用鏈式存儲結構來表示三元組。稀疏矩陣的鏈接表示采用十字鏈表：行鏈表與列鏈表十字交叉。行鏈表與列鏈表都是帶表頭結點的循環(huán)鏈表。用表頭結點表征是第幾行，第幾列。2.十字鏈表當矩陣中非零元素的個數(shù)和位置經(jīng)過運算后變化較20元素結點right——指向同一行中下一個非零元素的指針（向右域）down——指向同一列中下一個非零元素的指針（向下域）表頭結點行表頭結點列表頭結點next用于表示頭結點的鏈接rowcolvaldownrightcol=0nextrightrow=0nextdown元素結點rowcolvaldownrightcol=0nex21由于行、列表頭結點互相不沖突，所以可以合并起來：總表頭結點：row=0col=0nextdownrightrowcolnext由于行、列表頭結點互相不沖突，所以可以合并起來：row=0c22類型定義：typedefstruct{ inti,j;//非零元的行下標和列下標 ElemTypee;}Triple;typedefstructOLNode{//元素結點 union{Tripletriple;OLNode*next}; structOLNode*right,*down;

//該非零元所在行表和列表的后繼鏈域}OLNode,*OLink;OLinkM；類型定義：23稀疏矩陣的十字鏈表表示的示例稀疏矩陣的十字鏈表表示的示例24需要輔助結點作鏈表的表頭，同時每個結點要增加兩個指針域，所以只有在矩陣較大和較稀疏時才能起到節(jié)省空間的效果。分別用兩個一維數(shù)組存儲行鏈表的頭指針和列鏈表的頭指針，可加快訪問速度。需要輔助結點作鏈表的表頭，同時每個結點要增加兩個指針域，所以25十字鏈表的類型定義typedefstructOLNode{//元素結點 inti,j;//非零元的行和列下標 ElemTypee; structOLNode*right,*down;

//該非零元所在行表和列表的后繼鏈域}OLNode,*OLink;typedefstruct{ OLink*rhead,*chead;//行和列鏈表頭指針數(shù)組 intmu,nu,tu;}CrossList;十字鏈表的類型定義typedefstructOLNode26十字鏈表的建立(算法5.4)自學十字鏈表的建立(算法5.4)自學27第五章數(shù)組和廣義表第五章數(shù)組和廣義表28一維數(shù)組具有線性表的結構，但操作簡單，一般不進行插入和刪除操作，只定義給定下標讀取元素和修改元素的操作二維數(shù)組中，每個數(shù)據(jù)元素對應一對數(shù)組下標，在行方向上和列方向上都存在一個線性關系，即存在兩個前驅（前件）和兩個后繼（后件）。也可看作是以線性表為數(shù)據(jù)元素的線性表。n維數(shù)組中，每個數(shù)據(jù)元素對應n個下標，受n個關系的制約，其中任一個關系都是線性關系?？煽醋魇菙?shù)據(jù)元素為n-1維數(shù)組的一維數(shù)組。因此，多維數(shù)組和廣義表是對線性表的擴展：線性表中的數(shù)據(jù)元素本身又是一個多層次的線性表。一維數(shù)組具有線性表的結構，但操作簡單，一般不進行插入和刪除操295.1數(shù)組的定義5.2數(shù)組的順序表示和實現(xiàn)5.3矩陣的壓縮存儲5.1數(shù)組的定義305.1數(shù)組的定義ADTArray{數(shù)據(jù)對象：ji=0,…,bi-1,i=1,2,…,n,D={aj1j2…jn|n(>0)稱為數(shù)組的維數(shù)，bi是數(shù)組第i維的長度，ji是數(shù)組元素的第i維下標，aj1j2…jn∈ElemSet}數(shù)據(jù)關系：R={R1,R2,…,Rn} Ri={<aj1…ji…jn,aj1…ji+1…jn>|0≤jk≤bk-1,1≤k≤n且k≠i,0≤ji≤bi-2,aj1…ji…jn,aj1…ji+1…jn∈D,i=2,…n}5.1數(shù)組的定義ADTArray{31基本操作：InitArray(&A,n,bound1,…,boundn)DestroyArray(&A)Value(A,&e,index1,…,indexn)Assign(&A,e,index1,…,indexn)}ADTArray基本操作：325.2數(shù)組的順序表示多維數(shù)組用一維的存儲單元存放需約定次序。PASCAL和C語言是以行序為主序，F(xiàn)ORTRAN以列序為主序。給定維數(shù)和各維長度，數(shù)組的存儲空間確定。二維數(shù)組中任一元素aij的存儲地址:Loc(i,j)=Loc(0,0)+(b2*i+j)*Ln維數(shù)組：教材p93Loc（j1,j2,…,jn)=Loc(0,0,…,0)+∑ciji其中cn=L,ci-1=bi*ci,1<i≤n5.2數(shù)組的順序表示多維數(shù)組用一維的存儲單元存放需約定次序33類型定義#include<stdarg.h>#defineMAX_ARRAY_DIM8typedefstruct{ElemType*base;intdim;int*bounds;int*constants;}Array;類型定義#include<stdarg.h>345.3矩陣的壓縮存儲矩陣一般可用二維數(shù)組實現(xiàn)，特殊矩陣采用壓縮存儲。壓縮存儲：為多個值相同的元只分配一個存儲空間，對零元不分配空間。特殊矩陣：值相同的元素或者零元素在矩陣中的分布有一定規(guī)律稀疏矩陣：非零元較零元少，且分布沒有一定規(guī)律的矩陣5.3矩陣的壓縮存儲矩陣一般可用二維數(shù)組實現(xiàn)，特殊矩陣采用355.3.1.特殊矩陣對稱矩陣：aij=aji1≤i,j≤n壓縮存儲方法：為每一對對稱元分配一個存儲空間將下三角的元素，按行存儲到一維數(shù)組sa中共有n(n+1)/2個存儲單元，aij在一維數(shù)組中的位置k為：i(i-1)/2+j-1當i>=j否則j(j-1)/2+i-1三角矩陣：上（下）三角中的元均為常數(shù)c或0壓縮存儲方法：同上，只存儲上（下）三角元素。下三角：k=i*(i-1)/2+j-1上三角：k=(2n-i)(i-1)/2+j-1(按行)k=j(j-1)/2+i-1（按列）注意：k從零開始，i,j從1開始對角矩陣：所有非零元都集中在以主對角線為中心的帶狀區(qū)域中。壓縮方法：壓縮存儲到一維數(shù)組sa[]中，三對角矩陣有3n-2個元素。k=2*i+j-35.3.1.特殊矩陣對稱矩陣：aij=aji1≤365.3.2.稀疏矩陣1.三元組的表示稀疏矩陣可由表示非零元的三元組及其行列數(shù)唯一確定。t個非零元，t/(m*n)稱為稀疏因子<0.05用三元組(i,j,aij)存儲行和列的位置，及非零元數(shù)值。5.3.2.稀疏矩陣1.三元組的表示37（1）稀疏矩陣

(SparseMatrix)行數(shù)m=6,列數(shù)n=7,非零元素個數(shù)t=6

（1）稀疏矩陣(SparseMatrix)行數(shù)m=638稀疏矩陣轉置矩陣稀疏矩陣轉置矩陣39用三元組表表示的稀疏矩陣及其轉置用三元組表表示的稀疏矩陣及其轉置40（2）三元組順序表#defineMAXSIZE12500//非零元個數(shù)最大值typedefstruct{ inti,j;//行下標和列下標 ElemTypee;}Triple;typedefstruct{ Tripledata[MAXSIZE+1];//非零元三元組表 intmu,nu,tu;//行數(shù)、列數(shù)、非零元個數(shù)}TSMatrix;TSMatrixa,b;所需空間：3*tu+3若>mu*nu,則不必用三元組表示mu,nu,tu（2）三元組順序表#defineMAXSIZE125041(3)三元組表稀疏矩陣的轉置運算方法：按照b.data中的三元組的次序，即M的列序，依次在a.data中找到相應的三元組進行轉置。步驟：從k=1開始依次掃描找尋所有列號為k的項，將其行號變列號、列號變行號，順次存于轉置矩陣三元組表。其時間復雜度為O(a.nu*a.tu)。例：若矩陣有200行，200列，10,000個非零元素，總共有2,000,000次處理。(3)三元組表稀疏矩陣的轉置運算方法：按照b.data中的三42稀疏矩陣的轉置(算法5.1)

StatusTransposeSMatrix(TSMatrixM,TSMatrix&T){ intq,col,p; T.mu=M.nu; T.nu=M.mu; T.tu=M.tu; if(T.tu){q=1; for(col=1;col<=T.mu;++col) for(p=1;p<=M.tu;++p) if(M.data[p].j==col){ 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;}稀疏矩陣的轉置(算法5.1)43快速轉置算法方法：按a.data中三元組的次序進行轉置，并將轉置后的三元組置入b中恰當?shù)奈恢?。建立輔助數(shù)組num和cpot，num[col]表示矩陣第col列中非零元的個數(shù)，cpot[col]指示第col列的第一個非零元素在b.data中的恰當位置。按行掃描矩陣三元組表，根據(jù)某項的列號，確定它轉置后的行號，查cpot表，按查到的位置直接將該項存入轉置三元組表中。轉置時間復雜度為

O(nu+tu+nu+tu)=O(tu)。若矩陣有200列，10000個非零元素，總共需10000次處理?？焖俎D置算法方法：按a.data中三元組的次序進行轉置，并將44cpot[1]=1cpot[col]=cpot[col-1]+num[col-1]cpot[1]=145稀疏矩陣的快速轉置(算法5.2)StatusFastTransposeSMatrix(TSMatrixM,TSMatrix&T){T.mu=M.nu;T.nu=M.mu;T.tu=M.tu;if(T.tu){for(col=1;col<=M.nu;++col)num[col]=0; for(t=1;t<=M.tu;++t)++num[M.data[t].j]; cpot[1]=1; for(col=2;col<=M.nu;++col) cpot[col]=cpot[col-1]+num[col-1];for(p=1;p<=M.tu;++p){ col=M.data[p].j; q=cpot[col]; T.data[q].i=M.data[p].j; T.data[q].j=M.data[p].i; T.data[q].e=M.data[p].e; ++cpot[col];} }returnOK;}稀疏矩陣的快速轉置(算法5.2)462.十字鏈表當矩陣中非零元素的個數(shù)和位置經(jīng)過運算后變化較大時，就不宜采用順序存儲結構，而應采用鏈式存儲結構來表示三元組。稀疏矩陣的鏈接表示采用十字鏈表：行鏈表與列鏈表十字交叉。行鏈表與列鏈表都是帶表頭結點的循環(huán)鏈表。用表頭結點表征是第幾