數(shù)組和稀疏矩陣

數(shù)組和稀疏矩陣第1頁(yè)，課件共48頁(yè)，創(chuàng)作于2023年2月5.1.1數(shù)組的基本概念

數(shù)組是n(n＞1)個(gè)相同類型數(shù)據(jù)元素a1,a2,…,an構(gòu)成的有限序列,且該有限序列存儲(chǔ)在一塊地址連續(xù)的內(nèi)存單元中。由此可見,數(shù)組的定義類似于采用順序存儲(chǔ)結(jié)構(gòu)的線性表。第2頁(yè)，課件共48頁(yè)，創(chuàng)作于2023年2月數(shù)組具有以下性質(zhì)：(1)數(shù)組中的數(shù)據(jù)元素?cái)?shù)目固定。一旦定義了一個(gè)數(shù)組,其數(shù)據(jù)元素?cái)?shù)目不再有增減變化。(2)數(shù)組中的數(shù)據(jù)元素具有相同的數(shù)據(jù)類型。(3)數(shù)組中的每個(gè)數(shù)據(jù)元素都和一組惟一的下標(biāo)值對(duì)應(yīng)。(4)數(shù)組是一種隨機(jī)存儲(chǔ)結(jié)構(gòu)。可隨機(jī)存取數(shù)組中的任意數(shù)據(jù)元素。第3頁(yè)，課件共48頁(yè)，創(chuàng)作于2023年2月5.1.2數(shù)組的存儲(chǔ)結(jié)構(gòu)在一維數(shù)組中,一旦a1的存儲(chǔ)地址LOC(a1)確定,并假設(shè)每個(gè)數(shù)據(jù)元素占用k個(gè)存儲(chǔ)單元,則任一數(shù)據(jù)元素ai的存儲(chǔ)地址LOC(ai)就可由以下公式求出：LOC(ai)=LOC(a1)+(i-1)*k(0≤i≤n)上式說明,一維數(shù)組中任一數(shù)據(jù)元素的存儲(chǔ)地址可直接計(jì)算得到,即一維數(shù)組中任一數(shù)據(jù)元素可直接存取,因此,一維數(shù)組是一種隨機(jī)存儲(chǔ)結(jié)構(gòu)。同樣,二維及多維數(shù)組也滿足隨機(jī)存儲(chǔ)特性。第4頁(yè)，課件共48頁(yè)，創(chuàng)作于2023年2月對(duì)于一個(gè)m行n列的二維數(shù)組Am×n,有：將Am*n簡(jiǎn)記為A,A是這樣的一維數(shù)組：A=(a1,a2,…,ai…,am)其中,ai=(ai,1,ai,2,…,ai,n)(1≤j≤m)。第5頁(yè)，課件共48頁(yè)，創(chuàng)作于2023年2月

顯然,二維數(shù)組同樣滿足數(shù)組的定義。一個(gè)二維數(shù)組可以看作是每個(gè)數(shù)據(jù)元素都是相同類型的一維數(shù)組的一維數(shù)組。以此類推,任何多維數(shù)組都可以看作一個(gè)線性表,這時(shí)線性表中的每個(gè)數(shù)據(jù)元素也是一個(gè)線性表。多維數(shù)組是線性表的推廣。第6頁(yè)，課件共48頁(yè)，創(chuàng)作于2023年2月

對(duì)于二維數(shù)組來說,由于計(jì)算機(jī)的存儲(chǔ)結(jié)構(gòu)是線性的,如何用線性的存儲(chǔ)結(jié)構(gòu)存放二維數(shù)組元素就有一個(gè)行／列次序排放問題。以行序?yàn)橹餍虻拇鎯?chǔ)方式：即先存儲(chǔ)第1行,然后緊接著存儲(chǔ)第2行,最后存儲(chǔ)第m行。此時(shí),二維數(shù)組的線性排列次序?yàn)椋篴1,1,a1,2,…,a1,n,a2,1,a2,2,…,a2,n,…,am,1,am,2,…am,n第7頁(yè)，課件共48頁(yè)，創(chuàng)作于2023年2月

