數(shù)組和廣義表2009級(jí)

1、 5.3.1 廣義表的概念 5.3.2 廣義表的存儲(chǔ)和實(shí)現(xiàn) 5.3.3 廣義表的基本操作算法 5.3 廣義表 5.3.1 廣義表的概念廣義表是數(shù)據(jù)元素的有限序列。 記作： LS= (1,2 n)。其中，LS為廣義表的名字, i 為表中元素, i可以是單個(gè)元素，也可以是廣義表。在線性表中數(shù)據(jù)元素類型相同，在廣義表中， 元素可以為不可再分割的單個(gè)元素, 稱為原子(atom),也可以是廣義表，稱為子表元素(sublist)廣義表的定義是一個(gè)遞歸定義，因?yàn)樵诙x廣義表又用到了廣義表；5.3.1 廣義表的概念 A=( ) 空表 B=(b,c,d) C=(a, (b,c,d) D=(A, B, C)=()

2、, (b,c,d), (a,(b,c,d) E=(a, E) 例5.3.1 廣義表的概念廣義表的術(shù)語(yǔ)表頭：LS的第一個(gè)元素稱為表頭表尾：其余元素組成的表稱為L(zhǎng)S的表尾表長(zhǎng)：最外層包含元素個(gè)數(shù) 深度：所含括弧的重?cái)?shù)。原子的深度為 0，“空表”的深度為 1。LS = ( 1, 2, , n )表頭head表名表尾tail表長(zhǎng) n 例 A = ( ) 空表 B = (b,c,d) C = (a,B)=(a,(b,c,d) D = (A,B,C) = (), (b,c,d), (a,(b,c,d) E = (a,E)=(a,(a,E)表長(zhǎng) 0, 深度 1表長(zhǎng) 3，深度 1表長(zhǎng) 2，深度 2 表長(zhǎng) 3，

3、深度 3 表長(zhǎng)：2, 深度：無(wú)窮 例 A=（） B = (b,c,d) C = (a,(b,c,d) D = (A,B,C)表頭 無(wú) 表尾( )表頭 b 表尾 (c,d )表頭 a 表尾 (b,c,d)表頭 A 表尾 (B,C)廣義表： 表頭+表尾 廣義表 L= (1, 2 n) 表頭: 1 表尾: (2 , ,n) 廣義表 L= (1, 2 n) 子表: 1 2 3 n 廣義表(1, 2 n)的兩種分解方法：廣義表：子表1 +子表2 + + 子表n 5.3.1 廣義表的概念5.3.1 廣義表的概念 例 C = (a,(b,c,d) D=（A,B,C) = ( ), (b,c,d), (a,(

4、b,c,d) E= (a, E)廣義表特點(diǎn)有次序有長(zhǎng)度有深度可遞歸可共享一個(gè)直接前驅(qū)和一個(gè)直接后繼表中元素個(gè)數(shù)表中括號(hào)的重?cái)?shù)自己可以作為自己的子表可以為其他廣義表所共享 z-(x+y) r=z Bike=(Frame, FrontWheel,RearWheel,GearShift,FootPedal)廣義表的應(yīng)用人工智能 函數(shù)調(diào)用關(guān)系實(shí)體對(duì)象 lisp (=, r,z) (minus,z, (Plus,x,y) M=(A,B,C) A=(a1,a2,a3), B=(b1,b2) C=( ) Frame=(grips,brake,fork,mailframe) FrontWheel=(WRim,

5、Hub,Bearing)P(x,y,z)=x10y3z2+2x6y3z2+3x5y2z2+x4y4z+6x3y4z+2yz+15 P(x,y,z)=(x10+2x6)y3+3x5y2)z2+(x4+6x3)y4+2y)z+15P(x,y,z)= Az2+Bz+15 P=z(A,2),(B,1),(15,0)A(x,y)=(x10+2x6)y3+3x5y2=Cy3+Dy2 A=y(C,3),(D,2)B(x,y)= (x4+6x3)y4+2y=Ey4+Fy B=y(E,4),(F,1)C(x)= x10+2x6 C=x(1,10),(2,6)D(x)= 3x5 D=x(3,5)E(x)= x4+

6、6x3 E=x(1,4),(6,3)F(x)= 2 F=x(2,0)M元多項(xiàng)式P(x,y,z)的 廣義表表示為P=z(y(x(1,10),(2,6),3),( x(3,5),2),2),( y(x(1,4),(6,3),4),( x(2,0),1),1),(15,0) M元多項(xiàng)式的廣義表表示 InitGList(&L) CreateGList(&L,S) DestroyGList(&L) CopyGList(&T.L) GListLength(L) GListDepth(L) GListEmpty(L) GetHead(L) GetTail(L) InsertFirst_GL(&L,e) De

7、leteFirst_GL(&L,&e) GLTraverse_GL(L,visit()廣義表的基本操作LS= (1,2 n)。5.3.2 廣義表的存儲(chǔ)廣義表的存儲(chǔ)頭尾指針的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)0原子結(jié)點(diǎn)元素 表結(jié)點(diǎn)1表頭結(jié)點(diǎn)表尾結(jié)點(diǎn) 廣義表中的數(shù)據(jù)元素可能為原子或廣義表，由此需要兩種結(jié)點(diǎn)： 表結(jié)點(diǎn)：存儲(chǔ)廣義表； 原子結(jié)點(diǎn)：存儲(chǔ)原子元素。typedef enum ATOM,LISTElemTag; /ATOM=0:原子,LIST=1: 列表typedef struct GLNode ElemTag tag; /標(biāo)志域 union AtomType atom; /原子結(jié)點(diǎn)的值域 struct struct

8、 GLNode *hp,*tp;ptr; /表結(jié)點(diǎn)的指針域：ptr.hp指向表頭， ptr.tp指向表尾 *GList;0 tag atom原子結(jié)點(diǎn)表結(jié)點(diǎn)tag ptr1 hp tp頭尾鏈表的類型定義A=NULL A=（） B = (b,c,d) C = (a,(b,c,d) Bbcd1110b0c0d(c,d)(d)(b,c,d)a(b,c,d)(b,c,d)b(c,d)c(d)d( )C11110a0b0c0d( )1(a,(b,c,d)廣義表： 表頭+表尾 廣義表 L= (1, 2 n) 表頭: 1 表尾: (2 , ,n) 廣義表 L= (1, 2 n) 子表: 1 2 3 n 廣義表

9、(1, 2 n)的兩種分解方法：廣義表：子表1 +子表2 + + 子表n 5.3.2 廣義表的存儲(chǔ)5.3.2 廣義表的存儲(chǔ)表頭、表尾構(gòu)造法 1 (2, , n) 表結(jié)點(diǎn)tag=1 指向表頭的指針指向表尾的指針原子空表 L=NULLtag=0 atom1 L0 a 1 1 1 1 1 1 L = (a , ( b, c ) , ( ( d ) ) )a(b, c), (d) (b,c)b(c)c(d)(d) (d) d例0 b 0 c 0 d ( )( )( )( )5.3.2 廣義表的存儲(chǔ)子表構(gòu)造法 1 2, , n 1 原子空表 L=NULL非空表 1 指向子表1 的指針tag=0 atom

10、 1 指向子表2 的指針指向子表n 的指針L例 a ( b, c ) ( d ) L=( a , ( b ,c ) , ( d ) )1 L1 1 1 1 b c ( d ) 1 1 d 0 a 0 b 0 c 0 d L=( a , ( b ,c) , ( d ) )的頭尾鏈表存儲(chǔ)結(jié)構(gòu) 5.3.3 廣義表的基本操作的算法1 L1 1 1 1 1 0 d 1 0 c 0 b 0 a n1 n!=n*(n-1)! 遞歸終止條件, 遞歸終止時(shí)問(wèn)題的求解；遞歸算法的設(shè)計(jì)遞歸算法基本設(shè)計(jì)思想 例 求解n!的遞歸算法 將問(wèn)題求解分解為與原問(wèn)題性質(zhì)相同,但 規(guī)模較小問(wèn)題的求解； n=1 n!=1 遞歸項(xiàng)：

11、 終止項(xiàng)：遞歸項(xiàng)：終止項(xiàng)：遞歸算法的設(shè)計(jì)例 求解n!的遞歸算法 int fact(int n) /求解并返回 n! if(n=1) return(1) ; else return(n*fact(n-1); n=1 n!=1 遞歸項(xiàng)： 終止項(xiàng)： n1 n!=n*(n-1)!5.3.3 廣義表的基本操作的算法廣義表： 表頭+表尾 廣義表 L= (1, 2 n) 表頭: 1 表尾: (2 , ,n) 廣義表 L= (1, 2 n) 子表: 1 2 3 n 廣義表(1, 2 n)的兩種分解方法：廣義表：子表1 +子表2 + + 子表n 復(fù)制廣義表 CopyGList(T,L)1 L1 1 1 1 1

12、0 d 1 0 c 0 b 0 a L=( a , ( b ,c ) , ( d ) )表頭表尾a( ( b ,c ) , ( d ) ) 復(fù)制廣義表的遞歸求解： 基本項(xiàng)： L 為空表，T=NULL; L 為原子結(jié)點(diǎn),復(fù)制原子結(jié)點(diǎn); 遞歸項(xiàng)： L 為非空表，建立表結(jié)點(diǎn), 復(fù)制表頭, 復(fù)制表尾，新的廣義表由新的表結(jié)點(diǎn) 和表頭和表尾連接而成;復(fù)制廣義表 CopyGList(T,L) void GListCopy(GList &T,GList L) /采用頭尾鏈表存儲(chǔ)結(jié)構(gòu)，由廣義表L復(fù)制得到廣義表T if (!L) T=NULL; /復(fù)制空表 else T=(GList)malloc(sizeof(

13、GLNode); /建表結(jié)點(diǎn)T-tag=L-tag;if (L-tag=ATOM) T-data=L-data;elseGListCopy(T-ptr.hp,L-ptr.hp);GListCopy(T-ptr.tp, L-ptr.tp); 求廣義表的深度GListDepth(L)廣義表L的深度=廣義表L中括號(hào)重?cái)?shù)GListDepth(L)=1+MAX(GListDepth(L的元素 ) GListDepth(L) 例 L=( a , ( b ,c ) , ( ( d ) ) ) GListDepth(b,c) GListDepth(a) GListDepth( (d) ) =0=1=2=3GL

14、istDepth(L)的遞歸求解： 基本項(xiàng): L為空表，GListDepth(L)=1; L 為原子，GListDepth(L)=0; 遞歸項(xiàng): L 為非空表，GListDepth(L)=1+max(GListDepth(L的元素 );求廣義表的深度GListDepth(L)( ( d ) ) L=( a , ( b ,c ) , ( ( d ) ) ) 的深度1 L1 1 1 1 1 0 d 1 0 c 0 b 0 a ( b ,c )ahp tp int GListDepth(GList L) /采用頭尾鏈表存儲(chǔ)結(jié)構(gòu)，求廣義表L的深度。 if (!L) return 1; /空表 if (

15、L-tag=ATOM) return 0; for (max=0,pp=L;pp;pp=pp-ptr.tp) dep=GListDepth(pp-ptr.hp); if (depmax) max=dep; return max+1;建立廣義表輸入：字符串 (1, 2, , n )結(jié)果: 建立廣義表的頭尾鏈表遞歸項(xiàng)：將廣義表分解成n個(gè)子表1, 2, , n ，依次建立1, 2, , n 對(duì)應(yīng)的表結(jié)點(diǎn)和子表,并將將建立子表表結(jié)點(diǎn)插入表尾。終止項(xiàng) 空表: L=NULL 原子: 建立原子結(jié)點(diǎn)子表和廣義表的關(guān)系相鄰兩個(gè)子表之間的關(guān)系( ( d ) )1 L1 1 1 1 1 0 d 1 0 c 0 b

16、0 a ( b ,c )a子表L=( a , ( b ,c ) , ( ( d ) ) ) 1 指向子表1的指針 1 指向子表2的指針 1 指向子表n的指針L子表和廣義表的關(guān)系相鄰兩個(gè)子表之間的關(guān)系void CreateGList(GList &L, char str) /建立str對(duì)應(yīng)廣義表L if(strcmp(str,()=0)L=NULL;/空表 else if(strlen(str)=1) /建原子結(jié)點(diǎn) L=(GList)malloc(sizeof(GLNode); L-tag=ATOM; L-atom=str0; else/非空廣義表，建表結(jié)點(diǎn) L=(GList)malloc(sizeof(GLNode);/表結(jié)點(diǎn) L-tag=LIST; p=L; SubString(sub,str,2,strlen(str)-2);/脫外層括號(hào) 由sub中所含n個(gè)子表建立n個(gè)子表; /if /if /CreateGList do /由sub中所含n個(gè)子串建立n個(gè)子表 sever(sub,hsub); /*hsub為最外層第一個(gè),之前的 子串,sub為第一個(gè),之后的子串*/ CreateGList(p-ptr.hp,hsub);/建hsub對(duì)應(yīng)的子表 if(!strempty(sub) /建下一個(gè)子表的表結(jié)點(diǎn) p-ptr.tp =(GList)malloc(sizeof(GLN