【正文】 i = 1。 37 for (k = 1。 // 將稀疏矩陣 A 的行數(shù)值作為其轉(zhuǎn)置矩陣 B 的列數(shù)值 Blen = 。 // j 指示 Bdata 中三元組的序號 ， // i 指示 中三元組的序號 ， // k指示 A 的列號 （ 即 B 的行號 ） Bm = 。 為了找到矩陣 M 的每一列中所有的非零元素 ， 需要對其三元組 從第一行起進行掃描 ， 方法如下： 轉(zhuǎn)置的三元組表 Bdata 原始的三元組表 r c v 1 2 12 1 3 9 3 1 3 3 6 14 4 3 24 5 2 18 6 1 15 6 4 7 36 利用三元組順序表存儲實現(xiàn)矩陣的轉(zhuǎn)置 c 3 6 1 5 1 4 6 3 r 1 1 2 2 3 3 4 6 v 3 15 12 18 9 24 7 14 void TransposeTSMatrix ( TSMatrix A, TSMatrix *B ) { // 采用三元組表結構 ， 求稀疏矩陣 A 的轉(zhuǎn)置矩陣 B。 由于 A是以 M的行序為主序來存放每個非零元的 ， 由此得到轉(zhuǎn)置后矩陣的三元組表 B恰是 以 “ 行序為主序 ” 。 方法二： 按照 中三元組的次序進行轉(zhuǎn)置 ，并將轉(zhuǎn)置后的三元組置入 中恰當?shù)奈恢?。 將每三元組中的 row 和 col 相互調(diào)換； 重排三元組之間的次序 。 假設 A 和 B 是 TSMatrix（ 三元組順序表 ） 類型變量 ， 分別表示矩陣 Ｍ和其轉(zhuǎn)置矩陣Ｔ 。 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 M = 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 [1] [2] [3] [4] [5] [6] [7] [8] (a) 稀疏矩陣 (b) 三元組順序表 31 (2) 利用三元組順序表實現(xiàn)矩陣的轉(zhuǎn)置運算 將矩陣的行列值相互交互； 在這 3 點中 ， 最關鍵的是第 3 條 ， 即如何使 中的三元組以 Ｔ的行 （ Ｍ的列 ） 為主序依次排列 。 // 矩陣的行數(shù) 、 列數(shù)和非零個數(shù) } TSMatrix。 typedef struct { // 三元組順序表存儲結構定義 Triple data[ MAXSIZE+1]。col // 該非零元的行下標和列下標 ElementType e。 28 稀疏矩陣的存儲結構 1. 三元組順序表 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 M = 矩陣 M 可以由三元組表 (1, 3, 3)， (1, 6, 15)， (2, 1, 12)， (2, 5, 18)， (3, 1, 9)， (3, 4, 24)， (4, 6, 7)， (6, 3, 14) 再加上 （ 7, 6） 這一對總的行列值來描述 。 因此 ，稀疏矩陣可以由表示非零元的三元組及其矩陣的總的行列數(shù)唯一確定 。因此 ， 除了存儲非零元素的值 aij 之外 ， 還必須同時記下 非零元素 所在矩陣的行 i 號和列 j號 。 通常認為 ? ≤25%30%時稱為稀疏矩陣 。 其方法為 27 一般來說 ， 當 矩陣中非零元素的個數(shù)遠遠小于矩陣元素的總數(shù)時 ， 稱之為稀疏矩陣 。 24 例如： 帶狀矩陣中最常見的是三對角帶狀矩陣 。 該方陣共有 (2b+1)n(b+1)b 個非零元素 。 這個帶狀區(qū)域若包含主對角線上下各 b 條對角線道上元素 ， 那么 ， b 稱為該帶狀矩陣的半帶寬 ， 或稱該帶狀矩陣的帶寬為 (2b+1)。 2. 三角矩陣 22 ??????????198706540032000 1 ??????????19875421 a aa a aa a a下三角矩陣 三角矩陣除了和對稱矩陣一樣 ， 只存儲矩陣的下(上 ) 三角中的元之外 ， 再加上一個存儲常數(shù) c 的存儲空間即可 。 以一維數(shù)組 B[n(n+1)/2] 作為 n 階對稱矩陣 M 的存儲結構 ， 21 a31 a22 a21 a11 an, n … an,1 … B Loc(A[i][j]=1 2 3 4 … 12)1( ??nn … 2 )1( ?nn Loc(A[i][j])=Loc(A[1][1])+i*(i1)/2+j1 (ij) 三角矩陣分為下三角矩陣和上三角矩陣 。 20 對于對稱矩陣 ， 可以為每一對對稱元只分配一個存儲空間 ， 這樣就可以將 n2 個元壓縮存儲到 n(n+1)/2 個元的空間中 。 在所有這些統(tǒng)稱為 “ 特殊矩陣 ” 的 矩陣中 ， 非零元的分布都有一個明顯的規(guī)律 ， 從而都可以將其壓縮存儲到一維數(shù)組中 ， 并且找到每個非零元在一維數(shù)組中的對應關系 。 18 稀疏矩陣的邏輯結構 稀疏矩陣的存儲結構 假若相同的元素或者零元素在矩陣中的分布有一定規(guī)律 ， 則稱特殊矩陣 。 ② 非零元素很少的稀疏 矩陣 ， 可采用只存 非零元素的方法實現(xiàn)壓縮存儲 。 在數(shù)據(jù)結構中 ， 我們感興趣的不是矩陣本身 ，而是如何存儲矩陣的元素而使矩陣的各種運算能夠有效地進行 。 16 不難得到三維數(shù)組任意元素 aijk的地址： Loc(A[i][j][k])=Loc(A[1][1][1])+((i1)*m*n+(j1)*n+(k1))*size,其中：１ ≤i≤r, １ ≤j≤m, １ ≤k≤n。 假設每個數(shù)據(jù)元素占 size個存儲單元 ， 且以行序為主序的進行存儲 ， 首元素 a111的地址為 Loc(A[1][1][1]),求任意元素 aijk的地址 。 數(shù)組的地址計算 14 ⑵ 二維數(shù)組的 地址計算 假設每個數(shù)據(jù)元素占 1 個存儲單元 ， 且以行序為主序的進行存儲 ， 則二維數(shù)組 A 中任一元素 aij 的存儲位置可以由下面定位公式確定 LOC (A[i],[ j]) = LOC (A[1], [1]) + n*(i1)+(j1) 其中： LOC (A[i[,[ j]) 是 aij 的存儲位置； LOC (A[1], [1]) 是 a11 的存儲位置 ，