第3章2稀疏矩陣和廣義表

1、 1稀疏矩陣稀疏矩陣：非零元素個(gè)數(shù)遠(yuǎn)遠(yuǎn)少于零元素個(gè)數(shù)的矩陣非零元素個(gè)數(shù)遠(yuǎn)遠(yuǎn)少于零元素個(gè)數(shù)的矩陣 0000280000000091039000000006000017000110150022000A76 三元組線性表表示：三元組線性表表示：( (1,4,22),(1,7,15),(2,2,11),(2,6,17),(3,4,-6),(4,6,39),(5,1,91),(6,3,28) ) 2 2稀疏矩陣的三元組線性表表示稀疏矩陣的三元組線性表表示 稀疏矩陣若用二維數(shù)組存儲(chǔ)太浪費(fèi)空間。稀疏矩陣若用二維數(shù)組存儲(chǔ)太浪費(fèi)空間。 一般只考慮存儲(chǔ)非零元素，每個(gè)非零元素一般只考慮存儲(chǔ)非零元素，每個(gè)非零元素可由

2、行可由行、列列、值三元組值三元組(i, j, a(i, j, aijij) )表示，三元表示，三元組按行號(hào)為主序、列號(hào)為輔序進(jìn)行排列，構(gòu)成組按行號(hào)為主序、列號(hào)為輔序進(jìn)行排列，構(gòu)成一個(gè)表示稀疏矩陣的一個(gè)表示稀疏矩陣的三元組線性表。三元組線性表。 三元組線性表可用順序或鏈接方式存儲(chǔ)。三元組線性表可用順序或鏈接方式存儲(chǔ)。 3 3稀疏矩陣的抽象數(shù)據(jù)類型稀疏矩陣的抽象數(shù)據(jù)類型ADT SparseMatrix is Data: 用用三元組線性表表示的稀疏矩陣，三元組線性表表示的稀疏矩陣， 用類型名用類型名SMatrix表示表示 Operation: void InitMatrix(SMatrix &M);

3、 SMatrix Transpose(SMatrix &M); SMatrix Add(SMatrix &M1, SMatrix &M2); SMatrix Multiply(SMatrix &M1, SMatrix &M2); void InputMatrix(SMatrix &M, int m, int n); void OutputMatrix(SMatrix &M);end SparseMatrix有順序和鏈接兩種有順序和鏈接兩種三元組線性表及其行數(shù)三元組線性表及其行數(shù)、列數(shù)列數(shù)、非零元個(gè)數(shù)。非零元個(gè)數(shù)。1. 順序存儲(chǔ)順序存儲(chǔ) 用順序結(jié)構(gòu)存儲(chǔ)三元組線性表，即用順序結(jié)構(gòu)存儲(chǔ)三元組線性表，

4、即數(shù)組的每個(gè)元素?cái)?shù)組的每個(gè)元素對應(yīng)一個(gè)非零元的三元組。對應(yīng)一個(gè)非零元的三元組。 7 0 0 0 15 0 0 0 0 0 0 0 -2 0 0 0 0 21 0 0 0 -1 0 0A=12345rowcolval1 171 51534 -141 -246 21sm:MaxTermsmnt465非零元以行序?yàn)橹餍虼鎯?chǔ)非零元以行序?yàn)橹餍虼鎯?chǔ)( (1,1,7), (1,5,15), (3,4,-1), (4,1,-2), (4,6,21) )2. 鏈接存儲(chǔ)鏈接存儲(chǔ) 用鏈接結(jié)構(gòu)存儲(chǔ)三元組線性表用鏈接結(jié)構(gòu)存儲(chǔ)三元組線性表（1）帶行指針向量的鏈接存儲(chǔ)）帶行指針向量的鏈接存儲(chǔ) 每一行的非每一行的非零元零元

5、對應(yīng)一個(gè)單鏈表對應(yīng)一個(gè)單鏈表( (按列號(hào)次序按列號(hào)次序) )，用一維數(shù)組保存所有單鏈表的頭指針用一維數(shù)組保存所有單鏈表的頭指針。 7 0 0 0 15 0 0 0 0 0 0 0 -2 0 0 0 0 21 0 0 0 -1 0 0A=( (1,1,7), (1,5,15), (3,4,-1), (4,1,-2), (4,6,21) )12341 1 71 5 15 3 4 -1 4 1 -2 4 6 21 vectormnt465帶行指針向量的鏈接存儲(chǔ)結(jié)構(gòu)（2）十字鏈接存儲(chǔ)）十字鏈接存儲(chǔ) 既帶既帶行指針向量，又帶列指針向量，行指針向量，又帶列指針向量，每一個(gè)結(jié)點(diǎn)每一個(gè)結(jié)點(diǎn)同時(shí)位于兩個(gè)單鏈表中

