數(shù)據(jù)結(jié)構(gòu)-第七周-稀疏矩陣課件

矩陣是一個具有m行n列的數(shù)據(jù)表，共包含有m*n個元素，每個元素處在確定行和列的交點(diǎn)位置上，與一對行號和列號唯一對應(yīng)。

矩陣是很多科學(xué)與工程計算問題中研究的數(shù)學(xué)對象，在用高級語言編程時，一般采用二維數(shù)組來存儲矩陣。

矩陣 矩陣是一個具有m行n列的數(shù)據(jù)表，共包含有m*n個元素，每個普通矩陣的完全存儲如果矩陣中的每個元素的值都是不能確定的值，那么存儲這樣的矩陣時，每個元素都必須存儲，即需要完全存儲。

用高級語言描述時，就是使用二維數(shù)組的形式存儲矩陣。普通矩陣的完全存儲如果矩陣中的每個元素的值都是不能確定的值，有的矩陣中，非零元素非常少---稀疏矩陣還有一些矩陣的元素分布有一定的規(guī)律---特殊矩陣（比如對稱矩陣、三角矩陣）特殊矩陣和稀疏矩陣有的矩陣中，非零元素非常少---稀疏矩陣特殊矩陣和稀疏矩陣3

6

4

7

86

2

8

4

24

8

1

6

97

4

6

0

58

2

9

5

7對稱矩陣3c

c

c

c6

2

c

c

c48

1

c

c7

4

6

0

c8

2

9

5

7三角矩陣特殊矩陣36478對稱矩陣3cccc三a00a010

0

0a10a11

a120

00a21

a22

a23000

a32

a33

a340

0

0

a43

a44對角矩陣特殊矩陣a00a01000對角矩陣特殊矩陣15000210

000000

010600

0000509

00000稀疏矩陣稀疏矩陣15000210稀疏矩陣稀對于特殊矩陣和稀疏矩陣若仍采用二維數(shù)組形式存放，將造成存儲單元的很大浪費(fèi)?？梢岳眠@些矩陣的特點(diǎn)和規(guī)律，只存儲部分元素，從而提高存儲空間的利用率。矩陣的壓縮存儲對于特殊矩陣和稀疏矩陣矩陣的壓縮存儲特殊矩陣和稀疏矩陣的壓縮存儲 在對特殊矩陣和稀疏矩陣進(jìn)行存儲時，為了節(jié)省存儲空間，可以對這類矩陣進(jìn)行壓縮存儲。

壓縮存儲的基本思想是：⑴多個值相同的元素只分配一個存儲空間；⑵對零元素不分配存儲空間。

特殊矩陣和稀疏矩陣的壓縮存儲 在對特殊矩陣和稀疏矩陣進(jìn)行對稱矩陣的壓縮存儲3647862842481697460582957A＝n階對稱矩陣（方陣）特點(diǎn)：aij=aji如何壓縮存儲？只存儲下三角部分的元素或是上三角部分的元素，使得每兩個對稱元素共享一個存儲空間。對稱矩陣的壓縮存儲36478A＝n階對稱矩陣（方陣）壓縮存儲后節(jié)省了多少空間？對于一個n階對稱矩陣，如果完全存儲需要n2個存儲空間；如果壓縮存儲，需要n(n+1)/2個存儲空間。對稱矩陣的壓縮存儲3647862842481697460582957A＝壓縮存儲后節(jié)省了多少空間？對于一個n階對稱矩陣，如果完全存儲定義一個一維數(shù)組sa[n(n+1)/2]作為n階對稱矩陣A的存儲結(jié)構(gòu)，那么對稱矩陣A中任一元素aij和sa[k]之間的對應(yīng)關(guān)系如何？對稱矩陣的壓縮存儲定義一個一維數(shù)組sa[n(n+1)/2]作為n階對稱矩陣A的(a)下三角矩陣(b)存儲說明(c)計算方法aij在一維數(shù)組中的下標(biāo)=陰影部分的面積=

i×(i+1)/2+j

0…

i

n-10…j…n-1

