數(shù)據(jù)結(jié)構(gòu)-合肥工業(yè)大學(xué) 4(合肥工大)

第四章數(shù)組和廣義表華電計(jì)算機(jī)系第四章數(shù)組和廣義表★數(shù)組的邏輯結(jié)構(gòu)★數(shù)組的順序存儲(chǔ)分配★矩陣的壓縮存儲(chǔ)★稀疏矩陣★廣義表華電計(jì)算機(jī)系★數(shù)組的邏輯結(jié)構(gòu)NorthChinaElectricPowerUniversity一個(gè)二維數(shù)組的類型定義如下：

其中c,d設(shè)為1，數(shù)組可表示為：ElemType

A[c..m][d..n]

A=a11a12…a1na21a22…a2n…………am1am2…amn

它可以看成是由m個(gè)行向量或n個(gè)列向量組成的線性表。也即，二維數(shù)組可以看成是一種推廣的線性表，這種線性表的每一個(gè)數(shù)據(jù)元素本身也是一個(gè)線性表。類似地，一個(gè)三維數(shù)組可以看成是數(shù)據(jù)元素為二維數(shù)組的線性表一個(gè)n維數(shù)組可視為其數(shù)據(jù)元素為n-1維數(shù)組的線性表。華電計(jì)算機(jī)系NorthChinaElectricPowerUniversity★數(shù)組的順序存儲(chǔ)分配一.一維數(shù)組A[1:n]a1a2a3…an-1anLoc(ai)=Loc(a1)+(i-1)

kA[1:n]=(a1,a2,a3,…,an)若已知每個(gè)元素占k個(gè)存儲(chǔ)單元，并且知道第一個(gè)元素的存儲(chǔ)地址Loc(a1),則華電計(jì)算機(jī)系NorthChinaElectricPowerUniversity二.二維數(shù)組A[1:m][1:n]

a11a12a13

…

…a1n

a21a22a23

……a2nA[1:m][1:n]=…………am1am2am3

…

…

amn

行序?yàn)橹餍蚍峙浞绞?/p>

列序?yàn)橹餍蚍峙浞绞饺A電計(jì)算機(jī)系NorthChinaElectricPowerUniversitya11...a1na21...a2na31...aij...amn第1行第2行……

a11a12a13

…

…a1n

a21a22a23

……a2nA[1:m][1:n]=…………am1am2am3

…

…

amn

1.行序?yàn)橹餍蚍峙浞绞饺A電計(jì)算機(jī)系NorthChinaElectricPowerUniversity

a11a12a13

…

…a1n

a21a22a23

……a2na31a32a33

……a3nA[1:m][1:n]=…………aij……am1am2am3

…

…

amni-1

行

若已知每個(gè)元素占k個(gè)存儲(chǔ)單元，并且知道第一個(gè)元素的存儲(chǔ)地址LOC(a11),則

Loc(aij)=Loc(a11)+(i

1)

n

k+(j

1)

k

=Loc(a11)+[(i

1)

n+(j

1)]

k華電計(jì)算機(jī)系NorthChinaElectricPowerUniversitya11...am1a12...am2a13...aij...amn第1列第2列……

a11a12a13

…

…a1n

a21a22a23

……a2nA[1:m][1:n]=…………am1am2am3

…

…

amn

2.

列序?yàn)橹餍蚍峙浞绞饺A電計(jì)算機(jī)系NorthChinaElectricPowerUniversity

a11a12a13

…

…a1n

a21a22a23

……a2na31a32a33

……a3nA[1:m][1:n]=…………aij……am1am2am3

…

…

amnj-1列

若已知每個(gè)元素占k個(gè)存儲(chǔ)單元，并且知道第一個(gè)元素的存儲(chǔ)地址LOC(a11),則

Loc(aij)=Loc(a11)+(j

1)

m

k+(i

1)

k=Loc(a11)+[(j

1)

m+(i

1)]

