數(shù)據(jù)結(jié)構(gòu) 廣義表

1、8.1 8.1 廣義表的定義廣義表的定義第第8 8章章 廣義表廣義表8.2 8.2 廣義表的存儲結(jié)構(gòu)廣義表的存儲結(jié)構(gòu)8.3 8.3 廣義表的運算廣義表的運算本章小結(jié)本章小結(jié)8.1 8.1 廣義表的定義廣義表的定義 廣義表簡稱表廣義表簡稱表,它是線性表的推廣。一個廣義它是線性表的推廣。一個廣義表是表是n(n0)個元素的一個序列個元素的一個序列,若若n=0時則稱為空時則稱為空表。設(shè)表。設(shè)ai為廣義表的第為廣義表的第i個元素個元素,則廣義表則廣義表GL的一的一般表示與線性表相同：般表示與線性表相同： GL=(a1,a2,ai,an) 其中其中n表示廣義表的長度表示廣義表的長度,即廣義表中所含元即廣義

2、表中所含元素的個數(shù)素的個數(shù),n0。如果。如果ai是單個數(shù)據(jù)元素是單個數(shù)據(jù)元素,則則ai是廣是廣義表義表GL的原子；如果的原子；如果ai是一個廣義表是一個廣義表,則則ai是廣義是廣義表表GL的子表。的子表。 廣義表具有如下重要的特性：廣義表具有如下重要的特性： (1)廣義表中的數(shù)據(jù)元素有相對次序；廣義表中的數(shù)據(jù)元素有相對次序； (2)廣義表的長度定義為最外層包含元素個數(shù)；廣義表的長度定義為最外層包含元素個數(shù)； (3)廣義表的深度定義為所含括弧的重數(shù)。其中廣義表的深度定義為所含括弧的重數(shù)。其中,原原子的深度為子的深度為0,空表的深度為空表的深度為1； (4)廣義表可以共享；一個廣義表可以為其他廣義

3、廣義表可以共享；一個廣義表可以為其他廣義表共享；這種共享廣義表稱為再入表；表共享；這種共享廣義表稱為再入表； (5)廣義表可以是一個遞歸的表。一個廣義表可以廣義表可以是一個遞歸的表。一個廣義表可以是自已的子表。這種廣義表稱為遞歸表。遞歸表的是自已的子表。這種廣義表稱為遞歸表。遞歸表的深度是無窮值深度是無窮值,長度是有限值；長度是有限值； (6)任何一個非空廣義表任何一個非空廣義表GL均可分解為表頭均可分解為表頭head(GL) = a1和表尾和表尾tail(GL) = ( a2,an) 兩部分。兩部分。 為了簡單起見為了簡單起見,下面討論的廣義表不包括前面定下面討論的廣義表不包括前面定義的再入

