內(nèi)容提要廣義表的概念廣義表的存儲結(jié)構(gòu)廣義表的課件

1、2022/7/246. 1 廣義表的概念 定義：廣義表是n(n=0)個元素a1,a2,an的有限序列，其中ai或者是原子或者是一個廣義表。 GList = a1,a2,an | aiAtomSet或aiGList 原子結(jié)點(diǎn) 子表結(jié)點(diǎn) 2022/7/24例如: A = ( ) B = (a, b, c) C = (a, (b, c, d), e) D = (a, b), c, (d, (e, f), g) ) E = (a, ( ), ( ), ( ), b) L=(a, (a, b), (a, (a, b), c), ( ) 注意：（ ）、 （）是不同的。 線性表是廣義表的特殊情況。 2022

2、/7/24 遞歸表：允許遞歸的表。 表的長度: 表中直接元素的個數(shù). 表的深度： 表中嵌套的最大層次數(shù)。 表頭: 第一個元素. 表尾: 除表頭外剩下部分組成的廣義表例如:A表的表頭是( )，表尾是( )；B表的表頭是a，表尾是(b, c)；C表的表頭是a，表尾是( (b, c, d), e)；D表的表頭是(a b)，表尾是(c, (d, (e, f), g) )；E表的表頭是a，表尾是( ( ), ( ), ( ), b)。2022/7/24 例: X = ( e ) Y = (a, (b, c, d) Z = (X, Y) R = (a, R) S = ( ( ) ) 請指出它們的深度、表頭

3、、表尾。 2022/7/24廣義表的基本操作 構(gòu)造一個廣義表 釋放廣義表空間 遍歷廣義表 復(fù)制廣義表 求廣義表的長度 求廣義表的深度 求廣義表的表頭 求廣義表的表尾2022/7/246.2 廣義表的存儲結(jié)構(gòu)1. 基本思想： 使用鏈?zhǔn)酱鎯Y(jié)構(gòu)（順序難以表達(dá)數(shù)據(jù)元素的層次關(guān)系） 結(jié)點(diǎn)結(jié)構(gòu)typeData/sublistnext2022/7/242. 類型定義:enum GListNodeType ATOM, LIST ;template struct GListNode GListNodeType type; union T data; GListNode *sublist; ; GListNod

4、e * next; ;2022/7/24舉例: 約定廣義表結(jié)構(gòu)有“頭結(jié)點(diǎn)” 頭結(jié)點(diǎn)的type域值取LIST 2022/7/242022/7/24template class GList GListNode *head;public: GList(); GList(GList head, GList tail); / 利用表頭、表尾構(gòu)造對象 GList(GList &gl); GList( ); void Traverse( ); / 遍歷算法 int Length( ); / 計(jì)算表的長度 int Depth( ); / 計(jì)算表的深度 ; 2022/7/24 6.3 廣義表的基本操作算法 1.

5、 構(gòu)造函數(shù) 2022/7/24template GList:GList(GList head, GList tail) head=new GListNode; / 創(chuàng)建表頭結(jié)點(diǎn) head-type=LIST; head-next=NULL; / 將表頭的頭結(jié)點(diǎn)作為第一個數(shù)據(jù)結(jié)點(diǎn) head-sublist= head.head; / 將表尾第一個數(shù)據(jù)結(jié)點(diǎn)作為第二個數(shù)據(jù)結(jié)點(diǎn) head.head-next = tail.head-sublist; delete tail.head; / 釋放表尾的頭結(jié)點(diǎn) head.head=tail.head=NULL; 2022/7/242. 遍歷廣義表(遞歸)t

6、emplate void GList:Traverse(GListNode *p) cout sublist; p; p=p-next) if (p-type=ATOM) cout data ; else Traverse(p); cout ); template void GList:Traverse( ) Traverse(head ); 2022/7/243復(fù)制廣義表 (遞歸)template GListNode *GList:Copy(GListNode* p) head=new GListNode; / 創(chuàng)建頭結(jié)點(diǎn) head-type=LIST; head-next=head-sub

7、list=NULL; / 復(fù)制原子結(jié)點(diǎn)、子表結(jié)點(diǎn)及其子表 for (p=p-sublist; p; p=p-next) newp=new GListNode; newp-type = p-type; if (p-type=ATOM) newp-data =p-data; else newp-sublist=Copy(p); / 復(fù)制子表結(jié)點(diǎn)及其子表 if (head-sublist=NULL) head-sublist=tail=newp; else tail-next=newp; tail=newp; 2022/7/24 tail-next=NULL; return head;templat

8、e GList:GList(GList &gl) head = Copy(gl.head); 2022/7/244求廣義表的長度template int GList:Length() n=0; for (p=head-sublist; p; p=p-next) n+; return n;2022/7/245. 求廣義表的深度算法(遞歸)depth(p)的遞歸定義為:1）遞歸終止條件： 當(dāng)*p為原子時，depth(p)=0, 2）遞歸規(guī)律： depth(p) =1+ Max depth(ai)2022/7/24 template int GList:Depth(GListNode *p) if

9、(p-type=ATOM) return 0; maxdepth=0; for (q=p-sublist; q; q=q-next) depth=Depth(q); if (depthmaxdepth) maxdepth=depth; return maxdepth+1;2022/7/24template int GList:Depth() return Depth(head); 2022/7/246. 廣義表的析構(gòu)算法 (遞歸) template void GList:Free(GListNode *p) if (p=NULL) return; q=p; / q指向待釋放結(jié)點(diǎn) p=p-sublist; / p指向第一個結(jié)點(diǎn) delete q; 2022/7/24while( p ) q=p; / q指向待釋放結(jié)點(diǎn) p=p-next; / p指向下一個結(jié)點(diǎn) if (q-type=ATOM) de