k華電計(jì)算機(jī)系

a11a12a13

…

…a1n

a21a22a23

……a2nm=…………am1am2am3

…

…

amn

A[1:m][1:n]

所謂壓縮存儲(chǔ)是指為多個(gè)值相同的元素,或者位置分布有規(guī)律的那些元素分配盡可能少的存儲(chǔ)空間，而對(duì)0元素一般情況下不分配存儲(chǔ)空間。傳統(tǒng)做法★矩陣的壓縮存儲(chǔ)華電計(jì)算機(jī)系

a11a12a13

…

…a1n

a21a22a23

……a2na31a32a33

……a3nA[1:n][1:n]=…………an1an2an3

…

…

ann傳統(tǒng)做法：定義一個(gè)二維數(shù)組A[1:n,1:n]一.對(duì)稱矩陣的壓縮存儲(chǔ)

一個(gè)n階矩陣A的元素滿足性質(zhì)

aij

=aji

1≤i,j≤n則稱矩陣A為n階對(duì)稱矩陣。華電計(jì)算機(jī)系a11a21a22......aij......ann

k=123......n*(n+1)/2

a11a12a13

…

…a1n

a21a22a23

……a2na31a32a33

……a3nA[1:n][1:n]=…………an1an2an3

…

…

ann

A中任意一元素aij與V[k]之間存在對(duì)應(yīng)關(guān)系:k={i

(i-1)/2+j當(dāng)i≥j時(shí)j

(j-1)/2+i當(dāng)i<j時(shí)V華電計(jì)算機(jī)系只存儲(chǔ)下三角元素時(shí)尋址公式為：

loc(A[i][j])=loc(A[1][1])+[i(i-1)/2+j-1]*l傳統(tǒng)做法：定義一個(gè)二維數(shù)組

B[1:n][1:n]0元素0元素二.對(duì)角矩陣的壓縮存儲(chǔ)

若一個(gè)矩陣中，值非0的元素對(duì)稱地集中在主對(duì)角線兩旁的一個(gè)帶狀區(qū)域中(該區(qū)域之外的元素都為0元素)，稱這樣的矩陣為對(duì)角矩陣。例.

三對(duì)角矩陣的壓縮存儲(chǔ)

b11b12b21b22b23b32b33b34bn-1n

bnn-1

bnn0元素0元素非零元素的個(gè)數(shù)為3（n-2）+4B[1:n][1:n]=b11b12b21

bij

......

b22......

k=1234......3n-2

bnn

b11b12b21b22b23b32b33b34bn-1n

bnn-1

bnn0元素0元素B中任一非零元素bij

與V[k]之間存在對(duì)應(yīng)關(guān)系：k=2

i+j–2i=[k/3]+1j=k-2(i-1)B[1:n][1:n]=對(duì)角線數(shù)組中某元素尋址公式為：

loc(A[i][j])=loc(A[1][1])+[2(i-1)+j-1]*l傳統(tǒng)做法：定義一個(gè)二維數(shù)組A[1:6][1:6]一.什么是稀疏矩陣?一個(gè)較大的矩陣中，零元素的個(gè)數(shù)相對(duì)于整個(gè)矩陣元素的總個(gè)數(shù)所占比例較大時(shí)，可以稱該矩陣為一個(gè)稀疏矩陣。

M

=

1500220-150113000000-60000000091000000028000★稀疏矩陣三元組：(i,j,value)例如：

（1,1,15）表示第1行、第1列、值為15的元素。（1,4,22）表示第1行、第4列、值為22的元素。（1,6,-15）表示第1行、第6列、值為-15的元素。

15

00

22

0-15

0

11

3

000

000

-6

00

000000

91

00000

00

28

000二.稀疏矩陣的三元組表示(m,n,t)其中，m,n,t

分別表示稀疏矩陣的總的行數(shù)、總的列數(shù)與非零元素的總個(gè)數(shù)。

若一個(gè)m

n階稀疏矩陣具有t個(gè)非零元素，則用t+1個(gè)三元組來存儲(chǔ),其中第一個(gè)三元組分別用來給出稀疏矩陣的總行數(shù)m、總列數(shù)n以及非零元素的總個(gè)數(shù)t；第二個(gè)三元組到第t+1個(gè)三元組按行序?yàn)橹餍虻姆绞揭来未鎯?chǔ)t個(gè)非零元素。

