第5章數(shù)組和廣義表

第5章數(shù)組數(shù)組可以看成是一種特殊的線性表，即線性表中數(shù)據(jù)元素本身也是一個(gè)線性表。5.1數(shù)組的定義和特點(diǎn)定義數(shù)組特點(diǎn)數(shù)組結(jié)構(gòu)固定數(shù)據(jù)元素同構(gòu)數(shù)組運(yùn)算給定一組下標(biāo)，存取相應(yīng)的數(shù)據(jù)元素給定一組下標(biāo)，修改數(shù)據(jù)元素的值()()()()()()()()()5.2數(shù)組的順序表示和實(shí)現(xiàn)次序約定以行序?yàn)橹餍蛞粤行驗(yàn)橹餍?/p>

a11a12……..a1n

a21a22……..a2n

am1am2……..amn

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

按行序?yàn)橹餍虼娣臿mn……..

am2am1……….a2n……..

a22a21a1n

…….a12

a1101n-1m*n-1n

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

a2na1n……….am2……..

a22a12am1

…….a21

a11

a11

a12

……..

a1n

a21

a22……..

a2n

am1

am2

……..amn

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

5.3矩陣的壓縮存儲(chǔ)矩陣是很多科學(xué)與工程計(jì)算問題中研究的數(shù)學(xué)對象,本節(jié)討論如何存儲(chǔ)矩陣的元,從而對矩陣進(jìn)行各種有效運(yùn)算；對一些特殊矩陣我們可以用很少的空間來存儲(chǔ)以到達(dá)壓縮的目的。5.3.1特殊矩陣對稱矩陣〔相同元素取一次，實(shí)現(xiàn)了壓縮〕

a11a12

….

……..a1n

a21

a22

……..…….a2n

an1

an2

……..ann

….a11a21a22a31a32an1ann

…...…...k=01234n(n-1)/2n(n+1)/2-1按行序?yàn)橹餍颍喝蔷仃?/p>

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)橹餍颍簩蔷仃?/p>

a11

a120

…………….0

a21

a22

a23

0

……………00

0

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

