[教育學]第五章數(shù)組與廣義表-文庫吧資料
2024-10-20 11:12本頁面
【正文】 組表表示見圖 (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)置。 三元組表 ? 將表示稀疏矩陣的非零元素的三元組按行優(yōu)先 (或列優(yōu)先 )的順序排列 (跳過零元素 )，并依次存放在向量中，這種稀疏矩陣的順序存儲結(jié)構(gòu)稱為三元組表。 其中每一個非零元素所在的行號、列號和值組成一個三元組 (i， j， aij)， 并由此三元組惟一確定。由于非零元素的分布一般是沒有規(guī)律的，因此在存儲非零元素的同時，還必須存儲非零元素所在的行號、列號，才能迅速確定一個非零元素是矩陣中的哪一個元素。 稀疏矩陣 ? 設(shè)矩陣 Amn中有 s個非零元素，若 s遠遠小于矩陣元素的總數(shù) (即 sm n)， 則稱 A為稀疏矩陣。 由此可知，一個 k對角線矩陣 (k為奇數(shù) )A是滿足下述條件的矩陣： 若 |ij|(k1)／ 2， 則元素 aij=0。 對應(yīng)關(guān)系 ? 其中： 非零元素僅出現(xiàn)在主對角上 (aii， 0≤i≤n1)，緊鄰主對角線上面的那條對角線上 (ai， i+1 ，0≤i≤n2)和緊鄰主對角線下面的那條對角線上 (a i+1， i， 0≤i≤n2)。 由此可知，一個 k對角線矩陣 (k為奇數(shù) )A是滿足下述條件的矩陣： 若 |ij|(k1)／ 2， 則元素 aij=0。 示意圖 帶狀矩陣 a20 a21 a22 a23 a24 對應(yīng)關(guān)系 ? 其中： 非零元素僅出現(xiàn)在主對角上 (aii， 0≤i≤n1)，緊鄰主對角線上面的那條對角線上 (ai， i+1 ，0≤i≤n2)和緊鄰主對角線下面的那條對角線上 (a i+1， i， 0≤i≤n2)。 示意圖 （ 2）三角矩陣的壓縮存儲 ? 三角矩陣中的重復元素 c可共享一個存儲空間，其余的元素正好有 n (n+1)／ 2個，因此，三角矩陣可壓縮存儲到向量sa[0．． n(n+1)／ 2]中，其中 c存放在向量的最后一個分量中。 ②下三角矩陣 與上三角矩陣相反，它的主對角線上方均為常數(shù) c， 如下圖 (b)所示。 ①按 行優(yōu)先順序 存儲主對角線 (包括對角線 )以下的元素 對稱矩陣的壓縮存儲 ②元素 aij的存放位置 ? aij元素前有 i行 (從第 0行到第 i1行 )，一共有： 1+2+…+ i=i (i+1)／ 2個元素； 在第 i行上， aij之前恰有 j個元素 (即 ai0，ail， … ， ai,j1)， 因此有： sa[i (i+1)／ 2+j]= aij 三角矩陣 （ 1）三角
教學課件相關(guān)推薦
鄂ICP備17016276號-1