第四章數(shù)組和矩陣

1、第四章 數(shù)組和矩陣 -蔣菲菲主主 要要 內(nèi)內(nèi) 容容1 、數(shù)組的定義數(shù)組的定義 2 、數(shù)組的順序存儲和實現(xiàn)數(shù)組的順序存儲和實現(xiàn) 3、 特殊矩陣的壓縮存儲特殊矩陣的壓縮存儲 1） 三角矩陣三角矩陣 2） 稀疏矩陣稀疏矩陣 數(shù)組的定義 從邏輯結構上看，數(shù)組可以看成是一般線性表的擴充。二維數(shù)組可以看成是“其數(shù)據(jù)元素是一維數(shù)組（線性表）”的線性表。以二維數(shù)組為例： 二維數(shù)組中的每個元素都受兩個線性關系的約束即行關系和列關系，在每個關系中，每個元素aij都有且僅有一個直接前趨，都有且僅有一個直接后繼。 在行關系中在行關系中 a ij直接前趨是 aij-1 a ij直接后繼是 aij+1在列關系中在列關系中

2、 a ij直接前趨是 ai-1j a ij直接后繼是 ai+1j 數(shù)組的特性數(shù)組的特性 二維數(shù)組可看成一個線性表二維數(shù)組可看成一個線性表A=(a0，a1，ap) (p=m-1或或n-1)，其中，其中aj是一個是一個列向量列向量形式的線性表：形式的線性表： aj=（a0j，a1j，am-1,j），）， 0jn-1 或或ai是一個行向量形式的線性表：是一個行向量形式的線性表： ai=（ai0，ai1，ai,n-1），）， 0im-1 a00 a01 a0,n-1a10 a11 a1,n-1 am-1,0 am-1,1 am-1,n-1a00 a01 a0,n-1a10 a11 a1,n-1 am-

3、1,0 am-1,1 am-1,n-1 a0 a1 apa0a1 ap 數(shù)組的順序存儲和實現(xiàn) 實際上數(shù)組是一組有固定個數(shù)的元素的集合。也就是說，一旦定義了數(shù)組的維數(shù)和每一維的上下限，數(shù)組中元素的的個數(shù)就固定了。例如二維數(shù)組A34，它有3行，4列，即由12個元素組成。由于這個性質，使得對數(shù)組的操作不象對線性表的操作那樣，不可以在表中任意一個合法的位置插入或刪除一個元素 對于數(shù)組的操作一般只有兩類：1） 獲得特定位置的元素值；2） 修改特定位置的元素值。 一維數(shù)組在內(nèi)存中的存放很簡單，只要順序存放在連續(xù)的內(nèi)存單元即可。 二維數(shù)組，如何用順序結構表示？內(nèi)存地址是一維的，而數(shù)組是二維的，要將二維數(shù)組擠

4、入一維的地址中，有兩個策略： 以行為主序（C語言使用） 以列為主序a00 a01 a0n-1a10 a11 a1n-1am-10 am-11 am-1n-1a00 a01 a0,n-1a10 a11 a1,n-1 am-1,0 am-1,1 am-1,n-1 am-1,n-1 am-1,1 am-1,0 a1,n-1 a11 a10 a0,n-1 a01 a00 am-1,n-1 a1,n-1 a0,n-1 am-1,1 a11 a01 am-1,0 a10 a00a00 a01 a0,n-1a10 a11 a1,n-1 am-1,0 am-1,1 am-1,n-1行行優(yōu)優(yōu)先先順順序序列列優(yōu)優(yōu)