aij每行元素個數(shù)12…iaij在本行中的序號aij第0行第1行…第i-1行對稱矩陣的壓縮存儲

(a)下三角矩陣(b)存儲說明對于下三角中的元素aij（i>=j），在一維數(shù)組sa中的下標(biāo)k與i、j的關(guān)系為：k＝i×(i＋1)/2＋j上三角中的元素aij（i＜j），因?yàn)閍ij＝aji，則訪問和它對應(yīng)的元素aji即可，即：k＝j(luò)×(j＋1)/2＋i

對稱矩陣的壓縮存儲

第1行第n-1行第0行

a00

a10

a11

a20

a21

a22

aij…

a

n-10

an-11…

an-1n-1…第2行012345kn(n+1)/2-1對于下三角中的元素aij（i>=j），在一維數(shù)組sa中的下標(biāo)例：將壓縮存儲在一維數(shù)組a中的4x4階對稱矩陣按矩陣格式輸出。inti,j;for(i=0;i<4;i++){for(j=0;j<4;j++)if(i>=j)cout<<a[i*(i+1)/2+j];/*輸出主對角線以及主對角線以下元素*/else

cout<<a[j*(j+1)/2+i];/*輸出主對角線以上元素*/cout<<endl;}例：將壓縮存儲在一維數(shù)組a中的4x4階inti,j;三角矩陣的壓縮存儲3c

c

c

c62c

c

c481c

c7460c82957(a)下三角矩陣34810c2946c

c１57c

c

c08c

c

c

c7(b)上三角矩陣n階上（下）三角矩陣是指下（上）三角（不包括主對角線）中的元素均為常數(shù)c三角矩陣的壓縮存儲3cccc(a)下三角矩陣的壓縮存儲3c

c

c

c62c

c

c481c

c7460c82957(a)下三角矩陣34810c2946c

c１57c

c

c08c

c

c

c7(b)上三角矩陣如何壓縮存儲三角矩陣？可以只存儲上三角（或下三角）部分的元素，對于常量c多開辟一個空間來存儲。三角矩陣的壓縮存儲3cccc(a)下下三角矩陣中任一元素aij在一維數(shù)組中的下標(biāo)k與i、j的對應(yīng)關(guān)系：i×(i＋1)/2＋j

當(dāng)i≥jn×(n＋1)/2

當(dāng)i＜jk=下三角矩陣的壓縮存儲012345

k

n(n+1)/2-1n(n+1)/2第1行第0行

a00

a10

a11

a20

a21

aij…

an-1n-1…第2行

c

a22存儲下三角元素對角線上方的常數(shù)——只存一個數(shù)據(jù)元素sa[n(n+1)/2]用于存放常量c下三角矩陣中任一元素aij在一維數(shù)組中的下標(biāo)k與i、j的對應(yīng)矩陣中任一元素aij在數(shù)組中的下標(biāo)k與i、j的對應(yīng)關(guān)系：

i×(2n-i+1)/2+j-i

當(dāng)i≤jn×(n＋1)/2

當(dāng)i＞jk=上三角矩陣的壓縮存儲存儲上三角元素對角線上方的常數(shù)——只存一個數(shù)據(jù)元素sa[n(n+1)/2]用于存放常量c矩陣中任一元素aij在數(shù)組中的下標(biāo)k與i、j的對應(yīng)關(guān)系：i對角矩陣壓縮存儲對角矩陣：n階對角矩陣是指所有非零元素都集中在以主對角線為中心的帶狀區(qū)域中，除了主對角線和它的上下方若干條對角線的元素外，所有其他元素都為零。

對角矩陣壓縮存儲對角矩陣：n階三對角矩陣：n階三對角矩陣的非零元素僅出現(xiàn)在主對角線(aii,0<=i<=n-1)上以及緊鄰主對角線上面的那條對角線上（aii+1,0<=i<=n-2)和緊鄰主對角線下面的那條對角線上（ai+1i,0<=i<=n-2)

a00

a01

000a10

a11

a12

000a21

a22

a23

