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

1、第八章廣義表8.1 廣義表的類型定義ADT Glist 數(shù)據(jù)對象：Dei | i=1,2,.,n; n0; eiAtomSet 或 eiGList, AtomSet為某個數(shù)據(jù)對象 數(shù)據(jù)關(guān)系： LR| ei-1 ,eiD, 2in ADT Glist基本操作:廣義表是遞歸定義的線性結(jié)構(gòu)， LS = ( 1, 2, , n )其中：i 或為原子 或為廣義表例如: A = ( ) F = (d, (e) D = (a,(b,c), F) C = (A, D, F) B = (a, B) = (a, (a, (a, , ) ) )廣義表是一個多層次的線性結(jié)構(gòu)例如：D=(E, F)其中: E=(a, (

2、b, c) F=(d, (e)DEFa( )d( )bce廣義表 LS = ( 1, 2, , n )的結(jié)構(gòu)特點:1) 廣義表中的數(shù)據(jù)元素有相對次序；2) 廣義表的長度定義為最外層包含元素個數(shù)；3) 廣義表的深度定義為所含括弧的重數(shù)； 注意：“原子”的深度為 0 “空表”的深度為 1 4) 廣義表可以共享；5) 廣義表可以是一個遞歸的表。 遞歸表的深度是無窮值，長度是有限值。6) 任何一個非空廣義表 LS = ( 1, 2, , n) 均可分解為 表頭 Head(LS) = 1 和 表尾 Tail(LS) = ( 2, , n) 兩部分。例如: D = ( E, F ) = (a, (b, c

3、)，F(xiàn) )Head( D ) = E Tail( D ) = ( F )Head( E ) = a Tail( E ) = ( ( b, c) )Head( ( b, c) ) = ( b, c) Tail( ( b, c) ) = ( )Head( ( b, c) ) = b Tail( ( b, c) ) = ( c )Head( ( c ) ) = c Tail( ( c ) ) = ( ) 結(jié)構(gòu)的創(chuàng)建和銷毀 InitGList(&L); DestroyGList(&L); CreateGList(&L, S); CopyGList(&T, L);基本操作 狀態(tài)函數(shù) GListLengt

4、h(L); GListDepth(L); GListEmpty(L); GetHead(L); GetTail(L); 插入和刪除操作 InsertFirst_GL(&L, e); DeleteFirst_GL(&L, &e); 遍歷 Traverse_GL(L, Visit();8.2 廣義表的表示方法通常采用頭、尾指針的鏈表結(jié)構(gòu)表結(jié)點:原子結(jié)點：tag=1 hp tptag=0 data1) 表頭、表尾分析法：構(gòu)造存儲結(jié)構(gòu)的兩種分析方法:若表頭為原子，則為空表 ls=NIL非空表 lstag=1 指向表頭的指針指向表尾的指針tag=0 data否則，依次類推。L = ( a, ( x, y

5、 ), ( ( x ) ) )a( x, y )( ) 1 LL = ( )0 a 1 1 1 1 1 0 x ( )x2) 子表分析法：若子表為原子，則為空表 ls=NIL非空表 1 指向子表1 的指針tag=0 data否則，依次類推。 1 指向子表2 的指針 1 指向子表n 的指針ls例如: a (x, y) (x) LS=( a, (x,y), (x) )ls廣義表的頭尾鏈表存儲表示：typedef enum ATOM, LIST ElemTag; / ATOM=0:原子, LIST=1:子表typedef struct GLNode ElemTag tag; / 標(biāo)志域 union

6、AtomType atom; / 原子結(jié)點的數(shù)據(jù)域 struct struct GLNode *hp, *tp; ptr; ; *GListtag=1 hp tpptr表結(jié)點例一 求廣義表的深度例二 復(fù)制廣義表例三 創(chuàng)建廣義表的存儲結(jié)構(gòu)廣義表的深度=Max 子表的深度 +1例一 求廣義表的深度可以直接求解的兩種簡單情況為： 空表的深度 = 1 原子的深度 = 0 將廣義表分解成 n 個子表，分別(遞歸)求得每個子表的深度， int GlistDepth(Glist L) / 返回指針L所指的廣義表的深度 for (max=0, pp=L; pp; pp=pp-ptr.tp) dep = Gli

