特殊矩陣廣義表及其應(yīng)用課件

1、特殊矩陣廣義表及其應(yīng)用特殊矩陣廣義表及其應(yīng)用數(shù)組的定義：數(shù)組是滿足下列條件的同類型數(shù)據(jù)元素 的集合： 對(duì)于該集合中任一數(shù)據(jù)元素 來(lái)說(shuō)，ji = 0，bi-1， i =1，2，n，n0稱為數(shù)組的維數(shù)，bi是數(shù)組第i維的長(zhǎng)度，ji是數(shù)組元素的第i維下標(biāo)； 數(shù)據(jù)元素之間的關(guān)系表示為Ri = |，0jkbk-1 ，1kn且ki，0jibi-2 ，i =1，2，n，且R = R1，R2，. Rn； 數(shù)組的定義： 下面以二維數(shù)組為例解釋上述關(guān)于數(shù)組的定義?！纠?.1】設(shè)有二維數(shù)組A，其第1維的長(zhǎng)度b1= 3，第2維的長(zhǎng)度b2 = 4；數(shù)據(jù)元素描述為，其中j1 = 0，b1-1= 0，1，2，j2 = 0，

2、b2-1= 0，1，2，3；則該二維數(shù)組共有12個(gè)具有相同數(shù)據(jù)類型的數(shù)據(jù)元素，分別為： Amn = a11 a12 a1n a21 a22 a2n am1 am2 amn (1im, 1jn) 下面以二維數(shù)組為例解釋上述關(guān)于數(shù)組的定義。【例 可以看出，二維數(shù)組每一行是一個(gè)一維數(shù)組，元素間存在序偶關(guān)系；每一列也是一個(gè)一維數(shù)組，元素間也同樣存在序偶關(guān)系。即：每個(gè)元素都受著兩個(gè)關(guān)系的約束： 、 。 若把每一行看作是一個(gè)整體，則行與行之間是線性關(guān)系；若把每一列看作是一個(gè)整體，則列與列之間也是線性關(guān)系。 可以看出，二維數(shù)組每一行是一個(gè)一維數(shù)組，元素間 這樣，我們可以把二維數(shù)組看成是一個(gè)線性表，它的每一個(gè)

3、數(shù)據(jù)元素是一個(gè)一維數(shù)組，也是一個(gè)線性表。 由此可以推廣到n維數(shù)組。我們說(shuō)n維數(shù)組是一個(gè)線性表，它的每一個(gè)數(shù)據(jù)元素是n-1維數(shù)組，也是一個(gè)線性表。 數(shù)組一旦被定義，其維數(shù)及每維的長(zhǎng)度(維界)就不再改變。因此，數(shù)組的運(yùn)算除了初始化和銷毀之外，只有查找元素和修改元素值的操作。 這樣，我們可以把二維數(shù)組看成是一個(gè)線性表，它的矩陣的定義： 矩陣是由mn個(gè)數(shù)排列成m行(橫向)、n列(縱向)所形成的矩形數(shù)表： 稱為mn矩陣，簡(jiǎn)記為A=(aij)mn，其中aij為A的第i行第j列的元素。 矩陣的定義：稱為mn矩陣，簡(jiǎn)記為A=(aij)mn，其中矩陣與數(shù)組的關(guān)系 ： 對(duì)照上述數(shù)組的定義，我們不難看出，矩陣中所有