4、表和遞歸表義的再入表和遞歸表,即只討論一般的廣義表。另即只討論一般的廣義表。另外外,我們規(guī)定用小寫字母表示原子我們規(guī)定用小寫字母表示原子,用大寫字母表示用大寫字母表示廣義表的表名。例如：廣義表的表名。例如： A=() B=(e) C=(a,(b,c,d) D=(A,B,C)=(),(e),(a,(b,c,d) E=(a,(a,b),(a,b),c) 如果把每個表的名字如果把每個表的名字(若有的話若有的話)寫在其表的前面寫在其表的前面,則則上面的上面的5個廣義表可相應(yīng)地表示如下：個廣義表可相應(yīng)地表示如下： A() B(e) C(a,(b,c,d) D(A(),B(e),C(a,(b,c,d) E

5、(a,(a,b),(a,b),c) 若用圓圈和方框分別表示表和單元素若用圓圈和方框分別表示表和單元素,并用線段把表并用線段把表和它的元素和它的元素(元素結(jié)點應(yīng)在其表結(jié)點的下方元素結(jié)點應(yīng)在其表結(jié)點的下方)連接起來連接起來,則則可得到一個廣義表的圖形表示。例如可得到一個廣義表的圖形表示。例如,上面五個廣義表上面五個廣義表的圖形表示如下圖所示。的圖形表示如下圖所示。 c a b a b E d e a b c D A B C d b c C a B e A a 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 8.2 廣

6、義表的存儲結(jié)構(gòu)廣義表的存儲結(jié)構(gòu) 廣義表是一種遞歸的數(shù)據(jù)結(jié)構(gòu)廣義表是一種遞歸的數(shù)據(jù)結(jié)構(gòu),因此很難為每個因此很難為每個廣義表分配固定大小的存儲空間廣義表分配固定大小的存儲空間,所以其存儲結(jié)構(gòu)只所以其存儲結(jié)構(gòu)只好采用動態(tài)鏈?zhǔn)浇Y(jié)構(gòu)。好采用動態(tài)鏈?zhǔn)浇Y(jié)構(gòu)。 我們將一個廣義表看成一棵樹我們將一個廣義表看成一棵樹,為了方便存儲為了方便存儲,將將其轉(zhuǎn)換成一棵二叉樹。其轉(zhuǎn)換過程已在第其轉(zhuǎn)換成一棵二叉樹。其轉(zhuǎn)換過程已在第6章中介紹章中介紹過過,這里以示例中的廣義表這里以示例中的廣義表C說明其轉(zhuǎn)換過程。如下說明其轉(zhuǎn)換過程。如下圖所示圖所示,左邊的圖表示轉(zhuǎn)換的中間狀態(tài)左邊的圖表示轉(zhuǎn)換的中間狀態(tài),右邊的圖表示右邊的圖表示

7、轉(zhuǎn)換的最終狀態(tài)轉(zhuǎn)換的最終狀態(tài),即一棵二叉樹。從二叉樹中看到即一棵二叉樹。從二叉樹中看到,有有兩類結(jié)點兩類結(jié)點,一類為圓圈結(jié)點一類為圓圈結(jié)點,在這里對應(yīng)子表；另一類在這里對應(yīng)子表；另一類為方形結(jié)點為方形結(jié)點,在這里對應(yīng)原子。在這里對應(yīng)原子。 C a b c d C a b c d C 1 0 a 1 0 b 0 c 0 d 廣義表的存儲結(jié)構(gòu)廣義表的存儲結(jié)構(gòu) typedef struct lnode int tag; /*結(jié)點類型標(biāo)識結(jié)點類型標(biāo)識*/ union ElemType data; struct lnode *sublist; val; struct lnode *link;/*指向下一

8、個元素指向下一個元素*/ GLNode;/*廣義表結(jié)點類型定義廣義表結(jié)點類型定義*/廣義表的兩種基本情況廣義表的兩種基本情況 ： g1 1 g2 1 * * * * * * 第 1 個元素 第 2 個元素 第 n 個元素 （a）空表 （b）非空表 為原子的情況為原子的情況 ： g3 0 a 8.3 8.3 廣義表的運算廣義表的運算1. 求廣義表的長度求廣義表的長度 在廣義表中在廣義表中,同一層次的每個結(jié)點是通過同一層次的每個結(jié)點是通過link域鏈域鏈接起來的接起來的,所以可把它看做是由所以可把它看做是由link域鏈接起來的單域鏈接起來的單鏈表。這樣鏈表。這樣,求廣義表的長度就是求單鏈表的長度求

9、廣義表的長度就是求單鏈表的長度,可可以采用以前介紹過的求單鏈表長度的方法求其長度。以采用以前介紹過的求單鏈表長度的方法求其長度。求廣義表長度的非遞歸算法如下：求廣義表長度的非遞歸算法如下： int GLLength(GLNode *g) /*g為一個廣義表頭結(jié)點的指針為一個廣義表頭結(jié)點的指針*/ int n=0; g=g-val.sublist;/*g指向廣義表的第一個元素指向廣義表的第一個元素*/ while (g!=NULL) n+; g=g-link; return n; 2. 求廣義表的深度求廣義表的深度 對于帶頭結(jié)點的廣義表對于帶頭結(jié)點的廣義表g,廣義表深度的遞歸定義廣義表深度的遞歸

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

11、if (g=NULL) return 1; /*為空表時返回為空表時返回1*/ while (g!=NULL) /*遍歷表中的每一個元素遍歷表中的每一個元素*/ if (g-tag=1) /*元素為子表的情況元素為子表的情況*/ dep=GLDepth(g); /*遞歸調(diào)用求出子表的深度遞歸調(diào)用求出子表的深度*/ if (depmax) max=dep; /*max為同一層所求過的子表中深度的最大值為同一層所求過的子表中深度的最大值*/ g=g-link; /*使使g指向下一個元素指向下一個元素*/ return(max+1); /*返回表的深度返回表的深度*/3. 建立廣義表的鏈?zhǔn)酱鎯Y(jié)構(gòu)建

12、立廣義表的鏈?zhǔn)酱鎯Y(jié)構(gòu) 假定廣義表中的元素類型假定廣義表中的元素類型ElemType為為char類型類型,每每個原子的值被限定為英文字母。個原子的值被限定為英文字母。 并假定廣義表是一個表達(dá)式并假定廣義表是一個表達(dá)式,其格式為：元素之間用其格式為：元素之間用一個逗號分隔一個逗號分隔,表元素的起止符號分別為左、右圓括號表元素的起止符號分別為左、右圓括號,空表在其圓括號內(nèi)不包含任何字符。例如空表在其圓括號內(nèi)不包含任何字符。例如“(a,(b,c,d)”就是一個符合上述規(guī)定的廣義表格式。就是一個符合上述規(guī)定的廣義表格式。 生成廣義表鏈?zhǔn)酱鎯Y(jié)構(gòu)的算法如下：生成廣義表鏈?zhǔn)酱鎯Y(jié)構(gòu)的算法如下：GLNode

