第6章 特殊矩陣、廣義表及其應(yīng)用

1、第第6 6章章 16.1 數(shù)組與矩陣 6.2 特殊矩陣的壓縮存儲 6.3 矩陣的應(yīng)用實(shí)例 6.4 廣義表第6章 特殊矩陣、廣義表及其應(yīng)用第第6 6章章 2 6.1.1 數(shù)組與矩陣的概念及其相互關(guān)系 6.1.2 數(shù)組的存儲結(jié)構(gòu)第第6 6章章 3數(shù)組是滿足下列條件的同類型數(shù)據(jù)元素?cái)?shù)組是滿足下列條件的同類型數(shù)據(jù)元素 的集合：的集合： 對于該集合中任一數(shù)據(jù)元素對于該集合中任一數(shù)據(jù)元素 來說，來說，ji = 0，bi-1， i =1，2，n，n0稱為數(shù)組的維數(shù)，稱為數(shù)組的維數(shù)，bi是數(shù)組是數(shù)組第第i維的長度，維的長度，ji是數(shù)組元素的第是數(shù)組元素的第i維下標(biāo)；維下標(biāo)； 數(shù)據(jù)元素之間的關(guān)系表示為數(shù)據(jù)元素之

2、間的關(guān)系表示為Ri = |，0jkbk-1 ，1kn且且ki，0jibi-2 ，i =1，2，n，且且R = R1，R2，. Rn； nijjja.1nijjja.11nijjja.1nijjja.1第第6 6章章 4 下面以二維數(shù)組為例解釋上述關(guān)于數(shù)組的定義。下面以二維數(shù)組為例解釋上述關(guān)于數(shù)組的定義?！纠纠?.1】設(shè)有二維數(shù)組】設(shè)有二維數(shù)組A，其第，其第1維的長度維的長度b1= 3，第，第2維的長度維的長度b2 = 4；數(shù)據(jù)元素描述為，其中；數(shù)據(jù)元素描述為，其中j1 = 0，b1-1= 0，1，2，j2 = 0，b2-1= 0，1，2，3；則該二維數(shù)組共有；則該二維數(shù)組共有12個具有相同個

3、具有相同數(shù)據(jù)類型的數(shù)據(jù)元素，分別為：數(shù)據(jù)類型的數(shù)據(jù)元素，分別為： Amn = a11 a12 a1n a21 a22 a2n am1 am2 amn (1im, 1jn)第第6 6章章 5 可以看出，二維數(shù)組每一行是一個一維數(shù)組，元素可以看出，二維數(shù)組每一行是一個一維數(shù)組，元素間存在序偶關(guān)系；每一列也是一個一維數(shù)組，元素間也間存在序偶關(guān)系；每一列也是一個一維數(shù)組，元素間也同樣存在序偶關(guān)系。即：每個元素都受著兩個關(guān)系的約同樣存在序偶關(guān)系。即：每個元素都受著兩個關(guān)系的約束：束： 、 。 若把每一行看作是一個整體，則行與行之間是線性若把每一行看作是一個整體，則行與行之間是線性關(guān)系；若把每一列看作是一

4、個整體，則列與列之間也是關(guān)系；若把每一列看作是一個整體，則列與列之間也是線性關(guān)系。線性關(guān)系。 21jja121jja21jjia2jjia第第6 6章章 6 這樣，我們可以把二維數(shù)組看成是一個線性表，它這樣，我們可以把二維數(shù)組看成是一個線性表，它的每一個數(shù)據(jù)元素是一個一維數(shù)組，也是一個線性表。的每一個數(shù)據(jù)元素是一個一維數(shù)組，也是一個線性表。 由此可以推廣到由此可以推廣到n維數(shù)組。我們說維數(shù)組。我們說n維數(shù)組是一個線維數(shù)組是一個線性表，它的每一個數(shù)據(jù)元素是性表，它的每一個數(shù)據(jù)元素是n-1維數(shù)組，也是一個線維數(shù)組，也是一個線性表。性表。 數(shù)組一旦被定義，其維數(shù)及每維的長度數(shù)組一旦被定義，其維數(shù)及每