5、先先順順序序數(shù)組的順序表示與實現(xiàn)數(shù)組的順序表示與實現(xiàn) 對于數(shù)組A，一旦給定其維數(shù)n及各維長度bi（1in），則該數(shù)組中元素的個數(shù)是固定的，不可以對數(shù)組做插入和刪除操作，不涉及移動元素操作，因此對于數(shù)組而言，采用順序存儲法比較合適。 以二維數(shù)組Amn為例，假設每個元素只占一個存儲單元，“以行為主”存放數(shù)組，下標從1開始，首元素a11的地址為Loc1,1，求任意元素aij的地址。aij是排在第i，第j列，并且前面的第i-1行有n*（i-1）個元素，第行第j個前面還有個元素。由此得到如下地址計算公式： Loci,j=Loc1,1+n(i-1)+(j-1) 以列為主：Loci,j=Loc1,1+m(j

6、-1)+(i-1)例2：已知二維數(shù)組Am,m按行存儲的元素地址公式是： Loc(aij)= Loc(a11)+(i-1)*m+(j-1)*K , 按列存儲的公式是？ Loc(aij)=Loc(a11)+(j-1)*m+(i-1)*K （盡管是方陣，但公式仍不同）（盡管是方陣，但公式仍不同）例1：一個二維數(shù)組A，行下標的范圍是1到6，列下標的范圍是0到7，每個數(shù)組元素用相鄰的6個字節(jié)存儲，存儲器按字節(jié)編址。那么，這個數(shù)組的體積是 個字節(jié)。 288例3：設數(shù)組a60 70的首地址為2048，每個元素占2個存儲單元，若以 列序為主序順序存儲，則元素a3258的存儲地址為 。8950LOC(aij)=

7、LOC(ac1，c2)+(j-c2)*(d1-c1+1)+i-c1)*L得：LOC(a32,58)=2048+(58-1)*(60-1+1)+32-1)*28950答：請注意審題！答：請注意審題！利用列優(yōu)先通式：答：答： Volume=m*n*L=(6-1+1)*(7- 0 +1)*6=48*6=288 特殊矩陣的壓縮存儲 有些高階矩陣中，非零元素非常少（遠小于mn），此時若仍采用二維數(shù)組順序存放就不合適了，因為很多存儲空間存儲的都是0，只有很少的一些空間存放的是有效數(shù)據(jù)，這將造成存儲單元很大的浪費。另外，還有一些矩陣其元素的分布有一定規(guī)律，我們可以利用這些規(guī)律，只存儲部分元素，從而提高存儲空

8、間的利用率。上述矩陣叫做特殊矩陣。 為了節(jié)省空間，對這類矩陣進行壓縮存儲 壓縮原則是：對有規(guī)律的元素和值相同的元素只分配一個存儲空間，對于零元素不分配空間。 1、三角矩陣 三角矩陣大體分為三類 對于一個n階矩陣A來說： 下三角矩陣：當ij時，有aij=C(典型C=0) 對稱矩陣：矩陣中的所有元素均滿足aij=aji下三角矩陣 對于下三角矩陣的壓縮存儲，我們只存儲下三角的非零元素，對于零元素則不存。我們按“行序為主序”進行存儲，得到的序列是a11,a21,a22,a31,a32,a33an1,an2ann。由于下三角矩陣的元素個數(shù)為n(n+1)/2：第1行：1個第2行：2個第3行：3個第n行：n

9、個1+2+3+n=n(n+1)/2下三角矩陣的壓縮形式：a11 a21a22 a31 a32 a33 ann1 2 3 4 5 6 n(n+1)/2 下三角矩陣中元素aij(ij)，在一維數(shù)組A中的位置為：Loc i ,j=Loc1,1 +前i-1行非零元素個數(shù)+第i行中aij前非零元素個數(shù) 前i-1行元素個數(shù)=1+2+3+4+ +（i-1）= i (i -1)/2， 第i行中aij前非零元素個數(shù)=j-1，所以有： LOC i ,j= LOC1,1+ i (i -1)/2+ j-1 同樣，對于上三角矩陣對于上三角矩陣，也可以將其壓縮存儲到一個大小為n(n+1)/2的一維數(shù)組C中。其中元素aij