M=

15

00

22

0

-15

0

11

3

000

000

-6

00

000000

91

00000

00

28

000

M[1:6][1:6]6681115142216-15221134-623351916328

A=A[1:9][1:3]1500220-150113000000-60000000091000000028000M=

1500091001100000300028220-6000000000-1500000N=表示稀疏矩陣M的三列的二維數(shù)組

[1][2][3]A[0]668A[1]1115A[2]1422A[3]16-15A[4]2211A[5]233A[6]34-6A[7]5191A[8]6328

[1][2][3]B[0]668B[1]1115B[2]1591B[3]2211B[4]323B[5]3628B[6]4122B[7]43-6B[8]61-15表示稀疏矩陣M的三列的二維數(shù)組A=B=三.矩陣的轉(zhuǎn)置1)轉(zhuǎn)置過程按照B數(shù)組中元素的最終排列順序進(jìn)行由于矩陣M的列經(jīng)過轉(zhuǎn)置后變?yōu)镹的行,所以可以按照M的列序來轉(zhuǎn)置.為了按順序找到M中的每一列的所有非0元素,對(duì)數(shù)組A從第一行起將每行的第二列掃描n遍,每遍掃描分別找到矩陣N的從第一行到第n行的各行所有非0元素,并產(chǎn)生B數(shù)組相應(yīng)的行。

void

transmat(A,B){(m,n,t)=(A[0,1],A[0,2],A[0,3]);(B[0,1],B[0,2],B[0,3])=(n,m,t);

if(A[p][2]==col){B[q][1]=A[p][2];B[q][2]=A[p][1];B[q][3]=A[p][3];q=q+1;}

}}華電計(jì)算機(jī)系if(t!=0)

{q=1;for(col=1;col<=n;col++)

for(p=1;p<=t;p++)

算法的評(píng)價(jià)1.空間開銷：2*3*(t+1)，當(dāng)t<1/3*(m*n)時(shí)，所需存儲(chǔ)量比按矩形結(jié)構(gòu)存儲(chǔ)的二維數(shù)組要少。2.時(shí)間開銷：O(n*t)。常規(guī)矩陣的轉(zhuǎn)置運(yùn)算需要的時(shí)間為O(n*m),

若非0元素的個(gè)數(shù)t與m*n有相同的數(shù)量級(jí)時(shí)，算法tranmat的運(yùn)算量就達(dá)到了O(m*n2)了，這時(shí)，雖然節(jié)省了一些存儲(chǔ)空間，卻浪費(fèi)了大量的計(jì)算時(shí)間。

算法的改進(jìn)之處：對(duì)A數(shù)組的掃描存在著浪費(fèi)現(xiàn)象，即n次掃描中每次都要檢查t個(gè)元素，實(shí)際并不需要。因?yàn)椋好看涡枰獟呙璧腁的元素在減少，凡在某遍掃描中已轉(zhuǎn)置到B中去的A的元素以后就不需要再掃描了。華電計(jì)算機(jī)系2)B數(shù)組中元素的生成不是順序的而是跳躍式的即轉(zhuǎn)換按數(shù)組A中行的順序進(jìn)行，但轉(zhuǎn)換后的元素在B中不是連續(xù)存放，而是將它放入它在B中最終應(yīng)占據(jù)的位置。設(shè)：Num[1..n]:存放矩陣N中各行非0元素的個(gè)數(shù);Pot[1..n]:存放矩陣N中各行第一個(gè)非0元素在數(shù)組B中應(yīng)占的位置.pot[1]=1pot[j]=pot[j-1]+num[j-1](2≤j≤n)1500220-150113000000-60000000091000000028000M=