4、數(shù)據(jù)元素組成了一個(gè)二維數(shù)組，矩陣的每一行、每一列的數(shù)據(jù)元素分別組成等長(zhǎng)的一維數(shù)組。 我們也可以說(shuō)，矩陣是一個(gè)線性表，其每一個(gè)數(shù)據(jù)元素(行或列)也是一個(gè)線性表。 矩陣與數(shù)組的關(guān)系 ： 6.1.1 數(shù)組與矩陣的概念及其相互關(guān)系 6.1.2 數(shù)組的存儲(chǔ)結(jié)構(gòu)6.1 數(shù)組與矩陣 6.1.1 數(shù)組與矩陣的概念及其相互關(guān)系 6.1 由于數(shù)組一般不作插入和刪除操作，因此采用順序存儲(chǔ)結(jié)構(gòu)是理所當(dāng)然的。問(wèn)題是：以什么次序來(lái)存儲(chǔ)各元素的值？ 下面以二維數(shù)組為例來(lái)說(shuō)明：二維數(shù)組一般有兩種方法來(lái)存儲(chǔ)：1、按行優(yōu)先順序存儲(chǔ) 將數(shù)組元素按行向量排列， i+1行向量接在 i 行向量后面。 由于數(shù)組一般不作插入和刪除操作，因此

5、采用順序存儲(chǔ)結(jié) a11 a12 . a1n a21 a22 . a2n am1 am2 . amn .Loc( aij)=Loc(a11)+(i-1)n+(j-1)*l 按行序?yàn)橹餍虼娣?amn . am2 am1 . a2n . a22 a21 a1n . a12 a1101n-1m*n-1n a11 a12 .2、按列優(yōu)先順序存儲(chǔ) 將數(shù)組元素按列向量排列， j+1列向量接在 j 列向量后面。2、按列優(yōu)先順序存儲(chǔ)按列序?yàn)橹餍虼娣?1m-1m*n-1m amn . a2n a1n . am2 . a22 a12 am1 . a21 a11 a11 a12 . a1n a21 a22 . a2n

6、 am1 am2 . amn .Loc(aij)=Loc(a11)+(j-1)m+(i-1)*l 按列序?yàn)橹餍虼娣?1m-1m*n-1m amn二維數(shù)組中任一元素的地址 按上述兩種方式順序存儲(chǔ)的數(shù)組，只要知道開(kāi)始結(jié)點(diǎn)的存放地址和每維的上下界（m、 n的值），以及每個(gè)數(shù)組元素所占用的字節(jié)數(shù)d，就可求出各個(gè)數(shù)組元素的存儲(chǔ)地址。 二維數(shù)組中任一元素的地址設(shè) 數(shù)組的首地址 即： a11 的地址 記為： LOC (a11)則：二維數(shù)組按“行優(yōu)先順序”存儲(chǔ)，數(shù)組元素的存儲(chǔ)地址為： LOC (a11) + 前面 i 1行元素所占字節(jié)數(shù) + 第j 行中前j 1個(gè)元素所占字節(jié)數(shù)即：LOC( aij ) = LO

7、C(a11) + ( i-1)*n*d +(j -1)*d 前面 i 1行元素的個(gè)數(shù)（每行n個(gè)）每個(gè)元素所占的字節(jié)數(shù)設(shè) 數(shù)組的首地址 即： a11 的地址 前面【例2】已知二維數(shù)組Amm按行存儲(chǔ)的元素地址公式是： Loc(aij)= Loc(a11)+(i-1)*m+(j-1)*K 按列存儲(chǔ)的公式是？ Loc(aij)=Loc(a11)+(j-1)*m+(i-1)*K （盡管是方陣，但公式仍不同）【例1】一個(gè)二維數(shù)組A，行下標(biāo)的范圍是1到6，列下標(biāo)的范圍是0到7，每個(gè)數(shù)組元素用相鄰的6個(gè)字節(jié)存儲(chǔ)，存儲(chǔ)器按字節(jié)編址。那么，這個(gè)數(shù)組占用 個(gè)字節(jié)。 答： m*n*L=(6-1+1)*(7- 0 +1

8、)*6=48*6=288【例2】已知二維數(shù)組Amm按行存儲(chǔ)的元素地址公式是： 6.1 數(shù)組與矩陣 6.2 特殊矩陣的壓縮存儲(chǔ) 6.3 矩陣的應(yīng)用實(shí)例 6.4 廣義表第6章 特殊矩陣、廣義表及其應(yīng)用 6.1 數(shù)組與矩陣 第6章 特殊矩陣、廣義表及其應(yīng)用 在用高級(jí)語(yǔ)言編寫程序時(shí)，通常用二維數(shù)組來(lái)存儲(chǔ)矩陣。但對(duì)一些數(shù)據(jù)分布呈某種規(guī)律的矩陣，或是0元素大量存在(遠(yuǎn)遠(yuǎn)多于非0元素)的矩陣，采用上述存儲(chǔ)方法會(huì)造成存儲(chǔ)空間的極大浪費(fèi)。 在用高級(jí)語(yǔ)言編寫程序時(shí)，通常用二維數(shù)組來(lái)存儲(chǔ)矩陣 若矩陣中非0元素呈某種規(guī)律分布，或存在大量0元素，為節(jié)省存儲(chǔ)空間，可對(duì)這類矩陣壓縮存儲(chǔ)： 即：為多個(gè)相同的非0元素只分配一個(gè)