an-1,n0

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)橹餍颍篗由{(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〕唯一確定5.3.2稀疏矩陣定義：非零元較零元少，且分布沒有一定規(guī)律的矩陣壓縮存儲(chǔ)原那么：只存矩陣的行列維數(shù)和每個(gè)非零元的行列下標(biāo)及其值稀疏程度的計(jì)算：稀疏矩陣的壓縮存儲(chǔ)方法順序存儲(chǔ)結(jié)構(gòu)三元組表#defineM20typedefstructnode{inti,j;intv;}JD;JDma[M];三元組表所需存儲(chǔ)單元個(gè)數(shù)為3(t+1)其中t為非零元個(gè)數(shù)利用三元組表求稀疏矩陣的轉(zhuǎn)置〔1〕P98~996

7

8

121213931-3361443245218611564-7maijv012345678ma[0].i,ma[0].j,ma[0].v分別存放矩陣行列維數(shù)和非零元個(gè)數(shù)行列下標(biāo)非零元值帶輔助行向量的二元組增加一個(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偽地址表示法偽地址：本元素在矩陣中〔包括零元素在內(nèi)〕按行優(yōu)先順序的相對位置〔如-3,按行優(yōu)先順序?yàn)?5〕

6

7

2123915-3201424243018361539-7maaddrv偽地址非零元值矩陣行列維數(shù)012345678偽地址表示法需存儲(chǔ)單元個(gè)數(shù)為2(t+1)求轉(zhuǎn)置矩陣P98問題描述：一個(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)對于一個(gè)m×n的矩陣M，它的轉(zhuǎn)置矩陣T是一個(gè)n×m矩陣，且T(i,j)=M(j,i)，1≤i≤n，1≤j≤m。一個(gè)稀疏矩陣的轉(zhuǎn)置矩陣仍然是稀疏矩陣。例：上述矩陣M＝的轉(zhuǎn)置矩陣為：T＝由a轉(zhuǎn)置到b只需：i.將矩陣的行列值相互交換；ii.將每個(gè)三元組中的i和j相互調(diào)換； iii.重排三元組之間的次序便可實(shí)現(xiàn)矩陣的轉(zhuǎn)置。(6×7)6行7列(7×6)7行6列 (7×6)7行6列

ijvaluei(j)j(i)valuei(j)j(i)value

12 12211213－313 9319161531 －313－3211243 24342431952 182518342461 15161546－7i.和ii.iii.36 146314251864－746－76314假設(shè)a和b是TSMatrix型的變量，分別表示矩陣M和T。圖5.5 矩陣a轉(zhuǎn)置到矩陣b的過程實(shí)現(xiàn)方法：i.直接取順序存算法思想：按照b.data中三元組的次序依次在a.data中找到相應(yīng)的三元組進(jìn)行轉(zhuǎn)置。算法5.1如下：StatusTransposeSMatrix(TSMatrixM,TSMatrix&T){ //采用三元組表存儲(chǔ)表示，求稀疏矩陣M的轉(zhuǎn)置矩陣T。 T.mu=M.nu; T.nu=M.mu; T.tu=M.tu; if(T.tu){ q=1; for(col=1;col<=M.nu;++col) for(p=1;p<=M.tu;++p) if(M.data[p].j==col){ T.data[q].i=M.data[p].j; T.data[q].j=M.data[p].j; T.data[q].e=M.data[p].e; ++q; } } returnOK;}//TransposeSMatrixMrow

colelem

1

212

1

39

3

1–3

3

614

4

324

5

218

6

115

6

4-7M’row

colelem

2

112

3

19

1

3–3

6

314

3

424

2

518

1

615

4

6-7Mrow

colelem

1

212

1

39

3

1–3

3

614

4

324

5

218

6

115

6

4-7M’row

colelem

1

3

-3

1

615

2

112

2

5

18

3

19

3

424

4

6-7

6

3146

7

8

121213931-3361443245218611564-7ijv012345678ma7

6

8

13-3161521122518319342446-76314ijv012345678mbkppppppppkkkkppppppppcol=1col=2

時(shí)間復(fù)雜度：O(nu×tu)，即和M的列數(shù)及非零元的個(gè)數(shù)的乘積乘正比。當(dāng)非零元的個(gè)數(shù)tu和mu×nu同數(shù)量級時(shí)，算法5.1的時(shí)間復(fù)雜度就為O(mu×)了（例如，假設(shè)在100×500的矩陣中有tu＝10000個(gè)非零元），雖然節(jié)省了存儲(chǔ)空間，但時(shí)間復(fù)雜度提高了。因此，該算法僅適于tu<<mu×nu的情況。ii.順序取直接存 算法思想：按照a.data中三元組的次序進(jìn)行轉(zhuǎn)置，并將轉(zhuǎn)置后的三元組置入b中適當(dāng)?shù)奈恢谩Ｔ诖?，附設(shè)了num和cpot兩個(gè)向量。num[col]表示矩陣M中第col列中非零元的個(gè)數(shù)，cpot[col]指示M中第col列的第一個(gè)非零元在b.data中的恰當(dāng)位置。顯然有：cpot[1]=1;cpot[col]=cpot[col－1]+num[col－1]2≤col≤a.nu例如，對上述矩陣M，num和cpot的值如表5.1所示。表5.1 矩陣M的向量cpot的值col 1 2 3 4 5 6 7num[col] 2 2 2 1 0 1 0cpot[col]1 3 5 7 8 8 96

7

8

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

6

8

13-3161521122518319342446-76314pppppppp4629753StatusFastTransposeSMatrix(TSMatrixM,TSMatrix&T){ //采用三元組順序表存儲(chǔ)表示，求稀疏矩陣M的轉(zhuǎn)置矩陣T。 T.mu=M.nu; T.nu=M.mu; T.tu=M.tu; if(T.tu){ for(col=1;col<=M.nu;++col) num[col]=0; for(t=1;t<=M.tu;++t) ++num[M.data[t].j]; //求M中每一列含非零元個(gè)數(shù) cpot[1]=1; //求第col列中第一個(gè)非零元在b.data中的序號 for(col=2;col<=M.nu;++col) cpot[col]=cpot[col－1]+num[col－1]; for(p=1;p<=M.tu;++p){ col=M.data[p].j; q=cpot[col]; T.data[q].i=M.data[p].j; T.data[q].j=M.data[p].i; T.data[q].e=M.data[p].e; ++cpot[col]; }//for }//if returnOK;}//FastTransposeSMatrix算法5.2時(shí)間復(fù)雜度：O(nu＋tu).在M的非零元個(gè)數(shù)tu和mu×nu等數(shù)量級時(shí),其時(shí)間復(fù)雜度為O(mu×nu).②行邏輯鏈接的順序表1．定義行邏輯鏈接的順序表：帶行鏈接信息的三元組表。2．C語言描述typedefstruct{ Triple data[MAXSIZE+1]; //非零元三元組表 int rpos[MAXRC+1]; //各行第一個(gè)非零元的位置表 int mu,nu,tu; //矩陣的行數(shù)、列數(shù)和非零元個(gè)數(shù)}RLSMatrix3．矩陣相乘運(yùn)算時(shí)間復(fù)雜度是O()i.經(jīng)典算法若設(shè)Q=M×N，其中，M是矩陣，N是矩陣。當(dāng)n1＝m2時(shí)有： for(i=1;i<=m1;++i) for(j=1;j<=n2;++j){ Q[i][j]=0; for(k=1;k<=n1;++k) Q[i][j]+=M[i][k]*N[k][j]; } ii.稀疏矩陣相乘算法當(dāng)M和N是稀疏矩陣并用三元組表作存儲(chǔ)結(jié)構(gòu)時(shí)，不能套用上述算法。例如，×

=兩個(gè)稀疏矩陣相乘所得的乘積矩陣不是稀疏矩陣，故乘積矩陣不應(yīng)采用壓縮存儲(chǔ)，而應(yīng)以二維數(shù)組表示。算法思想：對于M中每個(gè)元素M.data[p](p=1,2,…,M.tu)，找到N中所有滿足條件M.data[p].j=N.data[q].i〔即M.data中的j值和N.data中的i值相等〕的元素N.data[q]，求得M.data[p].v和N.data[q].v的乘積。乘積矩陣Q中每個(gè)元素的值是個(gè)累計(jì)和，這個(gè)乘積M.data[p].v×N.data[q].v只是Q[i][j]中的一局部。為便于操作，并對每個(gè)元素設(shè)一累計(jì)和的變量，其初值為零，然后掃描數(shù)組M，求得相應(yīng)元素的乘積并累加到適當(dāng)?shù)那罄塾?jì)和的變量上。乘積矩陣Q中的元素是否為非零元，只有在求得其累加和后才能得知。由于Q中元素的行號和M中元素的行號一致，又M中元素排列是以M的行序?yàn)橹餍虻?，由此可對Q中元素進(jìn)行逐行處理，先求得累計(jì)求和的中間結(jié)果〔Q的一行〕，然后再壓縮存儲(chǔ)到Q.data中去。