000

a32

a33

a34000a43

a44A=5階三對角矩陣非零元素個數(shù)是？當(dāng)|i-j|>1時，元素aij=0n階三對角矩陣：n階三對角矩陣的非零元素僅出現(xiàn)在主對角線(a元素aij與一維數(shù)組下標(biāo)k的關(guān)系：k=2+3(i－1)+(

j－i+1)=2i+j

(b)一維數(shù)組元素sa[k]和矩陣元素aij的對應(yīng)關(guān)系(c)壓縮到一維數(shù)組中a00a01a10a11a12a21a22a23a32a33a34a43a440123456789101112三對角矩陣的壓縮存儲(a)三對角矩陣

0

00

000

000

000

A=a00

a01a10

a11

a12a21

a22

a23a32

a33

a34a43

a44元素aij與一維數(shù)組下標(biāo)k的關(guān)系：(b)一維數(shù)組元素sa稀疏矩陣的壓縮存儲1500000

0

0

00110

000600

0000009

00000A=若矩陣Amxn中的非零元素個數(shù)非常少，且非零元素的分布沒有任何規(guī)律，則稱該矩陣為稀疏矩陣。稀疏矩陣的壓縮存儲150000稀疏矩陣的壓縮存儲1500000

0110000

000600

0000009

00000A=如何只存儲非零元素？稀疏矩陣中的非零元素的分布沒有規(guī)律。稀疏矩陣的壓縮存儲150000由于稀疏矩陣中非零元素的分布沒有規(guī)律，因此在存儲非零元素的值的同時，還必須記下該非零元素在矩陣中的行號和列號。稀疏矩陣的壓縮存儲定義三元組：稀疏矩陣中的每個非零元素對應(yīng)一個三元組：(行號，列號，非零元素值)——三元組由于稀疏矩陣中非零元素的分布沒有規(guī)律，因此在存儲非零元素的值三元組表：將稀疏矩陣的所有非零元素對應(yīng)的三元組所構(gòu)成的集合，按行優(yōu)先的順序排列成一個三元組線性表。三元組表：((0,2,1),(1,1,2),(2,0,3),(3,3,5),(4,4,6),(5,5,7),(5,6,4))如何存儲三元組表？三元組表：將稀疏矩陣的所有非零元素對應(yīng)的三元組所構(gòu)成的集合，若把稀疏矩陣的三元組線性表按順序存儲結(jié)構(gòu)存儲,則稱為稀疏矩陣的三元組順序表。若把稀疏矩陣的三元組線性表按順序存儲結(jié)構(gòu)存儲,則稱為稀疏矩陣示例A5×6=003513053100017000600200210000100800rowcolval數(shù)組b[m]0352011330255033101417415622620527211381049834行號：0到4列號：0到5該三元組線性表按“行序?yàn)橹餍颉?，用一維數(shù)組進(jìn)行存放按“列序?yàn)橹餍颉钡娜M線性表示例A5×6=003513053100017000600227typedefstruct

//三元組的類型定義{

introw; //非零元素行號 intcol;//非零元素列號

ElemTypeval; //非零元素值}tupletype;#defineMAXSIZE100;

typedefstruct //三元組順序表存儲結(jié)構(gòu)定義{ tupletypedata[MAXSIZE];//非零元素的三元組表

intrnum;

//矩陣行數(shù) intcnum; //矩陣列數(shù) intlen; //矩陣總非零元素個數(shù)

}table;三元組順序表存儲結(jié)構(gòu)定義typedefstruct //三元組的類型定義#def三元組順序表采用順序存儲結(jié)構(gòu)存儲三元組表

0015

0322

05-15

1111

123

236

4091

空空空閑閑閑rowcole0123456MAXSIZE-11500220-15

0113000

000600

00000091

00000A=5（矩陣的行數(shù)）6（矩陣的列數(shù)）7（非零元個數(shù)）三元組順序表采用順序存儲結(jié)構(gòu)存儲三元組表0(1)從一個稀疏矩陣創(chuàng)建其對應(yīng)三元組表以行序方式掃描二維稀疏矩陣A,將其非零的元素插入到三元組順序表m的后面。算法如下：#defineM16#defineN17

