1、8.1 廣義表的定義,第8章 廣義表,8.2 廣義表的存儲(chǔ)結(jié)構(gòu),8.3 廣義表的運(yùn)算,本章小結(jié),8.1 廣義表的定義 廣義表簡(jiǎn)稱表,它是線性表的推廣。一個(gè)廣義表是n(n0)個(gè)元素的一個(gè)序列,若n=0時(shí)則稱為空表。設(shè)ai為廣義表的第i個(gè)元素,則廣義表GL的一般表示與線性表相同： GL=(a1,a2,ai,an) 其中n表示廣義表的長(zhǎng)度,即廣義表中所含元素的個(gè)數(shù),n0。如果ai是單個(gè)數(shù)據(jù)元素,則ai是廣義表GL的原子；如果ai是一個(gè)廣義表,則ai是廣義表GL的子表。,廣義表具有如下重要的特性： (1)廣義表中的數(shù)據(jù)元素有相對(duì)次序； (2)廣義表的長(zhǎng)度定義為最外層包含元素個(gè)數(shù)； (3)廣義表的深度定

2、義為所含括弧的重?cái)?shù)。其中,原子的深度為0,空表的深度為1； (4)廣義表可以共享；一個(gè)廣義表可以為其他廣義表共享；這種共享廣義表稱為再入表； (5)廣義表可以是一個(gè)遞歸的表。一個(gè)廣義表可以是自已的子表。這種廣義表稱為遞歸表。遞歸表的深度是無(wú)窮值,長(zhǎng)度是有限值； (6)任何一個(gè)非空廣義表GL均可分解為表頭head(GL) = a1和表尾tail(GL) = ( a2,an) 兩部分。,為了簡(jiǎn)單起見(jiàn),下面討論的廣義表不包括前面定義的再入表和遞歸表,即只討論一般的廣義表。另外,我們規(guī)定用小寫(xiě)字母表示原子,用大寫(xiě)字母表示廣義表的表名。例如： A=() B=(e) C=(a,(b,c,d) D=(A,B

3、,C)=(),(e),(a,(b,c,d) E=(a,(a,b),(a,b),c),如果把每個(gè)表的名字(若有的話)寫(xiě)在其表的前面,則上面的5個(gè)廣義表可相應(yīng)地表示如下： A() B(e) C(a,(b,c,d) D(A(),B(e),C(a,(b,c,d) E(a,(a,b),(a,b),c) 若用圓圈和方框分別表示表和單元素,并用線段把表和它的元素(元素結(jié)點(diǎn)應(yīng)在其表結(jié)點(diǎn)的下方)連接起來(lái),則可得到一個(gè)廣義表的圖形表示。例如,上面五個(gè)廣義表的圖形表示如下圖所示。,A() B(e) C(a,(b,c,d) D(A(),B(e),C(a,(b,c,d) E(a,(a,b),(a,b),c),8.2 廣

4、義表的存儲(chǔ)結(jié)構(gòu) 廣義表是一種遞歸的數(shù)據(jù)結(jié)構(gòu),因此很難為每個(gè)廣義表分配固定大小的存儲(chǔ)空間,所以其存儲(chǔ)結(jié)構(gòu)只好采用動(dòng)態(tài)鏈?zhǔn)浇Y(jié)構(gòu)。 我們將一個(gè)廣義表看成一棵樹(shù),為了方便存儲(chǔ),將其轉(zhuǎn)換成一棵二叉樹(shù)。其轉(zhuǎn)換過(guò)程已在第6章中介紹過(guò),這里以示例中的廣義表C說(shuō)明其轉(zhuǎn)換過(guò)程。如下圖所示,左邊的圖表示轉(zhuǎn)換的中間狀態(tài),右邊的圖表示轉(zhuǎn)換的最終狀態(tài),即一棵二叉樹(shù)。從二叉樹(shù)中看到,有兩類結(jié)點(diǎn),一類為圓圈結(jié)點(diǎn),在這里對(duì)應(yīng)子表；另一類為方形結(jié)點(diǎn),在這里對(duì)應(yīng)原子。,廣義表的存儲(chǔ)結(jié)構(gòu),typedef struct lnode int tag; /*結(jié)點(diǎn)類型標(biāo)識(shí)*/ union ElemType data; struct lnod

5、e *sublist; val; struct lnode *link;/*指向下一個(gè)元素*/ GLNode;/*廣義表結(jié)點(diǎn)類型定義*/,廣義表的兩種基本情況 ：,為原子的情況 ：,8.3 廣義表的運(yùn)算 1. 求廣義表的長(zhǎng)度 在廣義表中,同一層次的每個(gè)結(jié)點(diǎn)是通過(guò)link域鏈接起來(lái)的,所以可把它看做是由link域鏈接起來(lái)的單鏈表。這樣,求廣義表的長(zhǎng)度就是求單鏈表的長(zhǎng)度,可以采用以前介紹過(guò)的求單鏈表長(zhǎng)度的方法求其長(zhǎng)度。,求廣義表長(zhǎng)度的非遞歸算法如下： int GLLength(GLNode *g) /*g為一個(gè)廣義表頭結(jié)點(diǎn)的指針*/ int n=0; g=g-val.sublist;/*g指向廣義

6、表的第一個(gè)元素*/ while (g!=NULL) n+; g=g-link; return n; ,2. 求廣義表的深度 對(duì)于帶頭結(jié)點(diǎn)的廣義表g,廣義表深度的遞歸定義是它等于所有子表中表的最大深度加1。若g為原子,其深度為0。 求廣義表深度的遞歸模型f()如下：,f(g)=,0 若g為原子,1 若g為空表,MAXf(subg)+1 其他情況,subg為g的子表,int GLDepth(GLNode *g) /*求帶頭結(jié)點(diǎn)的廣義表g的深度*/ int max=0,dep; if (g-tag=0) return 0; /*為原子時(shí)返回0*/ g=g-val.sublist; /*g指向第一個(gè)元

7、素*/ if (g=NULL) return 1; /*為空表時(shí)返回1*/ while (g!=NULL) /*遍歷表中的每一個(gè)元素*/ if (g-tag=1) /*元素為子表的情況*/ dep=GLDepth(g); /*遞歸調(diào)用求出子表的深度*/ if (depmax) max=dep; /*max為同一層所求過(guò)的子表中深度的最大值*/ g=g-link; /*使g指向下一個(gè)元素*/ return(max+1); /*返回表的深度*/ ,3. 建立廣義表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu) 假定廣義表中的元素類型ElemType為char類型,每個(gè)原子的值被限定為英文字母。 并假定廣義表是一個(gè)表達(dá)式,其格式為

8、：元素之間用一個(gè)逗號(hào)分隔,表元素的起止符號(hào)分別為左、右圓括號(hào),空表在其圓括號(hào)內(nèi)不包含任何字符。例如“(a,(b,c,d)”就是一個(gè)符合上述規(guī)定的廣義表格式。,生成廣義表鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)的算法如下： GLNode *CreatGL(char * /*遞歸構(gòu)造子表并鏈到表頭結(jié)點(diǎn)*/ ,else if (ch=) h=NULL; /*遇到)字符,子表為空*/ else h-tag=0; /*新結(jié)點(diǎn)作為原子結(jié)點(diǎn)*/ h-val.data=ch; else h=NULL; /*串結(jié)束,子表為空*/ ch=*s+; /*取下一個(gè)掃描字符*/ if (h!=NULL) /*串未結(jié)束判斷*/ if (ch=,)

9、/*當(dāng)前字符為,*/ h-link=CreatGL(s); /*遞歸構(gòu)造后續(xù)子表*/ else /*串結(jié)束*/ h-link=NULL; /*處理表的最后一個(gè)元素*/ return h; /*返回廣義表指針*/ ,4. 輸出廣義表 以h作為帶表頭附加結(jié)點(diǎn)的廣義表的表頭指針,打印輸出該廣義表時(shí),需要對(duì)子表進(jìn)行遞歸調(diào)用。輸出一個(gè)廣義表的算法如下：,void DispGL(GLNode *g) /*g為一個(gè)廣義表的頭結(jié)點(diǎn)指針*/ if (g!=NULL) /*表不為空判斷*/ if (g-tag=1) /*為表結(jié)點(diǎn)時(shí)*/ printf(); /*輸出(*/ if (g-val.sublist=NULL) printf(); /*輸出空子表*/ else DispGL(g-val.sublist); /*遞歸輸出子表*/ else printf(%c, g-val.data); /*為原子時(shí)輸出元素值*/ if (g-tag=1) printf(); /*為表結(jié)點(diǎn)時(shí)輸出)*/ if (g-link!=NULL) printf(,); DispGL(g-li