j123456

Num[j]212201

Pot[j]134688Procedurefasttranmat(A,B);Begin(m,n,t):=(A[0,1],A[0,2],A[0,3]);(B[0,1],B[0,2],B[0,3]):=(n,m,t);NorthChinaElectricPowerUniversityift<>0then[fori:=1tondonum[i]:=0;fori:=1totdonum[A[i,2]]:=num[A[i,2]]+1;pot[1]:=1;

forj:=2tondopot[j]:=pot[j-1]+num[j-1];fori:=1totdo[k:=A[i,2];B[pot[k],1]:=A[i,2];B[pot[k],2]:=A[i,1];B[pot[k],3]:=A[i,3];pot[k]:=pot[k]+1;]]End;voidfasttranspo(A,B)

{

(m,n,t)=(A[0][1],A[0][2],A[0][3]);(B[0][1],B[0][2],B[0][3])=(n,m,t);NorthChinaElectricPowerUniversity

if(t!=0){for(j=1;j<=n;j++)num[j]=0;

for(i=1;i<=t;i++)num[A[i,2]]=num[A[i,2]]+1;

//各行非零元素個(gè)數(shù)pot[1]=1;

for(j=2;j<=n;j++)pot[j]=pot[j-1]+num[j-1];

各行第一個(gè)非零元素的地址

for(i=1;i<=t;i++){k=A[i][2];B[pot[k]][1]=A[i][2];B[pot[k]][2]=A[i][1];B[pot[k]][3]=A[i][3];pot[k]=pot[k]+1;}

}}四.矩陣的相乘30050-1002000S=0210-200434411314522-1312A=B=42412221131-2424由于兩個(gè)稀疏矩陣的積并不一定仍是稀疏矩陣，故結(jié)果矩陣c=s*r仍需采用通常的矩形結(jié)構(gòu)的二維數(shù)組存儲(chǔ)方式。NorthChinaElectricPowerUniversitym*nR=n*p在經(jīng)典算法中，不管元素是否為0都需要相乘，但實(shí)際上只有S[i,k]和R[k,j]均不為0時(shí)，乘積才不為0。因此，需在A、B中找出相應(yīng)的各對(duì)元素(即數(shù)組A中第二列的值與數(shù)組B中第一列的值相等的元素)相乘即可。為了得到非0的乘積，對(duì)A中每一行的元素(i,k,Sik)，需要在B中找到所有相應(yīng)的元素(k,j,Rkj),為了便于在B中尋找R中第k行的第一個(gè)非0元素，和前面類似，需設(shè)置兩個(gè)數(shù)組Num[1:n]和Pot[1:n]，其中num[k]表示R中第k行非0元素的個(gè)數(shù)；pot[k]表示R中第k行第一個(gè)非0元素在B中的位置。pot[1]=1pot[j]=pot[j-1]+num[j-1](2≤j≤n)華電計(jì)算機(jī)系下面我們就給出矩陣乘法的算法：Procedurematrix-multiplication(A,B,C);Begin(m,n,t1):=(A[0,1],A[0,2],A[0,3]);ifn=B[0,1]then(p,t2):=(B[0,2],B[0,3])else[Write(‘Incompatible

matrix’);exit;]華電計(jì)算機(jī)系ift1*t2=0thenexit;{乘積為0矩陣}fori:=1tomdoforj:=1topdoC[i,j]:=0;fori:=1tondonum[i]:=0;fori:=1tot2donum[B[i,1]]:=num[B[i,1]]+1;pot[1]:=1;fori:=2ton+1dopot[i]:=pot[i-1]+num[i-1];fori:=1tot1do[k:=a[i,2];forj:=pot[k]topot[k+1]-1doC[A[i,1],B[j,2]]:=C[A[i,1],B[j,2]]+A[i,3]*B[j,3];]End;voidmatrx-multiplication(A,B,C){(m,n,t1)=(A[0][1],A[0][2],A[0][3]);if(n==B[0][1])(p,t2)=(B[0][2],B[0][3]);else{printf(“%s”,”incompatiblematrices”);exit(1);//矩陣不相容，不必做，退出

}華電計(jì)算機(jī)系if(t1*t2==0)exit(1);//矩陣為零矩陣，不必做，退出for(i=1;i<=m;i++)for(j=1;j<=p;j++)C[i][j]=0;//結(jié)果矩陣初始化for(i=1;i<=n;i++)num[i]=0;

for(i=1;i<=t2;i++)num[B[i][1]]=num[B[i][1]]+1;pot[1]=1;for(i=2;i<=n+1;i++)pot[i]=pot[i-1]+num[i-1];for(i=1;i<=t1;i++){k=a[i][2];for(j=pot[k];j<=pot[k+1]-1;j++)C[A[i][1]][B[j][2]]=C[A[i][1]][B[j][2]]+A[i][3]*B[j][3]}}