10、(i1時，元素時，元素aij=0。 K=0 1 2 3 4 5 3n-2 3n-1 數(shù)組數(shù)組a中的元素中的元素k與三對角帶狀矩陣中的元素與三對角帶狀矩陣中的元素aij存在存在一一一一對應關系對應關系，在，在aij之前有之前有i-1行行,共有共有3*(i-1)-1個非零元素，在第個非零元素，在第i行，有行，有j-i+1個非零元素，這樣，非零元素個非零元素，這樣，非零元素aij的地址為：的地址為： LOC(i,j)=LOC(1,1)+3*(i-1)-1+(j-i+1)*d =LOC(1,1)+(2i+j-3)*d 2稀疏矩陣 1 什么是稀疏矩陣 有較多值相同元素或較多零元素，且值相同元素或者零元素

11、分布沒有一定規(guī)律的矩陣稱為稀疏矩陣。例A = 0 12 9 0 0 0 0 0 0 0 0 0 0 0-3 0 0 0 0 14 0 0 0 24 0 0 0 0 0 18 0 0 0 0 015 0 0 -7 0 0 0A有42（67）個元素有8個非零元素如何進行稀疏矩陣的壓縮存儲？2、稀疏矩陣的壓縮存儲 對于稀疏矩陣的壓縮存儲，我們采取只存儲非零元素的方法。但由于稀疏矩陣中非零元素aij的分布一般是沒有規(guī)律的，因此，對于稀疏矩陣的壓縮存儲就要求在存儲非零元素的同時，還必須存儲一些輔助信息，即該非零元素在矩陣中所處的行號和列號。我們將這種存儲方法叫做稀疏矩陣的三元組表示法 把這些三元組按“行

12、序為主序”用一維數(shù)組進行存放，即將j矩陣的任何一行的全部非零元素的三元組按列號遞增存放。由此得到矩陣M，N的三元組表， 2 稀疏矩陣的壓縮存儲（只討論有較多零元素矩陣的壓縮存儲）1）三元組表（i, j, aij )A=( (0,1,12), (0,2,9), (2,0,-3),(2,5,14), (3,2,24), (4,1,18), (5,0,15), (5,3,-7) )加上行、列數(shù)6，7 A = 0 12 9 0 0 0 0 0 0 0 0 0 0 0-3 0 0 0 0 14 0 0 0 24 0 0 0 0 0 18 0 0 0 0 015 0 0 -7 0 0 0表示非零元的三元組

13、2）三元組順序表 假設以順序存儲結構來表示三元組表，則可得稀疏矩陣的一種壓縮存儲方式我們稱之為三元組順序表。三元組線性表結點的類型定義#define elemtype int#define MAXSIZE 100 /*非零元素的個數(shù)最多為100*/ typedef struct node int row, col; /*該非零元素的行下標和列下標*/ elemtype e； /*該非零元素的值*/ xnode;順序存儲的稀疏矩陣用C語言定義： typedef struct matrix xnode dataMAXSIZE; /* 非零元素的三元組表*/ int m, n, len; /*矩陣的

14、行數(shù)、列數(shù)和非零元素的個數(shù)*/smatrix；用于存儲非零元三元組的結構 A的三元組順序表圖示 A = 0 12 9 0 0 0 0 0 0 0 0 0 0 0-3 0 0 0 0 14 0 0 0 24 0 0 0 0 0 18 0 0 0 0 015 0 0 -7 0 0 0例如 ma1.row=0, ma1.col=1, ma1.value=12row col value0123456782 0 -32 0 -35 0 155 0 150 1 120 1 124 1 184 1 180 2 90 2 93 2 243 2 245 3 -75 3 -72 5 142 5 146 7 86

15、7 8 3 ) 轉置運算算法 轉置運算是一種最常用的矩陣運算。對于一個 m 行 n 列的矩陣 A，它的轉置矩陣 B 是一個n行m列的矩陣。例如，下圖中的矩陣A和B互為轉置矩陣。 A = 0 12 9 0 0 0 0 0 0 0 0 0 0 0-3 0 0 0 0 14 0 0 0 24 0 0 0 0 0 18 0 0 0 0 015 0 0 -7 0 0 0 B = 0 0 -3 0 0 1512 0 0 0 18 0 9 0 0 24 0 0 0 0 0 0 0 -7 0 0 0 0 0 0 0 0 14 0 0 0 0 0 0 0 0 0 A第第0 0 列列第一列第一列 第二列第二列第三

16、列第三列 第四列第四列第五列第五列 第六列第六列 . . B B第第0 0 行行第一行第一行 第二行第二行第三行第三行 第四行第四行第五行第五行 第六行第六行 . .轉置運算算法矩陣 B矩陣 A分析：分析：（1 1）將矩陣的行列數(shù)）將矩陣的行列數(shù)的值交換的值交換（2 2）將每一個三元組）將每一個三元組的的i i 和和 j j相互調(diào)換相互調(diào)換（3 3）重排三元組之間）重排三元組之間的次序的次序row col value0123456782 0 -32 0 -35 0 155 0 150 1 120 1 124 1 184 1 180 2 90 2 93 2 243 2 245 3 -75 3 -

