零基礎學數據結構廣義表PPT課件

1、8.1 廣義表 8.1.1 什么是廣義表 廣義表，也稱為列表（lists），是由n個類型相同的數據元素(a1,a2,a3,an)組成的有限序列。其中，廣義表中的元素ai可以是單個元素，也可以是一個廣義表。 通常，廣義表記作：GL=(a1,a2,a3,an)。其中，GL是廣義表的名字， n是廣義表的長度。如果廣義表中的ai是單個元素，則稱ai是原子。如果廣義表中的ai是一個廣義表，則稱ai是廣義表的子表。 習慣上用大寫字母表示廣義表的名字，用小寫字母表示原子。第1頁/共28頁8.1 廣義表 在廣義表GL中，a1稱為廣義表GL的表頭（head），其余元素組成的表(a2,a3,an)稱為廣義表GL的

2、表尾（tail）。廣義表是一個遞歸的定義，因為在描述廣義表時又用到了廣義表的概念。下面是一些廣義表的例子。 （1）A=()，廣義表A是長度為0的空表。 （2）B=(a)，B是一個長度為1且元素為原子的廣義表（其實就是前面討論過的一般的線性表）。 （3）C=(a,(b,c)，C是長度為2的廣義表。其中，第1個元素是原子a，第2個元素是一個子表(b,c)。 （4）D=(A,B,C)，D是一個長度為3的廣義表，這3個元素都是子表，第1個元素是一個空表A。 （5）E=(a,b,E)，E是一個長度為3的遞歸廣義表，相當于 E=(a,b,(a,b,(a,b,(a,b,(a,b)。第2頁/共28頁8.1 廣

3、義表 從上述定義和例子可推出廣義表的重要結論如下： （1）廣義表的元素既可以是原子，也可以是子表，子表的元素可以是元素，也可以是子表。廣義表的結構是一個多層次的結構。 （2）一個廣義表還可以是另一個廣義表的元素。例如，A、B和C是D的子表，在表D中不需要列出A、B和C的元素。 （3）廣義表可以是遞歸的表，即廣義表可以是本身的一個子表。例如，E就是一個遞歸的廣義表。 任何一個非空廣義表的表頭可以是一個原子，也可以是一個廣義表，而表尾一定是一個廣義表。例如： head(A)=()，tail（A）=()，head(C)=a,tail(C)=(b,c)， head(D)=A，tail(D)=(B,C)

4、 其中，head(A)表示取廣義表A的表頭元素，tail(A)表示取廣義表A的表尾元素。第3頁/共28頁8.1 廣義表 8.1.2 廣義表的抽象數據類型 1數據對象集合 廣義表的數據對象集合為ai|1in，ai可以是原子，也可以是廣義表。例如，A=(a,(b,c)是一個廣義表， A中包含兩個元素a和(b,c)，第2個元素為子表，包含了2個元素b和c。若把(b,c)看成一個整體，則a和(b,c)構成了一個線性表，在子表(b,c)的內部，b和c又構成了線性表。故廣義表可看作是線性表的擴展。第4頁/共28頁8.1 廣義表 2基本操作集合 （1）GetHead(L)：求廣義表的表頭。如果廣義表是空表，

5、則返回NULL；否則，返回指向表頭結點的指針。 （2）GetTail(L)：求廣義表的表尾。如果廣義表是空表，則返回NULL；否則，返回指向表尾結點的指針。 （3）GListLength(L)：返回廣義表的長度。如果廣義表是空表，則返回0；否則，返回廣義表的長度。 （4）GListDepth(L)：求廣義表的深度。廣義表的深度就是廣義表中括號嵌套的層數。如果廣義表是空表，則返回1；否則返回廣義表的深度。 （5）CopyGList(&T,L)：復制廣義表。由廣義表L復制得到廣義表T。復制成功返回1；否則，返回0。第5頁/共28頁8.2 廣義表的頭尾鏈表表示與實現(xiàn) 8.2.1 廣義表的頭尾

6、鏈表存儲結構 因廣義表中有兩種元素：原子和子表，所以廣義表的鏈表結點也分為兩種：原子結點和子表結點，其中，子表結點包含3個域：標志域、指向表頭的指針域和指向表尾的指針域。原子結點包含兩個域：標志域和值域。表結點和原子結點的存儲結構如圖8.1所示。 其中，tag=1表示是子表，hp和tp分別指向表頭結點和表尾結點，tag=0表示原子，atom用于存儲原子的值。第6頁/共28頁8.2 廣義表的頭尾鏈表表示與實現(xiàn)我們將廣義表的這種存儲結構稱為頭尾鏈表存儲表示。用頭尾鏈法表示的廣義表A=()，B=(a)，C=(a,(b,c)，D=(A,B,C)，E=(a,b,E)如圖8.2所示。第7頁/共28頁8.2

7、 廣義表的頭尾鏈表表示與實現(xiàn) 廣義表的頭尾鏈表存儲結構類型描述如下： typedef enumATOM,LISTElemTag; /*ATOM=0原子，LIST=1子表*/ typedef struct ElemTag tag;/*標志位tag用于區(qū)分元素是原子還是子表*/ union AtomType atom; /*AtomType是原子結點的值域*/ struct struct GLNode *hp,*tp; /*hp指向表頭，tp指向表尾*/ ptr; ; *GList,GLNode;第8頁/共28頁8.2 廣義表的頭尾鏈表表示與實現(xiàn) 8.2.2 廣義表的基本運算（1）求廣義表的表頭。

8、GLNode* GetHead(GList L)/*求廣義表的表頭結點操作*/ GLNode *p; if(!L) /*如果廣義表為空表，則返回NULL*/ printf(“該廣義表是空表！”); return NULL; p=L-ptr.hp; /*將廣義表的表頭指針賦值給p*/ if(!p) printf(“該廣義表的表頭是空表”); else if(p-tag=LIST) printf(“該廣義表的表頭是非空的子表?！?; else printf(“該廣義表的表頭是原子?！?; return p;第9頁/共28頁8.2 廣義表的頭尾鏈表表示與實現(xiàn) （2）求廣義表的表尾。 GLNode*

9、GeTail(GList L) /*求廣義表的表尾*/ if(!L) /*廣義表為空表，則返回NULL*/ printf(“該廣義表是空表！”); return NULL; return L-ptr.hp; /*廣義表不是空表，返回表尾結點的指針*/ 第10頁/共28頁8.2 廣義表的頭尾鏈表表示與實現(xiàn) （3）求廣義表的長度。求廣義表的長度只需要沿著表尾指針tp查找下去，統(tǒng)計子表個數，直到tp為NULL為止。如果廣義表是空表，則廣義表的長度為0。否則，將指針p指向結點的表尾指針，統(tǒng)計廣義表的長度。 int GListLength(GList L) int length=0; while(L)

10、/*如果廣義表非空，則將p指向表尾指針，統(tǒng)計表的長度*/ L=L-ptr.tp; length+; return length; 第11頁/共28頁8.2 廣義表的頭尾鏈表表示與實現(xiàn) （4）求廣義表的深度。求廣義表的深度可利用遞歸實現(xiàn)。如果廣義表是空表，則返回1。如果是原子，則返回0。如果是一個非空的廣義表，遞歸求每個子表的深度，令p指向表頭結點，即L的第一個元素a1（如果a1是子表），求a1的深度，當求出a1的深度后，然后求L的第2個元素a2的深度。依次類推，最后返回廣義表GL深度。 廣義表的深度就是廣義表中括號的層數。假設廣義表為GL=(a1,a2,a3,an)，ai可能是原子，也可能是子

11、表，求廣義表GL的深度可以分解為n個子問題，每個子問題就是求ai的深度。如果ai是原子，則深度為0；如果ai是子表，則繼續(xù)求ai的深度。廣義表GL的深度為所有元素ai的深度的最大值加1。根據定義，空表的深度為1。第12頁/共28頁8.2 廣義表的頭尾鏈表表示與實現(xiàn) 求廣義表的深度的算法實現(xiàn)如下。 int GListDepth(GList L) int max,depth; GLNode *p; if(!L) /*如果廣義表為空，則返回1*/ return 1; if(L-tag=ATOM) /*如果廣義表是原子，則返回0*/ return 0; for(max=0,p=L;p;p=p-ptr.

12、tp) /*逐層處理廣義表*/ depth=GListDepth(p-ptr.hp); if(maxtag=L-tag;if(L-tag=ATOM) /*復制原子*/ (*T)-atom=L-atom;else/*遞歸復制子表*/CopyList(&(*T)-ptr.hp),L-ptr.hp);CopyList(&(*T)-ptr.tp),L-ptr.tp); 第15頁/共28頁8.2 廣義表的頭尾鏈表表示與實現(xiàn)8.2.3 廣義表應用舉例（采用頭尾鏈表存儲結構） 【例8_1】設廣義表采用頭尾鏈表存儲結構，編寫算法，建立一個廣義表，并求出廣義表的長度、深度和原子個數。 分析：主要

13、考察大家對廣義表的頭尾鏈表存儲結構的理解與基本操作。因為廣義表表是遞歸定義的，所以可以使用遞歸的方法創(chuàng)建廣義表、求廣義表的長度、深度和原子個數。第16頁/共28頁8.3 廣義表的擴展線性鏈表表示與實現(xiàn) 8.3.1 廣義表的擴展線性鏈表存儲 采用擴展線性鏈表表示的廣義表也包含兩種結點：表結點和原子結點，這兩種結點都包含3個域。其中，表結點由標志域tag、表頭指針域hp和表尾指針域tp構成，原子結點由標志域、原子的值域和表尾指針域構成。 標志域tag用來區(qū)分當前結點是表結點還是原子結點，當tag=0時為原子結點，tag=1時為表結點，hp和tp分別指向廣義表的表頭和表尾，atom用來存儲原子結點的

14、值。擴展性鏈表的結點結構如圖8.5所示。第17頁/共28頁8.3 廣義表的擴展線性鏈表表示與實現(xiàn) 例如，A=()，B=(a)，C=(a,(b,c)，D=(A,B,C)，廣義表D的擴展性鏈表存儲結構如圖8.6所示。第18頁/共28頁8.3 廣義表的擴展線性鏈表表示與實現(xiàn)廣義表的擴展性鏈表存儲結構的類型定義描述如下：typedef enumATOM,LISTElemTag; /*ATOM=0，表示原子，LIST=1，表示子表*/typedef structElemTag tag;/*標志位tag用于區(qū)分元素是原子還是子表*/union AtomType atom; /*AtomType是原子結點的

15、值域，用戶自己定義類型*/ struct GLNode *hp;/*hp指向表頭*/ptr;struct GLNode *tp; /*tp指向表尾*/*GList,GLNode;第19頁/共28頁8.3 廣義表的擴展線性鏈表表示與實現(xiàn) 8.3.2 廣義表的基本運算 （1）求廣義表的表頭。 GLNode* GetHead(GList L) GLNode *p; p=L-ptr.hp; /*將廣義表的表頭指針賦值給p*/ if(!p) /*如果廣義表為空表，則返回NULL*/ printf(“該廣義表是空表！”); return NULL; else if(p-tag=LIST) printf(“

16、該廣義表的表頭是非空的子表。”); else printf(“該廣義表的表頭是原子?！?; return p; 第20頁/共28頁8.3 廣義表的擴展線性鏈表表示與實現(xiàn) （2）求廣義表的表尾。 GLNode* GeTail(GList L) GLNode *p,*tail; p=L-ptr.hp; if(!p) /*如果廣義表為空表，則返回NULL*/ printf(“該廣義表是空表！”); return NULL; tail=(GLNode*)malloc(sizeof(GLNode);/*生成tail結點*/ tail-tag=LIST; /*將標志域置為LIST*/ tail-ptr.h

17、p=p-tp; /*將tail的表頭指針域指向廣義表的表尾*/ tail-tp=NULL; /*將tail的表尾指針域置為空*/ return tail; /*返回指向廣義表表尾結點的指針*/ 第21頁/共28頁8.3 廣義表的擴展線性鏈表表示與實現(xiàn) （3）求廣義表的長度。 int GListLength(GList L) int length=0; /*初始化化廣義表的長度*/ GLNode *p=L-ptr.hp; while(p) /*如果廣義表非空，則將p指向表尾指針，統(tǒng)計表的長度*/ length+; p=p-tp; return length; 第22頁/共28頁8.3 廣義表的擴

18、展線性鏈表表示與實現(xiàn) （4）求廣義表的深度。如果廣義表是空表，即L-tag=LIST&L-ptr.hp=NULL，則返回1。如果是原子，即L-tag=ATOM，則返回0。 如果是一個非空的廣義表，則遞歸調用GlistDepth函數求廣義表的深度。先用頭指針域找到下一層的子表，如果該層還有子表，則繼續(xù)利用頭指針域找到下一層，直到該層次結點為原子或者是空表，返回到上一層，并返回所求深度值。然后在該層中利用表尾指針找到該表的表尾，繼續(xù)利用表頭指針進行掃描，重復執(zhí)行以上操作，直到所有層都返回。第23頁/共28頁8.3 廣義表的擴展線性鏈表表示與實現(xiàn) 求廣義表的深度的算法實現(xiàn)如下。int GListDepth(GList L) int max,depth; GLNode *p; if(L-tag=LIST&L-ptr.hp=NULL) /*廣義表為空，返回1*/ return 1; if(L-tag=ATOM) /*廣義表是原子，返回0*/ return 0; p=L-ptr.hp; for(max=0;p;p=p-tp) /*逐層處理廣義表*/ depth=GListDepth(p); if(maxtag=L-tag