即:華電計(jì)算機(jī)系026-1004C=為便于理解上述算法，說明如下：

因?yàn)镻ot[k]表示了R的第k行中第一個(gè)非零元素在B中的位置（行數(shù)），故pot[k+1]-1就表示了第k行中最后一個(gè)非零元素在B中的行數(shù)。為了正確表示出Ｒ中的第n行中的最后一個(gè)非零元素在B中的位置，故在數(shù)組pot中增加了一個(gè)元素pot[n+1]，且令pot[n+1]=pot[n]+num[n]此算法存儲(chǔ)量的占用為：O(3*(t1+t2)+2*n+m*p)

對(duì)于時(shí)間的復(fù)雜性,若認(rèn)為矩陣R每行中均為p個(gè)非零元素,則開銷為O(t1*p),故當(dāng)t1<<m*n時(shí),該算法比經(jīng)典算法要快些,在最壞情況下,即t1=O(m*n)時(shí),時(shí)間開銷變成O(m*n*p),與經(jīng)典算法相當(dāng),但其存儲(chǔ)開銷也將上升很快,所以,此算法也只適用于稀疏矩陣。如果算法得到的結(jié)果矩陣C仍是稀疏矩陣,并且它將繼續(xù)參加運(yùn)算,則可再把它變成三列的二維數(shù)組壓縮存儲(chǔ)形式。算法分析：執(zhí)行時(shí)間為:O（t1*p）其最壞情況下為O(m*n*p)

空間為：O(3*t1+t2)+2n+m*p用十字鏈表表示稀疏矩陣在鏈表中，稀疏矩陣的每個(gè)非零元素對(duì)應(yīng)一個(gè)含有五個(gè)域的結(jié)點(diǎn)，它們分別是

row:行域表示非零元素所在行

col:列域表示非零元素所在列

val:值域表示非零元素值

down:向下域,用以鏈接同一列中下一個(gè)非0元素

right:向右域,用以鏈接同一行中下一個(gè)非0元素結(jié)點(diǎn)結(jié)構(gòu)如下圖所示。rowcolvaldownright在十字鏈表中將稀疏矩陣每一行的非零元素通過right域鏈接成一個(gè)帶有表頭結(jié)點(diǎn)的行循環(huán)鏈表，將每一列的非零元素通過down域鏈接成一個(gè)帶有表頭結(jié)點(diǎn)的列循環(huán)鏈表。因此，每個(gè)非零元素即是第i行循環(huán)鏈表中的一個(gè)結(jié)點(diǎn)又是第j列循環(huán)鏈表中的一個(gè)結(jié)點(diǎn)。由于整個(gè)稀疏矩陣是由十字交叉的鏈結(jié)構(gòu)來表示的，故稱其為十字鏈表。如對(duì)下面的稀疏矩陣A可由如下圖所示的十字鏈表來表示。300700-1020000000000-8A=540000000000000000000011314731223-154-8H1H2H3H4H5H1H2H3H4H5HA54000000000011314731223-154-8H1H2H3H4H5HB