對(duì)一個(gè)已知以行序?yàn)橹餍虻挠?jì)算機(jī)系統(tǒng)中,當(dāng)二維數(shù)組第一個(gè)數(shù)據(jù)元素a1,1的存儲(chǔ)地址LOC(a1,1)和每個(gè)數(shù)據(jù)元素所占用的存儲(chǔ)單元k確定后,則該二維數(shù)組中任一數(shù)據(jù)元素ai,j的存儲(chǔ)地址可由下式確定：LOC(ai,j)=LOC(a1,1)+[(i-1)*n+(j-1)]*k其中n為列數(shù)。第8頁(yè)，課件共48頁(yè)，創(chuàng)作于2023年2月

同理可推出在以列序?yàn)橹餍虻挠?jì)算機(jī)系統(tǒng)中有：LOC(ai,j)=LOC(a1,1)+[(j-1)*m+(i-1)]*k其中m為行數(shù)。第9頁(yè)，課件共48頁(yè)，創(chuàng)作于2023年2月

例5.1對(duì)二維數(shù)組floata[5][4]計(jì)算：(1)數(shù)組a中的數(shù)組元素?cái)?shù)目；(2)若數(shù)組a的起始地址為2000,且每個(gè)數(shù)組元素長(zhǎng)度為32位(即4個(gè)字節(jié)),數(shù)組元素a[3][2]的內(nèi)存地址。

第10頁(yè)，課件共48頁(yè)，創(chuàng)作于2023年2月

解：由于C語(yǔ)言中數(shù)組的行、列下界均為0,該數(shù)組行上界為5-1=4,列上界為4-l=3,所以該數(shù)組的元素?cái)?shù)目共有(4-0+1)*(3-0+1)=5*4=20個(gè)。又由于C語(yǔ)言采用行序?yàn)橹餍虻拇鎯?chǔ)方式,則有：LOC(a3,2)=LOC(a0,0)+(i*n+j)*k=2000+(3*4+2)*4=2056第11頁(yè)，課件共48頁(yè)，創(chuàng)作于2023年2月5.1.3特殊矩陣的壓縮存儲(chǔ)特殊矩陣是指非零元素或零元素的分布有一定規(guī)律的矩陣,為了節(jié)省存儲(chǔ)空間,特別是在高階矩陣的情況下,可以利用特殊矩陣的規(guī)律,對(duì)它們進(jìn)行壓縮存儲(chǔ),也就是說,使多個(gè)相同的非零元素共享同一個(gè)存儲(chǔ)單元,對(duì)零元素不分配存儲(chǔ)空間。特殊矩陣的主要形式有對(duì)稱矩陣、對(duì)角矩陣等,它們都是方陣,即行數(shù)和列數(shù)相同。第12頁(yè)，課件共48頁(yè)，創(chuàng)作于2023年2月1.對(duì)稱矩陣的壓縮存儲(chǔ)若一個(gè)n階方陣A[n][n]中的元素滿足ai,j=aj,i(0≤i,j≤n-1),則稱其為n階對(duì)稱矩陣。由于對(duì)稱矩陣中的元素關(guān)于主對(duì)角線對(duì)稱,因此在存儲(chǔ)時(shí)可只存儲(chǔ)對(duì)稱矩陣中上三角或下三角中的元素,使得對(duì)稱的元素共享一個(gè)存儲(chǔ)空間。這樣,就可以將n2個(gè)元素壓縮存儲(chǔ)到個(gè)元素的空間中。不失一般性,我們以行序?yàn)橹餍虼鎯?chǔ)其下三角(包括對(duì)角線)的元素。第13頁(yè)，課件共48頁(yè)，創(chuàng)作于2023年2月

n2個(gè)元素←→n(n+1)/2個(gè)元素

A[0..n-1,0..n-1]←→B[0..n(n+1)/2-1]

a[i][j]←→b[k]k=+ji≥j+ii＜j第14頁(yè)，課件共48頁(yè)，創(chuàng)作于2023年2月上三角矩陣：

k=+j–ii≤j時(shí)i＞j時(shí)第15頁(yè)，課件共48頁(yè)，創(chuàng)作于2023年2月下三角矩陣：

k=