5、維的長度(維界維界)就不再就不再改變。因此，改變。因此，數(shù)組的運(yùn)算除了初始化和銷毀之外，只有數(shù)組的運(yùn)算除了初始化和銷毀之外，只有查找元素和修改元素值的操作。查找元素和修改元素值的操作。 第第6 6章章 7 矩陣是由矩陣是由mn個數(shù)排列成個數(shù)排列成m行行(橫向橫向)、n列列(縱向縱向)所所形成的矩形數(shù)表：形成的矩形數(shù)表： )1 ,1 (,.212222111211njmiaaaaaaaaaamnmmijnnnmA稱為稱為mn矩陣，簡記為矩陣，簡記為A=(aij)mn，其中，其中aij為為A的第的第i行行第第j列的元素。列的元素。 第第6 6章章 8 對照上述數(shù)組的定義，我們不難看出，矩陣中所有對

6、照上述數(shù)組的定義，我們不難看出，矩陣中所有數(shù)據(jù)元素組成了一個二維數(shù)組，矩陣的每一行、每一數(shù)據(jù)元素組成了一個二維數(shù)組，矩陣的每一行、每一列的數(shù)據(jù)元素分別組成等長的一維數(shù)組。列的數(shù)據(jù)元素分別組成等長的一維數(shù)組。 我們也可以說，矩陣是一個線性表，其每一個數(shù)據(jù)我們也可以說，矩陣是一個線性表，其每一個數(shù)據(jù)元素元素(行或列行或列)也是一個線性表。也是一個線性表。 第第6 6章章 9 6.1.1 數(shù)組與矩陣的概念及其相互關(guān)系 6.1.2 數(shù)組的存儲結(jié)構(gòu)第第6 6章章 10 由于數(shù)組一般不作插入和刪除操作，因此采用順序存儲結(jié)構(gòu)是理所當(dāng)然的。 下面以二維數(shù)組為例來說明：二維數(shù)組一般有兩種方法來存儲：1、按行優(yōu)先

7、順序存儲、按行優(yōu)先順序存儲 將數(shù)組元素按行向量排列， i+1行向量接在 i 行向量后面。第第6 6章章 11 a11 a12 . a1n a21 a22 . a2n am1 am2 . amn .Loc( aij)=Loc(a11)+(i-1)n+(j-1)*l 按行序?yàn)橹餍虼娣虐葱行驗(yàn)橹餍虼娣?amn . am2 am1 . a2n . a22 a21 a1n . a12 a1101n-1m*n-1n第第6 6章章 122、按列優(yōu)先順序存儲、按列優(yōu)先順序存儲 將數(shù)組元素按列向量排列， j+1列向量接在 j 列向量后面。第第6 6章章 13 按列序?yàn)橹餍虼娣虐戳行驗(yàn)橹餍虼娣?1m-1m*n-1

8、m amn . a2n a1n . am2 . a22 a12 am1 . a21 a11 a11 a12 . a1n a21 a22 . a2n am1 am2 . amn .Loc(aij)=Loc(a11)+(j-1)m+(i-1)*l 第第6 6章章 14 按上述兩種方式順序存儲的數(shù)組，只要知道按上述兩種方式順序存儲的數(shù)組，只要知道的值），以的值），以及及，就可求出各個數(shù)，就可求出各個數(shù)組元素的存儲地址。組元素的存儲地址。 第第6 6章章 15設(shè)設(shè) 數(shù)組的首地址數(shù)組的首地址 即：即： a11 的地址的地址 記為：記為： LOC (a11)則：二維數(shù)組按則：二維數(shù)組按“行優(yōu)先順序行優(yōu)先順

9、序”存儲，數(shù)組元素的存存儲，數(shù)組元素的存儲地址為：儲地址為： LOC (a11) + 前面前面 i 1行元素所占字節(jié)數(shù)行元素所占字節(jié)數(shù) + 第第j 行中前行中前j 1個元素所占字節(jié)數(shù)個元素所占字節(jié)數(shù)即：即：LOC( aij ) = LOC(a11) + ( i-1)*n*d +(j -1)*d 前面前面 i 1行元素的行元素的個數(shù)（每行個數(shù)（每行n個）個）每個元素所占每個元素所占的字節(jié)數(shù)的字節(jié)數(shù)第第6 6章章 16 Loc(aij)=Loc(a11)+(j-1)*m+(i-1)*K （盡管是方陣，但公式仍不同）（盡管是方陣，但公式仍不同）【例【例1 1】一個二維數(shù)組一個二維數(shù)組A A，行下標(biāo)的

10、范圍是，行下標(biāo)的范圍是1 1到到6 6，列下標(biāo)，列下標(biāo)的范圍是的范圍是0 0到到7 7，每個數(shù)組元素用相鄰的，每個數(shù)組元素用相鄰的6 6個字節(jié)存儲，個字節(jié)存儲，存儲器按字節(jié)編址。那么，這個數(shù)組占用存儲器按字節(jié)編址。那么，這個數(shù)組占用 個字節(jié)。個字節(jié)。 答：答： m*n*L=(6-1+1)*(7- 0 +1)*6=48*6=288第第6 6章章 17 6.1 數(shù)組與矩陣 6.2 特殊矩陣的壓縮存儲 6.3 矩陣的應(yīng)用實(shí)例 6.4 廣義表第6章 特殊矩陣、廣義表及其應(yīng)用第第6 6章章 18 在用高級語言編寫程序時，通常在用高級語言編寫程序時，通常。但對一些數(shù)據(jù)分布呈某種規(guī)律的矩陣，或是。但對一些數(shù)

