[工學(xué)]西北大學(xué)：數(shù)據(jù)結(jié)構(gòu)第5章 數(shù)組和廣義表-文庫(kù)吧
2025-09-14 19:55 本頁(yè)面
【正文】 推廣，就可以容易地得到ｎ維數(shù)組中任意元素 aj1j2…jn 的存儲(chǔ)地址的計(jì)算公式。 Loc[j1， j2， …j n]=Loc[c1， c2， … ， ]+? αi (jici) i=1 n 其中 αi =l ? (dkck+1) （ 1≤i≤n） k=i+1 n 返回主目錄 特殊矩陣的壓縮存儲(chǔ) 特殊矩陣壓縮存儲(chǔ)的壓縮原則是：對(duì)有規(guī)律的元素和值相同的元素只分配一個(gè)存儲(chǔ)單元，對(duì)于零元素不分配空間。 三角矩陣 三角矩陣大體分為：下三角矩陣、上三角矩陣和對(duì)稱(chēng)矩陣。對(duì)于一個(gè) n階矩陣 A來(lái)說(shuō)：若當(dāng) ij時(shí)，有aij=0，則稱(chēng)此矩陣為下三角矩陣；若當(dāng) ij時(shí)，有aij=0，則此矩陣稱(chēng)為上三角矩陣；若矩陣中的所有元素均滿(mǎn)足 aij=aji，則稱(chēng)此矩陣為對(duì)稱(chēng)矩陣。 返回主目錄 對(duì)于下三角矩陣，按 “ 行序?yàn)橹餍?” 進(jìn)行存儲(chǔ)，得到的序列為： a11,a21,a22,a31,a32,a33…a n1,an2…a nn。由于下三角矩陣的元素個(gè)數(shù)為 n(n+1)/2，所以可壓縮存儲(chǔ)到一個(gè)大小為 n(n+1)/2的一維數(shù)組中。下三角矩陣中元素 aij(ij)，在一維數(shù)組 A中的位置為： LOC[ i ,j]= LOC[1,1]+ i (i 1)/2+ j1 下三角矩陣： A= a11 a21 a22 a31 a32 a33 ┆ ┆ ┆ ┆ an1 an2 an3 … ann 返回主目錄 同樣 ， 對(duì)于上三角矩陣 ， 也可以將其壓縮存儲(chǔ)到一個(gè)大小為 n(n+1)/2的一維數(shù)組 C中 。 其中元素 aij(ij)在數(shù)組 C中的存儲(chǔ)位置為： Loc[i,j]= Loc[1,1]+j(j 1)/2+ i1 對(duì)于對(duì)稱(chēng)矩陣，因其元素滿(mǎn)足 aij=aji，我們可以為每一對(duì)相等的元素分配一個(gè)存儲(chǔ)空間，即只存下三角（或上三角）矩陣，從而將 n2個(gè)元素壓縮到n(n+1)/2個(gè)空間中。 返回主目錄 帶狀矩陣 帶狀矩陣 ：在矩陣 A中，所有的非零元素都集中在以主對(duì)角線(xiàn)為中心的帶狀區(qū)域中。最常見(jiàn)的是三對(duì)角帶狀矩陣。 An n = a11 a12 a21 a22 a23 a32 a33 a34 a43 a44 a45 … … … … … 特點(diǎn) : i=1, j=1,2。 當(dāng) 1in， j=i1, i, i+1 i=n, j=n1, n。 時(shí)， aij非零，其他元素均為零。 返回主目錄 三對(duì)角帶狀矩陣的壓縮存儲(chǔ)，以行序?yàn)橹餍蜻M(jìn)行存儲(chǔ)，并且只存儲(chǔ)非零元素。其方法為： 1. 確定存儲(chǔ)該矩陣所需的一維向量空間的大小 從三對(duì)角帶狀矩陣中可看出：除第一行和最后一行只有兩個(gè)元素外，其余各行均有 3個(gè)非零元素。由此可得到一維向量所需的空間大小為： 3n2。 2. 確定非零元素在一維數(shù)組空間中的位置 LOC[i , j] = LOC[1,1]+3 （ i1） 1+ji+1 =LOC[1,1]+2(i1)+j1 返回主目錄 稀疏矩陣 稀疏矩陣 ：指矩陣中大多數(shù)元素為零的矩陣。一般地，當(dāng)非零元素個(gè)數(shù)只占矩陣元素總數(shù)的 25%—30%,或低于這個(gè)百分?jǐn)?shù)時(shí)，我們稱(chēng)這樣的矩陣為稀疏矩陣。 0 0 3 0 0 15 12 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 M6 7= 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 0 15 0 0 7 0 0 0 N6 7= 返回主目錄 1. 稀疏矩陣的三元組表表示法 對(duì)于稀疏矩陣的壓縮存儲(chǔ)要求在存儲(chǔ)非零元素的同時(shí)，還必須存儲(chǔ)該非零元素在矩陣中所處的行號(hào)和列號(hào)。我們將這種存儲(chǔ)方法叫做稀疏矩陣的三元組表示法。 row col value 該非零元素所在的行號(hào) 該非零元素所在的列號(hào) 該非零元素的值 每個(gè)非零元素在一維數(shù)組中的表示形式如圖所示： 返回主目錄 三元組表的類(lèi)型說(shuō)明： define MAXSIZE 1000 /*非零元素的個(gè)數(shù)最多為 1000*/ typedef struct {int row, col。 /*該非零元素的行下標(biāo)和列下標(biāo) */ ElementType e； /*該非零元素的值 */ }Triple。 typedef struct {Triple data[MAXSIZE+1]。 /* 非零元素的三元組表 。 data[0]未用 */ int m, n, len。 /*矩陣的行數(shù) 、 列數(shù)和非零元素的個(gè)數(shù) */ }TSMatrix； 返回主目錄 1）用三元組表實(shí)現(xiàn)稀疏矩陣的轉(zhuǎn)置運(yùn)算 矩陣轉(zhuǎn)置：指變換元素的位置，把位于（ row， col）位置上的元素?fù)Q到（ col ， row）位置上，也就是說(shuō)，把元素的行列互換。 采用矩陣的正常存儲(chǔ)方式時(shí)，實(shí)現(xiàn)矩陣轉(zhuǎn)置的經(jīng)典算法如下： Void TransMatrix（ ElementType source[n][m], ElementType dest[m][n]） {/*Source和 dest分別為被轉(zhuǎn)置的矩陣和轉(zhuǎn)置后的矩陣（用二維數(shù)組表示） */ int i, j。 for(i=0。im。i++) for (j=0。j n。j++) dest[i][ j]=source[j] [i] 。 } 返回主目錄 實(shí)現(xiàn)轉(zhuǎn)置的簡(jiǎn)單方法： ① 矩陣 source的三元組表 A的行、列互換就可以得到B中的元素，如圖 ： ② 為了保證轉(zhuǎn)置后的矩陣的三元組表 B也是以 “ 行序?yàn)橹餍?” 進(jìn)行存放，則需要對(duì)行、列互換后的三元組 B，按 B的行下標(biāo)（即 A的列下標(biāo)）大小重新排序。 B （ i， j， x） ———— （ j， i， x） A 兩種處理轉(zhuǎn)置算法如下： 返回主目錄 算法一、 void TransposeTSMatrix(TSMatrix A, TSMatrix * B) { /*把矩陣 A轉(zhuǎn)置到 B所指向的矩陣中去 。 矩陣用三元組表表示 */ int i , j, k 。 Bm= 。 Bn= 。 Blen= 。 if(Blen0) { j=1。 for(k=1。 k=。 k++) for(i=1。 i=。 i++) if([i].col==k) { Bdata[j].row=[i].col Bdata[j].col=[i].row。 Bdata[j].e=[i].e。 j++。 } } } 返回主目錄 算法二、 FastTransposeTSMatrix (TSMatrix A, TSMatrix * B) { /*基于矩陣的三元組表示 ， 采用快速轉(zhuǎn)置法 ， 將矩陣 A轉(zhuǎn)置為 B所指的矩陣 */ int col , t , p， q。 int num[MAXSIZE], position[MAXSIZE] 。 Blen= 。 Bn= 。 Bm= 。 if(Blen) {for(col=1。col=。col+
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號(hào)-1