在表示有t個(gè)非零元素的m×n的矩陣的十字鏈表中，共有t+max（m，n）+1個(gè)結(jié)點(diǎn)，每個(gè)結(jié)點(diǎn)大約需要占用2～3個(gè)存儲(chǔ)單元。因此，只在矩陣非零元素個(gè)數(shù)t比矩陣的階m×n小的多的條件下，十字鏈表的存儲(chǔ)開銷才小于矩形結(jié)構(gòu)的二維數(shù)組的開銷m×n。

以上給出了稀疏矩陣的一種新的存儲(chǔ)思想，但如何將一個(gè)已知的稀疏矩陣以十字鏈表表示出來,還是一個(gè)需要解決的問題。下面我們就來討論在內(nèi)存中建立十字鏈表的具體算法。首先輸入三元組（m，n，t）它們是要存儲(chǔ)矩陣的行數(shù),列數(shù)及非零元素個(gè)數(shù),緊接著輸入t個(gè)形如（i，j，aij）的三元組,它們分別代表了t個(gè)非零元素行、列值及元素值，其輸入次序是按矩陣中以行為主順序輸入的。如此，對(duì)于前面圖中所示的含有5個(gè)非零元素的稀疏矩陣A。其輸入的數(shù)據(jù)依次為：5,4,5;1,1,3;1,4,7;2,3,-1;3,1,2;5,4,8算法中還需引入一輔助工作數(shù)組：

hdn：p[1：p]（p=max（m，n))及指針變量last。

其中hdn[i]是指向十字鏈表中第i行（也是第i列）行（列）鏈表的表頭結(jié)點(diǎn)的指針,last是指向當(dāng)前所建的行鏈表的最右（后）面的那個(gè)結(jié)點(diǎn)。這樣，建立十字鏈表的算法Mread（A）執(zhí)行的大致過程是：

i)按前述規(guī)定建立p個(gè)表頭結(jié)點(diǎn)（不包括HA）。

ii)建立每個(gè)行循環(huán)鏈表，在此過程中第i個(gè)鏈表示的表頭結(jié)點(diǎn)的val域先用來跟蹤第i列的列鏈表當(dāng)前最下（后）面的那個(gè)結(jié)點(diǎn)，其作用相當(dāng)于建立行鏈表時(shí)的指針last。

iii)建立表頭結(jié)點(diǎn)HA，并將全體p+1個(gè)表頭結(jié)點(diǎn)鏈成循環(huán)鏈表。算法具體描述如下：PROCEDUREMread(A)；

BEGINread(m，n，t)；p：=max(m，n)；

FORi=1TOpDO[newl(x);hdn[i]:=x;x↑.row:=x↑.col:=0;x↑.right:=x↑.val:=x];crow:=1;last:=hdn[1];FORi:=1TOtDO[read(rrow,cool,val);IFrrow>crowTHEN[last↑.right:=hdn[crow];crow:=rrow;last:=hdn[crow]]

newl(x);x↑.row:=rrow;

x↑.col:=ccol;

x↑.val:=val;last↑.right:=x;last:=x;(hdn[cool]↑.Val)↑.down:=x;

hdn[ccol]↑.val:=x]IFt≠0THENlast↑.right:=hdn[rrow];FORi:=1TOpDO[hdn[i].val)↑.down:=hdn[i];

newl(A);A↑.row:=m;A↑.col:=n;HA:=A;FORi:=1TOp-1DO