11、據(jù)分布呈某種規(guī)律的矩陣，或是0元元素大量存在素大量存在(遠(yuǎn)遠(yuǎn)多于非遠(yuǎn)遠(yuǎn)多于非0元素元素)的矩陣，采用上述存儲的矩陣，采用上述存儲方法會造成存儲空間的極大浪費(fèi)。方法會造成存儲空間的極大浪費(fèi)。 第第6 6章章 19 若矩陣中非若矩陣中非0 0元素呈某種規(guī)律分布，或存在大量元素呈某種規(guī)律分布，或存在大量0 0元元素，為節(jié)省存儲空間，可對這類素，為節(jié)省存儲空間，可對這類： 即：即：。 若值相同的非若值相同的非0 0元素或元素或0 0元素在矩陣中的分布有一元素在矩陣中的分布有一定的規(guī)律，我們稱此矩陣為定的規(guī)律，我們稱此矩陣為；反之，稱為；反之，稱為。第第6 6章章 20 所謂特殊矩陣是指非零元素或零元素

12、的分布有一所謂特殊矩陣是指非零元素或零元素的分布有一定規(guī)律的矩陣，下面我們討論幾種特殊矩陣的壓縮定規(guī)律的矩陣，下面我們討論幾種特殊矩陣的壓縮存儲。存儲。 在一個在一個n n階方陣階方陣A A中，若元素滿足下述性質(zhì)：中，若元素滿足下述性質(zhì)： aij=aji 0=i, j=0)(i=0)，元素總數(shù)為：元素總數(shù)為：n(n+1)/2 因此，我們可以按從上到下、從左到右將這些元素存因此，我們可以按從上到下、從左到右將這些元素存放在一個向量放在一個向量san(n+1)/2中。為了便于訪問對稱矩陣中。為了便于訪問對稱矩陣A A中的元素，我們必須在中的元素，我們必須在aij和和sak之間找一個對應(yīng)關(guān)系。之間找

13、一個對應(yīng)關(guān)系。a11 a12 a1n a21 a22 a2n an1 an2 ann 第第6 6章章 23 若若，則，則aij在下三角形中。在下三角形中。 aij之前的之前的i i行（從第行（從第0 0行到第行到第i-1行）一共有行）一共有1+2+i=i(i+1)/2個元素，在第個元素，在第i i行行上，上， aij之前恰有之前恰有j個元素（即個元素（即ai0, ai1, ai2, , aij-1），因此），因此有：有： k=i*(i+1)/2+j 0k n(n+1)/2 若若，則，則aij是在上三角矩陣中。因?yàn)槭窃谏先蔷仃囍小Ｒ驗(yàn)閍ij= aji，所以只，所以只要交換上述對應(yīng)關(guān)系式中的要交

14、換上述對應(yīng)關(guān)系式中的i和和j即可得到：即可得到： k=j*(j+1)/2+i 0kj第第6 6章章 27 下三角矩陣的存儲和對稱矩陣類似，下三角矩陣的存儲和對稱矩陣類似，sak和和aij對應(yīng)對應(yīng)關(guān)系是：關(guān)系是： i(i+1)/2+j ij n(n+1)/2 ij k =第第6 6章章 28 對角矩陣中，所有的非零元素集中在以主對角線對角矩陣中，所有的非零元素集中在以主對角線為中心的帶狀區(qū)域中，即除了主對角線和主對角線相為中心的帶狀區(qū)域中，即除了主對角線和主對角線相鄰兩側(cè)的若干條對角線上的元素之外，其余元素皆為鄰兩側(cè)的若干條對角線上的元素之外，其余元素皆為零。下圖給出了一個三對角矩陣，零。下圖給

15、出了一個三對角矩陣， a00 a01 a10 a11 a12 a21 a22 a23 . . . an-2 n-3 an-2 n-2 an-2 n-1 an-1 n-2 an-1 n-1 第第6 6章章 29三對角矩陣有如下特點(diǎn)：三對角矩陣有如下特點(diǎn)： 1, 2, 11, 1, 101 , 0, 0nnjniiiijniji當(dāng)當(dāng)時，時，aij非非0； 其它情況時，其它情況時，aij的值為的值為0。 第第6 6章章 30 我們以行序?yàn)橹餍蜻M(jìn)行存儲三對角矩陣，并且只存我們以行序?yàn)橹餍蜻M(jìn)行存儲三對角矩陣，并且只存儲矩陣中的非儲矩陣中的非0元素。元素。 在在n階三對角矩陣中，除了第一行和最后一行只有階

