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

8.1廣義表的定義第8章廣義表8.2廣義表的存儲結(jié)構(gòu)8.3廣義表的運算本章小結(jié)8.1廣義表的定義

廣義表簡稱表,它是線性表的推廣。一個廣義表是n(n≥0)個元素的一個序列,若n=0時則稱為空表。設(shè)ai為廣義表的第i個元素,則廣義表GL的一般表示與線性表相同：

GL=(a1,a2,…,ai,…,an)

其中n表示廣義表的長度,即廣義表中所含元素的個數(shù),n≥0。如果ai是單個數(shù)據(jù)元素,則ai是廣義表GL的原子；如果ai是一個廣義表,則ai是廣義表GL的子表。廣義表具有如下重要的特性：

(1)廣義表中的數(shù)據(jù)元素有相對次序；

(2)廣義表的長度定義為最外層包含元素個數(shù)；

(3)廣義表的深度定義為所含括弧的重數(shù)。其中,原子的深度為0,空表的深度為1；

(4)廣義表可以共享；一個廣義表可以為其他廣義表共享；這種共享廣義表稱為再入表；

(5)廣義表可以是一個遞歸的表。一個廣義表可以是自已的子表。這種廣義表稱為遞歸表。遞歸表的深度是無窮值,長度是有限值；

(6)任何非空廣義表GL均可分解為兩部分。表頭head(GL)=a1和表尾tail(GL)=(a2,…,an)約定用小寫字母表示原子，用大寫字母表示廣義表的表名。例如：

A=()B=(e)C=(a,(b,c,d))D=(A,B,C)=((),(e),(a,(b,c,d)))E=((a,(a,b),((a,b),c)))若用圓圈和方框分別表示表和單元素,并用線段把表和它的元素(元素結(jié)點應(yīng)在其表結(jié)點的下方)連接起來,則可得到一個廣義表的圖形表示。例如,上面五個廣義表的圖形表示如下圖所示。A=()B=(e)eABC=(a,(b,c,d))D=(A,B,C)=((),(e),(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)。將一個廣義表看成一棵樹，為了方便存儲,將其轉(zhuǎn)換成一棵二叉樹。其轉(zhuǎn)換過程已在“樹”一章中介紹過，這里以示例中的廣義表C說明其轉(zhuǎn)換過程。如下圖所示，左邊的圖表示轉(zhuǎn)換的中間狀態(tài)，右邊的圖表示轉(zhuǎn)換的最終狀態(tài)，即一棵二叉樹。從二叉樹中看到，有兩類結(jié)點，一類為圓圈結(jié)點，在這里對應(yīng)子表；另一類為方形結(jié)點，在這里對應(yīng)原子。typedef

struct

lnode{ inttag; /*結(jié)點類型標識*/ union {ElemTypedata;

struct

lnode*sublist; }val;

struct

lnode*link; /*指向下一個元素*/}GLNode; /*廣義表結(jié)點類型定義*/廣義表的兩種基本情況：為原子的情況：8.3廣義表的運算1.求廣義表的長度

在廣義表中,同一層次的每個結(jié)點是通過link域鏈接起來的,所以可把它看做是由link域鏈接起來的單鏈表。這樣,求廣義表的長度就是求單鏈表的長度,可以采用以前介紹過的求單鏈表長度的方法求其長度。求廣義表長度的非遞歸算法如下：

int

GLLength(GLNode*g)/*g為一個廣義表頭結(jié)點的指針*/{

intn=0;g=g->val.sublist;/*g指向廣義表的第一個元素*/while(g!=NULL){n++;g=g->link;}returnn;}2.求廣義表的深度對于帶頭結(jié)點的廣義表g，廣義表深度的遞歸定義是它等于所有子表中表的最大深度加1。若g為原子，其深度為0。求廣義表深度的遞歸模型f()如下：f(g)=0若g為原子

1 若g為空表MAX{f(subg)}+1其他情況，subg為g的子表

1∧

10a∧0b0c0dC0e1∧

1C=((a),(b,c,d),(e))∧∧1int

GLDepth(GLNode*g)/*求帶頭結(jié)點的廣義表g的深度*/{intmax=0,dep;if(g->tag==0)return0;/*為原子時返回0*/g=g->val.sublist; /*g指向第一個元素*/if(g==NULL)return1;/*為空表時返回1*/while(g!=NULL) /*遍歷表中的每一個元素*/{if(g->tag==1) /*元素為子表的情況*/{dep=GLDepth(g);/*遞歸調(diào)用求出子表的深度*/if(dep>max)max=dep; /*max為同一層所求過的子表中深度的最大值*/}g=g->link; /*使g指向下一個元素*/}return(max+1); /*返回表的深度*/}3.建立廣義表的鏈式存儲結(jié)構(gòu)假定廣義表中的元素類型ElemType為char類型，每個原子的值被限定為英文字母。并假定廣義表是一個表達式，其格式為：元素之間用一個逗號分隔，表元素的起止符號分別為左、右圓括號，空表在其圓括號內(nèi)不包含任何字符。例如“(a,(b,c,d))”就是一個符合上述規(guī)定的廣義表格式。

生成廣義表鏈式存儲結(jié)構(gòu)的算法如下：GLNode*CreatGL(char*&s){GLNode*h;charch;ch=*s;/*取一個掃描字符*/s++; /*串指針后移一位*/if(ch!='\0') /*串未結(jié)束判斷*/{h=(GLNode*)malloc(sizeof(GLNode));/*創(chuàng)建新結(jié)點*/

if(ch=='(') /*當前字符為左括號時*/ {h->tag=1; /*新結(jié)點作為表頭結(jié)點*/h->val.sublist=CreatGL(s);/*遞歸構(gòu)造子表并鏈到表頭結(jié)點*/ }

elseif(ch==')')h=NULL;/*遇到')'字符,子表為空*/ else{h->tag=0; /*新結(jié)點作為原子結(jié)點*/ h->val.data=ch; }}elseh=NULL; /*串結(jié)束,子表為空*/

ch=*s; /*取下一個掃描字符*/s++; /*串指針后移一位*/

if(h!=NULL) /*串未結(jié)束判斷*/

if(ch==',') /*當前字符為','*/h->link=CreatGL(s);/*遞歸構(gòu)造后續(xù)子表*/ else /*串結(jié)束*/h->link=NULL; /*處理表的最后一個元素*/returnh; /*返回廣義表指針*/}1∧

10a0b0c0dC0e1∧

1C=(a,(b,c,d),(e))∧∧4.輸出廣義表以h作為帶表頭附加結(jié)點的廣義表的表頭指針，打印輸出該廣義表時，需要對子表進行遞歸調(diào)用。輸出一個廣義表的算法如下：voidDispGL(GLNode*g)/*g為一個廣義表的頭結(jié)點指針*/{if(g!=NULL)/*表不為空判斷*/{if(g->tag==1)/*為表結(jié)點時*/ {printf("(");/*輸出'('*/if(g->val.sublist==NULL)

printf("");/*輸出空子表*/ elseDispGL(g->val.sublist);/*遞歸輸出子表*/ } elseprintf("%c",g->val.data);/*為原子時輸出元素值*/if(g->tag==1)

printf(")");/*為表結(jié)點時輸出')'*/if(g->link!=NULL)

{printf(",");

DispGL(g->link); /*遞歸輸出后續(xù)表的內(nèi)容*/ }}}1∧

10