[計(jì)算機(jī)軟件及應(yīng)用]結(jié)構(gòu)體數(shù)組結(jié)構(gòu)體數(shù)組(編輯修改稿)
2025-11-12 23:21 本頁面
【文章內(nèi)容簡(jiǎn)介】 1)/2+i ij k= 《 計(jì)算機(jī)軟件基礎(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 = 非零元素帶 《 計(jì)算機(jī)軟件基礎(chǔ) 》 課件 2021/11/11 16 例：三對(duì)角陣 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階對(duì)角陣有 （ 2h1） 條非零元素帶。 h 《 計(jì)算機(jī)軟件基礎(chǔ) 》 課件 2021/11/11 17 以上數(shù)組存儲(chǔ)方式與順序存儲(chǔ)線性表類似 數(shù)組元素的存儲(chǔ)位置是其下標(biāo)的線性函數(shù)。 總之： 特殊矩陣的壓縮存儲(chǔ)方法： 找出特殊矩陣的非零元素的分布規(guī)律，將其存儲(chǔ)到一個(gè)存儲(chǔ)空間，只需在算法中按公式計(jì)算即可實(shí)現(xiàn)矩陣元素的隨機(jī)存取。 《 計(jì)算機(jī)軟件基礎(chǔ) 》 課件 2021/11/11 18 稀疏因子：設(shè)在 m*n的矩陣中，有 t個(gè)非零元素，令 nmt???稱 ?為矩陣的稀疏因子。通常認(rèn)為 ?=。 我們?cè)诖鎯?chǔ)的時(shí)候，除了存儲(chǔ)非零元的值之外，還得存儲(chǔ)它所在的行號(hào)和列號(hào)。由此構(gòu)成一個(gè)三元組(i,j,aij)，該三元組唯一確定了該矩陣元素。 稀疏矩陣 : 《 計(jì)算機(jī)軟件基礎(chǔ) 》 課件 2021/11/11 19 含有大量零元素的矩陣 ,且無規(guī)律。僅存非零元素 ,可省空間 ,避免大量無意義運(yùn)算 ,提高運(yùn)算效率 . 例 : 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).三元組順序表 : 每個(gè)結(jié)點(diǎn)由三個(gè)域組成 。 。 . 《 計(jì)算機(jī)軟件基礎(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個(gè)非零元素則需要 3N個(gè)存儲(chǔ)單元 0 0 3 0 4 7 1 2 1 2 0 1 2 1 2 4 3 2 行 列 值 6 5 5 《 計(jì)算機(jī)軟件基礎(chǔ) 》 課件 2021/11/11 21 2. 鏈接存儲(chǔ)結(jié)構(gòu) : (1)三元組 (單 )鏈表 . 三元組線性表采用鏈接存儲(chǔ)結(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 缺點(diǎn)：算法事件復(fù)雜度高 3 0 0 7 4 0 1 2 1 1 0 2 2 1 2 2 ∧ 3 4 h 5 5 《 計(jì)算機(jī)軟件基礎(chǔ) 》 課件 2021/11/11 22 0 1 2 3 4 /\ (2) 行指針數(shù)組結(jié)構(gòu)的三元組鏈表 . 設(shè)置一個(gè)行指針數(shù)組 , 數(shù)組中每個(gè)元素為指針類型 ,它指向本行矩陣的第一個(gè)非零元素 ,若該行無非零元素 ,則指針為空 .
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號(hào)-1