16、三對角矩陣中，除了第一行和最后一行只有2個非個非0元素外，其余各行均有元素外，其余各行均有3個非個非0元素，元素， 共共2+2+3*(n-2) = 3n-2個非個非0元素。元素。 這樣，可以將該三對角矩陣存儲在一維數(shù)組這樣，可以將該三對角矩陣存儲在一維數(shù)組sa3n-2中?，F(xiàn)在，對給定的非中。現(xiàn)在，對給定的非0元素元素aij，與其對應(yīng)的數(shù)組元素的，與其對應(yīng)的數(shù)組元素的下標(biāo)是什么呢？下標(biāo)是什么呢？第第6 6章章 31 由三對角矩陣的特點(diǎn)知，矩陣中的非由三對角矩陣的特點(diǎn)知，矩陣中的非0元素元素aij的前的前面有面有i行，共有行，共有3i-1個非個非0元素；在元素元素；在元素aij所在的第所在的第i行

17、，行，aij之前有之前有j-i+1個非個非0元素。因此可得與非元素。因此可得與非0元素元素aij對應(yīng)對應(yīng)的數(shù)組元素的下標(biāo)為：的數(shù)組元素的下標(biāo)為： k=3i-1+j-i+1=2i+j 這樣，非零元素這樣，非零元素aij的地址為：的地址為： LOC(i,j)=LOC(0,0)+3*i-1+(j-i+1)*d =LOC(0,0)+(2i+j)*d第第6 6章章 32 上述的各種特殊矩陣，其非零元素的分布都是有上述的各種特殊矩陣，其非零元素的分布都是有規(guī)律的，因此總能找到一種方法將它們壓縮存儲到一規(guī)律的，因此總能找到一種方法將它們壓縮存儲到一個向量中，并且一般都能找到矩陣中的元素與該向量個向量中，并且

18、一般都能找到矩陣中的元素與該向量的對應(yīng)關(guān)系，通過這個關(guān)系，仍能對矩陣的元素進(jìn)行的對應(yīng)關(guān)系，通過這個關(guān)系，仍能對矩陣的元素進(jìn)行隨機(jī)存取。隨機(jī)存取。第第6 6章章 33 什么是稀疏矩陣？什么是稀疏矩陣？ 簡單說，設(shè)矩陣簡單說，設(shè)矩陣A A中有中有s s個非零元素，若個非零元素，若s s遠(yuǎn)遠(yuǎn)小于矩遠(yuǎn)遠(yuǎn)小于矩陣元素的總數(shù)（即陣元素的總數(shù)（即smst 存放矩陣M的數(shù)組是 adatamaxsize am , n , t data 1 3 -3 1 6 15 2 1 12 2 5 18 3 1 93 4 244 6 -75 3 14 第第6 6章章 40 第一個數(shù)組元素（三元組）所在的行號、列號分別第一個數(shù)

19、組元素（三元組）所在的行號、列號分別是：是： ( adata0).i (adata0) .j 它的值為：它的值為： ( adata0).v 第第6 6章章 41 若矩陣的非若矩陣的非0元素的個數(shù)和位置在操作過程中變化元素的個數(shù)和位置在操作過程中變化較大，則不宜采用順序存儲結(jié)構(gòu)來表示三元組的線較大，則不宜采用順序存儲結(jié)構(gòu)來表示三元組的線性表。性表。 可采用鏈?zhǔn)酱鎯Y(jié)構(gòu)來表示三元組的線性表?？刹捎面?zhǔn)酱鎯Y(jié)構(gòu)來表示三元組的線性表。第第6 6章章 42 在鏈表中，每個非在鏈表中，每個非0 0元素可用一個含有五個域的元素可用一個含有五個域的結(jié)點(diǎn)表示：結(jié)點(diǎn)表示：ijvcptrrptr i , j ,v

20、三個域分別表示該元素所在的行、列三個域分別表示該元素所在的行、列和非和非0元素的值。行指針域元素的值。行指針域 rptr 用以鏈接同一行中下一用以鏈接同一行中下一個非個非0元素；列指針域元素；列指針域 cptr 用以鏈接同一列中下一個非用以鏈接同一列中下一個非0元素。元素。 第第6 6章章 43 存儲時，每個非存儲時，每個非0 0元既是某個行鏈表中的一個結(jié)點(diǎn)，元既是某個行鏈表中的一個結(jié)點(diǎn)，又是某個列鏈表中的一個結(jié)點(diǎn)；整個矩陣構(gòu)成了一個十又是某個列鏈表中的一個結(jié)點(diǎn)；整個矩陣構(gòu)成了一個十字交叉的鏈表字交叉的鏈表故稱這樣的存儲結(jié)構(gòu)為故稱這樣的存儲結(jié)構(gòu)為 兩個兩個一維一維數(shù)組數(shù)組 M-chead M-

