《數(shù)據(jù)結(jié)構(gòu)》課件第四章

第四章數(shù)組內(nèi)容提要數(shù)組的定義、表示與實(shí)現(xiàn)矩陣的壓縮存儲(chǔ)特殊矩陣稀疏矩陣數(shù)組基本定義數(shù)組的維數(shù)一旦被定義，就不再改變二維數(shù)組也可以看作元素類(lèi)型為一維數(shù)組的一維數(shù)組類(lèi)型Typedefelemtypearray2[m][n];等價(jià)于Typedefelemtypearray1[n];//先定義一個(gè)一維數(shù)組Typedefarray1array2[m];數(shù)組的順序存儲(chǔ)方式由于存儲(chǔ)單元是一維的結(jié)構(gòu)，而數(shù)組是個(gè)多維的結(jié)構(gòu)，那么用一組連續(xù)存儲(chǔ)單元存放數(shù)組的元素時(shí)，映射問(wèn)題是關(guān)鍵。行優(yōu)先存儲(chǔ)：將數(shù)組按行向量排列，即第i+1行緊接在第i行后。（C語(yǔ)言采用這種方式）列優(yōu)先存儲(chǔ)：將數(shù)組元素按列向量排列。a00a01…a0na10a11..a20a00a10…an0a01a11..an1數(shù)組元素的存儲(chǔ)地址★

二維數(shù)組(m*n)Loc(i,j)=Loc(0,0)+(i*n+j)*s0<i≤m-1,0<j≤n-1（適用于數(shù)組下標(biāo)規(guī)定從0起始的編程語(yǔ)言）三維數(shù)組(m*n*p)Loc[i][j][k]=Loc[0][0][0]+(i*(n*p)+j*p+k)*s0<i≤m-1,0<j≤n-1，0<k≤p-1

下面是數(shù)組的順序存儲(chǔ)表示和實(shí)現(xiàn)typedefstruct{//數(shù)組元素基址，由InitArray函數(shù)來(lái)分配

ElemType*base;

//數(shù)組維數(shù)

intdim;//數(shù)組維界基址，存放每一維的長(zhǎng)度

int *bounds;

//數(shù)組映象函數(shù)常量基址，由InitArray分配

int*constants;}Array；數(shù)組的操作數(shù)組除了結(jié)構(gòu)的初始化和銷(xiāo)毀操作之外，只有兩個(gè)操作：給定一組下標(biāo)，讀取相應(yīng)的數(shù)據(jù)元素

GetValue(A,&e,i,j)給定一組下標(biāo)，修改相應(yīng)數(shù)據(jù)元素中的某一個(gè)或幾個(gè)數(shù)據(jù)項(xiàng)的值

ChangeValue(A,e,i,j)矩陣的壓縮存儲(chǔ)矩陣是很多科學(xué)與工程計(jì)算問(wèn)題中研究的數(shù)學(xué)對(duì)象。如何存儲(chǔ)矩陣的元，從而使矩陣的各種運(yùn)算能有效地進(jìn)行？這是很重要的。為了節(jié)約矩陣存儲(chǔ)的空間，往往對(duì)一些特殊矩陣進(jìn)行壓縮存儲(chǔ)——多個(gè)值相同的元只分配一個(gè)存儲(chǔ)空間；對(duì)零元不分配空間矩陣常識(shí)特殊矩陣——數(shù)值相同的元素或零元素在矩陣中的分布有一定規(guī)律對(duì)稱矩陣：兩種對(duì)稱方向下/上三角矩陣：右上/左下三角（不包括對(duì)角線）中的元均為常數(shù)或０稀疏矩陣稀疏因子＝非０元的個(gè)數(shù)／（m×n）當(dāng)稀疏因子≦0.05時(shí)的矩陣被稱為稀疏矩陣對(duì)稱矩陣的壓縮存儲(chǔ)對(duì)稱矩陣的特點(diǎn)：aij=aji(1<=i,j<=n)分配方法：為每一對(duì)對(duì)稱元分配一個(gè)存儲(chǔ)空間例：若以一維數(shù)組作為n階對(duì)稱矩陣的存儲(chǔ)結(jié)構(gòu)，以行序?yàn)橹餍颍鎯?chǔ)下三角(包括主對(duì)角線)矩陣。則數(shù)組與矩陣中的aij存在一一對(duì)應(yīng)的關(guān)系an,n..an,1…a31a22a21a11K=012n(n-1)/2n(n+1)/2-1j<i

