數(shù)組和稀疏矩陣

關(guān)于數(shù)組和稀疏矩陣第1頁，講稿共57頁，2023年5月2日，星期三5.1.1數(shù)組的基本概念

數(shù)組是n(n＞1)個相同類型數(shù)據(jù)元素a0,a1,…,an-1構(gòu)成的有限序列,且該有限序列存儲在一塊地址連續(xù)的內(nèi)存單元中。由此可見,數(shù)組的定義類似于采用順序存儲結(jié)構(gòu)的線性表。第2頁，講稿共57頁，2023年5月2日，星期三數(shù)組具有以下性質(zhì)：

(1)數(shù)組中的數(shù)據(jù)元素?cái)?shù)目固定，一旦定義了一個數(shù)組，其數(shù)據(jù)元素?cái)?shù)目不再有增減變化。

(2)數(shù)組中的數(shù)據(jù)元素具有相同的數(shù)據(jù)類型。

(3)數(shù)組中的每個數(shù)據(jù)元素都和一組唯一的下標(biāo)值對應(yīng)。

(4)數(shù)組是一種隨機(jī)存儲結(jié)構(gòu)，可隨機(jī)存取數(shù)組中的任意數(shù)據(jù)元素。第3頁，講稿共57頁，2023年5月2日，星期三5.1.2數(shù)組的存儲結(jié)構(gòu)

在一維數(shù)組中,假設(shè)a0的存儲地址由LOC(a0)確定,且每個數(shù)據(jù)元素占用k個存儲單元,則任一數(shù)據(jù)元素ai的存儲地址LOC(ai)就可由以下公式求出：

LOC(ai)=LOC(a0)+i*k(0≤i≤n-1)

上式說明,一維數(shù)組中任一數(shù)據(jù)元素的存儲地址可直接計(jì)算得到,即一維數(shù)組中任一數(shù)據(jù)元素可直接存取。因此,一維數(shù)組是一種隨機(jī)存儲結(jié)構(gòu)。同樣,二維及多維數(shù)組也滿足隨機(jī)存儲特性。第4頁，講稿共57頁，2023年5月2日，星期三對于一個m行n列的二維數(shù)組Am×n,有：

將Am*n簡記為A,A是這樣的一維數(shù)組：

A=(a0,a1,…,ai…,am-1)其中,ai=(ai,0,ai,1,…,ai,n－1)(0≤i≤m-1)。第5頁，講稿共57頁，2023年5月2日，星期三

顯然,二維數(shù)組同樣滿足數(shù)組的定義。一個二維數(shù)組可以看作是每個數(shù)據(jù)元素都是相同類型的一維數(shù)組的一維數(shù)組。以此類推,任何多維數(shù)組都可以看作一個線性表，這時線性表中的每個數(shù)據(jù)元素也是一個線性表。多維數(shù)組是線性表的推廣。第6頁，講稿共57頁，2023年5月2日，星期三

對于二維數(shù)組來說，由于計(jì)算機(jī)的存儲結(jié)構(gòu)是線性的,如何用線性的存儲結(jié)構(gòu)存放二維數(shù)組元素就有一個行／列次序排放問題。

以行序?yàn)橹餍虻拇鎯Ψ绞剑杭聪却鎯Φ?行,然后緊接著存儲第2行,最后存儲第m行。此時,二維數(shù)組的線性排列次序?yàn)椋?/p>

a0,0,a0,1,…,a0,n-1,a1,0,a1,1,…,a2,n-1,…,am-1,0,am-1,1,…am-1,n-1第7頁，講稿共57頁，2023年5月2日，星期三

對一個已知以行序?yàn)橹餍虻挠?jì)算機(jī)系統(tǒng)中,當(dāng)二維數(shù)組第一個數(shù)據(jù)元素a0,0的存儲地址LOC(a0,0)和每個數(shù)據(jù)元素所占用的存儲單元k確定后,則該二維數(shù)組中任一數(shù)據(jù)元素ai,j的存儲地址可由下式確定：

LOC(ai,j)=LOC(a0,0)+[i*n+j]*k

其中n為列數(shù)。第8頁，講稿共57頁，2023年5月2日，星期三

