[計算機軟件及應(yīng)用]結(jié)構(gòu)體數(shù)組結(jié)構(gòu)體數(shù)組(編輯修改稿)
2024-11-12 23:21 本頁面
【文章內(nèi)容簡介】 1)/2+i ij k= 《 計算機軟件基礎(chǔ) 》 課件 2021/11/11 15 K 0 1 2 3 … n(n1)/2 … n(n+1)/21 sa[k] a00 a10 a11 a20 … an11 … an1n1 隱含 a01 a02 … a1n1 ： 形狀： Ann = 非零元素帶 《 計算機軟件基礎(chǔ) 》 課件 2021/11/11 16 例：三對角陣 An n = 其中非零元素按行優(yōu)先順序存放： {a00 ,a01 ,a10 , a11, a12, a21, a22, a23,… , a n1,n2 , an1,n1 } 非零元素 aij的地址關(guān)系式： Loc(aij)= Loc(a00)+2*i+j (i=0,j=0,1 或 i=n1,j=n2,n1 或 0in1,j=i1,i,i+1) 推廣： n階對角陣有 （ 2h1） 條非零元素帶。 h 《 計算機軟件基礎(chǔ) 》 課件 2021/11/11 17 以上數(shù)組存儲方式與順序存儲線性表類似 數(shù)組元素的存儲位置是其下標的線性函數(shù)。 總之： 特殊矩陣的壓縮存儲方法： 找出特殊矩陣的非零元素的分布規(guī)律，將其存儲到一個存儲空間，只需在算法中按公式計算即可實現(xiàn)矩陣元素的隨機存取。 《 計算機軟件基礎(chǔ) 》 課件 2021/11/11 18 稀疏因子：設(shè)在 m*n的矩陣中，有 t個非零元素，令 nmt???稱 ?為矩陣的稀疏因子。通常認為 ?=。 我們在存儲的時候，除了存儲非零元的值之外，還得存儲它所在的行號和列號。由此構(gòu)成一個三元組(i,j,aij)，該三元組唯一確定了該矩陣元素。 稀疏矩陣 : 《 計算機軟件基礎(chǔ) 》 課件 2021/11/11 19 含有大量零元素的矩陣 ,且無規(guī)律。僅存非零元素 ,可省空間 ,避免大量無意義運算 ,提高運算效率 . 例 : A= 3 0 0 0 7 0 0 1 0 0 1 2 0 0 0 0 0 0 0 0 0 0 0 2 0 :按行優(yōu)先順序排列 . (1).三元組順序表 : 每個結(jié)點由三個域組成 。 。 . 《 計算機軟件基礎(chǔ) 》 課件 2021/11/11 20 A的三元組 順序 表表示 : (0,0,3) (0,4,7) (1,2,1) (2,0,1) (2,1,2) (4,3,2) 若有 N個非零元素則需要 3N個存儲單元 0 0 3 0 4 7 1 2 1 2 0 1 2 1 2 4 3 2 行 列 值 6 5 5 《 計算機軟件基礎(chǔ) 》 課件 2021/11/11 21 2. 鏈接存儲結(jié)構(gòu) : (1)三元組 (單 )鏈表 . 三元組線性表采用鏈接存儲結(jié)構(gòu)。 (0,0,3) (0,4,7) (1,2,1) (2,0,1) (2,1,2) (4,3,2) A= 3 0 0 0 7 0 0 1 0 0 1 2 0 0 0 0 0 0 0 0 0 0 0 2 0 缺點：算法事件復(fù)雜度高 3 0 0 7 4 0 1 2 1 1 0 2 2 1 2 2 ∧ 3 4 h 5 5 《 計算機軟件基礎(chǔ) 》 課件 2021/11/11 22 0 1 2 3 4 /\ (2) 行指針數(shù)組結(jié)構(gòu)的三元組鏈表 . 設(shè)置一個行指針數(shù)組 , 數(shù)組中每個元素為指針類型 ,它指向本行矩陣的第一個非零元素 ,若該行無非零元素 ,則指針為空 .
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號-1