13、 *CreatGL(char *&s) GLNode *h;char ch=*s+; /*取一個掃描字符取一個掃描字符*/ if (ch!=0) /*串未結(jié)束判斷串未結(jié)束判斷*/ h=(GLNode *)malloc(sizeof(GLNode);/*創(chuàng)建新結(jié)點創(chuàng)建新結(jié)點*/ if (ch=() /*當(dāng)前字符為左括號時當(dāng)前字符為左括號時*/ h-tag=1; /*新結(jié)點作為表頭結(jié)點新結(jié)點作為表頭結(jié)點*/ h-val.sublist=CreatGL(s); /*遞歸構(gòu)造子表并鏈到表頭結(jié)點遞歸構(gòu)造子表并鏈到表頭結(jié)點*/ else if (ch=) h=NULL; /*遇到遇到)字符字符,子

14、表為空子表為空*/ else h-tag=0; /*新結(jié)點作為原子結(jié)點新結(jié)點作為原子結(jié)點*/ h-val.data=ch; else h=NULL; /*串結(jié)束串結(jié)束,子表為空子表為空*/ ch=*s+; /*取下一個掃描字符取下一個掃描字符*/ if (h!=NULL) /*串未結(jié)束判斷串未結(jié)束判斷*/ if (ch=,) /*當(dāng)前字符為當(dāng)前字符為,*/ h-link=CreatGL(s); /*遞歸構(gòu)造后續(xù)子表遞歸構(gòu)造后續(xù)子表*/ else /*串結(jié)束串結(jié)束*/ h-link=NULL; /*處理表的最后一個元素處理表的最后一個元素*/ return h; /*返回廣義表指針返回廣義表指針

15、*/ 4. 輸出廣義表輸出廣義表 以以h作為帶表頭附加結(jié)點的廣義表的表頭指針作為帶表頭附加結(jié)點的廣義表的表頭指針,打印輸打印輸出該廣義表時出該廣義表時,需要對子表進(jìn)行遞歸調(diào)用。輸出一個廣義需要對子表進(jìn)行遞歸調(diào)用。輸出一個廣義表的算法如下：表的算法如下：void DispGL(GLNode *g) /*g為一個廣義表的頭結(jié)點指針為一個廣義表的頭結(jié)點指針*/ if (g!=NULL) /*表不為空判斷表不為空判斷*/ if (g-tag=1) /*為表結(jié)點時為表結(jié)點時*/ printf(); /*輸出輸出(*/ if (g-val.sublist=NULL) printf(); /*輸出空子表輸出空子表*/ else DispGL(g-val.sublist); /*遞歸輸出子表遞歸輸出子表*/ else printf(%c, g-val.data); /*為原子時輸出元素值為原子時輸出元素值*/ if (g-tag=1) printf(); /*為表結(jié)點時輸出為表結(jié)點時輸出)*/ if (g-link!=NULL) printf(,); DispGL(g-link); /*遞歸輸出后續(xù)表的內(nèi)容遞歸輸出后續(xù)