voidCreatTable(table*m,ElemTypeA[M1][N1]){ inti,j; m->rnum=M1;m->cnum=N1;m->len=0; for(i=0;i<M1;i++) {for(j=0;j<N1;j++) if(A[i][j]!=0)/*只存儲非零元素*/{ m->data[m->len].row=i;

m->data[m->len].col=j;

m->data[m->len].val=A[i][j];

m->len++; } }}(1)從一個稀疏矩陣創(chuàng)建其對應(yīng)三元組表

(2)取值操作，從三元組表中取出稀疏矩陣指定位置的元素值算法思路：先在三元組m中找到指定的位置,然后將該處的元素值賦給x。

intgetvalue(table*m,ElemType*x,inti,intj){intk=0;

if(i>=m->rnum||j>=m->cnum)return0;while(k<m->len&&i>m->data[k].row)k++;//找第i行while(k<m->len&&j>m->data[k].col)k++;//找第j列

if(m->data[k].row==i&&m->data[k].col==j)//元素存在

{*x=m->data[k].val;return1;}elsereturn0;}(2)取值操作，從三元組表中取出稀疏矩陣指定位置的元(3)稀疏矩陣賦值，將給定值，賦值到三元組表的指定位置算法思路：先在三元組表m中找到指定的位置k,若指定位置已經(jīng)有值，則用給定值替換原有值，否則，將指定位置k及其后面的元素后移一位,然后將給定的元素值x插入到指定位置處。

intputValue(table*m,ElemTypex,inti,intj){inti,k=0;

if(i>=m->rnum||j>=m->cnum)return0;while(k<m->len&&i>m->data[k].row)k++;//找第i行while(k<m->len&&j>m->data[k].col)k++;//找第j列if(m->data[k].row==i&&m->data[k].col==j)//元素存在m->data[k].val=x; //用給定值x替換原值(3)稀疏矩陣賦值，將給定值，賦值到三元組表的指定位置else/*元素不存在時，將其插入*/{for(i=m->len-1;i>=k;i--)

/*元素后移*/{m->data[i+1]=m->data[i];}

m->data[k].row=i;

m->data[k].col=j;

m->data[k].val=x;

m->len++;}return1;}else/*元素不存在時，將其插入*/

(4)按矩陣格式輸出以三元組順序表存儲的稀疏矩陣算法思路：對稀疏矩陣中的每個元素，從頭到尾掃描三元組m,若在三元組表中存在，則輸出其元素值，否則輸出0。

voidDispTable(table*m)

{

inti,j,k,e;for(i=0;i<m->rnum;i++)

{for(j=0;j<m->cnum;j++)

{e=0;

for(k=0;k<m->len;k++)

if(i==m->data[k].row&&j==m->data[k].col)

{e=m->data[k].val;break;}

cout<<e<<"";

}

cout<<endl;}

}(4)按矩陣格式輸出以三元組順序表存儲的稀疏矩陣

(5)矩陣轉(zhuǎn)置對于一個m×n的稀疏矩陣Am×n,其轉(zhuǎn)置矩陣是一個n×m的稀疏矩陣Bn×m。矩陣正常存儲時，轉(zhuǎn)置的一般算法？(5)矩陣轉(zhuǎn)置矩陣正常存儲時，轉(zhuǎn)置的一般算法？

(5)稀疏矩陣Am×n用三元組順序表ta存儲，實(shí)現(xiàn)對稀疏矩陣的轉(zhuǎn)置算法思路（1）：顯然，稀疏矩陣的轉(zhuǎn)置依舊是稀疏矩陣。

