數(shù)組可以看成是一種特殊的線性表

數(shù)組可以看成是一種特殊的線性表第1頁，共20頁，2023年，2月20日，星期六4.2數(shù)組的順序存儲(chǔ)結(jié)構(gòu)次序約定以行序?yàn)橹餍蛞粤行驗(yàn)橹餍?/p>

a11a12……..a1n

a21a22……..a2n

am1am2……..amn

….Loc(aij)=Loc(a11)+[(i-1)n+(j-1)]*l

按行序?yàn)橹餍虼娣?/p>

amn

……..

am2

am1

……….

a2n

……..

a22

a21

a1n

…….

a12

a1101n-1m*n-1n

按列序?yàn)橹餍虼娣?1m-1m*n-1m

amn

……..

a2n

a1n

……….

am2

……..

a22

a12

am1

…….

a21

a11

a11

a12

……..

a1n

a21

a22……..

a2n

am1

am2

……..amn

….Loc(aij)=Loc(a11)+[(j-1)m+(i-1)]*l

第2頁，共20頁，2023年，2月20日，星期六4.3矩陣的壓縮存儲(chǔ)對(duì)稱矩陣

a11a12

….

……..a1n

a21

a22

……..…….a2n

an1

an2

……..ann

….a11a21a22a31a32an1ann

…...…...k=01234n(n-1)/2n(n+1)/2-1按行序?yàn)橹餍颍旱?頁，共20頁，2023年，2月20日，星期六三角矩陣

a11

00

……..0

a21a22

0

……..0

an1an2an3……..ann

….0Loc(aij)=Loc(a11)+[(+(j-1)]*l

i(i-1)2a11a21a22a31a32an1ann

…...…...k=01234n(n-1)/2n(n+1)/2-1按行序?yàn)橹餍颍旱?頁，共20頁，2023年，2月20日，星期六對(duì)角矩陣

a11

a120

…………….0

a21

a22

a23

0

……………0

0

0

…an-1,n-2an-1,n-1

an-1,n

0

0

……an,n-1ann.

0

a32a33

a34

0

………0

……………Loc(aij)=Loc(a11)+2(i-1)+(j-1)

a11a12a21a22a23ann-1ann

…...…...k=01234n(n-1)/2n(n+1)/2-1按行序?yàn)橹餍颍旱?頁，共20頁，2023年，2月20日，星期六M由{(1,2,12),(1,3,9),(3,1,-3),(3,6,14),(4,3,24),(5,2,18),(6,1,15),(6,4,-7)}和矩陣維數(shù)（6,7）唯一確定稀疏矩陣定義：非零元較零元少，且分布沒有一定規(guī)律的矩陣壓縮存儲(chǔ)原則：只存矩陣的行列維數(shù)和每個(gè)非零元的行列下標(biāo)及其值第6頁，共20頁，2023年，2月20日，星期六稀疏矩陣的壓縮存儲(chǔ)方法順序存儲(chǔ)結(jié)構(gòu)三元組表#defineM20typedefstructnode{inti,j;intv;}JD;JDma[M];三元組表所需存儲(chǔ)單元個(gè)數(shù)為3(t+1)其中t為非零元個(gè)數(shù)6

7

8

121213931-3361443245218611564-7maijv012345678ma[0].i,ma[0].j,ma[0].v分別存放矩陣行列維數(shù)和非零元個(gè)數(shù)行列下標(biāo)非零元值第7頁，共20頁，2023年，2月20日，星期六帶輔助行向量的二元組表增加一個(gè)輔助數(shù)組NRA[m+1],其物理意義是第i行第一個(gè)非零元在二元組表中的起始地址（m為行數(shù)）顯然有：NRA[1]=1NRA[i]=NRA[i-1]+第i-1行非零元個(gè)數(shù)(i2)0123456NRA1335676

7

8

212391-36143242181154-7majv012345678矩陣列數(shù)和非零元個(gè)數(shù)列下標(biāo)和非零元值NRA[0]不用或存矩陣行數(shù)二元組表需存儲(chǔ)單元個(gè)數(shù)為2(t+1)+m+1第8頁，共20頁，2023年，2月20日，星期六偽地址表示法偽地址：本元素在矩陣中（包括零元素再內(nèi)）按行優(yōu)先順序的相對(duì)位置

