數(shù)據(jù)結(jié)構(gòu)數(shù)組和廣義表第一頁(yè)，共二十七頁(yè)，2022年，8月28日一維數(shù)組具有線性表的結(jié)構(gòu)，但操作簡(jiǎn)單，一般不進(jìn)行插入和刪除操作，只定義給定下標(biāo)讀取元素和修改元素的操作二維數(shù)組中，每個(gè)數(shù)據(jù)元素對(duì)應(yīng)一對(duì)數(shù)組下標(biāo)，在行方向上和列方向上都存在一個(gè)線性關(guān)系，即存在兩個(gè)前驅(qū)（前件）和兩個(gè)后繼（后件）。也可看作是以線性表為數(shù)據(jù)元素的線性表。n維數(shù)組中，每個(gè)數(shù)據(jù)元素對(duì)應(yīng)n個(gè)下標(biāo)，受n個(gè)關(guān)系的制約，其中任一個(gè)關(guān)系都是線性關(guān)系?？煽醋魇菙?shù)據(jù)元素為n-1維數(shù)組的一維數(shù)組。因此，多維數(shù)組和廣義表是對(duì)線性表的擴(kuò)展：線性表中的數(shù)據(jù)元素本身又是一個(gè)多層次的線性表。第二頁(yè)，共二十七頁(yè)，2022年，8月28日5.1數(shù)組的定義5.2數(shù)組的順序表示和實(shí)現(xiàn)5.3矩陣的壓縮存儲(chǔ)第三頁(yè)，共二十七頁(yè)，2022年，8月28日5.1數(shù)組的定義ADTArray{數(shù)據(jù)對(duì)象：ji=0,…,bi-1,i=1,2,…,n,D={aj1j2…jn|n(>0)稱為數(shù)組的維數(shù)，bi是數(shù)組第i維的長(zhǎng)度，ji是數(shù)組元素的第i維下標(biāo)，aj1j2…jn∈ElemSet}數(shù)據(jù)關(guān)系：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}第四頁(yè)，共二十七頁(yè)，2022年，8月28日基本操作：InitArray(&A,n,bound1,…,boundn)DestroyArray(&A)Value(A,&e,index1,…,indexn)Assign(&A,e,index1,…,indexn)}ADTArray第五頁(yè)，共二十七頁(yè)，2022年，8月28日5.2數(shù)組的順序表示多維數(shù)組用一維的存儲(chǔ)單元存放需約定次序。PASCAL和C語(yǔ)言是以行序?yàn)橹餍颍現(xiàn)ORTRAN以列序?yàn)橹餍颉＝o定維數(shù)和各維長(zhǎng)度，數(shù)組的存儲(chǔ)空間確定。二維數(shù)組中任一元素aij的存儲(chǔ)地址: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≤n第六頁(yè)，共二十七頁(yè)，2022年，8月28日類型定義#include<stdarg.h>#defineMAX_ARRAY_DIM8typedefstruct{ElemType*base;intdim;int*bounds;int*constants;}Array;第七頁(yè)，共二十七頁(yè)，2022年，8月28日5.3矩陣的壓縮存儲(chǔ)矩陣一般可用二維數(shù)組實(shí)現(xiàn)，特殊矩陣采用壓縮存儲(chǔ)。壓縮存儲(chǔ)：為多個(gè)值相同的元只分配一個(gè)存儲(chǔ)空間，對(duì)零元不分配空間。特殊矩陣：值相同的元素或者零元素在矩陣中的分布有一定規(guī)律稀疏矩陣：非零元較零元少，且分布沒(méi)有一定規(guī)律的矩陣第八頁(yè)，共二十七頁(yè)，2022年，8月28日5.3.1.特殊矩陣對(duì)稱矩陣：aij=aji1≤i,j≤n壓縮存儲(chǔ)方法：為每一對(duì)對(duì)稱元分配一個(gè)存儲(chǔ)空間將下三角的元素，按行存儲(chǔ)到一維數(shù)組sa中共有n(n+1)/2個(gè)存儲(chǔ)單元，aij在一維數(shù)組中的位置k為：i(i-1)/2+j-1當(dāng)i>=j否則j(j-1)/2+i-1三角矩陣：上（下）三角中的元均為常數(shù)c或0壓縮存儲(chǔ)方法：同上，只存儲(chǔ)上（下）三角元素。下三角：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開始對(duì)角矩陣：所有非零元都集中在以主對(duì)角線為中心的帶狀區(qū)域中。壓縮方法：壓縮存儲(chǔ)到一維數(shù)組sa[]中，三對(duì)角矩陣有3n-2個(gè)元素。k=2*i+j-3第九頁(yè)，共二十七頁(yè)，2022年，8月28日5.3.2.稀疏矩陣1.三元組的表示稀疏矩陣可由表示非零元的三元組及其行列數(shù)唯一確定。t個(gè)非零元，t/(m*n)稱為稀疏因子<0.05用三元組(i,j,aij)存儲(chǔ)行和列的位置，及非零元數(shù)值。第十頁(yè)，共二十七頁(yè)，2022年，8月28日（1）稀疏矩陣

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

