1、第三章 稀疏矩陣和廣義表,3.1 稀疏矩陣 3.1.1 稀疏矩陣的定義 為了說明什么是稀疏矩陣，首先要知道什么是矩陣。矩陣（matrix）是一個具有m行n列的數(shù)表，共包含有mn個數(shù)(元素)，每個元素處在確定行和列的交點位置上，都與一對行號和列號唯一對應。當一個矩陣中的行數(shù)和列數(shù)相同時，即m=n時則稱為n階矩陣或方陣。如圖3-1(a)就是一個34的矩陣，它包含3行、4列，具有12個元素，每個元素都對應著唯一的行號和列號，如第1行與第1列交點位置上的元素5對應的行號和列號均為1，第2,行與第4列交點位置上的元素9對應的行號和列號分別為2和4。 圖3-1 矩陣和稀疏矩陣,稀疏矩陣（sparse ma

2、trix）是矩陣中的一種特殊情況，其非零元素的個數(shù)遠遠小于零元素的個數(shù)。如圖3-1(b)就是一個56的稀疏矩陣，該矩陣中共有30個元素，其中非零元素為7個，占元素總數(shù)的7/30。在實際應用中，稀疏矩陣一般都比較大，非零元素所占的比例都比較小。如對于一個100100的稀疏矩陣，若非零元素的個數(shù)為200，則非零元素占總元素個數(shù)的比例僅為1/50。,2. 稀疏矩陣的三元組線性表表示 在計算機中存儲矩陣的一般方法是采用二維數(shù)組，其優(yōu)點是可以隨機地訪問每一個元 素，因而能夠較容易地實現(xiàn)矩陣的各種運算，如轉(zhuǎn)置運算、加法運算、乘法運算等。但對于稀疏矩陣來說，采用二維數(shù)組的存儲方法既浪費大量的存儲單元用來存放

3、零元素，又要在運算中花費大量的時間來進行零元素的無效計算，顯然是不可取的。一種較好的方法是：只考慮存儲占元素中極少數(shù)的非零元素。 對于稀疏矩陣中的每個非零元素，可用它所在的行號、列號以及元素值這三元組(i,j,aij)來表示。若把所有的三元組按照行號為主序（即為主關鍵字）、列號為輔序（即為次關鍵字，當行號相同時再考慮列號次序）進行排列，則就構(gòu)成了一個表示稀疏矩陣的三元組線性表。圖3-1(b)稀疏矩陣所對應的三元組線性表表示為： (1,1,3),(1,4,5),(2,3,-2),(3,1,1),(3,3,4),(3,5,6),(5,3,-1) 稀疏矩陣采用三元組線性表表示后，可以使用順序或鏈接方

4、式存儲，從而比采用二維數(shù)組存儲要大大地節(jié)省存儲空間。,3. 稀疏矩陣的運算概述 對稀疏矩陣的運算與對一般用二維數(shù)組所表示的矩陣的運算相同，通常為求一個稀疏矩陣的轉(zhuǎn)置，計算兩個矩陣的和，計算兩個矩陣的乘積等。一個矩陣的轉(zhuǎn)置結(jié)果仍是一個矩陣，該矩陣中的第i行與第j列交點位置上的元素等于被轉(zhuǎn)置矩陣中第j行與第i列交點位置上的元素。兩個矩陣的和仍然是一個矩陣，該矩陣中的第i行第j列位置上的元素等于兩個相加矩陣中對應位置上的元素之和。兩個相乘矩陣的乘積仍然是一個矩陣，該矩陣中的第i行第j列位置上的元素等于第一個乘數(shù)矩陣中的第i行與第二個乘數(shù)矩陣中的第j列上對應元素乘積之累加和。假定第一個乘數(shù)矩陣為Amn

5、，第二個乘數(shù)矩陣為Bnp，乘積結(jié)果矩陣為Cmp，則C中任一元素Cij等于 ，其中1im，1jp。,下面給出對稀疏矩陣的一些典型運算(操作)，假定用M表示一個采用三元組線性表存儲的稀疏矩陣，其存儲類型用標識符Matrix表示。 (1) 初始化稀疏矩陣M，使它成為不含任何元素的空矩陣 void InitMatrix(Matrix M) (2) 根據(jù)稀疏矩陣的三元組線性表建立稀疏矩陣的存儲結(jié)構(gòu) void InlutMatrix(Matrix M),(3) 按照一定格式輸出稀疏矩陣 void OutputMatrix(Matrix M) (4) 返回稀疏矩陣M的轉(zhuǎn)置矩陣 Matrix Transpos