21、rhead 第第6 6章章 44十字鏈表中非十字鏈表中非0元結(jié)點(diǎn)的類型說明如下：元結(jié)點(diǎn)的類型說明如下： typedef struct lnode int i , j ; datatype v ; struct lnode *cptr , *rptr ; OLnode； ijvcptrrptr第第6 6章章 45十字鏈表的類型描述如下：十字鏈表的類型描述如下： #define N 10 /預(yù)設(shè)稀疏矩陣的行數(shù)預(yù)設(shè)稀疏矩陣的行數(shù) #define K 10 /預(yù)設(shè)稀疏矩陣的列數(shù)預(yù)設(shè)稀疏矩陣的列數(shù) typedef /*行數(shù)、列數(shù)、非行數(shù)、列數(shù)、非0元個數(shù)元個數(shù)*/ Crosslist ; Crossli

22、st *M ; 第第6 6章章 46 討論：討論：如何建立一個十字鏈表如何建立一個十字鏈表 算法步驟：算法步驟： 1、建立兩個一維數(shù)組 Mchead 、 Mrhead 分別存儲列鏈表及行鏈表的頭指針。 初始時， Mcheadj = NULL , Mrheadj = NULL. 2、讀入非0元結(jié)點(diǎn)的三元組（ i , j , v ），生成一個結(jié)點(diǎn)*p ,將其插入第 i 個行鏈表和第j個列鏈表的正確位置上。 第第6 6章章 47 6.1 數(shù)組與矩陣 6.2 特殊矩陣的壓縮存儲6.3 矩陣的應(yīng)用實(shí)例 6.4 廣義表第6章 特殊矩陣、廣義表及其應(yīng)用第第6 6章章 48求稀疏矩陣求稀疏矩陣A A的轉(zhuǎn)置矩陣

23、的轉(zhuǎn)置矩陣B B 一個一個m mn n的矩陣的矩陣A A，它的轉(zhuǎn)置，它的轉(zhuǎn)置B B是一個是一個n nm m的矩陣，的矩陣，且且aij=bjiaij=bji，0 0i im m，0 0j jn n，即，即A A的行是的行是B B的的列，列，A A的列是的列是B B的行的行。0 0 -3 0 0 1512 0 0 0 18 09 0 0 24 0 00 0 0 0 0 70 0 14 0 0 0 0 0 0 0 0 00 0 0 0 0 0A = 0 12 9 0 0 0 00 0 0 0 0 0 0-3 0 0 0 14 0 00 0 24 0 0 0 00 18 0 0 0 0 0 15 0

24、0 -7 0 0 0B = 第第6 6章章 49 將將A A轉(zhuǎn)置為轉(zhuǎn)置為B B，就是將，就是將A A的三元組表的三元組表a-dataa-data置換為表置換為表B B的三元組表的三元組表b-datab-data。 有有： at = bt ; am = bn ; an = bm ; 但但:(adatax).i (bdatax).j 為什么？ 第第6 6章章 50 也不能將也不能將 (adatax).i 與與(adatax).j 簡單互簡單互換！換！為什么？ 如果只是簡單地交換如果只是簡單地交換a-dataa-data中中i i和和j j的內(nèi)容，那的內(nèi)容，那么得到的么得到的b-datab-data

25、將是一個按列優(yōu)先順序存儲的稀疏矩將是一個按列優(yōu)先順序存儲的稀疏矩陣陣B B，要得到按行優(yōu)先順序存儲的，要得到按行優(yōu)先順序存儲的b-datab-data，就必須重新，就必須重新排列三元組的順序。排列三元組的順序。 第第6 6章章 510 0 -3 0 0 1512 0 0 0 18 09 0 0 24 0 00 0 0 0 0 70 0 14 0 0 0 0 0 0 0 0 00 0 0 0 0 0A = 0 12 9 0 0 0 00 0 0 0 0 0 0-3 0 0 0 14 0 00 0 24 0 0 0 00 18 0 0 0 0 0 15 0 0 -7 0 0 0B = 行號行號i