9、存儲(chǔ)空間，對(duì)0元素不分配存儲(chǔ)空間。 若值相同的非0元素或0元素在矩陣中的分布有一定的規(guī)律，我們稱此矩陣為特殊矩陣；反之，稱為稀疏矩陣。 若矩陣中非0元素呈某種規(guī)律分布，或存在大量0元素，為節(jié)特殊矩陣 所謂特殊矩陣是指非零元素或零元素的分布有一定規(guī)律的矩陣，下面我們討論幾種特殊矩陣的壓縮存儲(chǔ)。1、對(duì)稱矩陣 在一個(gè)n階方陣A中，若元素滿足下述性質(zhì)： aij=aji 0=i, j=0)，元素總數(shù)為：n(n+1)/2 因此，我們可以按從上到下、從左到右將這些元素存放在一個(gè)向量san(n+1)/2中。為了便于訪問(wèn)對(duì)稱矩陣A中的元素，我們必須在aij和sak之間找一個(gè)對(duì)應(yīng)關(guān)系。a11 a12 a1n a2

10、1 a22 a2n an1 an2 ann 在這個(gè)下三角矩陣中，第i行恰有i+1個(gè)元素(i=0)， 若ij，則aij在下三角形中。 aij之前的i行（從第0行到第i-1行）一共有1+2+i=i(i+1)/2個(gè)元素，在第i行上， aij之前恰有j個(gè)元素（即ai0, ai1, ai2, , aij-1），因此有： k=i*(i+1)/2+j 0k n(n+1)/2 若ij，則aij是在上三角矩陣中。因?yàn)閍ij= aji，所以只要交換上述對(duì)應(yīng)關(guān)系式中的i和j即可得到： k=j*(j+1)/2+i 0kn(n+1)/2 若ij，則aij在下三角形中。 aij之前的i行（從2、三角矩陣 以主對(duì)角線劃分，

11、三角矩陣有上三角和下三角兩種。上三角矩陣如圖(a)所示，它的下三角（不包括主對(duì)角線）中的元素均為常數(shù)。下三角矩陣正好相反，它的主對(duì)角線上方均為常數(shù)，如圖(b)所示。在大多數(shù)情況下，三角矩陣常數(shù)為零。 a00 a01 a0 n-1 a00 c c c a11 a1 n-1 a10 a11 c . . c c an-1 n-1 an-1 0 an-1 1 an-1 n-1 (a)上三角矩陣 (b)下三角矩陣 2、三角矩陣 三角矩陣中的重復(fù)元素c可共享一個(gè)存儲(chǔ)空間，其余的元素正好有n(n+1)/2個(gè)，因此，三角矩陣可壓縮存儲(chǔ)到向量san(n+1)/2 +1中，其中c存放在向量的最后一個(gè)分量中。 a0