稀疏矩陣Bn×m是稀疏矩陣Am×n的轉(zhuǎn)置矩陣,假設(shè)使用三元組表ta存儲稀疏矩陣A，如何得到存儲稀疏矩陣B的三元組表tb簡單方法是：將存儲存儲稀疏矩陣Am×n的三元組表ta的行列號互換就可以得到轉(zhuǎn)置后的三元組表tb(5)稀疏矩陣Am×n用三元組順序表ta存儲，實(shí)現(xiàn)對稀A3×4=0091250000106rowcolval三元組順序表ta092011230250131124236B4×3=0500019001206rowcolval三元組順序表tb090211203251031214326三元組表ta的行列號互換A3×4=0091250000106rowcolv

(5)稀疏矩陣轉(zhuǎn)置(互換行列號）voidtrans(table*ta,table*tb)

{ inti;

tb->rnum=ta->cnum;

tb->cnum=ta->rnum;

tb->len=ta->len; for(i=0;i<ta->len;i++)

{

tb->data[i].row=ta->data[i].col; tb->data[i].col=ta->data[i].row; tb->data[i].val=ta->data[i].val;}}算法缺點(diǎn)：無法保證三元組表tb也是以“行序?yàn)橹餍颉边M(jìn)行存放(5)稀疏矩陣轉(zhuǎn)置(互換行列號）算法缺點(diǎn)：算法思路（2）：為了保證三元組表tb也是以“行序?yàn)橹餍颉边M(jìn)行存放，按照三元組ta的列序（即轉(zhuǎn)置后三元組表tb的行序）進(jìn)行轉(zhuǎn)置。即將稀疏矩陣A，按照列序?qū)⒚苛兄械姆橇阍?，轉(zhuǎn)置后依次送入三元組表tb中存儲，這樣得到的三元組表tb恰好是以“行序?yàn)橹餍颉?。具體過程：第一次掃描三元組表ta時，逐個找出所有列號為0的三元組，轉(zhuǎn)置后按順序送入三元組表tb中；同理，第二遍掃描三元組表ta,逐個找出所有列號為1的三元組，轉(zhuǎn)置后按順序送入三元組表tb中；反復(fù)進(jìn)行，將所有列號都進(jìn)行一遍。最后一遍掃描三元組表tb,逐個找出所有列號為cunm-1的三元組，轉(zhuǎn)置后按順序送入三元組表tb中。

(5)稀疏矩陣Am×n用三元組順序表ta存儲，實(shí)現(xiàn)對稀疏矩陣的轉(zhuǎn)置算法思路（2）：(5)稀疏矩陣Am×n用三元組順序表tA3×4=0091250000106rowcolval三元組順序表ta092011230250131124236B4×3=0500019001206rowcolval三元組順序表tb01234對A逐列轉(zhuǎn)置即：逐行得到B對ta按照列號從0到cnum-1依次掃描？A3×4=0091250000106rowcolv

(5)稀疏矩陣轉(zhuǎn)置（逐行得到B）voidtrans(table*ta,table*tb){intk,b,q;

tb->rnum=ta->cnum;

tb->cnum=ta->rnum;

tb->len=ta->len;(5)稀疏矩陣轉(zhuǎn)置（逐行得到B）q=0； /*q為tb->data的下標(biāo)*/if(tb->len!=0)

{for(k=0;k<ta->cnum;k++)

for(p=0;p<ta->len;p++)/*p為ta->data的下標(biāo)*/ if(ta->data[p].col==k)

{

tb->data[q].row=ta->data[p].col;

tb->data[q].col=ta->data[p].row;

tb->data[q].val=ta->data[p].val; q++;

}

}}q=0； /*q為tb->data的下標(biāo)*/