hdn[i]↑.val:=hdn[i+1];IFp=0THENHA↑.val:=HA;ELSE[hdn[p]↑.val:=ha;

ha↑.val:=hdn[1]]END;voidMread(A){

scanf(“%d,%d,%d”,m,n,t);p=max(m,n);for(i=1;i<=p;i++){x=neworthogonalNode;

hdn[i]=x;x->row=x->col=0;x->right=x->val=x;}crow=1;last=hdn[1];for(i=1;i<=t;i++){

scanf(“%d,%d,%d”,rrow,cool,val);if(rrow>crow){last->right=hdn[crow];crow=rrow;last=hdn[crow];}x=neworthogonalNode;x->row=rrow;x->col=ccol;x->val=val;

last->right=x;last=x;(hdn[cool]->val)->down=x;//建立列鏈

hdn[cool]->val=x;//追蹤當(dāng)前列鏈表的最下面一個(gè)結(jié)點(diǎn)

}if(t!=0)last->right=hdn[rrow];for(i=1;i<=p;i++)//閉合所有列鏈表

(hdn[i]->val)->down=hdn[i];A=neworthogonalNode;A->row=m;A->col=n;HA=A;for(i=1;i<=p-1;i++)

hdn[i]->val=hdn[i+1];if(p==0)HA->val=HA;Else{hdn[p]->val=HA;HA->val=hdn[1];}}

容易看出上述算法的時(shí)間復(fù)雜性為O(p+t)=O(m+n+t)，如果用矩形結(jié)構(gòu)的二維數(shù)組存儲(chǔ)矩陣時(shí),則所需時(shí)間為O(m*n)。因此，當(dāng)非零元素個(gè)數(shù)t比m*n小得多時(shí)用Mread算法存儲(chǔ)稀疏矩陣比用經(jīng)典方法要快。Aij=(i)

aij+bij(ii)

aij

(bij

=0)(iii)

bij

(aij

=0)

緊接著需要討論的問題是，在這種存儲(chǔ)結(jié)構(gòu)中，如何實(shí)現(xiàn)矩陣的運(yùn)算。最簡單的運(yùn)算是兩個(gè)m*n矩陣相加。設(shè)A，B是兩個(gè)用十字鏈表存儲(chǔ)的稀疏矩陣，我們討論A:=A+B的運(yùn)算，為區(qū)別和式A與被加數(shù)A寫為A=A+B，相加后不外乎這三種情況：當(dāng)將B加到A上去時(shí)，對(duì)A矩陣的十字鏈表來說，或者是改變結(jié)點(diǎn)的Val域值（aij+bij

≠0）,或者是不變（當(dāng)bij

=0時(shí)）或者是插入一個(gè)新結(jié)點(diǎn)（當(dāng)aij=0時(shí)），還可能是刪除一個(gè)結(jié)點(diǎn)（當(dāng)aij+bij=0時(shí)）。整個(gè)運(yùn)算可從矩陣的第一行開始，一行一行的進(jìn)行，一直到m行。對(duì)任何一行都從表頭結(jié)點(diǎn)出發(fā)找到各自的第一個(gè)結(jié)點(diǎn)開始進(jìn)行比較，為了便于插入和刪除結(jié)點(diǎn)，需設(shè)以下4組指針：

(1)ha，hb

分別表示矩陣A和B的十字鏈表的頭指針；

(2)Ca，Cb

分別指向A和B的行鏈表的表頭結(jié)點(diǎn)的指針；

(3)Pa，Pb

分別指向A和B的同一行上的兩個(gè)結(jié)點(diǎn)，這兩個(gè)指針將指向各非零元素；

(4)

qa指示Pa所指結(jié)點(diǎn)的行的前趨結(jié)點(diǎn)，為刪除插入服務(wù)。

hl[j]指示A矩陣中每一列的指針，初值指向每一列的列鏈表的表頭結(jié)點(diǎn)，以便在某行j列上插入或刪除某一結(jié)點(diǎn)時(shí)，讓hl[j]指向這一列的上一個(gè)結(jié)點(diǎn)。