6

7

2123915-3201424243018361539-7maaddrv偽地址非零元值矩陣行列維數(shù)012345678偽地址表示法需存儲(chǔ)單元個(gè)數(shù)為2(t+1)第9頁，共20頁，2023年，2月20日，星期六求轉(zhuǎn)置矩陣問題描述：已知一個(gè)稀疏矩陣的三元組表，求該矩陣轉(zhuǎn)置矩陣的三元組表問題分析一般矩陣轉(zhuǎn)置算法：for(col=0;col<n;col++)for(row=0;row<m;row++)n[col][row]=m[row][col];T(n)=O(mn)第10頁，共20頁，2023年，2月20日，星期六6

7

8

121213931-3361443245218611564-7ijv012345678maijv7

6

8

13-3161521122518319342446-76314012345678mb?第11頁，共20頁，2023年，2月20日，星期六解決思路：只要做到

將矩陣行、列維數(shù)互換將每個(gè)三元組中的i和j相互調(diào)換重排三元組次序，使mb中元素以N的行(M的列)為主序方法一：按M的列序轉(zhuǎn)置即按mb中三元組次序依次在ma中找到相應(yīng)的三元組進(jìn)行轉(zhuǎn)置。為找到M中每一列所有非零元素，需對(duì)其三元組表ma從第一行起掃描一遍。由于ma中以M行序?yàn)橹餍?所以由此得到的恰是mb中應(yīng)有的順序算法描述：算法分析：T(n)=O(M的列數(shù)n非零元個(gè)數(shù)t)若t與mn同數(shù)量級(jí)，則Ch4_1.c第12頁，共20頁，2023年，2月20日，星期六6

7

8

121213931-3361443245218611564-7ijv012345678ma7

6

8

13-3161521122518319342446-76314ijv012345678mbkppppppppkkkkppppppppcol=1col=2第13頁，共20頁，2023年，2月20日，星期六方法二：快速轉(zhuǎn)置即按ma中三元組次序轉(zhuǎn)置，轉(zhuǎn)置結(jié)果放入b中恰當(dāng)位置此法關(guān)鍵是要預(yù)先確定M中每一列第一個(gè)非零元在mb中位置，為確定這些位置，轉(zhuǎn)置前應(yīng)先求得M的每一列中非零元個(gè)數(shù)實(shí)現(xiàn)：設(shè)兩個(gè)數(shù)組num[col]：表示矩陣M中第col列中非零元個(gè)數(shù)cpot[col]：指示M中第col列第一個(gè)非零元在mb中位置顯然有：cpot[1]=1;cpot[col]=cpot[col-1]+num[col-1];(2colma[0].j)1357889colnum[col]cpot[col]12223241506170第14頁，共20頁，2023年，2月20日，星期六算法分析：T(n)=O(M的列數(shù)n+非零元個(gè)數(shù)t)若t與mn同數(shù)量級(jí)，則T(n)=O(mn)算法描述：Ch4_2.c第15頁，共20頁，2023年，2月20日，星期六6

7

8

121213931-3361443245218611564-7ijv012345678maijv012345678mbcolnum[col]cpot[col]1122323524715806817907

6

8

13-3161521122518319342446-76314pppppppp4629753第16頁，共20頁，2023年，2月20日，星期六鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)帶行指針向量的單鏈表表示每行的非零元用一個(gè)單鏈表存放設(shè)置一個(gè)行指針數(shù)組，指向本行第一個(gè)非零元結(jié)點(diǎn)；若本行無非零元，則指針為空表頭結(jié)點(diǎn)與單鏈表結(jié)點(diǎn)類型定義typedefstructnode{intcol;intval;structnode*link;}JD;typedefstructnode*TD;^13573-11-12-242^^^^需存儲(chǔ)單元個(gè)數(shù)為3t+m第17頁，共20頁，2023年，2月20日，星期六十字鏈表設(shè)行指針數(shù)組和列指針數(shù)組，分別指向每行、列第一個(gè)非零元結(jié)點(diǎn)定義tpedefstructnode{introw,col,v