同理可推出在以列序?yàn)橹餍虻挠?jì)算機(jī)系統(tǒng)中有：

LOC(ai,j)=LOC(a0,0)+[j*m+i]*k

其中m為行數(shù)。第9頁，講稿共57頁，2023年5月2日，星期三

例5.1對二維數(shù)組floata[5][4]計(jì)算：

(1)數(shù)組a中的數(shù)組元素?cái)?shù)目；

(2)若數(shù)組a的起始地址為2000，且每個數(shù)組元素長度為32位(即4個字節(jié))，數(shù)組元素a[3][2]的內(nèi)存地址。

第10頁，講稿共57頁，2023年5月2日，星期三

解：該數(shù)組的元素?cái)?shù)目共有5*4=20個。由于C語言采用行序?yàn)橹餍虻拇鎯Ψ绞?則有：

LOC(a3,2)=LOC(a0,0)+(i*n+j)*k=2000+(3*4+2)*4=2056第11頁，講稿共57頁，2023年5月2日，星期三5.1.3特殊矩陣的壓縮存儲

特殊矩陣是指非零元素或零元素的分布有一定規(guī)律的矩陣，為了節(jié)省存儲空間,特別是在高階矩陣的情況下，可以利用特殊矩陣的規(guī)律,對它們進(jìn)行壓縮存儲，也就是說，使多個相同的非零元素共享同一個存儲單元，對零元素不分配存儲空間。

特殊矩陣的主要形式有對稱矩陣、對角矩陣等，它們都是方陣，即行數(shù)和列數(shù)相同。第12頁，講稿共57頁，2023年5月2日，星期三

1.對稱矩陣的壓縮存儲若一個n階方陣A[n][n]中的元素滿足ai,j=aj,i(1≤i,j≤n),則稱其為n階對稱矩陣。由于對稱矩陣中的元素關(guān)于主對角線對稱，因此在存儲時可只存儲對稱矩陣中上三角或下三角中的元素，使得對稱的元素共享一個存儲空間。這樣,就可以將n2個元素壓縮存儲到n(n+1)/2個元素的空間中。不失一般性,我們以行序?yàn)橹餍虼鎯ζ湎氯?包括對角線)的元素，例如：第13頁，講稿共57頁，2023年5月2日，星期三15137a1150800a21a2218926a31a32a3330251………………..70613an1an2an3…ann

在這個下三角矩陣中，第i行恰有i個元素，元素總數(shù)為：n(n+1)/2

因此，我們可以按從上到下、從左到右將這些元素存放在一個向量b[0..n(n+1)/2-1]中。為了便于訪問對稱矩陣A中的元素，我們必須在aij和b[k]之間找一個對應(yīng)關(guān)系。第14頁，講稿共57頁，2023年5月2日，星期三

若i≧j，則aij在下三角形中。aij之前的i-1行共有1+2+…+i-1=i(i-1)/2個元素，在第i行上，aij之前有j-1個元素（即ai1,ai2,ai3,…,aij-1），因此有：a11a21a22a31…an1…annk=0123-1i*(i-1)/2+j–1當(dāng)i>=jj*(j-1)/2+i-1當(dāng)i<jk=第15頁，講稿共57頁，2023年5月2日，星期三2.三角矩陣的壓縮存儲

以主對角線劃分，三角矩陣有上三角和下三角兩種。上三角矩陣如圖a所示，它的下三角（不包括主對角線）中的元素均為常數(shù)c。下三角矩陣正好相反，它的主對角線上方均為常數(shù)c，如圖b所示。在大多數(shù)情況下，三角矩陣常數(shù)為零。

a00a01…a0n-1a00c…cca11…a1n-1a10a11…c…..……………..cc…an-1n-1an-10an-11…an-1n-1

(a)上三角矩陣(b)下三角矩陣第16頁，講稿共57頁，2023年5月2日，星期三