(1)由Ca，Cb確定Pa，Pb，分別指向A和B鏈表中第一行第一個(gè)非零元素。pa=Ca->right；p=Cb->right；若B中該行中無非零元素（即Pb->Col=0）則令Ca，Cb指針下移，指向下一行（即Ca=Ca->val；Cb=Cb->val）。下面將矩陣B加到矩陣A上去的運(yùn)算過程大致描述如下：剛開始由ha，hb確定Ca，Cb：

Ca=ha->val;Cb=hb->val;

(2)否則，比較這兩個(gè)結(jié)點(diǎn)進(jìn)行相加，這時(shí)可能有上述所說的三種情況：

①若Pa->col<pb->col,且pa->col≠0（不是表頭結(jié)點(diǎn)）則令pa指向本行的下一個(gè)結(jié)點(diǎn)即:

qa=pa;pa=pa->right；并重新加以比較。②若pa->col>pb->col

或pa->col=0(A在該行無非零元素，B

相應(yīng)行有非零元素)

則將B中相應(yīng)結(jié)點(diǎn)插入A中，設(shè)新結(jié)點(diǎn)為P：

qa->right=p；p->right=pa;

修改A中的列指針，首先需找到同一列中上一個(gè)結(jié)點(diǎn)，然后令hl[j]指向該結(jié)點(diǎn)。于是A的列表指針改為：P->down=hl[j]->down;hl[j]->down=P;Pb=Pb->right;③若pa->col=pb->col,則pa->val=pa->val+pb->val；

若pa->val!=0，則qa=Pa;Pa=Pa->right;Pb=Pb->right

(為下一次比較做準(zhǔn)備)

若pa->val=0，則刪除A中該結(jié)點(diǎn)：Qa->right=Pa->right;hl[j]->down=Pa->down;然后Pa=qa->right;Pb=Pb->right;(為下一次比較做準(zhǔn)備)

(3)重復(fù)步驟(2)，直到B的同一行中沒有非零元素為止(即Pb.Col=0到表頭結(jié)點(diǎn)了)，然后轉(zhuǎn)向下一行。以此類推直到m行都進(jìn)行完為止。此時(shí)Ca，Cb分別又指向十字鏈表的頭結(jié)點(diǎn)，即Ca->row!=0;Cb->row!=0(因?yàn)镃b->row≠0表示是行鏈表的表頭結(jié)點(diǎn))

上述算法的整個(gè)運(yùn)算過程在于對(duì)A和B的十字鏈表逐行掃描，其循環(huán)次數(shù)主要取決于A和B矩陣中非零元素的個(gè)數(shù)ta和tb,因此此算法的時(shí)間復(fù)雜度為O（ta+tb）。這一節(jié)的最后，我們來看看如何把用十字鏈表表示的稀疏矩陣的所有結(jié)點(diǎn)還給可利用空間棧。這里假設(shè)可用空間棧是通過right域鏈接起來的單鏈表，表頭指針為av，其歸還算法并不復(fù)雜，直接用類C語言描述如下：voidMerase(ha);//將以ha為表頭指針的十字鏈表的全部結(jié)點(diǎn)歸還給av棧{next=ha->val;//記下第一行行鏈表表頭結(jié)點(diǎn)

ha->right=av;av=ha;

while(next≠ha){t=next->right;next->right=av;

av=t;next=next->val;}}★廣義表若ai

為不可再分割的原子元素，則稱ai

為原子元素；若ai

為一個(gè)子表，則稱ai

為表元素。這里，用小寫字母表示原子元素，用大寫字母表示表元素。一.廣義表的定義廣義表是一個(gè)長度n≥0的有限序列。記作LS=(a1,a2,……,an-1,an)其中，LS為廣義表的名字,ai為表中元素；ai

可以是原子元素，也可以是一個(gè)子表。n為表的長度，長度為0