i≥j時(shí)i＜j時(shí)第16頁(yè)，課件共48頁(yè)，創(chuàng)作于2023年2月2.對(duì)角矩陣的壓縮存儲(chǔ)若一個(gè)n階方陣A滿足其所有非零元素都集中在以主對(duì)角線為中心的帶狀區(qū)域中,則稱其為n階對(duì)角矩陣。其主對(duì)角線上下方各有b條次對(duì)角線,稱b為矩陣半帶寬,(2b+1)為矩陣的帶寬。對(duì)于半帶寬為b(0≤b≤(n-1)/2)的對(duì)角矩陣,其|i-j|≤b的元素ai,j不為零,其余元素為零。下圖所示是半帶寬為b的對(duì)角矩陣示意圖。第17頁(yè)，課件共48頁(yè)，創(chuàng)作于2023年2月半帶寬為b的對(duì)角矩陣

第18頁(yè)，課件共48頁(yè)，創(chuàng)作于2023年2月當(dāng)b＝1時(shí)稱為三對(duì)角矩陣。其壓縮地址計(jì)算公式如下：k=2i+j

A←→B

a[i][j]←→b[k]第19頁(yè)，課件共48頁(yè)，創(chuàng)作于2023年2月

例5.2按行優(yōu)先順序和按列優(yōu)先順序列出四維數(shù)組A[2][2][2][2]所有元素在內(nèi)存中的存儲(chǔ)次序。第20頁(yè)，課件共48頁(yè)，創(chuàng)作于2023年2月

解：按行優(yōu)先的存儲(chǔ)次序:

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]第21頁(yè)，課件共48頁(yè)，創(chuàng)作于2023年2月

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

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]第22頁(yè)，課件共48頁(yè)，創(chuàng)作于2023年2月

例5.3對(duì)于二維數(shù)組A[m][n],其中m≤80,n≤80,先讀入m和n,然后讀該數(shù)組的全部元素,對(duì)如三種情況分別編寫相應(yīng)函數(shù):(1)求數(shù)組A靠邊元素之和;(2)求從A[0][0]開始的行、列互不相鄰的各元素之和;(3)當(dāng)m=n時(shí),分別求兩條對(duì)角線上的元素之和,否則打印出m≠n的信息。第23頁(yè)，課件共48頁(yè)，創(chuàng)作于2023年2月

解：(1)對(duì)應(yīng)算法如下：

voidproc1(ElemTypeA[][n]){ints=0,i,j;for(i=0;i<m;i++)/*第一列*/s=s+A[i][0];for(i=0;i<m;i++)/*最后一列*/s=s+A[i][n-1];for(j=0;j<n;j++)/*第一行*/s=s+A[0][j];for(j=0;j<n;j++)/*最后一行*/s=s+A[m-1][j];s=s-A[0][0]-A[0][n-1]-A[m-1][0]-A[m-1][n-1];/*減去4個(gè)角的重復(fù)元素值*/printf("s=%d\n",s);}第24頁(yè)，課件共48頁(yè)，創(chuàng)作于2023年2月(2)對(duì)應(yīng)算法如下：

voidproc2(maxixA){ ints=0,i=0,j=0; do {do { s=s+A[i][j]; j=j+2; /*跳過一列*/ }while(j<n); i=i+1; /*下一行*/if(j==0)j=1;elsej=0; }while(i<m); printf("s=%d\n",s);}第25頁(yè)，課件共48頁(yè)，創(chuàng)作于2023年2月(3)對(duì)應(yīng)算法如下：voidproc3(maxixA){ inti,s=0; if(m!=n)printf("m≠n"); else {for(i=0;i<m;i++)s=s+A[i][i];/*求第一條對(duì)角線之和*/for(i=0;i<n;i++)s=s+A[n-i-1][i];/*累加第二條對(duì)角線之和*/s-=A[n/2][n/2];printf("s=%d\n",s);}}第26頁(yè)，課件共48頁(yè)，創(chuàng)作于2023年2月5.2稀疏矩陣