三角矩陣的重復(fù)元素c可共享一個存儲空間，其余元素正好有n(n+1)/2個，因此，三角矩陣可壓縮存儲到b[0..n(n+1)/2]中，其中c存放在最后一個分量中。上三角矩陣中，主對角線之上的第i行(0≦i<n)恰有n-i個元素，按行優(yōu)先順序存放上三角矩陣中的元素aij時，aij之前的i行一共有i(2n-i+1)/2個元素，在第i行上，aij前恰好有j-i個元素：aii,aii+1,…aij-1。因此，b[k]和aij的對應(yīng)關(guān)系是：i(2n-i+1)/2+j-i當(dāng)i≦jn(n+1)/2當(dāng)i>jk=下三角矩陣的存儲和對稱矩陣類似，b[k]和aij對應(yīng)關(guān)系是：

i(i+1)/2+ji≧jn(n+1)/2i<jk=第17頁，講稿共57頁，2023年5月2日，星期三3.對角矩陣的壓縮存儲若一個n階方陣A滿足其所有非零元素都集中在以主對角線為中心的帶狀區(qū)域中，則稱其為n階對角矩陣，其主對角線上下方各有b條次對角線,稱b為矩陣半帶寬，(2b+1)為矩陣的帶寬。對于半帶寬為b(0≤b≤(n-1)/2)的對角矩陣，其|i-j|≤b的元素ai,j不為零,其余元素為零。下圖所示是半帶寬為b的對角矩陣示意圖。第18頁，講稿共57頁，2023年5月2日，星期三

半帶寬為b的對角矩陣

第19頁，講稿共57頁，2023年5月2日，星期三

a00a01a10a11a12a21a22a23….…..….可用以行序?yàn)橹餍虻?/p>

an-2n-3an-2n-2an-2n-1an-1n-2an-1n-1

形式存儲b[3n-2]中

當(dāng)b＝1時稱為三對角矩陣，如：主對角線下方的元素的下標(biāo)關(guān)系為i=j+1,此時k=3(i-1)+2主對角線上的元素的下標(biāo)關(guān)系為i=j,此時k=3(i-1)+3主對角線下的元素的下標(biāo)關(guān)系為i=j－1,此時k=3(i-1)+4即：k=2i+j第20頁，講稿共57頁，2023年5月2日，星期三

例5.2

按行優(yōu)先順序和按列優(yōu)先順序列出四維數(shù)組A[2][2][2][2]所有元素在內(nèi)存中的存儲次序。第21頁，講稿共57頁，2023年5月2日，星期三

解：按行優(yōu)先的存儲次序:A[0][0][0][0],A[0][0][0][1],A[0][0][1][0],A[0][0][1][1],A[0][1][0][0],A[0][1][0][1],A[0][1][1][0],A[0][1][1][1],A[1][0][0][0],A[1][0][0][1],A[1][0][1][0],A[1][0][1][1],A[1][1][0][0],A[1][1][0][1],A[1][1][1][0],A[1][1][1][1]第22頁，講稿共57頁，2023年5月2日，星期三

按列優(yōu)先的存儲次序:

A[0][0][0][0],A[1][0][0][0],A[0][1][0][0],A[1][1][0][0],A[0][0][1][0],A[1][0][1][0],A[0][1][1][0],A[1][1][1][0],A[0][0][0][1],A[1][0][0][1],A[0][1][0][1],A[1][1][0][1],A[0][0][1][1],A[1][0][1][1],A[0][1][1][1],A[1][1][1][1]第23頁，講稿共57頁，2023年5月2日，星期三5.2稀疏矩陣

一個階數(shù)較大的矩陣中的非零元素個數(shù)s相對于矩陣元素的總個數(shù)t十分小時，即s<<t時,稱該矩陣為稀疏矩陣。例如一個100×100的矩陣,若其中只有100個非零元素,就可稱其為稀疏矩陣。第24頁，講稿共57頁，2023年5月2日，星期三5.2.1稀疏矩陣的三元組表示

稀疏矩陣的壓縮存儲方法是只存儲非零元素。由于稀疏矩陣中非零元素的分布沒有任何規(guī)律,所以在存儲非零元素時還必須同時存儲該非零元素所對應(yīng)的行下標(biāo)和列下標(biāo)。這樣稀疏矩陣中的每一個非零元素需由一個三元組(i,j,ai,j)惟一確定,稀疏矩陣中的所有非零元素構(gòu)成三元組線性表。第25頁，講稿共57頁，2023年5月2日，星期三