第十一頁(yè)，共二十七頁(yè)，2022年，8月28日稀疏矩陣轉(zhuǎn)置矩陣第十二頁(yè)，共二十七頁(yè)，2022年，8月28日用三元組表表示的稀疏矩陣及其轉(zhuǎn)置第十三頁(yè)，共二十七頁(yè)，2022年，8月28日（2）三元組順序表#defineMAXSIZE12500//非零元個(gè)數(shù)最大值typedefstruct{ inti,j;//行下標(biāo)和列下標(biāo) ElemTypee;}Triple;typedefstruct{ Tripledata[MAXSIZE+1];//非零元三元組表 intmu,nu,tu;//行數(shù)、列數(shù)、非零元個(gè)數(shù)}TSMatrix;TSMatrixa,b;所需空間：3*tu+3若>mu*nu,則不必用三元組表示mu,nu,tu第十四頁(yè)，共二十七頁(yè)，2022年，8月28日(3)三元組表稀疏矩陣的轉(zhuǎn)置運(yùn)算方法：按照b.data中的三元組的次序，即M的列序，依次在a.data中找到相應(yīng)的三元組進(jìn)行轉(zhuǎn)置。步驟：從k=1開始依次掃描找尋所有列號(hào)為k的項(xiàng)，將其行號(hào)變列號(hào)、列號(hào)變行號(hào)，順次存于轉(zhuǎn)置矩陣三元組表。其時(shí)間復(fù)雜度為O(a.nu*a.tu)。例：若矩陣有200行，200列，10,000個(gè)非零元素，總共有2,000,000次處理。第十五頁(yè)，共二十七頁(yè)，2022年，8月28日稀疏矩陣的轉(zhuǎn)置(算法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;}第十六頁(yè)，共二十七頁(yè)，2022年，8月28日快速轉(zhuǎn)置算法方法：按a.data中三元組的次序進(jìn)行轉(zhuǎn)置，并將轉(zhuǎn)置后的三元組置入b中恰當(dāng)?shù)奈恢?。建立輔助數(shù)組num和cpot，num[col]表示矩陣第col列中非零元的個(gè)數(shù)，cpot[col]指示第col列的第一個(gè)非零元素在b.data中的恰當(dāng)位置。按行掃描矩陣三元組表，根據(jù)某項(xiàng)的列號(hào)，確定它轉(zhuǎn)置后的行號(hào)，查cpot表，按查到的位置直接將該項(xiàng)存入轉(zhuǎn)置三元組表中。轉(zhuǎn)置時(shí)間復(fù)雜度為

O(nu+tu+nu+tu)=O(tu)。若矩陣有200列，10000個(gè)非零元素，總共需10000次處理。第十七頁(yè)，共二十七頁(yè)，2022年，8月28日cpot[1]=1cpot[col]=cpot[col-1]+num[col-1]第十八頁(yè)，共二十七頁(yè)，2022年，8月28日稀疏矩陣的快速轉(zhuǎn)置(算法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;}第十九頁(yè)，共二十七頁(yè)，2022年，8月28日2.十字鏈表當(dāng)矩陣中非零元素的個(gè)數(shù)和位置經(jīng)過(guò)運(yùn)算后變化較大時(shí)，就不宜采用順序存儲(chǔ)結(jié)構(gòu)，而應(yīng)采用鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)來(lái)表示三元組。稀疏矩陣的鏈接表示采用十字鏈表：行鏈表與列鏈表十字交叉。行鏈表與列鏈表都是帶表頭結(jié)點(diǎn)的循環(huán)鏈表。用表頭結(jié)點(diǎn)表征是第幾行，第幾列。第二十頁(yè)，共二十七頁(yè)，2022年，8月28日元素結(jié)點(diǎn)right——指向同一行中下一個(gè)非零元素的指針（向右域）down——指向同一列中下一個(gè)非零元素的指針（向下域）表頭結(jié)點(diǎn)行表頭結(jié)點(diǎn)列表頭結(jié)點(diǎn)next用于表示頭結(jié)點(diǎn)的鏈接rowcolvaldownrightcol=0nextrightrow=0nextdown第二十一頁(yè)，共二十七頁(yè)，2022年，8月28日由于行、列表頭結(jié)點(diǎn)互相不沖突，所以可以合并起來(lái)：總表頭結(jié)點(diǎn)：row=0col=0nextdownrightrowcolnext第二十二頁(yè)，共二十七頁(yè)，2022年，8月28日類型定義：typedefstruct{ inti,j;//非零元的行下標(biāo)和列下標(biāo) ElemTypee;}Triple;typedefstructOLNode{//元素結(jié)點(diǎn) union{Tripletriple;OLNode*next}; structOLNode*right,*down;

//該非零元所在行表和列表的后繼鏈域}OLNode,*OLink;OLinkM；第二十三頁(yè)，共二十七頁(yè)，2022年，8月28日稀疏矩陣的十字鏈表表示的示例第二十四頁(yè)，共二十七頁(yè)，2022年，8月28日需要輔助結(jié)點(diǎn)作鏈表的表頭，同時(shí)每個(gè)結(jié)點(diǎn)要增加兩個(gè)指針域，所以只有在矩陣較大和較稀疏時(shí)才能起到節(jié)省空間的效果。分別用兩個(gè)一維數(shù)組存儲(chǔ)行鏈表的頭指針和列鏈表的頭指針，可加快訪問(wèn)速度。第二十五頁(yè)，共二十七頁(yè)，2022年，8月28日十字鏈表的類型定義typedefstructOLNode{//元素結(jié)點(diǎn) inti