一個(gè)階數(shù)較大的矩陣中的非零元素個(gè)數(shù)s相對(duì)于矩陣元素的總個(gè)數(shù)t十分小時(shí),即s<<t時(shí),稱該矩陣為稀疏矩陣。例如一個(gè)100×100的矩陣,若其中只有100個(gè)非零元素,就可稱其為稀疏矩陣。第27頁(yè)，課件共48頁(yè)，創(chuàng)作于2023年2月5.2.1稀疏矩陣的三元組表示稀疏矩陣的壓縮存儲(chǔ)方法是只存儲(chǔ)非零元素。由于稀疏矩陣中非零元素的分布沒有任何規(guī)律,所以在存儲(chǔ)非零元素時(shí)還必須同時(shí)存儲(chǔ)該非零元素所對(duì)應(yīng)的行下標(biāo)和列下標(biāo)。這樣稀疏矩陣中的每一個(gè)非零元素需由一個(gè)三元組(i,j,ai,j)惟一確定,稀疏矩陣中的所有非零元素構(gòu)成三元組線性表。第28頁(yè)，課件共48頁(yè)，創(chuàng)作于2023年2月假設(shè)有一個(gè)6×7階稀疏矩陣A(為圖示方便,我們所取的行列數(shù)都很小),A中元素如下圖所示。則對(duì)應(yīng)的三元組線性表為：((0,2,1),(1,1,2),(2,0,3),(3,3,5),(4,4,6),(5,5,7),(5,6,4))一個(gè)稀疏矩陣A第29頁(yè)，課件共48頁(yè)，創(chuàng)作于2023年2月若把稀疏矩陣的三元組線性表按順序存儲(chǔ)結(jié)構(gòu)存儲(chǔ),則稱為稀疏矩陣的三元組順序表。則三元組順序表的數(shù)據(jù)結(jié)構(gòu)可定義如下：第30頁(yè)，課件共48頁(yè)，創(chuàng)作于2023年2月#defineMaxSize100/*矩陣中非零元素最多個(gè)數(shù)*/typedefstruct{intr; /*行號(hào)*/intc; /*列號(hào)*/ElemTyped; /*元素值*/}TupNode; /*三元組定義*/typedefstruct{introws; /*行數(shù)值*/intcols; /*列數(shù)值*/intnums; /*非零元素個(gè)數(shù)*/TupNodedata[MaxSize];}TSMatrix;/*三元組順序表定義*/第31頁(yè)，課件共48頁(yè)，創(chuàng)作于2023年2月