假設(shè)有一個6×7階稀疏矩陣M(為圖示方便,我們所取的行列數(shù)都很小),M中元素如下圖所示。則對應(yīng)的三元組線性表為：

((0,1,12）,(0,2,9),(2,0,-3),(2,5,14),(3,2,24),(4,1,18),(5,0,16),(5,3,-7))第26頁，講稿共57頁，2023年5月2日，星期三

若把稀疏矩陣的三元組線性表按順序存儲結(jié)構(gòu)存儲,則稱為稀疏矩陣的三元組順序表。則三元組順序表的數(shù)據(jù)結(jié)構(gòu)可定義如下：第27頁，講稿共57頁，2023年5月2日，星期三

#defineMaxSize100//矩陣中非零元素最多個數(shù)

typedefstruct{inti; //行號

intj; //列號

ElemTypee; //元素值

}Triple; //三元組定義

typedefstruct{intmu; //行數(shù)值

intnu; //列數(shù)值

inttu; //非零元素個數(shù)

Tripledata[MaxSize+1];}TSMatrix;//三元組順序表定義

第28頁，講稿共57頁，2023年5月2日，星期三ije121213931-361432452181154-7M.dataM.mu=6M.nu=7M.tu=8第29頁，講稿共57頁，2023年5月2日，星期三用常規(guī)的二維數(shù)組表示時的算法

其時間復(fù)雜度為:O(M.mu×M.nu)for(col=1;col<=M.nu;++col)

for(row=1;row<=M.mu;++row)T[col][row]=M[row][col];（1）用三元組表示時矩陣轉(zhuǎn)置運(yùn)算的實(shí)現(xiàn)用三元組表示時如何實(shí)現(xiàn)？第30頁，講稿共57頁，2023年5月2日，星期三方法1：ije121213931-3614324521811564-7M.dataM.mu=6M.nu=7M.tu=8轉(zhuǎn)置后得Tijv13-31615211225183194246-76314T.dataT.mu=7T.nu=6T.tu=8第31頁，講稿共57頁，2023年5月2日，星期三StatusTransposeSMattrix(TSMatrixM,TSMatrix&T){//采用三元組表存儲表示，求稀疏矩陣的轉(zhuǎn)置矩陣TT.mu=M.nu;T.nu=M.mu;T.tu=M.tu;if(T.tu){q=1;

//q表示下一次找到的非零元在T.data中的下標(biāo)for(col=1;col<=M.nu;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;}//TransposeSMattrix其時間復(fù)雜度為:O(M.nu×M.tu)，若M.tu與M.muM.nu同數(shù)量級時，有O(M.mu×M.nu2)第32頁，講稿共57頁，2023年5月2日，星期三方法二：快速轉(zhuǎn)置其基本思想是對M.data僅掃描一遍，在掃描到每一個元素時將其放在T.data的合適的位置上。cpot[1]=1;cpot[col]=cpot[col-1]+num[col-1];(2colM.nu)1357889colnum[col]cpot[col]12223241506170第33頁，講稿共57頁，2023年5月2日，星期三方法2（快速轉(zhuǎn)置）：ije121213931-3614324521811564-7M.dataM.mu=6M.nu=7M.tu=8轉(zhuǎn)置后得TT.mu=7T.nu=6T.tu=8T.dataijv211231913-3631434242518161546-7123456781357889colnum[col]cpot[col]1222324150617046297538第34頁，講稿共57頁，2023年5月2日，星期三1）根據(jù)M的mu、nu和tu的值，對T的mu、nu和tu賦相應(yīng)的值；2）初始化數(shù)組num;3）掃描M.data，計(jì)算num的值；4）根據(jù)num的值，計(jì)算cpot的值；5）掃描M.data一遍，將非零元放在T.data的合適的位置上。算法描述如下頁所示：第35頁，講稿共57頁，2023年5月2日，星期三StatusFastTransposeSMatrix(TSMatrixM,TSMatrix&T){//采用三元組表存儲表示，求稀疏矩陣的轉(zhuǎn)置矩陣TT.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;col<=M.tu;t++)++num[M.data[t].j];cpot[1]=1;//求第col列中第一個非零元在T.data中的序號

for(col=2;col<=M.nu;col++)cpot[col]=cpot[col-1]+num[col-1];for(t=1;t<=M.tu;t++){col=M.data[t].j;q=cpot[col];T.data[q].i=M.data[t].j;T.data[q].j=M.data[t].i;T.data[q].e=M.data[t].e;++cpot[col];}}returnOK;}//FastTransposeSMatrix時間復(fù)雜度為：第36頁，講稿共57頁，2023年5月2日，星期三分析算法FastTransposeSMatrix的時間復(fù)雜度：時間復(fù)雜度為:O(M.nu+M.tu)for(col=1;col<=M.nu;++col)……for(t=1;t<=M.tu;++t)……for(col=2;col<=M.nu;++col)……for(p=1;p<=M.tu;++p)……第37頁，講稿共57頁，2023年5月2日，星期三