26、列號列號j 值值v行號行號i 列號列號j 值值v1 3 -31 6 152 1 122 5 18 3 1 93 4 244 6 -75 3 141 2 12 1 3 93 1 -33 5 144 3 245 2 186 1 156 4 -7第第6 6章章 52算法步驟如下：算法步驟如下：(1) 產(chǎn)生順序表b，存放轉(zhuǎn)置后的矩陣B Spmatrix *b; b = malloc( sizeof (Spmatrix); 并并確定其結(jié)點(diǎn)個數(shù)、行數(shù)、列數(shù)。即：bt = at ;bm = an ; bn = am ;第第6 6章章 53(2) 一維數(shù)組一維數(shù)組 bdata結(jié)點(diǎn)個數(shù)結(jié)點(diǎn)個數(shù) 中各數(shù)組元素賦值

27、，中各數(shù)組元素賦值，且且bdata 按行優(yōu)先。按行優(yōu)先。 具體做法如下：具體做法如下： 對三元組表對三元組表adata 掃描掃描(從第一行開始從第一行開始) 令：令：x為數(shù)組為數(shù)組adata 中數(shù)組元素的下標(biāo)中數(shù)組元素的下標(biāo) y為數(shù)組為數(shù)組bdata 中數(shù)組元素的下標(biāo)中數(shù)組元素的下標(biāo)第第6 6章章 54掃描過程：掃描過程：首先，令首先，令 y = 0; for (x = 0; x datax).j = = 1 (1是列號是列號) 若為1 則 (bdatay).v = (adatax).v (bdatay).i = (adatax).j (bdatay).j = (adatax).i y+第第6

28、 6章章 55 下面再次掃描三元組表（數(shù)組）下面再次掃描三元組表（數(shù)組）adata ，查，查尋矩陣尋矩陣M中第二列的元素：中第二列的元素：此時，此時，； for (x = 0; x datax).j = = 2 (2是列號是列號) 若為若為2 則則 (bdatay).v = (adatax).v (bdatay).i = (adatax).j (bdatay).j = (adatax).i y+第第6 6章章 56這樣，整個掃描的過程可描述為： for ( = 1; =； +) for (x = 0; x datax).j = = ) (bdatay).v = (adatax).v ; (bd

29、atay).i = (adatax).j ; (bdatay).j = (adatax).i ; y+ ; 第第6 6章章 57算法分析：算法分析： 該算法的時間主要耗費(fèi)在 z 和 x 的二重循環(huán)上，若矩陣M的列數(shù)為 n ，非0元素個數(shù)為 t ，則 算法的時間復(fù)雜度數(shù)量級為算法的時間復(fù)雜度數(shù)量級為: O( n*t )第第6 6章章 58 6.1 數(shù)組與矩陣 6.2 特殊矩陣的壓縮存儲 6.3 矩陣的應(yīng)用實(shí)例 6.4 廣義表第6章 特殊矩陣、廣義表及其應(yīng)用第第6 6章章 596.4.1 廣義表的概念 6.4.2 廣義表的存儲結(jié)構(gòu) 6.4.3 廣義表的應(yīng)用6.4 廣義表第第6 6章章 60 廣 義

30、 表 是廣 義 表 是 n ( n 0 ) 個 元 素 的 有 限 序 列個 元 素 的 有 限 序 列 , 記 作記 作 A=(a1, a2, , an) 其中其中, A是廣義表的名稱是廣義表的名稱, n是它的長度是它的長度, ai(1in)或者或者是數(shù)據(jù)元素是數(shù)據(jù)元素, 或者是廣義表?；蛘呤菑V義表。 習(xí)慣上：習(xí)慣上： 用英文大寫字母表示廣義表的名稱用英文大寫字母表示廣義表的名稱, 小寫字小寫字母表示數(shù)據(jù)元素。母表示數(shù)據(jù)元素。第第6 6章章 61 對于廣義表對于廣義表A中的某個元素中的某個元素ai ：若它是一個數(shù)：若它是一個數(shù)據(jù)元素時據(jù)元素時, 稱其為稱其為A的一個原子的一個原子; 當(dāng)其不是

