數(shù)據(jù)結(jié)構(gòu)課件第5章數(shù)組和廣義表-在線瀏覽
2025-06-16 08:39本頁(yè)面
【正文】 l hc k ji h g bfe dc b a 若一個(gè) n 階矩陣 M 中的元素滿(mǎn)足下述性質(zhì) 1. 對(duì)稱(chēng)矩陣 aij = aji 1 ≤ i， j ≤ n 則稱(chēng)為 n 階對(duì)稱(chēng)矩陣 。 假設(shè)以行序?yàn)橹餍虼鎯?chǔ)對(duì)稱(chēng)矩陣的 下三角 （ 包括對(duì)角線 ） 中的元 。 所謂下(上 ) 三角矩陣是指矩陣的上 (下 ) 三角 (不包括對(duì)角線 ) 中的元均為常數(shù) c 或?yàn)榱愕? n 階矩陣 。 ??????????1000980076504321 ??????????1987654321 a a a a a a 上三角矩陣 一個(gè) n 階方陣 ， 若它的全部非零元素落在一個(gè)以對(duì)角線為中心的帶狀區(qū)域中 ， 則稱(chēng)該矩陣為帶狀矩陣 ， 或?qū)蔷仃?。 3. 帶狀矩陣 0 0 b 條 b 條 23 在帶狀矩陣中 ， 當(dāng) | ij | b 時(shí) ， aij = 0。 a11 D = a12 a13 0 0 a21 a22 a23 a24 0 a31 a32 a33 a34 a35 0 a42 a43 a44 a45 0 0 a53 a54 a55 D 矩陣是一個(gè) 5 階 、 半帶寬為 2 的帶狀矩陣 ， 在其主對(duì)角線 a1 a2 a3 a4 a55 上下各有 2 條對(duì)角線 ，共有 (2b+1)n(b+1)b = 19 個(gè)非零元素 。 25 特點(diǎn)： 當(dāng) i=1 j=1,2 1in,j=i1,i,i+1 i=n,j=n1,n aij非零 ， 其它元素均為零 a11 Ann= a12 ０ 0 0 a21 a22 a23 ０ 0 0 a32 a33 a34 ０ 0 ０ a43 a44 a45 0 0 … … … 除第一行和最后一行只有兩個(gè)元素外 ， 其余各行均有 3個(gè)非零元素 ， 由此得到一維向量所需的空間大小為：３ n2 Ｌ oc(a[i][j])=Loc(a[1][1])+2(i1)+j1 26 三對(duì)角帶狀矩陣的壓縮存儲(chǔ) ， 以行序?yàn)橹餍蜻M(jìn)行存儲(chǔ) ， 且只存儲(chǔ)非零元素 。 假設(shè)在 m n 的矩陣中 ，若有 t 個(gè)元素不為零 ， 令 ? = t / (m n)， 則稱(chēng) ? 為矩陣的稀疏因子 。 稀疏矩陣的邏輯結(jié)構(gòu) 1. 稀疏矩陣的定義 按照壓縮存儲(chǔ)的概念 ， 只存儲(chǔ)稀疏矩陣的非零元素 。 反之 ， 一個(gè)三元組 ( i, j, aij ) 唯一確定了矩陣的一個(gè)非零元素 。 假設(shè)以順序存儲(chǔ)結(jié)構(gòu)表示三元組表 ， 則可以得到稀疏矩陣的一種壓縮存儲(chǔ)方式 ， 這種方式稱(chēng)之為三元組順序表 。 29 define MAXSIZE 1000 // 假設(shè)非零元個(gè)數(shù)的最大值為 1000 typedef struct { // 三元組順序表的元素結(jié)構(gòu)定義 int row, 。 // 該非零元的值 } Triple。 // 非零元三元組表 ， data[0] 未用 int m, n, len。 // 三元組順序表的類(lèi)型名 30 (1) 三元組順序存儲(chǔ)表示 在這里 ， data 域中表示非零元的三元組是以行序?yàn)橹餍蝽樞蚺帕械?。 32 顯然 ， 一個(gè)稀疏矩陣的轉(zhuǎn)置矩陣仍是稀疏矩陣 。 那么 ， 只要做到下面 3 點(diǎn)就可以由 A 得到 B， 實(shí)現(xiàn)矩陣的轉(zhuǎn)置 。 33 原 始 的 三 元 組 表 原 矩 陣 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 Ｍ = [1] [2] [3] [4] [5] [6] [7] [8] 1 3 3 1 6 15 2 1 12 2 5 18 3 1 9 3 4 24 4 6 7 6 3 14 row col e 轉(zhuǎn) 置 矩 陣 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 Ｔ = 轉(zhuǎn) 置 的 三 元 組 表 [1] [2] [3] [4] [5] [6] [7] [8] 1 2 12 1 3 9 3 1 3 3 6 14 4 3 24 5 2 18 6 1 15 6 4 7 row col e 使 中的三元組以 T 的行 （ M 的列 ） 為主序依次排列的方法有如下兩種： 34 方法一： 按照 中三元組的次序 ， 依次在 中找到相應(yīng)的三元組進(jìn)行轉(zhuǎn)置 。 采用方法一 ① 算法思想 在 A中按三元組的列域值 (col) 開(kāi)始掃描 ， 依序?qū)⑷M 的列域值 (col ) 與行域值 (row ) 進(jìn)行對(duì)換 ， 并且存入 B中 。 35 按照方法一 ， 即按照 “ 被轉(zhuǎn)置矩陣 ” M的三元組表 A 的 “ 列序 ” 遞增順序進(jìn)行轉(zhuǎn)置 。 在程序中 ， int i,j,k。 // 將稀疏矩陣 A 的列數(shù)值作為其轉(zhuǎn)置矩陣 B 的行數(shù)值 Bn = 。 // 轉(zhuǎn)置矩陣 B與稀疏矩陣 A的非零元個(gè)數(shù)相等 ② 算法編 (稀 疏矩陣“列序”遞增轉(zhuǎn)置算法 ) if ( Blen0 ) { j = 1。 k = 。 i = 。 } // TransposeSMatrix Bdata[j].row = [i].col。 // 稀疏矩陣 A 的行域值成為其轉(zhuǎn)置矩陣 M 的列域值 Bdata[j].e = [i].e。 // Bdata 中三元組的序號(hào)加 1 } // if ( ) 結(jié)束 } // if ( Blen0 ) 結(jié)束 38 ③ 算法分析 一般矩陣的轉(zhuǎn)置算法 （ 經(jīng)典算法 ） 為： 39 for ( col = 0。 ++col ) for ( row = 0。 ++row ) dest[col][row] = source[row][col]。 前面給出的求轉(zhuǎn)置矩陣算法的主要工作是在 i 和 k 的兩重循環(huán)中完成的 ， 所以此算法的時(shí)間復(fù)雜度為 O( ) 即和矩陣 A 的列數(shù)和非零元的個(gè)數(shù)的乘積成正比 。 由此可見(jiàn) ， 上述求轉(zhuǎn)置矩陣算法只適合于 len m n 的情況 。 例如 ， 在進(jìn)行 “ 將矩陣 B 加到矩陣 A 上 ” 的 操作時(shí) ， 由于非零元素的插入或刪除將會(huì)引起 中元素的大量移動(dòng) 。 41 2. 十字鏈表 (1) 稀疏矩陣的十字鏈表存儲(chǔ)表示 ? 矩陣中非零元的行號(hào) row； ? 矩陣中非零元的列號(hào) col； ? 矩陣中非零元的值 e； ? 向
醫(yī)療健康相關(guān)推薦
鄂ICP備17016276號(hào)-1