三元組順序表又稱有序的雙下標(biāo)法，它的特點(diǎn)是，非零元在表中按行序有序存儲，因此便于進(jìn)行依行順序處理的矩陣運(yùn)算。然而，若需隨機(jī)存取某一行中的非零元，則需從頭開始進(jìn)行查找。2.行邏輯鏈接的順序表typedefstruct{Tripledata[MAXSIZE+1];//非零元三元組表

intrpos[MAXRC+1];//各行第一個非零元的位置表

intmu,nu,tu;}RLSMatrix;//行邏輯鏈接順序表類型在行邏輯鏈接的順序表表示稀疏矩陣時，一些操作的實(shí)現(xiàn)。第38頁，講稿共57頁，2023年5月2日，星期三（1）取值運(yùn)算，給定一組下標(biāo)，求矩陣的元素值voidvalue(RLSMatrixM,intr,intc,ElemType&e){p=M.rpos[r];//第r行第一個非零元的位置

q=…;//第r行最后一個非零元的位置

while(p<=q&&M.data[p].j<c)p++;if(p>q){e=0;return;}if(M.data[p].j==c)e=M.data[p].e;elsee=0;}//value第39頁，講稿共57頁，2023年5月2日，星期三for(i=1;i<=m1;++i)for(j=1;j<=n2;++j){Q[i][j]=0;for(k=1;k<=n1;++k)Q[i][j]+=M[i][k]*N[k][j];}其時間復(fù)雜度為:O(m1×n2×n1)(2)矩陣乘法運(yùn)算:2.1精典乘法運(yùn)算算法：第40頁，講稿共57頁，2023年5月2日，星期三M1002000N=3×44×2Q=M

×N06-1004Q=3×2100010001000A=B=110000003×44×2C=A

×B111111C=3×2第41頁，講稿共57頁，2023年5月2日，星期三M、N和Q的三元組表示分別如下：ije131452-1312ije2221131-2324ije2621-1324M.dataN.dataQ.dataQ[i][j]=第42頁，講稿共57頁，2023年5月2日，星期三

