《數(shù)據(jù)結構》課件第四章

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

二維數(shù)組(m*n)Loc(i,j)=Loc(0,0)+(i*n+j)*s0<i≤m-1,0<j≤n-1（適用于數(shù)組下標規(guī)定從0起始的編程語言）三維數(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ù)組的順序存儲表示和實現(xiàn)typedefstruct{//數(shù)組元素基址，由InitArray函數(shù)來分配

ElemType*base;

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

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

int *bounds;

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

int*constants;}Array；數(shù)組的操作數(shù)組除了結構的初始化和銷毀操作之外，只有兩個操作：給定一組下標，讀取相應的數(shù)據(jù)元素

GetValue(A,&e,i,j)給定一組下標，修改相應數(shù)據(jù)元素中的某一個或幾個數(shù)據(jù)項的值

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

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

1j－+2)1i－(i=k當當下標轉換算法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);}輸入并存儲對稱矩陣的算法VoidMyint(elemtypea[],intn);{for(k=0;k<n(n+1)/2;k++)Scanf(&a[k]);}讀取對稱矩陣中某元素的算法Statusgetelem(elemtypea[],inti,intj,elemtype&e){k=ij_to_k(i,j);

if(k>=0){e=a[k];returnOK;}elsereturnERROR;}輸出打印對稱矩陣的算法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);}}}//行為主序稀疏矩陣的存儲

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

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

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

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

Tripledata[MAXSIZE+1]；

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

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

對于一個m*n的矩陣M，它的轉置矩陣T是一個n*m的矩陣轉置方法：矩陣行列值轉換，原有的m*n矩陣M要變?yōu)閚*m的矩陣T。每個三元組中的row和col位置互換，即原來的Aij對應Bji三元組A的排列是以原矩陣的行號為主序，而三元組B是以原矩陣的列為排列順序rowcolvalue121213931-3361443245218611564-7rowcolvalue13-3161521122518319342446-76314稀疏矩陣的轉置算法時間復雜度：

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

//采用三元組表存儲表示，求稀疏矩陣A的轉置矩陣B。

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

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

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

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時間復雜度：O(nu*tu)十字鏈表當矩陣的非零元個數(shù)和位置在操作(即矩陣運算)過程中變化較大時，就不宜采用順序存儲結構來表示三元組的線性表。 例如，在作“將矩陣B加到矩陣A上”的操作時，由于非零元的添加或正負抵消歸零等將會引起A.data中元素值的變動。為此，對這種類型的矩陣，采用鏈式存儲結構表示三元組的線性表更為恰當。每個非零元可用一個含五個域的結點表示其中row，col和val三個域分別表示該非零元所在的行、列和非零元的值向右域right用以鏈接同一行中下一個非零元向下域down用以鏈接同一列中下一個非零元。rightdownvalcolrow//—

—稀疏矩陣的十字鏈表存儲表示—

—

typedefstructOLNode{ inti，j；

ElemTypee；

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

typedefstruct{

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

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

}CrossList；

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