17、72 5 142 5 146 7 86 7 8row colv alue 0123456781 0 121 0 123 5 -73 5 -70 2 -30 2 -32 3 242 3 240 5 150 5 152 0 92 0 95 2 145 2 141 4 181 4 187 6 87 6 8轉置運算算法轉置運算算法按照A的列序來進行轉換的基本思想 對 a 從頭至尾掃描： 第一次掃描時，將 a 中列號為0的所有元組交換行列值后，依次賦值到 b 中 第二次掃描時，將 ma 中列號為1的所有元組交換行列值后，依次賦值到 mb 中 依此類推，直至將 ma 的所有三元組賦值到 mb 中i j v

18、0 1 120 2 92 0 -32 5 143 2 244 1 185 0 155 3 -7i j v2 0 -31 4 180 2 -35 0 150 5 150 1 121 0 124 1 180 2 92 0 93 2 242 3 245 3 -73 5 -72 5 145 2 14A矩陣B矩陣對A六次掃描完成轉置運算第一次掃描查第一次掃描查找第找第0 0列元素列元素第一次掃第一次掃描結束描結束第二次掃第二次掃描結束描結束第二次掃描查第二次掃描查找第找第1 1列元素列元素第三次掃描查第三次掃描查找第找第2 2列元素列元素第四次掃描查第四次掃描查找第找第3 3列元素列元素第五次掃描查第五

19、次掃描查找第找第4 4列元素列元素第六次掃描查第六次掃描查找第找第5 5列元素列元素轉置運算算法圖示0123456786 7 87 6 8int transpose(smatrix a) /*a轉置為b*/ smatrix b; int cols,m,k,n=0;if(a.term=0)return(0);b.row=a.col; b.col=a.row; b.term=a.term;for(cols=0;colsa.col;cols+) /*按列號掃描*/for(m=0;ma.term;m+) /*對三元組掃描*/if(a.datam.j=cols) /*進行轉置*/ b.datan.i=a

20、.datam.j;b.datan.j=a.datam.i;b.datan.e=a.datam.e;n+; printf(n轉置后的矩陣為:n);for(k=0;ka.term;k+)printf(%5d%5d%5dn,b.datak.i,b.datak.j,b.datak.e); void main() int s; smatrix a;printf(n請輸入a得行數(shù)、列數(shù)以及非零的個數(shù):n);scanf(%d%d%d,&a.row,&a.col,&a.term);printf(n請輸入轉置前的三元組:n);for(s=0;sa.term;s+)scanf(%d%d%d

21、,&a.datas.i,&a.datas.j,&a.datas.e);transpose(a); 時間復雜度分析時間復雜度分析 算法的基本操作為將 a 中的三元組賦值到 b，是在兩個循環(huán)中完成的，故算法的時間復雜度為 O(n t) ), 其中n 為A矩陣的列數(shù), t為非0元素個數(shù)。 當非零元的個數(shù) t 和矩陣元素個數(shù)mn 同數(shù)量級時，即 t m n ，轉置運算算法的時間復雜度為O（ m m n）。由此可見：在這種情況下，用三元組順序表存儲矩陣，雖然可能節(jié)省了存儲空間，但時間復雜度提高了，因此算法僅適于 t m m n n 的情況。 該算法效率不高的原因是：對為實現(xiàn) A 到 B 的轉置，該算法對 a 進行了多次掃描。其特點是：以B矩陣的三元組為中心，在 A 矩陣的三元組中通盤查找合適的結點置入 bk 中 經(jīng)典算法Void transport(enm,elemtype destmn)int I,j;for(i=o;im;i+)for(j=0;jn;j+)destij=sourceji;二、稀疏矩陣的鏈式存儲結構-十字鏈表 用三元組表法表示的稀疏矩陣，比起用二維數(shù)組存儲，節(jié)約了空間.但是，在進行矩陣加法、減法和乘法等運算