[教育學(xué)]第五章數(shù)組與廣義表(編輯修改稿)
2024-11-10 11:12 本頁面
【文章內(nèi)容簡介】 n2)。 當(dāng) |ij|1時，元素 aij=0。 由此可知，一個 k對角線矩陣 (k為奇數(shù) )A是滿足下述條件的矩陣： 若 |ij|(k1)／ 2， 則元素 aij=0。 對角矩陣可按行優(yōu)先順序或?qū)蔷€的順序，將其壓縮存儲到一個向量中，并且也能找到每個非零元素和向量下標(biāo)的對應(yīng)關(guān)系。 對應(yīng)關(guān)系 ? 其中： 非零元素僅出現(xiàn)在主對角上 (aii， 0≤i≤n1)，緊鄰主對角線上面的那條對角線上 (ai， i+1 ，0≤i≤n2)和緊鄰主對角線下面的那條對角線上 (a i+1， i， 0≤i≤n2)。 當(dāng) |ij|1時，元素 aij=0。 由此可知，一個 k對角線矩陣 (k為奇數(shù) )A是滿足下述條件的矩陣： 若 |ij|(k1)／ 2， 則元素 aij=0。 對角矩陣可按行優(yōu)先順序或?qū)蔷€的順序，將其壓縮存儲到一個向量中，并且也能找到每個非零元素和向量下標(biāo)的對應(yīng)關(guān)系。 稀疏矩陣 ? 設(shè)矩陣 Amn中有 s個非零元素，若 s遠(yuǎn)遠(yuǎn)小于矩陣元素的總數(shù) (即 sm n)， 則稱 A為稀疏矩陣。 稀疏矩陣的壓縮存儲 ? 為了節(jié)省存儲單元，可只存儲非零元素。由于非零元素的分布一般是沒有規(guī)律的，因此在存儲非零元素的同時，還必須存儲非零元素所在的行號、列號，才能迅速確定一個非零元素是矩陣中的哪一個元素。稀疏矩陣的壓縮存儲會失去隨機存取功能。 其中每一個非零元素所在的行號、列號和值組成一個三元組 (i， j， aij)， 并由此三元組惟一確定。 稀疏矩陣進行壓縮存儲通常有兩類方法：順序存儲和鏈?zhǔn)酱鎯Α? 三元組表 ? 將表示稀疏矩陣的非零元素的三元組按行優(yōu)先 (或列優(yōu)先 )的順序排列 (跳過零元素 )，并依次存放在向量中，這種稀疏矩陣的順序存儲結(jié)構(gòu)稱為三元組表。 注意： 以下的討論中，均假定三元組是按行優(yōu)先順序排列的。 示例 ? 【例】下圖 (a)所示的稀疏矩陣 A的三元組表表示見圖 (b) （ 1）三元組表的類型說明 ? define MaxSize 10000 //由用戶定義 typedef int ElementType； //由用戶定義 typedef struct { int row， col； ElementType e； }Triple； typedef struct{ Tuple data[MaxSize]； //三元組表空間 int m, n， len； //矩陣的行數(shù)、列數(shù)及非零元個數(shù) }TSMatrix； 稀疏矩陣的轉(zhuǎn)置 ? 用三元組實現(xiàn)稀疏矩陣的轉(zhuǎn)置 ? 用帶行表的三元組實現(xiàn)稀疏矩陣的轉(zhuǎn)置。 0 0 8 17 0 0 3 0 6 20 13 0 28 0 0 5 12 0 0 15 0 0 13 5 0 3 0 12 8 0 28 0 17 6 0 0 0 20 0 15 0 2 8 0 3 17 1 1 3 1 3 6 1 4 20 2 0 13 2 2 28 3 0 5 3 1 12 3 4 15 轉(zhuǎn)置算法說明 算法 把三元組 A轉(zhuǎn)換為三元組 B(轉(zhuǎn)置）的算法 A中從第一行開始找出所
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號-1