31、一個數(shù)據(jù)當(dāng)其不是一個數(shù)據(jù)元素時元素時, 則稱它為廣義表則稱它為廣義表A的子表。的子表。 當(dāng)廣義表當(dāng)廣義表A非空時非空時, 稱第一個元素稱第一個元素a1為為A的表頭的表頭(head), 稱其余元素組成的表稱其余元素組成的表(a2, , an)為為A的表尾的表尾(tail)。廣義表舉例如下廣義表舉例如下: A=( ) A是一個空表是一個空表, 其長度為零。其長度為零。 B=(e) 廣義表廣義表B只有一個原子只有一個原子e, B的長度為的長度為1。 第第6 6章章 62 C=(a, (b, c, d), 廣義表廣義表C的長度為的長度為2, 兩個元素分別兩個元素分別為原子為原子a和子表和子表(b, c

32、, d) D=(A, B, C), 廣義表廣義表D的長度為的長度為3, 3 個元素都是廣個元素都是廣義表。義表。 E=(a, E), 這是一個遞歸的表這是一個遞歸的表, 其長度為其長度為2, E表相當(dāng)表相當(dāng)于一個無窮表。于一個無窮表。從以上例子可以看出：從以上例子可以看出： 廣義表可以共享子表廣義表可以共享子表, 且允許遞歸。且允許遞歸。 廣義表的元素之間除了存在次序關(guān)系外廣義表的元素之間除了存在次序關(guān)系外, 還存在層還存在層次關(guān)系。次關(guān)系。 第第6 6章章 63 廣義表中元素的最大層次為表的深度。元素的層次廣義表中元素的最大層次為表的深度。元素的層次就是包含該元素的括號對的數(shù)目。就是包含該元

33、素的括號對的數(shù)目。 例如例如: F=(a, b, (c, (d) 其中其中, 數(shù)據(jù)元素?cái)?shù)據(jù)元素a, b在第一層在第一層, 數(shù)據(jù)元素?cái)?shù)據(jù)元素c在第二層在第二層, 數(shù)據(jù)元素?cái)?shù)據(jù)元素d在第三層。廣義表在第三層。廣義表F的深度為的深度為3。 任何一個非空廣義表，其表頭可能是原子任何一個非空廣義表，其表頭可能是原子, 也可能是也可能是廣義表廣義表, 而其表尾必定為廣義表。而其表尾必定為廣義表。第第6 6章章 64例如例如: 若若 C=(a, (b, c, d) D=(A, B, C) 則：Head(D)=A Tail(D)=(B, C) Head(C)=a Tail(C)=(b, c, d)以上是廣義表

34、的兩個操作以上是廣義表的兩個操作： 取表頭 Head 、取表尾Tail 這些操作還可以嵌套調(diào)用：這些操作還可以嵌套調(diào)用： Head（ Tail(D) ） Head(B,C) = B取廣義表取廣義表D D的第二個元的第二個元素素第第6 6章章 65注意：注意： 廣義表廣義表（）（）和廣義表和廣義表( )不同。不同。 （）（）為空表，長度為空表，長度 n0 ，不能分解成表頭和表尾。，不能分解成表頭和表尾。 ( ) 不是空表，其長度不是空表，其長度 n = 1 ，可以分解得到表頭是，可以分解得到表頭是空表空表( ) , 表尾是空表表尾是空表( ) .第第6 6章章 66 6.4.1 廣義表的概念 6

35、.4.2 廣義表的存儲結(jié)構(gòu) 6.4.3 廣義表的應(yīng)用6.4 廣義表第第6 6章章 67 由于廣義表（由于廣義表（a1, a2, , an)中的數(shù)據(jù)元素可以具有不中的數(shù)據(jù)元素可以具有不同的結(jié)構(gòu)同的結(jié)構(gòu)(或是原子或是原子, 或是列表）或是列表）, 因此難以用順序存儲因此難以用順序存儲結(jié)構(gòu)表示結(jié)構(gòu)表示, 通常采用鏈?zhǔn)酱鎯Y(jié)構(gòu)通常采用鏈?zhǔn)酱鎯Y(jié)構(gòu), 每個數(shù)據(jù)元素可用每個數(shù)據(jù)元素可用一個結(jié)點(diǎn)表示。一個結(jié)點(diǎn)表示。 如何設(shè)定結(jié)點(diǎn)的結(jié)構(gòu)？由于列表中的數(shù)據(jù)元素可能如何設(shè)定結(jié)點(diǎn)的結(jié)構(gòu)？由于列表中的數(shù)據(jù)元素可能為原子或列表為原子或列表, 由此需要兩種結(jié)構(gòu)的結(jié)點(diǎn)由此需要兩種結(jié)構(gòu)的結(jié)點(diǎn): 一種是表結(jié)點(diǎn)一種是表結(jié)點(diǎn), 用

36、以表示列表用以表示列表; 一種是原子結(jié)點(diǎn)一種是原子結(jié)點(diǎn), 用用以表示原子。以表示原子。 第第6 6章章 68 按前述分析：按前述分析： 由此由此, 一個一個可由可由 3 個域組成個域組成: ; 而而只需兩個只需兩個域域: ：原子結(jié)點(diǎn)原子結(jié)點(diǎn)atomtag = 0 tag = 1hptp表結(jié)點(diǎn)表結(jié)點(diǎn)第第6 6章章 69原子結(jié)點(diǎn)原子結(jié)點(diǎn)atomtag = 0 類型說明如下：類型說明如下： typedef enum ATOM, LIST ElemTag ; /*ATOM=0：原子, LIST=1:子表*/tag = 1hptp表結(jié)點(diǎn)表結(jié)點(diǎn)枚舉類型枚舉類型第第6 6章章 70typedef struc