12、0 a01 a0 n-1 a00 c c c a11 a1 n-1 a10 a11 c . . c c an-1 n-1 an-1 0 an-1 1 an-1 n-1 (a)上三角矩陣 (b)下三角矩陣 三角矩陣中的重復(fù)元素c可共享一個(gè)存儲(chǔ)空間，其余的元 上三角矩陣中，主對(duì)角線之上的第i行(0ij 上三角矩陣中，主對(duì)角線之上的第i行(0in)恰 下三角矩陣的存儲(chǔ)和對(duì)稱矩陣類似，sak和aij對(duì)應(yīng)關(guān)系是： i(i+1)/2+j ij n(n+1)/2 ij k = 下三角矩陣的存儲(chǔ)和對(duì)稱矩陣類似，sak和aij對(duì)應(yīng)關(guān)3、對(duì)角矩陣 對(duì)角矩陣中，所有的非零元素集中在以主對(duì)角線為中心的帶狀區(qū)域中，即除

13、了主對(duì)角線和主對(duì)角線相鄰兩側(cè)的若干條對(duì)角線上的元素之外，其余元素皆為零。下圖給出了一個(gè)三對(duì)角矩陣， 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 3、對(duì)角矩陣三對(duì)角矩陣有如下特點(diǎn)： 當(dāng)時(shí)，aij非0； 其它情況時(shí)，aij的值為0。 三對(duì)角矩陣有如下特點(diǎn)： 當(dāng)時(shí)，aij非0； 我們以行序?yàn)橹餍蜻M(jìn)行存儲(chǔ)三對(duì)角矩陣，并且只存儲(chǔ)矩陣中的非0元素。 在n階三對(duì)角矩陣中，除了第一行和最后一行只有2個(gè)非0元素外，其余各行均有3個(gè)非0元素， 共2+2+3*(n-2) = 3n-2個(gè)非0元素。

14、 這樣，可以將該三對(duì)角矩陣存儲(chǔ)在一維數(shù)組sa3n-2中。現(xiàn)在，對(duì)給定的非0元素aij，與其對(duì)應(yīng)的數(shù)組元素的下標(biāo)是什么呢？ 我們以行序?yàn)橹餍蜻M(jìn)行存儲(chǔ)三對(duì)角矩陣，并且只存儲(chǔ)矩 由三對(duì)角矩陣的特點(diǎn)知，矩陣中的非0元素aij的前面有i行，共有3i-1個(gè)非0元素；在元素aij所在的第i行，aij之前有j-i+1個(gè)非0元素。因此可得與非0元素aij對(duì)應(yīng)的數(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 由三對(duì)角矩陣的特點(diǎn)知，矩陣中的非0元素aij的前 上述的各種特

15、殊矩陣，其非零元素的分布都是有規(guī)律的，因此總能找到一種方法將它們壓縮存儲(chǔ)到一個(gè)向量中，并且一般都能找到矩陣中的元素與該向量的對(duì)應(yīng)關(guān)系，通過(guò)這個(gè)關(guān)系，仍能對(duì)矩陣的元素進(jìn)行隨機(jī)存取。 上述的各種特殊矩陣，其非零元素的分布都是有規(guī)律的，因稀疏矩陣 什么是稀疏矩陣？ 簡(jiǎn)單說(shuō)，設(shè)矩陣A中有s個(gè)非零元素，若s遠(yuǎn)遠(yuǎn)小于矩陣元素的總數(shù)（即st 存放矩陣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 若定義指針變量a存放矩陣M三元組表的首地址： 第一個(gè)數(shù)組元素（三元組）所在的行號(hào)、列號(hào)分

16、別是： ( adata0).i (adata0) .j 它的值為： ( adata0).v 第一個(gè)數(shù)組元素（三元組）所在的行號(hào)、列號(hào)分別是：2、十字鏈表 若矩陣的非0元素的個(gè)數(shù)和位置在操作過(guò)程中變化較大，則不宜采用順序存儲(chǔ)結(jié)構(gòu)來(lái)表示三元組的線性表。 可采用鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)來(lái)表示三元組的線性表。2、十字鏈表 在鏈表中，每個(gè)非0元素可用一個(gè)含有五個(gè)域的結(jié)點(diǎn)表示：ijvcptrrptr 其中：i , j ,v 三個(gè)域分別表示該元素所在的行、列和非0元素的值。行指針域 rptr 用以鏈接同一行中下一個(gè)非0元素；列指針域 cptr 用以鏈接同一列中下一個(gè)非0元素。 在鏈表中，每個(gè)非0元素可用一個(gè)含有五個(gè)域的