7、stDepth(pp-ptr.hp); if (dep max) max = dep; return max + 1; / GlistDepthif (!L) return 1; if (L-tag = ATOM) return 0; 1 1 1 Lfor (max=0, pp=L; pp; pp=pp-ptr.tp) dep = GlistDepth(pp-ptr.hp); if (dep max) max = dep; 例如:pppp-ptr.hppppppp-ptr.hppp-ptr.hp例二 復(fù)制廣義表新的廣義表由新的表頭和表尾構(gòu)成?？梢灾苯忧蠼獾膬煞N簡單情況為： 空表復(fù)制求得的新表自

8、然也是空表; 原子結(jié)點可以直接復(fù)制求得。 將廣義表分解成表頭和表尾兩部分，分別(遞歸)復(fù)制求得新的表頭和表尾，若 ls= NIL 則 newls = NIL否則 構(gòu)造結(jié)點 newls, 由 表頭ls-ptr.hp 復(fù)制得 newhp 由 表尾 ls-ptr.tp 復(fù)制得 newtp 并使 newls-ptr.hp = newhp, newls-ptr.tp = newtp復(fù)制求廣義表的算法描述如下:Status CopyGList(Glist &T, Glist L) if (!L) T = NULL; / 復(fù)制空表 else if ( !(T = (Glist)malloc(sizeof(G

9、LNode) ) exit(OVERFLOW); / 建表結(jié)點 T-tag = L-tag; if (L-tag = ATOM) T-atom = L-atom; / 復(fù)制單原子結(jié)點 else / else return OK; / CopyGList分別復(fù)制表頭和表尾CopyGList(T-ptr.hp, L-ptr.hp); / 復(fù)制求得表頭T-ptr.hp的一個副本L-ptr.hpCopyGList(T-ptr.tp, L-ptr.tp); / 復(fù)制求得表尾T-ptr.tp 的一個副本L-ptr.tp語句 CopyGList(T-ptr.hp, L-ptr.hp);等價于 CopyGLi

10、st(newhp, L-ptr.tp); T-ptr.hp = newhp;例三 創(chuàng)建廣義表的存儲結(jié)構(gòu) 對應(yīng)廣義表的不同定義方法相應(yīng)地有不同的創(chuàng)建存儲結(jié)構(gòu)的算法。 假設(shè)以字符串 S = (1, 2, , n ) 的形式定義廣義表 L，建立相應(yīng)的存儲結(jié)構(gòu)。 由于S中的每個子串i定義 L 的一個子表，從而產(chǎn)生 n 個子問題，即分別由這 n個子串 (遞歸)建立 n 個子表，再組合成一個廣義表。 可以直接求解的兩種簡單情況為：由串( )建立的廣義表是空表；由單字符建立的子表只是一個原子結(jié)點。如何由子表組合成一個廣義表？ 首先分析廣義表和子表在存儲結(jié)構(gòu)中的關(guān)系。先看第一個子表和廣義表的關(guān)系: 1 L指向

11、廣義表的頭指針指向第一個子表的頭指針再看相鄰兩個子表之間的關(guān)系: 1 1 指向第i+1個子表的頭指針指向第i個子表的頭指針可見，兩者之間通過表結(jié)點相鏈接。若 S = ( ) 則 L = NIL；否則，構(gòu)造第一個表結(jié)點 *L， 并從串S中分解出第一個子串1，對應(yīng)創(chuàng)建第一個子廣義表 L-ptr.hp； 若剩余串非空，則構(gòu)造第二個表結(jié)點 L-ptr.tp，并從串S中分解出第二個子串 2，對應(yīng)創(chuàng)建第二個子廣義表 ； 依次類推，直至剩余串為空串止。void CreateGList(Glist &L, String S) if (空串) L = NULL; / 創(chuàng)建空表 else L=(Glist) ma

12、lloc(sizeof(GLNode); L-tag=List; p=L; sub=SubString(S,2,StrLength(S)-1); /脫去串S的外層括弧 / else 由sub中所含n個子串建立n個子表;do sever(sub, hsub); / 分離出子表串hsub=i if (!StrEmpty(sub) p-ptr.tp=(Glist)malloc(sizeof(GLNode); / 建下一個子表的表結(jié)點*(p-ptr.tp) p=p-ptr.tp; while (!StrEmpty(sub);p-ptr.tp = NULL; / 表尾為空表創(chuàng)建由串hsub定義的廣義表p-ptr.hp;if (StrLength(hsub)=1) p-ptr.hp=(GList)malloc(sizeof(GLNode); p-ptr.hp-tag=ATOM; p-ptr.hp-atom