1i－+2)1j－(jj≥i

1j－+2)1i－(i=k當(dāng)當(dāng)下標(biāo)轉(zhuǎn)換算法intij_to_k(inti,intj){If(i<1||j<1)return(-1);If(i>=j)return(i(i-1)/2+j-1);Elsereturn(j(j-1)/2+i-1);}輸入并存儲(chǔ)對(duì)稱矩陣的算法VoidMyint(elemtypea[],intn);{for(k=0;k<n(n+1)/2;k++)Scanf(&a[k]);}讀取對(duì)稱矩陣中某元素的算法Statusgetelem(elemtypea[],inti,intj,elemtype&e){k=ij_to_k(i,j);

if(k>=0){e=a[k];returnOK;}elsereturnERROR;}輸出打印對(duì)稱矩陣的算法Voidprint(elemtypeA[];inti;intn){for(inti=1;i<=n;i++){printf(“\n);for(j=1;j<=n;j++){getelem(A,i,j,e);printf(“%d”,e);}}}//行為主序稀疏矩陣的存儲(chǔ)

定義：如果一個(gè)m*n的矩陣中非零元素比零元素的個(gè)數(shù)少得多，且非零元素的分布沒(méi)有規(guī)律壓縮存儲(chǔ)：只存儲(chǔ)非零元素由一個(gè)三元組能夠惟一確定矩陣的每個(gè)非零元——三元組順序表

//非零元個(gè)數(shù)的最大值為mu*nu*0.05，假設(shè)為40#defineMAXSIZE40

typedefstruct{introw，col;ElemTypevalue；}Triple；typedefstruct{

//data:非零元三元組表，data[0]用來(lái)放置總行數(shù)、總列數(shù)和非零元素個(gè)數(shù)

Tripledata[MAXSIZE+1]；

//矩陣的行數(shù)、列數(shù)和非零元個(gè)數(shù)

intmu，nu，tu;//tu表示稀疏矩陣中的非零元素的個(gè)數(shù)}TSMatrix；typedefstruct{introw，col;ElemTypevalue；}Triple；typedefstruct{Tripledata[MAXSIZE+1]；……稀疏矩陣的轉(zhuǎn)置運(yùn)算

對(duì)于一個(gè)m*n的矩陣M，它的轉(zhuǎn)置矩陣T是一個(gè)n*m的矩陣轉(zhuǎn)置方法：矩陣行列值轉(zhuǎn)換，原有的m*n矩陣M要變?yōu)閚*m的矩陣T。每個(gè)三元組中的row和col位置互換，即原來(lái)的Aij對(duì)應(yīng)Bji三元組A的排列是以原矩陣的行號(hào)為主序，而三元組B是以原矩陣的列為排列順序rowcolvalue121213931-3361443245218611564-7rowcolvalue13-3161521122518319342446-76314稀疏矩陣的轉(zhuǎn)置算法時(shí)間復(fù)雜度：

O(nu*tu)已知矩陣的三元組順序表A,求其轉(zhuǎn)置矩陣的三元組順序表BStatusTransposeSMatrix(TSMatrixA，TSMatrix&B){

//采用三元組表存儲(chǔ)表示，求稀疏矩陣A的轉(zhuǎn)置矩陣B。

B.mu=A.nu；B.nu=A.mu；B.tu=A.tu；

if(B.tu){q=1；//b組,0號(hào)位存其他的信息

for(j=1；j<=A.nu；++j)for(p=1；p<=A.tu；++p)//p是A組的下標(biāo)

if(A.data[p].col==j){

B.data[q].row=A.data[p].col;B.data[q].col=A.data[p].row;B.data[q].value=A.data[p].value;q++;}}returnOK；}//TransposeSMatrix時(shí)間復(fù)雜度：O(nu*tu)十字鏈表當(dāng)矩陣的非零元個(gè)數(shù)和位置在操作(即矩陣運(yùn)算)過(guò)程中變化較大時(shí)，就不宜采用順序存儲(chǔ)結(jié)構(gòu)來(lái)表示三元組的線性表。 例如，在作“將矩陣B加到矩陣A上”的操作時(shí)，由于非零元的添加或正負(fù)抵消歸零等將會(huì)引起A.data中元素值的變動(dòng)。為此，對(duì)這種類(lèi)型的矩陣，采用鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)表示三元組的線性表更為恰當(dāng)。每個(gè)非零元可用一個(gè)含五個(gè)域的結(jié)點(diǎn)表示其中row，col和val三個(gè)域分別表示該非零元所在的行、列和非零元的值向右域right用以鏈接同一行中下一個(gè)非零元向下域down用以鏈接同一列中下一個(gè)非零元。rightdownvalcolrow//—

—稀疏矩陣的十字鏈表存儲(chǔ)表示—

—

typedefstructOLNode{ inti，j；

ElemTypee；

structOLNode*right，*down;}OLNode；*OLink；

typedefstruct{

//行和列鏈表頭指針向量,基址由CreateSMatrix分配

OLink*rhead，*chead; intmu，nu,tu;//稀疏矩陣的行數(shù)、列數(shù)和非 零元個(gè)數(shù)

}CrossList；

稀疏矩陣M的十字鏈表311541122213M.cheadM.rhead生成十字鏈表(當(dāng)i值為0時(shí)結(jié)束輸入)兩個(gè)矩陣相加和第二章中討論的兩個(gè)一元多項(xiàng)式相加極為相似。不同的是一元多項(xiàng)式中只有一個(gè)變?cè)?即指數(shù)項(xiàng))，而矩陣中每個(gè)非零元有兩個(gè)變?cè)?行值和列值)，每個(gè)結(jié)點(diǎn)既在行表中又在列表中，致使插入