五章數(shù)組和廣義表ppt課件

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

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

3、3 廣義表的存儲構(gòu)造廣義表的存儲構(gòu)造 廣義表中的數(shù)據(jù)元素可以是單元素，或是廣義表，很難用順序存儲構(gòu)造表示，常采用鏈?zhǔn)酱鎯?gòu)造。 1.表頭表尾鏈存儲構(gòu)造 有兩類結(jié)點(diǎn)：表結(jié)點(diǎn)和單元素結(jié)點(diǎn)。 tag=1 hp tp 表結(jié)點(diǎn) tag=0 data 單元素結(jié)點(diǎn) tag標(biāo)志域，0表示結(jié)點(diǎn)為單元素結(jié)點(diǎn)，1表示為表結(jié)點(diǎn)；hp：表頭指針域； tp：表尾指針域； data： 值域。5.3 5.3 廣義表的存儲構(gòu)造廣義表的存儲構(gòu)造方式描畫為：方式描畫為： 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 廣義表的存儲構(gòu)造廣義表的存儲構(gòu)造這種存儲構(gòu)造的特點(diǎn)是：這種存儲構(gòu)造的特點(diǎn)是：最上層的表結(jié)點(diǎn)數(shù)即為廣義表的長度；最上層的表結(jié)點(diǎn)數(shù)即為廣義表的長度； 層次清楚；層次清楚；表結(jié)點(diǎn)數(shù)目多，與廣義表中括號對的數(shù)目不匹配。表結(jié)點(diǎn)數(shù)目多，與廣義表中括號對的數(shù)目不匹配。 5.3 5.3 廣義表的存儲構(gòu)造廣義表的存儲構(gòu)造2. 2. 同層結(jié)點(diǎn)鏈存儲構(gòu)造同層結(jié)點(diǎn)鏈存儲構(gòu)造 有兩類結(jié)點(diǎn)：表

5、結(jié)點(diǎn)和單元素結(jié)點(diǎn)。有兩類結(jié)點(diǎn)：表結(jié)點(diǎn)和單元素結(jié)點(diǎn)。 tag=1 hp tp tag=1 hp tp 表結(jié)點(diǎn)表結(jié)點(diǎn) tag=0 data tp tag=0 data tp 單元素結(jié)點(diǎn)單元素結(jié)點(diǎn) tp tp為鏈接同層下一結(jié)點(diǎn)的指針域，其它域的含義為鏈接同層下一結(jié)點(diǎn)的指針域，其它域的含義同表頭表尾鏈構(gòu)造。同表頭表尾鏈構(gòu)造。5.3 5.3 廣義表的存儲構(gòu)造廣義表的存儲構(gòu)造同層結(jié)點(diǎn)鏈構(gòu)造的特點(diǎn)是：同層結(jié)點(diǎn)鏈構(gòu)造的特點(diǎn)是：表結(jié)點(diǎn)的數(shù)目與廣義表的括號對數(shù)目一致；表結(jié)點(diǎn)的數(shù)目與廣義表的括號對數(shù)目一致；寫遞歸算法不方便。寫遞歸算法不方便。例例: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)三類表結(jié)點(diǎn)三類表結(jié)點(diǎn)(tag=1): 整個(gè)表的