37、t GLNode ElemTag tag ; union AtomType atom ; struct struct GLNode *hp, *tp ; ptr ; ; Glist ;公共部分公共部分, 用于區(qū)分用于區(qū)分原子結(jié)點(diǎn)和表結(jié)點(diǎn)原子結(jié)點(diǎn)和表結(jié)點(diǎn)原子結(jié)點(diǎn)和原子結(jié)點(diǎn)和表結(jié)點(diǎn)的聯(lián)表結(jié)點(diǎn)的聯(lián)合部分合部分ptr.hp和和ptr.pt分別指向分別指向表頭和表尾表頭和表尾廣義表類型廣義表類型第第6 6章章 71 A=( ) B=(e) C=(a, (b, c, d) D=(A, B, C) E=(a, E)Glist *A; A = NULL10eBCDE110a1110b0c0d111110a第第

38、6 6章章 72在這種存儲結(jié)構(gòu)中有幾種情況：在這種存儲結(jié)構(gòu)中有幾種情況： 除空表的表頭指針為空外，對任何非空廣義表，除空表的表頭指針為空外，對任何非空廣義表，其表頭指針均指向一個表結(jié)點(diǎn)，且該結(jié)點(diǎn)中的其表頭指針均指向一個表結(jié)點(diǎn)，且該結(jié)點(diǎn)中的（或?yàn)樵咏Y(jié)點(diǎn)，或?yàn)楸斫Y(jié)點(diǎn)），（或?yàn)樵咏Y(jié)點(diǎn)，或?yàn)楸斫Y(jié)點(diǎn)），（除非表尾為空，則指針為空，否則（除非表尾為空，則指針為空，否則必為表結(jié)點(diǎn)）；必為表結(jié)點(diǎn)）；第第6 6章章 73 如在廣如在廣義表義表D中，原子中，原子a和和e在同一層次上，而在同一層次上，而b、c和和d在同一在同一層次且比層次且比a和和e低一層，低一層，B和和C是同一層的子表；是同一層的子表； 第第

39、6 6章章 74 6.4.1 廣義表的概念 6.4.2 廣義表的存儲結(jié)構(gòu) 6.4.3 廣義表的應(yīng)用6.4 廣義表第第6 6章章 75 一個一個m元多項(xiàng)式的每一項(xiàng)最多有元多項(xiàng)式的每一項(xiàng)最多有m個變元，如果用個變元，如果用單鏈表表示，則每個節(jié)點(diǎn)應(yīng)該包括單鏈表表示，則每個節(jié)點(diǎn)應(yīng)該包括m個指數(shù)項(xiàng)和一個數(shù)個指數(shù)項(xiàng)和一個數(shù)據(jù)項(xiàng)；如果多項(xiàng)式各項(xiàng)的變元數(shù)不相同，將勢必造成存據(jù)項(xiàng)；如果多項(xiàng)式各項(xiàng)的變元數(shù)不相同，將勢必造成存儲空間的浪費(fèi)。為此，我們考慮采用其它的方式來存儲儲空間的浪費(fèi)。為此，我們考慮采用其它的方式來存儲一個一個m元多項(xiàng)式。元多項(xiàng)式。 我們以三元多項(xiàng)式：我們以三元多項(xiàng)式：P(x,y,z) = x10

40、y3z2+2x6y3z2+3x5y2z2+x4y4z+6x3y4z+2yz+15 為例，討論其存儲表示。為例，討論其存儲表示。 第第6 6章章 76P(x,y,z) = x10y3z2+2x6y3z2+3x5y2z2+x4y4z+6x3y4z+2yz+15 該多項(xiàng)式中各項(xiàng)的變元數(shù)目不盡相同，某些因子多該多項(xiàng)式中各項(xiàng)的變元數(shù)目不盡相同，某些因子多次出現(xiàn)，我們可以將其改寫為：次出現(xiàn)，我們可以將其改寫為：P(x,y,z) = (x10 + 2x6)y3+3x5y2)z2+(x4 + 6x3)y4+2y)z+15 此時，該多項(xiàng)式就變成了變元此時，該多項(xiàng)式就變成了變元z的多項(xiàng)式，的多項(xiàng)式，即即A z2 + B z1 +15 z0，對這個一元多項(xiàng)式我們用單鏈表，對這個一元多項(xiàng)式我們用單鏈表表示為：表示為： 第第6 6章章 77 變元變元z的多項(xiàng)式的多項(xiàng)式A z2 + B z1 +15 z0中的中的A、B又是一個又是一個多項(xiàng)式。多項(xiàng)式。 其中，其中，A = (x10 + 2x6) y3 + 3x5y2