17、結(jié)點(diǎn)表示 存儲(chǔ)時(shí)，每個(gè)非0元既是某個(gè)行鏈表中的一個(gè)結(jié)點(diǎn)，又是某個(gè)列鏈表中的一個(gè)結(jié)點(diǎn)；整個(gè)矩陣構(gòu)成了一個(gè)十字交叉的鏈表故稱這樣的存儲(chǔ)結(jié)構(gòu)為十字鏈表。 可用兩個(gè)分別存儲(chǔ)行鏈表和列鏈表的頭指針的一維數(shù)組表示十字鏈表。 M-chead M-rhead 存儲(chǔ)時(shí)，每個(gè)非0元既是某個(gè)行鏈表中的一個(gè)結(jié)點(diǎn)，又是某個(gè)十字鏈表中非0元結(jié)點(diǎn)的類型說(shuō)明如下： typedef struct lnode int i , j ; datatype v ; struct lnode *cptr , *rptr ; OLnode； ijvcptrrptr十字鏈表中非0元結(jié)點(diǎn)的類型說(shuō)明如下：ijvcptrrptr十字鏈表的類型描述

18、如下： #define N 10 /預(yù)設(shè)稀疏矩陣的行數(shù) #define K 10 /預(yù)設(shè)稀疏矩陣的列數(shù) typedef struct OLnode *cheadN , *rheadK ; int m , n , t ; /*行數(shù)、列數(shù)、非0元個(gè)數(shù)*/ Crosslist ; Crosslist *M ; 十字鏈表的類型描述如下： 討論：如何建立一個(gè)十字鏈表 算法步驟： 1、建立兩個(gè)一維數(shù)組 Mchead 、 Mrhead 分別存儲(chǔ)列鏈表及行鏈表的頭指針。 初始時(shí)， Mcheadj = NULL , Mrheadj = NULL. 2、讀入非0元結(jié)點(diǎn)的三元組（ i , j , v ），生成一個(gè)結(jié)

19、點(diǎn)*p ,將其插入第 i 個(gè)行鏈表和第j個(gè)列鏈表的正確位置上。 討論：如何建立一個(gè)十字鏈表 6.1 數(shù)組與矩陣 6.2 特殊矩陣的壓縮存儲(chǔ)6.3 矩陣的應(yīng)用實(shí)例 6.4 廣義表第6章 特殊矩陣、廣義表及其應(yīng)用 6.1 數(shù)組與矩陣 第6章 特殊矩陣、廣義表及其應(yīng)用【例】求稀疏矩陣A的轉(zhuǎn)置矩陣B 一個(gè)mn的矩陣A，它的轉(zhuǎn)置B是一個(gè)nm的矩陣，且aij=bji，0im，0jn，即A的行是B的列，A的列是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

20、 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 = 【例】求稀疏矩陣A的轉(zhuǎn)置矩陣B 0 0 -3 將A轉(zhuǎn)置為B，就是將A的三元組表a-data置換為表B的三元組表b-data。 有： at = bt ; am = bn ; an = bm ; 但:(adatax).i (bdatax).j 為什么？ 將A轉(zhuǎn)置為B，就是將A的三元組表a-data置換為表 也不能將 (adatax).i 與(adatax).j 簡(jiǎn)單互換！為什么？ 答：如果只是簡(jiǎn)單地交換a-data中i和j的內(nèi)容，那么得