6、edMatrix(Matrix M (5) 返回稀疏矩陣M1和M2之和，要求兩個矩陣的行、列數(shù)均分別相同 Matrix AddMatrix(Matrix M1, Matrix M2) (6) 返回稀疏矩陣M1和M2之乘積，要求M1的列數(shù)等于M2的行數(shù) Matrix MultiplyMatrix(Matrix M1, Matrix M2),3.1.2 稀疏矩陣的存儲結(jié)構(gòu) 1. 順序存儲 稀疏矩陣的順序存儲就是對其相應的三元組線性表進行順序存儲。假定每個非零元素的三元組用如下記錄結(jié)構(gòu)定義： struct Triple int row, col; ElemType val; ; 其中row和col用

7、來分別存儲元素的行號和列號，val用來存儲元素值。 一個稀疏矩陣的順序存儲類型定義如下： struct SMatrix int m, n, t; struct Triple smMaxTerms+1; ;,其中m,n和t域分別用來存儲稀疏矩陣的行數(shù)、列數(shù)和非零元素的個數(shù)，sm數(shù)組域用來順序存儲每個三元組元素，假定下標為0的元素sm0不用，從下標為1起使用。MaxTerms為一個事先定義的全局常量，其值要大于等于非零元素的個數(shù)t，由它決定sm數(shù)組的大小。例如，若用SMatrix類型的對象存儲圖3-1(b)所示的稀疏矩陣，則m,n和t域的值應分別為5,6和7，sm數(shù)組中的內(nèi)容如圖3-2所示。,2.

8、 鏈接存儲 稀疏矩陣的鏈接存儲就是對其相應的三元組線性表進行鏈接存儲。下面介紹兩種鏈接存儲方法。 (1)帶行指針向量的鏈接存儲 在這種鏈接存儲中，需要把具有相同行號的三元組結(jié)點按照列號從小到大的順序鏈接成一個單鏈表，每個三元組結(jié)點的類型可定義為： struct TripleNode int row, col; /*存儲行號和列號*/ ElemType val; /*存儲元素值*/ struct TripleNode* next; /*指向同一行的下一個結(jié)點*/ ; 稀疏矩陣中的每一行對應一個單鏈表，每一個單鏈表都有一個表頭指針，為了把它們保存起來，便于訪問每一個單鏈表，需要使用一個行指針向量（

9、即一維數(shù)組），該向量中的第i個分量（即對應數(shù)組中下標為i的元素）用來存儲稀疏矩陣中第i行所對應的單鏈表的表頭指針。帶行指針向量的鏈接存儲類型定義如下： struct LMatrix int m, n, t; struct TripleNode* lmMaxRows+1; ;,其中，m、n和t分別用來保存稀疏矩陣的行數(shù)、列數(shù)和非零元素的個數(shù)，lm向量用來存儲m個行單鏈表的表頭指針，第i行單鏈表的表頭指針存于第i分量lmi中，而第0分量lm0未用，MaxRows為全局變量，其值要大于等于所存儲矩陣的行數(shù)。 例如，若利用LMatrix類型的對象存儲圖3-1(b)所示的稀疏矩陣，則鏈接存儲結(jié)構(gòu)如圖3-

10、3所示，其中每個單鏈表中的結(jié)點由動態(tài)分配鏈接而成。,圖3-3 帶行指針向量的鏈接存儲結(jié)構(gòu),3.1.3 稀疏矩陣的運算 1. 初始化運算 稀疏矩陣的存儲類型不同，其初始化過程也不同，對于SMatrix類型的對象，初始化過程為： void InitMatrix1(struct SMatrix* M) M-m=0; M-n=0; M-t=0; 對于LMatrix類型的對象，其初始化如下： void InitMatrix2(struct LMatrix* M) int i; M-m=0; M-n=0; M-t=0; for(i=1; ilmi=NULL; 對于CLMatrix類型的對象，初始化過程為：

11、,void InitMatrix3(struct CLMatrix* M) int i; M-m=0; M-n=0; M-t=0; for(i=1; irmi=NULL; for(i=1; icmi=NULL; 2. 稀疏矩陣的建立 稀疏矩陣的建立假定采用鍵盤輸入，輸入時應按照對應三元組線性表中三元組排列的次序進行，可以每行輸入一個三元組，行號、列號和元素值之間用空格分開，最后以按下回車鍵結(jié)束，當輸入完所有三元組后，以輸入一個特殊的三元組(0,0,0)結(jié)束整個輸入過程。若稀疏矩陣采用SMatrix類型存儲，則相應的輸入算法為： void InputMatrix1(struct SMatrix*

12、 M, int m, int n) /*m和n分別表示稀疏矩陣的行數(shù)和列數(shù)*/ int k=0; int row, col; ElemType val;,M-m=m; M-n=n; printf(輸入每個三元組:n); scanf(%d %d %d,while(row!=0) struct CrossNode *cp, *newp; k+; /*得到和建立一個新結(jié)點*/ newp=malloc(sizeof(struct CrossNode); newp-row=row; newp-col=col; newp-val=val; newp-right=newp-down=NULL; /*把新結(jié)點

13、鏈接到所在行單鏈表的末尾*/ cp=M-rmrow; if(cp=NULL) M-rmrow=newp; else while(cp-right!=NULL) cp=cp-right; cp-right=newp; /*把新結(jié)點鏈接到所在列單鏈表的末尾*/,cp=M-cmcol; if(cp=NULL) M-cmcol=newp; else while(cp-down!=NULL) cp=cp-down; cp-down=newp; /*輸入下一個三元組*/ scanf(%d %d %d, 3.2 廣義表 3.2.1 廣義表的定義 廣義表（generalized list）簡稱表，它是線性表的

14、推廣。一個廣義表是n(n0)個元素的一個序列，當n=0時則稱為空表。在一個非空的廣義表中，其元素可以是某一確定類型的對象(這種元素被稱做單元素)，也可以是由單元素構(gòu)成的表(這種元素可相對地被稱做子表或表元素)。顯然，廣義表的定義是遞歸的，廣義表是一種遞歸的數(shù)據(jù)結(jié)構(gòu)。,設ai為廣義表的第i個元素，則廣義表的一般表示與線性表相同： (a1,a2,ai,ai+1,an) 其中n表示廣義表的長度，即廣義表中所含元素的個數(shù)，n0。 同線性表一樣，也可以用一個標識符來命名一個廣義表，如用LS命名上面的廣義表，則為： LS=(a1,a2,ai,ai+1,an) 在廣義表的討論中，為了把單元素同表元素區(qū)別開來

15、，一般用小寫字母表示單元素，用大寫字母表示表，如： A=( ) B=(e) C=(a,(b,c,d) D=(A,B,C)=(),(e),(a,(b,c,d) E=(a,(a,b),(a,b),c) 其中A是一個空表，其長度為0；B是一個只含有單元素e的表，其長度為1；C中有兩個元素，一個是單元素a，另一個是表元素(b,c,d)，C的長度為2；D中有三個元素，其中每個元素又都是一個表，D的長度為3；E中只含有一個元素，該元素是一個表，該表中包含有三個元素，其中后兩個元素又都是表。,把每個表的名字（若有的話）寫在其表的前面也是一種表示廣義表的方法，對于上面的五個廣義表可相應地表示為： A( ) B

16、(e) C(a,(b,c,d) D(A( ),B(e),C(a,(b,c,d) E(a,(a,b),(a,b),c) 若用圓圈和方框分別表示表（表元素）和單元素，并用線段把表和它的元素（元素結(jié)點應在其表結(jié)點的下方）連接起來，則可得到一個廣義表的圖形表示。如上面五個廣義表的圖形表示如圖3-6所示。,圖3-6 廣義表的圖形表示,3.2.2 廣義表的存儲結(jié)構(gòu) struct GNode int tag; /*標志域*/ union /*值域或子表的表頭指針域*/ ElemType data; struct GNode* sublist; ; struct GNode* next; /*指向后繼結(jié)點的指

17、針域*/ ;,3.2.3 廣義表的運算 求廣義表長度的遞歸算法如下： int LenthGList(struct GNode* GL) /*求GL所指向的廣義表的長度*/ if(GL!=NULL) return 1+LenthGList(GL-next); else return 0; 下面是求一個廣義表深度的算法： int DepthGList(struct GNode* GL) /*求GL所指向的廣義表的深度*/ /*給max賦初值0*/ int max=0; /*遍歷表中的每一個結(jié)點,求出所有子表的最大深度*/,while(GL!=NULL) if(GL-tag=1) /*遞歸調(diào)用求出一個子表的深度*/ int dep=DepthGList(GL-sublist); /*讓max始終為同一層所求過的子表中深度的最大值*/ if(depmax) max=dep; GL=GL-next; /*使GL指向同一層的下一個結(jié)點*/ /*返回表的深度*/ return max+1; ,3.2.4 簡單程序舉例 該程序比較簡單，如下所示： #include #include typede