6、同時(shí)位于兩個(gè)單鏈表中。 7 0 0 0 15 0 0 0 0 0 0 0 -2 0 0 0 0 21 0 0 0 -1 0 0A=515 11-2 4621 41714-1 3col val right down row cvrv ( (1,1,7), (1,5,15), (3,4,-1), (4,1,-2), (4,6,21) )12345rowcolval M.sm:MaxTermsM.mM.nM.t000 1 2 . . .MaxRows.M.vectorM.mM.nM.t00012345rowcolval M.sm:MaxTermsM.mM.nM.t 1 2 . . .MaxRows.

7、M.vectorM.mM.nM.t 7 0 0 0 15 0 0 0 0 0 0 0 -2 0 0 0 0 21 0 0 0 -1 0 0A=1234m.trowcolval1 171 51534 -141 -246 21sm:輸出：輸出：( (1,1,7), (1,5,15), (3,4,-1), (4,1,-2), (4,6,21) ) 7 0 0 0 15 0 0 0 0 0 0 0 -2 0 0 0 0 21 0 0 0 -1 0 0A=12345rowcolval1 171 51534 -141 -246 21sm:123451 171 4-243 -151 1564 21 7 0

8、0 -2 0 0 0 0 0 0 -1 0 0 0 0 0 A= 15 0 0 0 0 0 0 21 4*66*4 12345rowcolval1 171 51534 -141 -246 211 171 4-243 -151 1564 2112345rowcolval i /S存放轉(zhuǎn)置矩陣存放轉(zhuǎn)置矩陣for (i=1; i=M.t; i+) num M.smi.col +; LMatrix Add(LMatrix M1, LMatrix M2) int k=0; /統(tǒng)計(jì)非零元個(gè)數(shù)統(tǒng)計(jì)非零元個(gè)數(shù) Triple *p1, *p2, *p, *newptr; LMatrix M; InitMatri

9、x(M); M.m=M1.m; M.n=M1.n; if ( (M1.t=0) & (M2.t=0) ) return M; for (int i=1; icol col ) *newptr=*p1; p1=p1-next; else if (p1-col p2-col ) *newptr=*p2; p2=p2-next; else if ( p1-val + p2-val = 0 ) p1=p1-next; p2=p2-next; continue; else *newptr=*p1; newptr-val+=p2-val; p1=p1-next; p2=p2-next; /以下插入以下插入

10、newptr到第到第i行鏈尾，并后移行鏈尾，并后移p指針指針 newptr-next=NULL; if (p=NULL ) M.vectori=newptr; else p-next=newptr; p=newptr; k+; /while while (p1!=NULL) newptr=new TripleNode; *newptr=*p1; newptr-next=NULL; if (p=NULL ) M.vectori=newptr; else p-next=newptr; p=newptr; p1=p1-next; k+; /while while (p2!=NULL) newptr=

11、new TripleNode; *newptr=*p2; newptr-next=NULL; if (p=NULL ) M.vectori=newptr; else p-next=newptr; p=newptr; p2=p2-next; k+; /while /for M.t=k; return M;O(M1.t+M2.t) 廣義表廣義表是線性表的推廣。是線性表的推廣。廣義表廣義表是是 n(n=0) n(n=0) 個(gè)數(shù)據(jù)元素個(gè)數(shù)據(jù)元素a a1 1, a, a2 2, , ， a an n 構(gòu)成的有限序列，數(shù)構(gòu)成的有限序列，數(shù)據(jù)元素可以是單個(gè)元素（稱為據(jù)元素可以是單個(gè)元素（稱為單元素單元素），