21、到的b-data將是一個(gè)按列優(yōu)先順序存儲(chǔ)的稀疏矩陣B，要得到按行優(yōu)先順序存儲(chǔ)的b-data，就必須重新排列三元組的順序。 由于A的列是B的行，因此按a-data的列序轉(zhuǎn)置，所得到的轉(zhuǎn)置矩陣B的三元組表b-data必定是按行優(yōu)先存放的。 也不能將 (adatax).i 與(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

22、0 -7 0 0 0B = 行號(hào)i 列號(hào)j 值v行號(hào)i 列號(hào)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 -70 0 -3 0 0 15A = 0 算法步驟如下：(1) 產(chǎn)生順序表b，存放轉(zhuǎn)置后的矩陣B Spmatrix *b; b = malloc( sizeof (Spmatrix); 并確定其結(jié)點(diǎn)個(gè)數(shù)、行數(shù)、列數(shù)。即：bt = at ;bm = an ; bn = am ;算法步驟如下：bt = at ;(2) 一維數(shù)組 bdata結(jié)點(diǎn)個(gè)數(shù)

23、 中各數(shù)組元素賦值，且bdata 按行優(yōu)先。 具體做法如下： 對(duì)三元組表adata 掃描(從第一行開(kāi)始) 令：x為數(shù)組adata 中數(shù)組元素的下標(biāo) y為數(shù)組bdata 中數(shù)組元素的下標(biāo)(2) 一維數(shù)組 bdata結(jié)點(diǎn)個(gè)數(shù) 中各數(shù)組元素賦掃描過(guò)程：首先，令 y = 0; for (x = 0; x datax).j = = 1 (1是列號(hào)) 若為1 則 (bdatay).v = (adatax).v (bdatay).i = (adatax).j (bdatay).j = (adatax).i y+ 該輪for循環(huán)結(jié)束后，矩陣N中第一行（即矩陣M中第一列）的元素的三元組已存放在三元組表（數(shù)組）b

24、data 中了。掃描過(guò)程：首先，令 y = 0; 該輪for循環(huán)結(jié) 下面再次掃描三元組表（數(shù)組）adata ，查尋矩陣M中第二列的元素：此時(shí)，y值為上輪for 循環(huán)后的結(jié)果； for (x = 0; x datax).j = = 2 (2是列號(hào)) 若為2 則 (bdatay).v = (adatax).v (bdatay).i = (adatax).j (bdatay).j = (adatax).i y+ 下面再次掃描三元組表（數(shù)組）adata 這樣，整個(gè)掃描的過(guò)程可描述為： y = 0 ; for ( z = 1; z =矩陣M的列數(shù)；z+) for (x = 0; x datax).j =

25、 = z ) (bdatay).v = (adatax).v ; (bdatay).i = (adatax).j ; (bdatay).j = (adatax).i ; y+ ; 這樣，整個(gè)掃描的過(guò)程可描述為：算法分析： 該算法的時(shí)間主要耗費(fèi)在 z 和 x 的二重循環(huán)上，若矩陣M的列數(shù)為 n ，非0元素個(gè)數(shù)為 t ，則 算法的時(shí)間復(fù)雜度數(shù)量級(jí)為: O( n*t )算法分析： 6.1 數(shù)組與矩陣 6.2 特殊矩陣的壓縮存儲(chǔ) 6.3 矩陣的應(yīng)用實(shí)例 6.4 廣義表第6章 特殊矩陣、廣義表及其應(yīng)用 6.1 數(shù)組與矩陣 第6章 特殊矩陣、廣義表及其應(yīng)用6.4.1 廣義表的概念 6.4.2 廣義表的存儲(chǔ)

26、結(jié)構(gòu) 6.4.3 廣義表的應(yīng)用6.4 廣義表6.4.1 廣義表的概念6.4 廣義表廣義表的概念 廣義表是n(n0)個(gè)元素的有限序列, 記作 A=(a1, a2, , an) 其中, A是廣義表的名稱, n是它的長(zhǎng)度, ai(1in)或者是數(shù)據(jù)元素, 或者是廣義表。 習(xí)慣上： 用英文大寫字母表示廣義表的名稱, 小寫字母表示數(shù)據(jù)元素。廣義表的概念 對(duì)于廣義表A中的某個(gè)元素ai ：若它是一個(gè)數(shù)據(jù)元素時(shí), 稱其為A的一個(gè)原子; 當(dāng)其不是一個(gè)數(shù)據(jù)元素時(shí), 則稱它為廣義表A的子表。 當(dāng)廣義表A非空時(shí), 稱第一個(gè)元素a1為A的表頭(head), 稱其余元素組成的表(a2, , an)為A的表尾(tail)。

27、廣義表舉例如下: A=( ) A是一個(gè)空表, 其長(zhǎng)度為零。 B=(e) 廣義表B只有一個(gè)原子e, B的長(zhǎng)度為1。 對(duì)于廣義表A中的某個(gè)元素ai ：若它是一個(gè)數(shù) C=(a, (b, c, d), 廣義表C的長(zhǎng)度為2, 兩個(gè)元素分別為原子a和子表(b, c, d) D=(A, B, C), 廣義表D的長(zhǎng)度為3, 3 個(gè)元素都是廣義表。 E=(a, E), 這是一個(gè)遞歸的表, 其長(zhǎng)度為2, E表相當(dāng)于一個(gè)無(wú)窮表。從以上例子可以看出： 廣義表可以共享子表, 且允許遞歸。 廣義表的元素之間除了存在次序關(guān)系外, 還存在層次關(guān)系。 C=(a, (b, c, d), 廣義表C的長(zhǎng)度為2 廣義表中元素的最大層次

28、為表的深度。元素的層次就是包含該元素的括號(hào)對(duì)的數(shù)目。 例如: F=(a, b, (c, (d) 其中, 數(shù)據(jù)元素a, b在第一層, 數(shù)據(jù)元素c在第二層, 數(shù)據(jù)元素d在第三層。廣義表F的深度為3。 任何一個(gè)非空廣義表，其表頭可能是原子, 也可能是廣義表, 而其表尾必定為廣義表。 廣義表中元素的最大層次為表的深度。元素的層次例如: 若 C=(a, (b, c, d) D=(A, B, C) 則：Head(D)=A Tail(D)=(B, C) Head(C)=a Tail(C)=(b, c, d)以上是廣義表的兩個(gè)操作： 取表頭 Head 、取表尾Tail 這些操作還可以嵌套調(diào)用： Head（ T

29、ail(D) ） Head(B,C) = B取廣義表D的第二個(gè)元素例如: 若 C=(a, (b, c, d) D=(注意： 廣義表（）和廣義表( )不同。 （）為空表，長(zhǎng)度 n0 ，不能分解成表頭和表尾。 ( ) 不是空表，其長(zhǎng)度 n = 1 ，可以分解得到表頭是空表( ) , 表尾是空表( ) .注意： 6.4.1 廣義表的概念 6.4.2 廣義表的存儲(chǔ)結(jié)構(gòu) 6.4.3 廣義表的應(yīng)用6.4 廣義表 6.4.1 廣義表的概念6.4 廣義表 由于廣義表（a1, a2, , an)中的數(shù)據(jù)元素可以具有不同的結(jié)構(gòu)(或是原子, 或是列表）, 因此難以用順序存儲(chǔ)結(jié)構(gòu)表示, 通常采用鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu), 每個(gè)數(shù)

30、據(jù)元素可用一個(gè)結(jié)點(diǎn)表示。 如何設(shè)定結(jié)點(diǎn)的結(jié)構(gòu)？由于列表中的數(shù)據(jù)元素可能為原子或列表, 由此需要兩種結(jié)構(gòu)的結(jié)點(diǎn): 一種是表結(jié)點(diǎn), 用以表示列表; 一種是原子結(jié)點(diǎn), 用以表示原子。 由于廣義表（a1, a2, , an)中的數(shù)據(jù)元 按前述分析：若列表不空, 則可分解成表頭和表尾; 反之, 一對(duì)確定的表頭和表尾可唯一確定列表。 由此, 一個(gè)表結(jié)點(diǎn)可由 3 個(gè)域組成: 標(biāo)志域、指示表頭的指針域和指示表尾的指針域; 而原子結(jié)點(diǎn)只需兩個(gè)域: 標(biāo)志域和值域：原子結(jié)點(diǎn)atomtag = 0 tag = 1hptp表結(jié)點(diǎn) 按前述分析：若列表不空, 則可分解成表頭和表尾; 反之原子結(jié)點(diǎn)atomtag = 0 類型

31、說(shuō)明如下： typedef enum ATOM, LIST ElemTag ; /*ATOM=0：原子, LIST=1:子表*/tag = 1hptp表結(jié)點(diǎn)枚舉類型原子結(jié)點(diǎn)atomtag = 0 類型說(shuō)明如下：tag = typedef struct GLNode ElemTag tag ; union AtomType atom ; struct struct GLNode *hp, *tp ; ptr ; ; Glist ;公共部分, 用于區(qū)分原子結(jié)點(diǎn)和表結(jié)點(diǎn)原子結(jié)點(diǎn)和表結(jié)點(diǎn)的聯(lián)合部分ptr.hp和ptr.pt分別指向表頭和表尾廣義表類型typedef struct GLNode公共部分,

32、 用 A=( ) B=(e) C=(a, (b, c, d) D=(A, B, C) E=(a, E)Glist *A; A = NULL10eBCDE110a1110b0c0d111110a A=( ) B=(e) 在這種存儲(chǔ)結(jié)構(gòu)中有幾種情況： 除空表的表頭指針為空外，對(duì)任何非空廣義表，其表頭指針均指向一個(gè)表結(jié)點(diǎn)，且該結(jié)點(diǎn)中的hp域指示廣義表表頭（或?yàn)樵咏Y(jié)點(diǎn)，或?yàn)楸斫Y(jié)點(diǎn)），tp域指向廣義表表尾（除非表尾為空，則指針為空，否則必為表結(jié)點(diǎn)）；在這種存儲(chǔ)結(jié)構(gòu)中有幾種情況： 容易分清廣義表中原子和子表所在層次。如在廣義表D中，原子a和e在同一層次上，而b、c和d在同一層次且比a和e低一層，B和C是

33、同一層的子表； 最高層的表結(jié)點(diǎn)個(gè)數(shù)即為廣義表的長(zhǎng)度。 容易分清廣義表中原子和子表所在層次。如在廣義表D中，原 6.4.1 廣義表的概念 6.4.2 廣義表的存儲(chǔ)結(jié)構(gòu) 6.4.3 廣義表的應(yīng)用6.4 廣義表 6.4.1 廣義表的概念6.4 廣義表m元多項(xiàng)式的表示 一個(gè)m元多項(xiàng)式的每一項(xiàng)最多有m個(gè)變?cè)?，如果用單鏈表表示，則每個(gè)節(jié)點(diǎn)應(yīng)該包括m個(gè)指數(shù)項(xiàng)和一個(gè)數(shù)據(jù)項(xiàng)；如果多項(xiàng)式各項(xiàng)的變?cè)獢?shù)不相同，將勢(shì)必造成存儲(chǔ)空間的浪費(fèi)。為此，我們考慮采用其它的方式來(lái)存儲(chǔ)一個(gè)m元多項(xiàng)式。 我們以三元多項(xiàng)式：P(x,y,z) = x10y3z2+2x6y3z2+3x5y2z2+x4y4z+6x3y4z+2yz+15 為例，討論其存儲(chǔ)表示。 m元多項(xiàng)式的表示 P(x,y,z) = x10y3z2+2x6y3z2+3x5y2z2+x4y4z+6x3y4z+2yz+15 該多項(xiàng)式中各項(xiàng)的變?cè)獢?shù)目不盡相同，某些因子多次出現(xiàn)，我們可以將其改寫為：P(x,y,z) = (x10 + 2x6)y3+3x5y2)z2+(x4 + 6x3)y4+2y)z+15 此時(shí)，該多項(xiàng)式就變成了變?cè)獄的多項(xiàng)式，即A z2 + B z1 +15 z0，對(duì)這個(gè)一元多項(xiàng)式我們用單鏈表表示為： P(x,y,z) =