1、第五章第五章 數組和廣義表數組和廣義表5.1 廣義表的定義廣義表的定義5.2 廣義表的根本運算廣義表的根本運算5.3 廣義表的存儲構造廣義表的存儲構造5.1 5.1 數組和廣義表的定義數組和廣義表的定義 廣義表定義廣義表定義 廣義表可定義為：數據元素可以是表的線性表。廣義表可定義為：數據元素可以是表的線性表。 記為：記為：LSLS(d1,d2,dn)(d1,d2,dn) LS LS為表名，為表名， di (i di (i1,2,n)1,2,n)，可以是單元素，可以是單元素( (用小寫字母表示用小寫字母表示) )； 也可以是廣義表也可以是廣義表( (稱為子表，用大寫字母表示稱為子表，用大寫字母表

2、示) )； n n為表的長度，當長度為為表的長度，當長度為0 0時稱為空表；時稱為空表； 稱非空表的第一個元素稱非空表的第一個元素d1d1為表頭，為表頭， 其他元素組成的表其他元素組成的表(d2,dn)(d2,dn)稱為表尾。稱為表尾。5.2 5.2 數組和廣義表的根本運算數組和廣義表的根本運算 數組的根本運算數組的根本運算 給定下標，存取相應的數據元素；給定下標，存取相應的數據元素； 給定下標，修正相應的數據元素；給定下標，修正相應的數據元素； 廣義表的根本運算廣義表的根本運算 取表頭取表頭 HEAD(LS) HEAD(LS)； 取表尾取表尾 TAIL(LS) TAIL(LS)。5.3 5.

3、3 廣義表的存儲構造廣義表的存儲構造 廣義表中的數據元素可以是單元素，或是廣義表，很難用順序存儲構造表示，常采用鏈式存儲構造。 1.表頭表尾鏈存儲構造 有兩類結點：表結點和單元素結點。 tag=1 hp tp 表結點 tag=0 data 單元素結點 tag標志域，0表示結點為單元素結點，1表示為表結點；hp：表頭指針域； tp：表尾指針域； data： 值域。5.3 5.3 廣義表的存儲構造廣義表的存儲構造方式描畫為：方式描畫為： TYPE nodeptr=nodetypeTYPE nodeptr=nodetypenodetype=RECORDnodetype=RECORD tag:0.1

4、tag:0.1 CASE tag OF CASE tag OF 0:(data:elemtp) 0:(data:elemtp) 1:(hp,tp:nodeptr) 1:(hp,tp:nodeptr) END END；5.3 5.3 廣義表的存儲構造廣義表的存儲構造這種存儲構造的特點是：這種存儲構造的特點是：最上層的表結點數即為廣義表的長度；最上層的表結點數即為廣義表的長度； 層次清楚；層次清楚；表結點數目多，與廣義表中括號對的數目不匹配。表結點數目多，與廣義表中括號對的數目不匹配。 5.3 5.3 廣義表的存儲構造廣義表的存儲構造2. 2. 同層結點鏈存儲構造同層結點鏈存儲構造 有兩類結點：表

5、結點和單元素結點。有兩類結點：表結點和單元素結點。 tag=1 hp tp tag=1 hp tp 表結點表結點 tag=0 data tp tag=0 data tp 單元素結點單元素結點 tp tp為鏈接同層下一結點的指針域，其它域的含義為鏈接同層下一結點的指針域，其它域的含義同表頭表尾鏈構造。同表頭表尾鏈構造。5.3 5.3 廣義表的存儲構造廣義表的存儲構造同層結點鏈構造的特點是：同層結點鏈構造的特點是：表結點的數目與廣義表的括號對數目一致；表結點的數目與廣義表的括號對數目一致；寫遞歸算法不方便。寫遞歸算法不方便。例例:P(x,y,z)=:P(x,y,z)=x10y3z2+2x6y3z2

6、+3x5y2z2+x4y4z+6x3y4z+2yz+1x10y3z2+2x6y3z2+3x5y2z2+x4y4z+6x3y4z+2yz+15 5=(x10y3+2x6y3+3x5y2)z2 =(x10y3+2x6y3+3x5y2)z2 +(x4y4+6x3y4+2y)z+15+(x4y4+6x3y4+2y)z+15=(x10+2x6)y3+3x5y2)z2 =(x10+2x6)y3+3x5y2)z2 +(x4+6x3)y4+2y)z+15+(x4+6x3)y4+2y)z+15=Az2+Bz+15z0=Az2+Bz+15z0其中其中: A=Cy3+Dy2 C=x10+2x6 : A=Cy3+Dy2 C=x10+2x6 D=3x5D=3x5可用廣義表表示為可用廣義表表示為: :P(x,y,z)=z(A,2),(B,1),(15,0)P(x,y,z)=z(A,2),(B,1),(15,0)A=y(c,3),(D,2) B=y(E,4),(2,1)A=y(c,3),(D,2) B=y(E,4),(2,1)C=x(1,10),(2,6) E=x(1,4),(6,3) C=x(1,10),(2,6) E=x(1,4),(6,3) D=x(3,5)D=x(3,5)三類表結點三類表結點(tag=1): 整個表的