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

數(shù)組可以看成是一種特殊的線性表第一頁，共二十頁，2022年，8月28日4.2數(shù)組的順序存儲結(jié)構(gòu)次序約定以行序為主序以列序為主序

a11a12……..a1n

a21a22……..a2n

am1am2……..amn

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

按行序為主序存放

amn

……..

am2

am1

……….

a2n

……..

a22

a21

a1n

…….

a12

a1101n-1m*n-1n

按列序為主序存放01m-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

第二頁，共二十頁，2022年，8月28日4.3矩陣的壓縮存儲對稱矩陣

a11a12

….

……..a1n

a21

a22

……..…….a2n

an1

an2

……..ann

….a11a21a22a31a32an1ann

…...…...k=01234n(n-1)/2n(n+1)/2-1按行序為主序：第三頁，共二十頁，2022年，8月28日三角矩陣

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按行序為主序：第四頁，共二十頁，2022年，8月28日對角矩陣

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按行序為主序：第五頁，共二十頁，2022年，8月28日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ī)律的矩陣壓縮存儲原則：只存矩陣的行列維數(shù)和每個非零元的行列下標及其值第六頁，共二十頁，2022年，8月28日稀疏矩陣的壓縮存儲方法順序存儲結(jié)構(gòu)三元組表#defineM20typedefstructnode{inti,j;intv;}JD;JDma[M];三元組表所需存儲單元個數(shù)為3(t+1)其中t為非零元個數(shù)6

7

8

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

7

8

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

6

7

2123915-3201424243018361539-7maaddrv偽地址非零元值矩陣行列維數(shù)012345678偽地址表示法需存儲單元個數(shù)為2(t+1)第九頁，共二十頁，2022年，8月28日求轉(zhuǎn)置矩陣問題描述：已知一個稀疏矩陣的三元組表，求該矩陣轉(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)第十頁，共二十頁，2022年，8月28日6

7

8

121213931-3361443245218611564-7ijv012345678maijv7

6

8

13-3161521122518319342446-76314012345678mb?第十一頁，共二十頁，2022年，8月28日解決思路：只要做到

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

7

8

121213931-3361443245218611564-7ijv012345678ma7

6

8

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

7

8

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

6

8

13-3161521122518319342446-76314pppppppp4629753第十六頁，共二十頁，2022年，8月28日鏈式存儲結(jié)構(gòu)帶行指針向量的單鏈表表示每行的非零元用一個單鏈表存放設置一個行指針數(shù)組，指向本行第一個非零元結(jié)點；若本行無非零元，則指針為空表頭結(jié)點與單鏈表結(jié)點類型定義typedefstructnode{intcol;intval;structnode*link;}JD;typedefstructnode*TD;^13573-11-12-242^^^^需存儲單元個數(shù)為3t+m第十七頁，共二十頁，2022年，8月28日十字鏈表設行指針數(shù)組和列指針數(shù)組，分別指向每行、列第一個非零元結(jié)點定義tpedefstructnode{introw,c