第三章 稀疏矩陣和廣義表(jian)

1、7600070015000001800000240001400003000000000009120M3.1稀疏矩陣3.1.1稀疏矩陣的定義非零元素個(gè)數(shù)較少，且分布沒有一定規(guī)律的矩陣第三章 稀疏矩陣和廣義表三元組線性表表示：只存矩陣的行列維數(shù)和每個(gè)非零元素的行列下標(biāo)及其值.M由(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）唯一確定稀疏矩陣的運(yùn)算概述：與用二維數(shù)組所表示的矩陣的運(yùn)算相同,通常為求一個(gè)稀疏矩陣的轉(zhuǎn)置,計(jì)算兩個(gè)矩陣的和,計(jì)算兩個(gè)矩陣的乘積等。首先，三元組用如

2、下記錄結(jié)構(gòu)定義： struct Triple int row, col; ElemType val; ; 其中row和col用來分別存儲元素的行號和列號，val用來存儲元素值。其次，一個(gè)稀疏矩陣的順序存儲類型定義如下： struct SMatrix int m, n, t; struct Triple smMaxTerms+1; ;3.1.2稀疏矩陣的存儲結(jié)構(gòu)1順序存儲結(jié)構(gòu)2鏈接存儲結(jié)構(gòu)l帶行指針向量的鏈接存儲 需要把具有相同行號的三元組結(jié)點(diǎn)按照列號從小到大的順序鏈接成一個(gè)單鏈表，每個(gè)三元組結(jié)點(diǎn)的類型可定義為： struct TripleNode int row, col; /*存儲行號和列號

3、*/ ElemType val; /*存儲元素值*/ struct TripleNode* next; ; /*指向同一行的下一個(gè)結(jié)點(diǎn)*/ 為便于訪問每一個(gè)單鏈表，需要使用一個(gè)行指針向量（即一維數(shù)組），該向量中的第i個(gè)分量（即對應(yīng)數(shù)組中下標(biāo)為i的元素）用來存儲稀疏矩陣中第i行所對應(yīng)的單鏈表的表頭指針。帶行指針向量的鏈接存儲類型定義如下： struct LMatrix int m, n, t; struct TripleNode* lmMaxRows+1; ; 其中，lm向量用來存儲m個(gè)行單鏈表的表頭指針，MaxRows為全局變量，其值要大于等于所存儲矩陣的行數(shù)。如對應(yīng)以上矩陣的帶行指針向量的鏈

4、接存儲u十字鏈表Y設(shè)行指針數(shù)組和列指針數(shù)組，分別指向每行、列第一個(gè)非零元Y結(jié)點(diǎn)定義row col valdownright34008000450003A113418225234v十字鏈接存儲3.2.1 稀疏矩陣的運(yùn)算 稀疏矩陣的建立稀疏矩陣的建立稀疏矩陣的輸出稀疏矩陣的輸出 3.2 廣義表廣義表 3.2.1 廣義表的定義 廣義表廣義表（generalized list）簡稱表，它是線性表的推廣。一個(gè)廣義表是n(n0)個(gè)元素的一個(gè)序列，當(dāng)n=0時(shí)則稱為空表。在一個(gè)非空的廣義表中，其元素可以是某一確定類型的對象(這種元素被稱做單元素)，也可以是由單元素構(gòu)成的表(這種元素可相對地被稱做子表或表元素)

5、。顯然，廣義表的定義是遞歸的，廣義表是一種遞歸的數(shù)據(jù)結(jié)構(gòu)。 設(shè)ai為廣義表的第i個(gè)元素，則廣義表的一般表示與線性表相同： (a1,a2,ai,ai+1,an) 其中n表示廣義表的長度，即廣義表中所含元素的個(gè)數(shù)，n0。 同線性表一樣，也可以用一個(gè)標(biāo)識符來命名一個(gè)廣義表，如用LS命名上面的廣義表，則為： LS=(a1,a2,ai,ai+1,an) 在廣義表的討論中，為了把單元素同表元素區(qū)別開在廣義表的討論中，為了把單元素同表元素區(qū)別開來，一般用小寫字母表示單元素，用大寫字母表示來，一般用小寫字母表示單元素，用大寫字母表示表，如：表，如： A=( ) B=(e) C=(a,(b,c,d) D=(A,

6、B,C)=(),(e),(a,(b,c,d) E=(a,(a,b),(a,b),c)若用圓圈表示表（表元素）若用圓圈表示表（表元素）,用方框表示單元素，用方框表示單元素，用線段把表和它的元素（元素結(jié)點(diǎn)應(yīng)在其表結(jié)點(diǎn)的用線段把表和它的元素（元素結(jié)點(diǎn)應(yīng)在其表結(jié)點(diǎn)的下方）連接起來，則可得到一個(gè)廣義表的圖形表示。下方）連接起來，則可得到一個(gè)廣義表的圖形表示。如上面五個(gè)廣義表的圖形表示如圖如上面五個(gè)廣義表的圖形表示如圖3-6所示。所示。3.2.2 廣義表的存儲結(jié)構(gòu)廣義表的存儲結(jié)構(gòu) struct GNode int tag; /標(biāo)志域標(biāo)志域 union ElemType data; /單元素?cái)?shù)值單元素?cái)?shù)值

7、struct GNode* sublist; /表元素的表頭指針表元素的表頭指針 ; struct GNode* next; ; /指向其后繼結(jié)點(diǎn)的指針域指向其后繼結(jié)點(diǎn)的指針域=0 單元素結(jié)點(diǎn)單元素結(jié)點(diǎn)=1 子表結(jié)點(diǎn)子表結(jié)點(diǎn)以上五個(gè)廣義表的鏈接存儲結(jié)構(gòu)的示意圖如下：以上五個(gè)廣義表的鏈接存儲結(jié)構(gòu)的示意圖如下： 3.2.3 廣義表的運(yùn)算廣義表的運(yùn)算廣義表的運(yùn)算主要有求廣義表的長度和深度，向廣義表的運(yùn)算主要有求廣義表的長度和深度，向廣義表插入元素和從廣義表中查找或刪除元素，建廣義表插入元素和從廣義表中查找或刪除元素，建立廣義表的存儲結(jié)構(gòu)，打印廣義表等。由于廣義表立廣義表的存儲結(jié)構(gòu)，打印廣義表等。由于

8、廣義表是一種遞歸的數(shù)據(jù)結(jié)構(gòu)，所以對廣義表的運(yùn)算一般是一種遞歸的數(shù)據(jù)結(jié)構(gòu)，所以對廣義表的運(yùn)算一般采用遞歸的算法。采用遞歸的算法。求廣義表的長度求廣義表的長度 在廣義表中，在廣義表中，同一層次的每個(gè)結(jié)點(diǎn)是通過同一層次的每個(gè)結(jié)點(diǎn)是通過next域域鏈接起來的，所以可把它看做是由鏈接起來的，所以可把它看做是由next域鏈接起域鏈接起來的單鏈表。來的單鏈表。因此求廣義表的長度是求單鏈表的長因此求廣義表的長度是求單鏈表的長度。遞歸算法如下：度。遞歸算法如下： int LenthGList(struct GNode* GL) if(GL!=NULL) return 1+LenthGList(GL-next); else return 0; 求廣義表的深度求廣義表的深度 廣義表深度的遞歸定義是它等于所有子表中表的最大深度廣義表深度的遞歸定義是它等于所有子表中表的最大深度加加1，若一個(gè)表為空或僅由單元素所組成，則深度為，若一個(gè)表為空或僅由單元素所組成，則深度為1。算。算法如下：法如下： int DepthGList(struct GNode* GL)