數(shù)據(jù)結(jié)構(gòu)第五章數(shù)組與廣義表(編輯修改稿)
2024-11-14 15:43 本頁(yè)面
【文章內(nèi)容簡(jiǎn)介】 的那條對(duì)角線上 (aii+1,0≦i≦n 2)和緊鄰主對(duì)角線下面的那條對(duì)角線上 (ai+1 i,0≦i≦n 2)。顯然，當(dāng) ∣ ij∣1 時(shí)，元素aij=0。 ? 由此可知，一個(gè) k對(duì)角矩陣 (k為奇數(shù) )A是滿足下述條件的矩陣：若 ∣ ij∣(k 1)/2 ，則元素 aij=0。 ? 對(duì)角矩陣可按行優(yōu)先順序或?qū)蔷€的順序，將其壓縮存儲(chǔ)到一個(gè)向量中，并且也能找到每個(gè)非零元素和向量下標(biāo)的對(duì)應(yīng)關(guān)系。 中國(guó)科大 《 數(shù)據(jù)結(jié)構(gòu) 》 518 矩陣的壓縮存儲(chǔ) 在三對(duì)角矩陣?yán)锔綕M足條件 i=0， j=0、 1，或 i=n1j=n n1或 1in1,j=i i、 i+1的元素 aij外，其余元素都是零。 對(duì)這種矩陣，我們也可按行優(yōu)序?yàn)橹餍騺?lái)存儲(chǔ)。除第 0行和第n1行是 2個(gè)元素外，每行的非零元素都是 3個(gè)，因此，需存儲(chǔ)的元素個(gè)數(shù)為 3n2。 數(shù)組 sa中的元素 sa[k]與三對(duì)角帶狀矩陣中的元素 aij存在一一對(duì)應(yīng)關(guān)系，在 aij之前有 i行 ,共有 3*i1個(gè)非零元素，在第 i行，有 ji+1個(gè)非零元素 . a n1 n1 a n1 n2 … … a21 a12 a11 a10 a01 a00 K=0 1 2 3 4 5 … … 3n 2 3n1 中國(guó)科大 《 數(shù)據(jù)結(jié)構(gòu) 》 519 矩陣的壓縮存儲(chǔ) 稀疏矩陣 ? 定義：設(shè)矩陣 A中有 s個(gè)非零元素，若 s遠(yuǎn)遠(yuǎn)小于矩陣元素的總數(shù)（即 sm n），則稱 A為 稀疏矩陣 。 設(shè)在的矩陣 A中，有 s個(gè)非零元素。令 e=s/(m*n)，稱 e為矩陣的 稀疏因子 。通常認(rèn)為 e≦ 時(shí)稱之為 稀疏矩陣 。 ? 稀疏矩陣的存儲(chǔ) ? 存儲(chǔ)非零元素的同時(shí)，還必須記下所屬行和列的位置（ i,j)。 ? 一個(gè)三元組 (i,j,aij)唯一確定了矩陣 A的一個(gè)非零元。 ? 稀疏矩陣可由表示非零元的三元組及其行列數(shù)唯一確定。 ? 這樣的存儲(chǔ)方法大大節(jié)約了存儲(chǔ)空間，但矩陣的運(yùn)算變得復(fù)雜。 中國(guó)科大 《 數(shù)據(jù)結(jié)構(gòu) 》 520 矩陣的壓縮存儲(chǔ) ? 三元組法存儲(chǔ) 8 4 4 6 2 5 2 5 5 4 2 4 11 3 2 3 7 3 1 2 5 4 0 1 2 1 0 0 data col row 0 2 0 0 5 0 0 0 0 7 0 0 0 0 0 11 5 2 0 0 0 0 0 0 0 0 0 0 8 0 中國(guó)科大 《 數(shù)據(jù)結(jié)構(gòu) 》 521 矩陣的壓縮存儲(chǔ) ? 帶行向量的三元組法 ? 注意：第三行在三元表中不存在，所以行向量以上一行的位置代替 8 4 4 6 2 5 2 5 5 4 2 4 11 3 2 3 7 3 1 2 5 4 0 1 2 1 0 0 data col row 0 2 0 0 5 0 0 0 0 7 0 0 0 0 0 11 5 2 0 0 0 0 0 0 0 0 0 0 8 0 4 3 2 1 0 6 3 3 2 0 行向量 rpos 中國(guó)科大 《 數(shù)據(jù)結(jié)構(gòu) 》 522 矩陣的壓縮存儲(chǔ) ? 三元組法表示的矩陣轉(zhuǎn)置 ? 方法 1：先行欄對(duì)調(diào)地復(fù)制，再排序 ? 方法 2：對(duì)目標(biāo)矩陣逐行掃描 0 2 0 0 5 0 0 0 0 7 0 0 0 0 0 11 5 2 0 0 0 0 0 0 0 0 0 0 8 0 0 0 0 0 0 2 0 0 0 0 0 0 0 0 0 0 7 11 0 0 5 0 5 0 8 0 0 2 0 0 中國(guó)科大 《 數(shù)據(jù)結(jié)構(gòu) 》 523 矩陣的壓縮存儲(chǔ) row col data 0 0 1 2 1 0 4 5 2 1 3 7 3 2 3 11 4 2 4 5 5 2 5 2 6 4 4 8 0 2 0 0 5 0 0 0 0 7 0 0 0 0 0 11 5 2 0 0 0 0 0 0 0 0 0 0 8 0 0 0 0 0 0 2 0 0 0 0 0 0 0 0 0 0 7 11 0 0 5 0 5 0 8 0 0 2 0 0 ro
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號(hào)-1