12、也可以是），也可以是廣義表（稱為廣義表（稱為子表子表或或表元素表元素）。）。廣義表廣義表是一種遞歸是一種遞歸的數(shù)據(jù)結(jié)構(gòu)。的數(shù)據(jù)結(jié)構(gòu)。 廣義表廣義表一般表示為一般表示為: : LS = ( a1, a2, ， an ) n n 稱為稱為廣義表的廣義表的長度長度，n=0 n=0 時(shí)稱為時(shí)稱為空表空表 表示法：表示法： 小寫字母表示單元素，大寫字母表示表元素小寫字母表示單元素，大寫字母表示表元素 A=( ) B=(d) C=(a, (b,c) D=(A,B,C)=( (), (d), (a,(b,c) ) A( ) B( d ) C( a, (b,c) ) D( A(), B(d), C(a,(b,

13、c) ) 表的表的深度深度指括號(hào)嵌套的最大次數(shù)。指括號(hào)嵌套的最大次數(shù)。 A A和和B B的深度為的深度為1 1，C C的深度為的深度為2 2，D D的深度為的深度為3 3。dabcdabcA BCD A BC A=NULL0 d 0 a 1 0 b 0 c BC1 1 1 0 d 0 a 1 0 b 0 c D不帶表頭附加結(jié)點(diǎn)的鏈接結(jié)構(gòu)不帶表頭附加結(jié)點(diǎn)的鏈接結(jié)構(gòu)A=( ) B=(d)C=(a, (b,c) D=(A,B,C)=( (), (d), (a,(b,c) )A1 B1 0 a 1 0 b 0 c C1 0 d 帶表頭附加結(jié)點(diǎn)的鏈接結(jié)構(gòu)帶表頭附加結(jié)點(diǎn)的鏈接結(jié)構(gòu)A=( ) B=(d)C=

14、(a, (b,c) D=(A,B,C)=( (), (d), (a,(b,c) ) 遞歸算法如下：遞歸算法如下：（也可用非遞歸算法）也可用非遞歸算法） int Length(GLNode *GL) O(n) （n為結(jié)點(diǎn)為結(jié)點(diǎn)數(shù)）數(shù)） if (GL!=NULL) return 1 + Length(GL-next); else return 0; 采用不帶表頭附加結(jié)點(diǎn)的鏈接結(jié)構(gòu)采用不帶表頭附加結(jié)點(diǎn)的鏈接結(jié)構(gòu) 遞歸算法如下遞歸算法如下：(深度為所有子表中的最大深度加深度為所有子表中的最大深度加1) int Depth(GLNode *GL) O(n) （n為結(jié)點(diǎn)數(shù)）為結(jié)點(diǎn)數(shù)） int dep, m

15、ax=0; while (GL!=NULL) if (GL-tag=1) dep=Depth(GL-sublist); if (depmax) max=dep; GL=GL-next; return max+1; A=( ) #; B=(d) d; C=(a, (b,c) a,(b,c); D=( (), (d), (a,(b,c) ) (#), (d), (a,(b,c); 掃描每一個(gè)輸入的字符，根據(jù)不同類型作不同掃描每一個(gè)輸入的字符，根據(jù)不同類型作不同處理。若是空表（處理。若是空表（#），直接結(jié)束；若是單元素（字），直接結(jié)束；若是單元素（字母），先建立新結(jié)點(diǎn)，再遞歸調(diào)用建立后續(xù)結(jié)點(diǎn)或母），

16、先建立新結(jié)點(diǎn)，再遞歸調(diào)用建立后續(xù)結(jié)點(diǎn)或結(jié)束；若是子表（結(jié)束；若是子表（(），先遞歸調(diào)用建立子表，再），先遞歸調(diào)用建立子表，再遞歸調(diào)用建立后續(xù)結(jié)點(diǎn)或結(jié)束。遞歸調(diào)用建立后續(xù)結(jié)點(diǎn)或結(jié)束。void Create(GLNode *&GL) O(n)（n為讀入的字符數(shù)）為讀入的字符數(shù)） char ch; cinch / 只可能讀入只可能讀入 # 、 ( 及字母及字母 if (ch=#) GL=NULL; /建立空表建立空表 else if ( ch=( ) /遞歸構(gòu)造子表遞歸構(gòu)造子表 GL=new GLNode; GL-tag=1; Create(GL-sublist); else /建立單元素結(jié)點(diǎn)建立單

17、元素結(jié)點(diǎn) GL=new GLNode; GL-tag=0; GL-data=ch; cinch; / 只可能讀入只可能讀入 , 、 ) 及及 ; if (GL!=NULL) if (ch=,) Create(GL-next); /遞歸構(gòu)造后繼表遞歸構(gòu)造后繼表 else if ( (ch=) | (ch=;) ) GL-next=NULL; MPrint: 輸出廣義表最外層的一對括號(hào)，調(diào)用輸出廣義表最外層的一對括號(hào)，調(diào)用Print 輸出廣義表其余內(nèi)容。輸出廣義表其余內(nèi)容。 Print: 先輸出第一個(gè)元素（若是非空子表，則先輸出第一個(gè)元素（若是非空子表，則遞歸調(diào)用輸出），再遞歸調(diào)用輸出后繼表。遞歸調(diào)用輸出），再遞歸調(diào)用輸出后繼表。 void MPrint(GLNode *GL)