以上算法的時間復(fù)雜度為O(ta->cnum*ta->len)而將二維數(shù)組存儲在一個m行n列矩陣中時,其轉(zhuǎn)置算法的時間復(fù)雜度為O(m*n)當(dāng)非零元素個數(shù)較小時，O(ta->cnum*ta->len)優(yōu)于O(m*n)以上算法的時間復(fù)雜度為算法思路（3）：分段定位總體思路：轉(zhuǎn)置時，對三元組表ta中的三元組依次進(jìn)行轉(zhuǎn)置，轉(zhuǎn)置后的三元組直接放到對應(yīng)稀疏矩陣B的三元組表tb中的分段位置上。為了能將待轉(zhuǎn)置的三元組表ta中的元素一次定位到三元組表tb的正確位置，需要預(yù)先對三元組表tb進(jìn)行分段定位。1）預(yù)先處理階段(a)計算稀疏矩陣A每一列中非零元素的個數(shù)（即：A轉(zhuǎn)置后的稀疏矩陣B每一行中非零元素的個數(shù)）設(shè)置一個數(shù)組num[]來存放這些數(shù)。例如：num[k]中存放的是矩陣A中第k列的非零元素的個數(shù)（即：矩陣B中第k行的非零元素的個數(shù)）

(5)稀疏矩陣Am×n用三元組順序表ta存儲，實(shí)現(xiàn)對稀疏矩陣的轉(zhuǎn)置算法思路（3）：分段定位(5)稀疏矩陣Am×n用三元組算法思路（3）：分段定位1）預(yù)先處理階段(b)計算稀疏矩陣A每一列中的第一個非零元素在三元組表tb中的正確位置（即：A轉(zhuǎn)置后的矩陣B每一行中的第一個非零元素在三元組表tb中的正確位置）設(shè)置一個數(shù)組pot[]來存放這些位置。例如：pot[k]中存放的是矩陣A中第k列中的第一個非零元素在三元組表tb中的正確位置算法思路（3）：分段定位A5×6=003513053100017000600002102000100800rowcolval0352011330255033101417415622621137203381049834三元組順序表ta1、計算數(shù)組num[]num[]數(shù)組初值為0；將三元組表ta掃描一遍，對于其中列號為k的元素，給相應(yīng)的num[k]加1。2、計算數(shù)組pot[]pot[0]=0;pot[k]=pot[k-1]+num[k-1];//k>=1A5×6=003513053100017000600002k012345num[k]212311pot[k]0235891）預(yù)先處理階段預(yù)先處理階段得到一個分段定位的結(jié)果k012345num[k]212311pot[k]02358算法思路（3）：分段定位2）轉(zhuǎn)置階段對三元組表ta進(jìn)行掃描。數(shù)組pot[]中的值記錄了矩陣A中每一列的第一個非零元素在三元組表tb中的正確位置。每當(dāng)矩陣A中第k列有一個非零元素存入到三元組表tb時，將pot[k]++，即：pot[k]始終存放矩陣A第k列中的下一個非零元素的正確位置。因此，通過pot[k]可以得到三元組表ta中每個元素轉(zhuǎn)置加入到三元組表tb時的正確位置。算法思路（3）：分段定位

(5)稀疏矩陣轉(zhuǎn)置（分段定位）voidtrans(table*ta,table*tb)