找M.data中的j值和N.data中的i值相等的非零元相乘。如：P101的M.data[1]:1,1,3中的j=1N.data[1]:1,2,2中的i=1那么這兩個(gè)非零元值相乘得6，該值為乘積矩陣的第1行第2列。如此下去，只進(jìn)行三次的乘積運(yùn)算即可得矩陣的積。結(jié)論：兩個(gè)稀疏矩陣的乘積不一定是稀疏矩陣。

StatusMlutSMatrix(RLSMatrixM,RLSMatrixN,RLSMatrix&Q){ //求矩陣乘積Q=M×N，采用邏輯鏈接存儲(chǔ)表示。 if(M.nu!=N.mu) returnERROR; Q.mu=M.mu; Q.nu=M.nu; Q.tu=0; //Q初始化 if(M.tu*N.tu!=0){ //Q是非零矩陣 for(arow=1;arow<=M.mu;++arow){ //處理M的每一行 ctemp[]=0; //當(dāng)前各元素累加器清零 Q.rpos[arow]=Q.tu+1;if(arow<M.mu) tp=M.rpos[arow+1];兩個(gè)稀疏矩陣相乘(Q=M×N)的過程可大致描述如下：Q初始化；if(Q是非零矩陣){ //逐行求積 for(arow=1;arow<=M.mu;++arow){ //處理M的每一行 ctemp[]=0; //累加器清零 計(jì)算Q中第arow行的積并存入ctemp[]中； 將ctemp[]中非零元壓縮存儲(chǔ)到Q.data；}//forarow}//if算法5.3是上述過程求精的結(jié)果。算法5.3如下： else tp=M.tu+1; for(p=M.rpos[arow];p<tp;++p){

//為當(dāng)前行中每一個(gè)非零元找到對應(yīng)元在N中的行號 brow=M.data[p].j; if(brow<N.mu) t=N.rpos[brow+1]; else t=N.tu+1; for(q=N.rpos[brow];q<t;++q){ ccol=N.data[q].j; //乘積元素在Q中的列號 ctemp[ccol]+=M.data[p].e*N.data[q].e; }//forq }//求得Q中第crow(=arow)行的非零元 for(ccol=1;ccol<=Q.nu;++ccol) //壓縮存儲(chǔ)該行非零元 if(ctemp[ccol]){ if(++Q.tu>MAXSIZE) returnERROR; Q.data[Q.tu]=(arow,ccol,ctemp[ccol]); }//if }//forarow }//ifreturnOK;}//MlutSMatrix時(shí)間復(fù)雜度：O(M.mu×N.nu+M.tu×N.tu/N.mu)。其中累加器ctemp初始化的時(shí)間復(fù)雜度為O(M.mu×N.nu)，求Q的所有非零元的時(shí)間復(fù)雜度為O(M.tu×N.tu/N.mu)，進(jìn)行壓縮存儲(chǔ)的時(shí)間復(fù)雜度為O(M.mu×N.nu)。鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)帶行指針向量的單鏈表表示每行的非零元用一個(gè)單鏈表存放設(shè)置一個(gè)行指針數(shù)組，指向本行第一個(gè)非零元結(jié)點(diǎn)；假設(shè)本行無非零元，那么指針為空表頭結(jié)點(diǎn)與單鏈表結(jié)點(diǎn)類型定義typedefstructnode{intcol;intval;structnode*link;}JD;typedefstructnode*TD;^13573-11-12-242^^^^需存儲(chǔ)單元個(gè)數(shù)為3t+m十字鏈表1．定義

十字鏈表：在鏈表中，每個(gè)非零元既是某個(gè)行鏈表中的一個(gè)結(jié)點(diǎn)，又是某個(gè)列鏈表中的一個(gè)結(jié)點(diǎn)，這個(gè)矩陣構(gòu)成了一個(gè)十字交叉的鏈表結(jié)構(gòu)。可用兩個(gè)分別存儲(chǔ)行鏈表的頭指針和列鏈表的頭指針的一維數(shù)組表示之。2．結(jié)點(diǎn)結(jié)構(gòu)rowcolvaldownright其中，row，col和val分別表示該非零元所在的行、列和非零元的值。right域，用以鏈接同一行中下一個(gè)非零元。down域，用以鏈接同一列中下一個(gè)非零元。結(jié)點(diǎn)定義tpedefstructnode{introw,col,val;structnode*down,*right;}JD;113418225234^^^^^^^217^^從鍵盤接收信息建立十字鏈表算法算法分析：T(n)=o(ts)

其中：t——非零元個(gè)數(shù)

s=max(m,n)令q=NULL,p=rh[r-1],〔1〕尋找插入位置：當(dāng)p!=NULL且c>p->col時(shí)，p和q右移〔2〕插入：a、假設(shè)p==NULL且q==NULL，即本行空，那么rh[r-1]==s;b、假設(shè)p==NULL,q!=NULL，即走到行末，那么q->right=sc、假設(shè)c==p->col，那么修改p->vald、假設(shè)c<p->col且q==NULL，那么在p之前插入s，即s是行鏈表中第一個(gè)結(jié)點(diǎn)，令rh[r-1]=s;s->right=p;e、假設(shè)c<p->col且q!=NULL，那么在p之前插入s，即s->right=p;q->right=s;418^^234^^m=4,n=31,1,32,1,72,2,52,3,44,1,8Ch4_3.c113^^217^^225^^

例：寫出矩陣的三元組表和十字鏈表

5

6

6

115144168233347516三元組表ijv0123456115^516^^^347^^144168^233^^^^十字鏈表5.4廣義表的定義（1）定義廣義表又稱列表，是線性表的推廣。一般記作：其中，LS是廣義表的名稱（用大寫字母表示），n是它的長度?？梢允菃蝹€(gè)元素，也可以是另一個(gè)廣義表。原子：廣義表LS中是單個(gè)元素，則稱為原子。用小寫字母表示。

子表：廣義表LS中是廣義表，則稱為子表。

表頭（Head）：當(dāng)廣義表LS非空時(shí)，其第一個(gè)元素即為表頭。表尾（Tail）：廣義表LS中除表頭元素外，其余元素組成的表。由表頭、表尾的定義易知：任何一個(gè)非空列表其表頭可能是原子，也可能是列表，而其表尾必定是列表。廣義表的長度：表中元素的個(gè)數(shù)，深度：層次數(shù)，即括號的個(gè)數(shù)。例如：①A=()——A是一個(gè)空表，它的長度為零，深度為1。②B=(e)——列表B只有一個(gè)原子e，B的長度為1，深度也為1。③C=(a,(b,c,d))——列表C的長度為2，深度為2，兩個(gè)元素分別為原子a和子表(b,c,d)。④D=(A,B,C)——列表D的長度為3，深度為1，3個(gè)元素都是列表。將子表的值帶入后，那么有D=((),(e),(a,(b,c,d)))。⑤E=(a,E)——這是一個(gè)遞歸的表，它的長度為2，深度為∞。E相當(dāng)于一個(gè)無限的列表E=(a,(a,(a,…)))?！?〕廣義表的抽象數(shù)據(jù)類型定義ADTGList{ 數(shù)據(jù)對象：D={ei|i=1,2,…,n；n≥0；ei∈AtomSet或ei∈GList;} 數(shù)據(jù)關(guān)系：R1＝{<ei-1,ei>|ei-1,ei∈D,2≤i≤n} 根本操作： InitGList(&L); 操作結(jié)果：創(chuàng)立空的廣義表L。 CreateGList(&L,S); 初始條件：S是廣義表的書寫形式串。 操作結(jié)果：由S創(chuàng)立廣義表L。DestroyGList(&L); 初始條件：廣義表L已存在。 操作結(jié)果：銷毀廣義表L。CopyGList(&T,L); 初始條件：廣義表L已存在。 操作結(jié)果：由廣義表L復(fù)制得到廣義表T。GListLength(L); 初始條件：廣義表L已存在。 操作結(jié)果：求廣義表L的長度，即元素個(gè)數(shù)。GListDepth(L); 初始條件：廣義表L已存在。 操作結(jié)果：求廣義表L的深度。GListEmpty(L); 初始條件：廣義表L已存在。 操作結(jié)果：判定廣義表L是否為空。GetHead(L); 初始條件：廣義表L已存在。 操作結(jié)果：取廣義表L的頭。GetTail(L); 初始條件：廣義表L已存在。 操作結(jié)果：取廣義表L的尾。InsertFirst_GL(&L,e); 初始條件：廣義表L已存在。 操作結(jié)果：插入元素e作為廣義表L的第一個(gè)元素。DeleteFirst_GL(&L,&e); 初始條件：廣義表L已存在。 操作結(jié)果：刪除廣義表L的第一個(gè)元素，并用e返回其值。Traverse_GL(L,visit()); 初始條件：廣義表L已存在。 操作結(jié)果：遍歷廣義表L，用函數(shù)visit處理每個(gè)元素，}ADTGList①列表的元素可以是子表，而子表的元素還可以是子表……故，列表是一個(gè)多層次的結(jié)構(gòu)。如圖5.7所示的列表D。圖中圓圈表示列表，以方塊表示原子。②列表可為其他列表所共享。③列表可以是一個(gè)遞歸的表，即列表也可以是其本身的一個(gè)子表?！?〕3個(gè)重要結(jié)論：D

ABCE

ea

bcd

圖5.7 列表的圖形表示5.5廣義表的存儲(chǔ)結(jié)構(gòu)

因?yàn)閺V義表的數(shù)據(jù)元素是不定的，所以通常采用鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)來表示?！?〕頭尾鏈表存儲(chǔ)表示①結(jié)點(diǎn)結(jié)構(gòu)原子結(jié)點(diǎn)tag=0atomtag=1hptp

表結(jié)點(diǎn)tag：標(biāo)志域。tag＝1表示表結(jié)點(diǎn)；tag＝0表示原子結(jié)點(diǎn)。hp：指示表頭的指針域。tp：指示表尾的指針域。atom：值域。②C語言描述 typedefenum{ATOM,LIST}ElemTag;//ATO