結(jié)構(gòu)體數(shù)組結(jié)構(gòu)體數(shù)組-閱讀頁
2025-06-02 22:09本頁面
【正文】 元素 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） 條非零元素帶。 總之： 特殊矩陣的壓縮存儲(chǔ)方法： 找出特殊矩陣的非零元素的分布規(guī)律，將其存儲(chǔ)到一個(gè)存儲(chǔ)空間，只需在算法中按公式計(jì)算即可實(shí)現(xiàn)矩陣元素的隨機(jī)存取。通常認(rèn)為 ?=。由此構(gòu)成一個(gè)三元組(i,j,aij)，該三元組唯一確定了該矩陣元素。僅存非零元素 ,可省空間 ,避免大量無意義運(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/6/16 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/6/16 21 2. 鏈接存儲(chǔ)結(jié)構(gòu) : (1)三元組 (單 )鏈表 . 三元組線性表采用鏈接存儲(chǔ)結(jié)構(gòu)。 采用動(dòng)態(tài)存儲(chǔ)結(jié)構(gòu) :每個(gè)非零元素用一個(gè)結(jié)點(diǎn)由五個(gè)數(shù)據(jù)域組成 :三個(gè)數(shù)值 ,兩個(gè)指針 . 三個(gè)數(shù)值： i， j， 、列號(hào)和元素值。 三元組順序表結(jié)構(gòu)定義如下： define MAX 100 typedef struct { int i。 /*列 */ DataType d。 /*三元組 */ typedef struct { int md。 /*總列數(shù) */ int td。 }tabletype。 /*行 */ int j。/*元素值 */ }tupletype。 /*總行數(shù) */ int nd。 /*總非零元素?cái)?shù) */ tupletype data[MAX]。 /*三元組表 */ tabletype sa。 sbmd=。 sbtd=。 for(v=0。 v++) { for(p=0。 p++) {if([p].j= =v) {sbdata[q].i=[p].j。 sbdata[q].d=[p].d。 } } } } } q為 []的下標(biāo) 以 []的 j域次序搜索 p為 []的下標(biāo) 6 7 6 0 2 11 0 4 17 1 1 25 3 0 19 4 3 37 5 6 50 sa: 0 3 19 1 1 25 2 0 11 3 4 37 4 0 17 6 5 50 7 6 6 sb: 《 計(jì)算機(jī)軟件基礎(chǔ) 》 課件 2021/6/16 31 算法分析： 上述算法的時(shí)間復(fù)雜度為： O( ) 關(guān)鍵在于非零元素個(gè)數(shù)。 特殊矩陣：計(jì)算公式。 A= 作業(yè) P145: 1, 3 ????????????????????500000000003700000000019000000000000250001701100
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號(hào)-1