Q初始化;ifQ是非零矩陣{//逐行求積

for(arow=1;arow<=M.mu;++arow){//處理M的每一行

ctemp[]=0;//累加器清零計(jì)算Q中第arow行的積并存入ctemp[]中；將ctemp[]中非零元壓縮存儲到Q.data；

}//forarow}//if

基本思想：…………第43頁，講稿共57頁，2023年5月2日，星期三StatusMultSMatrix(RLSMatrixM,RLSMatrixN,RLSMatrix&Q){//求矩陣乘積Q=M×N,采用行邏輯鏈接存儲表示

if(M.nu!=N.mu)returnERROR;Q.mu=M.mu;Q.nu=N.nu;Q.tu=0;//初始化Q，Q.tu表示現(xiàn)已存入Q中的非零元個數(shù)

if(M.tu*N.tu!=0){//Q是非零矩陣

for(arow=1;arow<=M.mu;++arow){

處理M的每一行

}//forarow}//ifreturnOK;}//MultSMatrix第44頁，講稿共57頁，2023年5月2日，星期三

ctemp[]=0;//當(dāng)前行各元素累加器清零

Q.rpos[arow]=Q.tu+1;//Q的第arow行在Q.data中的位置

if(arow<M.mu)tp=M.rpos[arow+1];else{tp=M.tu+1}for(p=M.rpos[arow];p<tp;++p){

//對當(dāng)前行中每一個非零元給它該乘的元素乘一遍

brow=M.data[p].j;if(brow<N.mu)t=N.rpos[brow+1];else{t=N.tu+1}//t為本行最后一個非零元的下一位

for(q=N.rpos[brow];q<t;++q){ccol=N.data[q].j;//乘積元素在Q中列號

ctemp[ccol]+=M.data[p].e*N.data[q].e;}//forq

處理的每一行M第45頁，講稿共57頁，2023年5月2日，星期三}//求得Q中第crow(=arow)行的非零元for(ccol=1;ccol<=Q.nu;++ccol)//壓縮存儲該行非零元if(ctemp[ccol]){if(++Q.tu>MAXSIZE)returnERROR;Q.data[Q.tu]=（arow,ccol,ctemp[ccol]）;}//if第46頁，講稿共57頁，2023年5月2日，星期三分析上述算法的時間復(fù)雜度累加器ctemp初始化的時間復(fù)雜度為(M.muN.nu)，求Q的所有非零元的時間復(fù)雜度為(M.tuN.tu/N.mu)，進(jìn)行壓縮存儲的時間復(fù)雜度為(M.muN.nu)，總的時間復(fù)雜度就是(M.muN.nu+M.tuN.tu/N.mu)。若M是m行n列的稀疏矩陣，N是n行p列的稀疏矩陣，則M中非零元的個數(shù)M.tu=Mmn，N中非零元的個數(shù)

N.tu=Nnp，相乘算法的時間復(fù)雜度就是(mp(1+nMN))

，當(dāng)M<0.05和N<0.05及n<1000時，相乘算法的時間復(fù)雜度就相當(dāng)于(mp)。第47頁，講稿共57頁，2023年5月2日，星期三

思考：如果兩個稀疏矩陣M和N是可乘的，且M和N都以行邏輯鏈接的三元組順序表進(jìn)行存儲，編寫一個類-C算法，求這兩個矩陣的相乘積Q，Q以二維數(shù)組的形式存儲（即Q不進(jìn)行壓縮）。第48頁，講稿共57頁，2023年5月2日，星期三//-------稀疏矩陣的十字鏈表存儲表示---------typedefstructOLNode{inti,j;Elemtypee;structOLNode*right,*down;}OLNode,*OLink;typedefstruct{OLink*rhead,*chead;//行和列鏈表頭指針向量基址

intmu,nu,tu;}CrossList3.十字鏈表e結(jié)點(diǎn)結(jié)構(gòu)示意圖:ijerightdown第49頁，講稿共57頁，2023年5月2日，星期三30050-100200011314522-1312^^^^^^^第50頁，講稿共57頁，2023年5月2日，星期三3.1創(chuàng)建一個稀疏矩陣的十字鏈表存儲結(jié)構(gòu)基本思想:創(chuàng)建一個稀疏矩陣M的十字鏈表存儲結(jié)構(gòu)的過程就是給M的5個域賦確切值的過程。1）輸入M的行m、列n和非零元的個數(shù)t；2）申請存儲行、列鏈表頭指針的存儲空間；3）建立m+n個空鏈表；4）輸入一個非零元的(行，列，值）；5）產(chǎn)生一個結(jié)點(diǎn)p；并給其i,j,e賦相應(yīng)值；6）將p插在相應(yīng)行的適當(dāng)位置上；7）將p插在相應(yīng)列的適當(dāng)位置上；8）重復(fù)4）、5）、6）、7）步，直到非零元輸入完為止。第51頁，講稿共57頁，2023年5月2日，星期三StatusCreatMatrix_OL(CrossList&M){//創(chuàng)建稀疏矩陣M，采用十字鏈表存儲表示

//if(M)free(M);錯！刪除這一行P104scanf(&m,&n,&t);//輸入行、列和非零元的個數(shù)

M.mu=m;M.nu=n;M.tu=t;if(!(m.rhead=(OLink*)malloc((m+1)*sizeof(Olink)))exit(OVERFLOWER);//0號單元不用

if(!(m.chead=(OLink*)malloc((n+1)*sizeof(Olink)))exit(OVERFLOWER);//0號單元不用

M.rhead[]=NULL;M.chead[]=NULL;//初始化頭指針，