{intk,q,i;

intnum[N],pot[N];

tb->rnum=ta->cnum;

tb->cnum=ta->rnum;

tb->len=ta->len;(5)稀疏矩陣轉(zhuǎn)置（分段定位）for(k=0;k<ta->cnum;k++) /*初始化num[]為0*/{ num[k]=0; }for(i=0;i<ta->len;i++)

/*將三元組表ta掃描一遍，對于其中列號為k的元素，給相應(yīng)的num[k]加1。*/{ num[ta->data[i].col]++; }pot[0]=0;for(k=1;k<ta->cnum;k++)

/*計算pot[]各數(shù)組元素的值*/{ pot[k]=pot[k-1]+num[k]; }for(p=0;i<ta->len;p++){ j=ta->data[p].col; q=pot[j];

tb->data[q].row=ta->data[p].col; tb->data[q].col=ta->data[p].row; tb->data[q].val=ta->data[p].val;

pot[j]++;

/*矩陣A本列上下一個非零元素的位置，即矩陣B本行上下一個非零元素的位置*/} }for(k=0;k<ta->cnum;k++) /*初始

以上算法的時間主要耗費(fèi)在四個并列的單循環(huán)上，這四個并列的單循環(huán)分別循環(huán)了：ta->cnum、ta->len、ta->cnum、ta->len次，因此總的時間復(fù)雜度為：O(ta->cnum+ta->len)以上算法的時間主要耗費(fèi)在四個并列的單循環(huán)上，除了順序存儲，也可以把稀疏矩陣按鏈?zhǔn)酱鎯Y(jié)構(gòu)進(jìn)行壓縮存儲。除了順序存儲，也可以把稀疏矩陣按鏈?zhǔn)酱鎯Y(jié)構(gòu)進(jìn)行壓縮存儲。稀疏矩陣的三元組線性表的鏈?zhǔn)酱鎯?、簡單鏈?zhǔn)酱鎯ο∈杈仃嘇的每個非0元素對應(yīng)一個結(jié)點(diǎn)，結(jié)點(diǎn)含有的域?yàn)?row(行號)、col(列號),val(元素值),next(鏈域)。將所有的結(jié)點(diǎn)串成一個鏈表。稀疏矩陣簡單鏈?zhǔn)酱鎯κ纠∈杈仃嚨娜M線性表的鏈?zhǔn)酱鎯?、簡單鏈?zhǔn)酱鎯ο∈杈仃嘇的稀疏矩陣的三元組線性表的鏈?zhǔn)酱鎯?、行鏈表組將稀疏矩陣Am×n每一行中非零元素對應(yīng)的結(jié)點(diǎn)構(gòu)成一個鏈表，m個行鏈表形成一個鏈表組-----行鏈表組即：創(chuàng)建一個指針數(shù)組，數(shù)組元素中存放的就是某一行鏈表的第一個結(jié)點(diǎn)的地址，即該行鏈表的頭指針。例如：ah[i]是第i個行鏈表的頭指針稀疏矩陣的三元組線性表的鏈?zhǔn)酱鎯?、行鏈表組將稀疏矩陣Am×3、稀疏矩陣的正交鏈表（十字鏈表）存儲與實(shí)現(xiàn)正交鏈表存儲思路是：為稀疏矩陣的每一行非零元素設(shè)置一個單獨(dú)鏈表,同時也為每一列非零元素設(shè)置一個單獨(dú)鏈表。這樣稀疏矩陣的每一個非零元素就同時包含在兩個鏈表中,即：每一個非零元素同時包含在所在行的行鏈表中和所在列的列鏈表中。從而降低了鏈表的長度，也方便了行方向和列方向的搜索。稀疏矩陣的三元組線性表的鏈?zhǔn)酱鎯?、稀疏矩陣的正交鏈表（十字鏈表）存儲與實(shí)現(xiàn)稀疏矩陣的三元組采用正交鏈表存儲結(jié)構(gòu)來存儲稀疏矩陣：稀疏矩陣每個非零元素存儲為一個鏈表結(jié)點(diǎn)結(jié)點(diǎn)結(jié)構(gòu)為：rowcolvaldownrightrow：存儲非零元素的行號col：存儲非零元素的列號val：存儲非零元素的值right：指針域，指向同一行中的下一個非零元素結(jié)點(diǎn)down：指針域，指向同一列中的下一個非零元素結(jié)點(diǎn)采用正交鏈表存儲結(jié)構(gòu)來存儲稀疏矩陣：rowcolvaldow

202∧M=300501002000

003

035∧∧

111∧∧∧稀疏矩陣的壓縮存儲——正交鏈表∧存儲所有列鏈表的頭指針的指針數(shù)組存儲所有行鏈表的頭指針的指針數(shù)組任一非零元素M[i][j]所對應(yīng)的結(jié)點(diǎn)，既處在第i-1行的行鏈表上，又處在第j-1列的列鏈表上202∧M=3005正交鏈表結(jié)點(diǎn)結(jié)構(gòu)定義如下：typedef

struct

OLNode

{

int

row,

col;

//行號與列號

ElemType

val;

//值

struct

OLNode

*right,

*down;

//指針域

}OLNode,

*OLink;

typedef

struct

{

OLink

*rowhead,

*colhead;

//

存放行、列鏈表的頭指針的數(shù)組的首地址

int

rnum,

cnum,