1、8.1 廣義表的定義,第8章 廣義表,8.2 廣義表的存儲結(jié)構(gòu),8.3 廣義表的運算,本章小結(jié),8.1 廣義表的定義 廣義表簡稱表, 它是線性表的推廣。一個廣義表是n(n0)個元素的一個序列： GL=(a1,a2,ai,an) 廣義表的一般表示與線性表相同。 ai為廣義表的第i個元素，n表示廣義表的長度,即廣義表中所含元素的個數(shù),n0。若n=0時則稱為空表。,8.1 廣義表的定義 廣義表示一種遞歸定義的線性結(jié)構(gòu)，廣義表的元素既可以是普通的數(shù)據(jù)元素，也可以是廣義表。 對于GL=(a1,a2,ai,an)來說，如果ai是單個數(shù)據(jù)元素,則ai是廣義表GL的原子；如果ai是一個廣義表,則ai是廣義表G

2、L的子表。,我們規(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) F=(a,F)=(a,(a,(a,),廣義表具有如下重要的特性： (1)廣義表中的數(shù)據(jù)元素是有順序的； (2)廣義表的長度定義為最外層包含元素個數(shù)； (3)廣義表的深度定義為所含括弧的重數(shù)。其中,原子的深度為0,空表的深度為1； (4)廣義表可以共享；一個廣義表可以為其他廣義表共享；這種共享廣義表稱為再入表； (5)廣義表可以是一個遞歸的表。一個廣義表可以是自已的子表。這種廣義

3、表稱為遞歸表。 遞歸表的深度是無窮值,長度是有限值；,廣義表具有如下重要的特性： (6)任何一個非空廣義表GL均可分解為表頭head(GL)和表尾tail(GL) 兩部分。 表頭是廣義表的第一個元素： head(GL)= a1 表尾是廣義表中除了表頭之外的所有元素構(gòu)成的廣義表 ：tail(GL) = ( a2,an),如果把每個表的名字(若有的話)寫在其表的前面,則上面的5個廣義表可相應(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é)點應(yīng)在

4、其表結(jié)點的下方)連接起來,則可得到一個廣義表的圖形表示。例如,上面五個廣義表的圖形表示如下圖所示。 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 廣義表的存儲結(jié)構(gòu) 廣義表是一種遞歸的數(shù)據(jù)結(jié)構(gòu),因此很難為每個廣義表分配固定大小的存儲空間,所以其存儲結(jié)構(gòu)只好采用動態(tài)鏈式結(jié)構(gòu)。 有兩類結(jié)點,一類為圓圈結(jié)點,在這里對應(yīng)子表；另一類為方形結(jié)點,在這里對應(yīng)原子。,廣義表的存儲結(jié)構(gòu),廣義表的情況 ：,為原子的情況 ：,typedef struct lnode int tag; /*結(jié)點類型標識*/ union ElemT

5、ype data; struct lnode *sublist; val; struct lnode *link;/*指向下一個元素*/ GLNode;/*廣義表結(jié)點類型定義*/,廣義表的存儲結(jié)構(gòu),8.3 廣義表的運算 1. 求廣義表的長度 在廣義表中,同一層次的每個結(jié)點是通過link域鏈接起來的,所以可把它看做是由link域鏈接起來的單鏈表。這樣,求廣義表的長度就是求單鏈表的長度,可以采用以前介紹過的求單鏈表長度的方法求其長度。,求廣義表長度的非遞歸算法如下： int GLLength(GLNode *g) /*g為一個廣義表頭結(jié)點的指針*/ int n=0; g=g-val.sublist

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

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

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

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