其中,data域中表示的非零元素通常以行序?yàn)橹餍蝽樞蚺帕?它是一種下標(biāo)按行有序的存儲(chǔ)結(jié)構(gòu)。這種有序存儲(chǔ)結(jié)構(gòu)可簡(jiǎn)化大多數(shù)矩陣運(yùn)算算法。下面的討論假設(shè)data域按行有序存儲(chǔ)。第32頁(yè)，課件共48頁(yè)，創(chuàng)作于2023年2月(1)從一個(gè)二維矩陣創(chuàng)建其三元組表示以行序方式掃描二維矩陣A,將其非零的元素插入到三元組t的后面。算法如下：voidCreatMat(TSMatrix&t,ElemTypeA[M][N]){ inti,j; t.rows=M;t.cols=N;t.nums=0; for(i=0;i<M;i++) {for(j=0;j<N;j++) if(A[i][j]!=0)/*只存儲(chǔ)非零元素*/{t.data[t.nums].r=i;t.data[t.nums].c=j; t.data[t.nums].d=A[i][j];t.nums++; } }}第33頁(yè)，課件共48頁(yè)，創(chuàng)作于2023年2月(2)三元組元素賦值先在三元組t中找到適當(dāng)?shù)奈恢胟,將k～t.nums個(gè)元素后移一位,將指定元素x插入到t.data[k]處。算法如下：intValue(TSMatrix&t,ElemTypex,intrs,intcs){inti,k=0;if(rs>=t.rows||cs>=t.cols)return0;while(k<t.nums&&rs>t.data[k].r)k++; /*查找行*/while(k<t.nums&&cs>t.data[k].c)k++; /*查找列*/第34頁(yè)，課件共48頁(yè)，創(chuàng)作于2023年2月if(t.data[k].r==rs&&t.data[k].c==cs) t.data[k].d=x;/*存在這樣的元素else/*不存在這樣的元素時(shí)插入一個(gè)元素*/{for(i=t.nums-1;i>k;i--)/*元素后移*/{t.data[i+1].r=t.data[i].r;t.data[i+1].c=t.data[i].c;t.data[i+1].d=t.data[i].d; } t.data[k].r=rs;t.data[k].c=cs;t.data[k].d=x; t.nums++;}return1;}第35頁(yè)，課件共48頁(yè)，創(chuàng)作于2023年2月(3)將指定位置的元素值賦給變量先在三元組t中找到指定的位置,將該處的元素值賦給x。算法如下：intAssign(TSMatrixt,ElemType&x,intrs,intcs){intk=0;if(rs>=t.rows||cs>=t.cols)return0;while(k<t.nums&&rs>t.data[k].r)k++;while(k<t.nums&&cs>t.data[k].c)k++;if(t.data[k].r==rs&&t.data[k].c==cs){x=t.data[k].d;return1;}elsereturn0;}第36頁(yè)，課件共48頁(yè)，創(chuàng)作于2023年2月(4)輸出三元組從頭到尾掃描三元組t,依次輸出元素值。算法如下：voidDispMat(TSMatrixt){inti; if(t.nums<=0)return; printf(“\t%d\t%d\t%d\n",t.rows,t.cols,t.nums); printf("------------------\n"); for(i=0;i<t.nums;i++) printf("\t%d\t%d\t%d\n",t.data[i].r,t.data[i].c,t.data[i].d);}第37頁(yè)，課件共48頁(yè)，創(chuàng)作于2023年2月(5)矩陣轉(zhuǎn)置對(duì)于一個(gè)m×n的矩陣Am×n,其轉(zhuǎn)置矩陣是一個(gè)n×m的矩陣。設(shè)為Bn×m,滿足ai,j=bj,i,其中1≤i≤m,1≤j≤n。其完整的轉(zhuǎn)置算法如下：voidTranTat(TSMatrixt,TSMatrix&tb){intp,q=0,v; /*q為tb.data的下標(biāo)*/tb.rows=t.cols;tb.cols=t.rows;tb.nums=t.nums;if(t.nums!=0){for(v=0;v<t.cols;v++) for(p=0;p<t.nums;p++) /*p為t.data的下標(biāo)*/第38頁(yè)，課件共48頁(yè)，創(chuàng)作于2023年2月if(t.data[p].c==v){ tb.data[q].r=t.data[p].c; tb.data[q].c=t.data[p].r; tb.data[q].d=t.data[p].d; q++;}}}第39頁(yè)，課件共48頁(yè)，創(chuàng)作于2023年2月以上算法的時(shí)間復(fù)雜度為O(t.cols*t.nums),而將二維數(shù)組存儲(chǔ)在一個(gè)m行n列矩陣中時(shí),其轉(zhuǎn)置算法的時(shí)間復(fù)雜度為O(m*n)。最壞情況是當(dāng)稀疏矩陣中的非零元素個(gè)數(shù)t.nums和m*n同數(shù)量級(jí)時(shí),上述轉(zhuǎn)置算法的時(shí)間復(fù)雜度就為O(m*n2)。對(duì)其他幾種矩陣運(yùn)算也是如此?？梢?常規(guī)的非稀疏矩陣應(yīng)采用二維數(shù)組存儲(chǔ),只有當(dāng)矩陣中非零元素個(gè)數(shù)s滿足s<<m*n時(shí),方可采用三元組順序表存儲(chǔ)結(jié)構(gòu)。這個(gè)結(jié)論也同樣適用于下面要討論的十字鏈表。第40頁(yè)，課件共48頁(yè)，創(chuàng)作于2023年2月5.2.2稀疏矩陣的十字鏈表表示

十字鏈表為稀疏矩陣的每一行設(shè)置一個(gè)單獨(dú)鏈表,同時(shí)也為每一列設(shè)置一個(gè)單獨(dú)鏈表。這樣稀疏矩陣的每一個(gè)非零元素就同時(shí)包含在兩個(gè)鏈表中,即每一個(gè)非零元素同時(shí)包含在所在行的行鏈表中和所在列的列鏈表中。這就大大降低了鏈表的長(zhǎng)度,方便了算法中行方向和列方向的搜索,因而大大降低了算法的時(shí)間復(fù)雜度。第41頁(yè)，課件共48頁(yè)，創(chuàng)作于2023年2月

(a)結(jié)點(diǎn)結(jié)構(gòu)(b)頭結(jié)點(diǎn)結(jié)構(gòu)對(duì)于一個(gè)m×n的稀疏矩陣,每個(gè)非零元素用一個(gè)結(jié)點(diǎn)表示,結(jié)點(diǎn)結(jié)構(gòu)可以設(shè)計(jì)成如下圖(a)所示結(jié)構(gòu)。其中i,j,value分別代表非零元素所在的行號(hào)、列號(hào)和相應(yīng)的元素值；down