java數(shù)據(jù)結構第五章數(shù)組和廣義表(編輯修改稿)
2025-06-16 22:26 本頁面
【文章內(nèi)容簡介】 C=A+B）定義為 public class Matrix { private int value[][]。 } 0 0 0 1 0 , 11 0 1 1 1 , 11 , 0 1 , 1 1 , 1……… … … ……nnmnm m m na a aa a aa a a???? ? ? ????????????Aij ij ijc a b?? 矩陣的壓縮存儲 討論： 對象 .如何 存儲矩陣中的元素 ,使對矩陣的各種操作 更方便、效率更高 。 ，常遇到一些矩陣，其 元素 有 許多值相同 或 大量元素值 為 零 。如何 節(jié)省空間 。 ３ . 什么是壓縮存儲？ 多個值 相同的元素 ， 只分配一個 元素值的存儲 空間 ，且 零 元素 不占存儲空間 。 ４ . 所有二維數(shù)組（矩陣）都能壓縮嗎？ 未必，要看矩陣是否具備以上壓縮條件。 ５ . 什么樣的矩陣具備以上壓縮條件？ 一些 特殊矩陣 （如：對稱矩陣，三角矩陣，對角矩陣）和 稀疏矩陣 等。 ６ .什么叫特殊矩陣？ 若值 相同的元素 或者 零元素 在矩陣中的分布 有一定規(guī)律 ，則該類矩陣稱為特殊矩陣。 ７ .什么叫稀疏矩陣？（重點） 若值 相同的元素 或者 零元素 在矩陣中的分布 不具有規(guī)律 ，且矩陣中 非零元素 的 個數(shù)較少 （一般 小于 5%）時。（無確切定義） 一、特殊矩陣 １、 n階 對稱矩陣 ：若 n階矩陣Ａ中的元素滿足如下條件： aij=aji 1≤i,j≤n。 如： 壓縮存儲方案 ：為 每一對 對稱元素 分配一個存儲空間，則可將 n*n個元素壓縮存儲到n(n+1)/2個元素的空間中。 ????????????10765794364215318方法： １）按行序為主序存儲其下三角（含對角線元素）（以此為例） ２）按行序為主序存儲其上三角（含對角線元素） ３）按列序為主序存儲其下三角（含對角線元素） ４）按列序為主序存儲其上三角（含對角線元素） aij在一維數(shù)組中的序號 =陰影部分的面積 ∵ 一維數(shù)組下標從 0開始 ∴ aij在一維數(shù)組中的下標 k= i (i+1)/2+ j 0 … i n1 0 … j … n1 aij 每行元素個數(shù) 1 2 … i aij在本行中的序號 aij 第 0行 第 1行 … 第 i1行 對稱矩陣的壓縮存儲（ 存儲下三角 ） (c) 計算方法 (b) 存儲說明 (a)下三 角矩陣 第 1行 第 n1行 第 0行 a00 a10 a11 a20 a21 a22 aij … a n10 an11 … an1n1 … 第 2行 0 1 2 3 4 5 k n(n+1)/21 問：如何獲取矩陣中的元素（或賦值）？ 關鍵 ：找到該元素 在一維數(shù)組 sa中 的 位置 k。即確定sa[k]與矩陣元素 aij之間存在的 一一對應關系 。 ????????????jiijjjijiik當當2/)1(2/)1(（可獲得下三角元素） （可獲得上三角元素（不含主對角線）） 注： 我們將 sa就稱為 n階對稱矩陣的 壓縮存儲 。 若計算 aij存放地址，則可以利用以下公式獲得： LOC[aij]=LOC[a00]+（ i(i+1)/2+j） *L, i=j， L為每個元素的存儲單元大小。 三角矩陣： （１） 上三角矩陣 ：是指矩陣的下三角（不包括對角線）中的元均為 常數(shù)Ｃ或零 的 n階矩陣。 （２） 下三角矩陣 ：是指矩陣的上三角（不包括對角線）中的元均為常數(shù)Ｃ或零的 n階矩陣。 壓縮存儲 方案 ： 只存儲其 下（上）三角中的元素 之外，需 加一個存儲 常數(shù) c的存儲空間即可。 特殊矩陣的壓縮存儲 —— 三角矩陣 3 c c c c 6 2 c c c 4 8 1 c c 7 4 6 0 c 8
環(huán)評公示相關推薦
鄂ICP備17016276號-1