大學(xué)《數(shù)據(jù)結(jié)構(gòu)》第四章：多維數(shù)組和廣義表-第三節(jié)-廣義表基礎(chǔ)

1、第三節(jié)廣義表基礎(chǔ)一、廣義表的定義廣義表是線性表的推廣。即廣義表中放松對(duì)表元素的原子限制，容 許它們具有其自身結(jié)構(gòu)。1、廣義表定義廣義表是n(n20)個(gè)元素al , a2 , . , ai，an的有限序列。其中：ai-或者是原子或者是一個(gè)廣義表。廣義表通常記作：Ls=( al , a2 , . , ai , . , an)0Ls是廣義表的名字，n為它的長(zhǎng)度。假設(shè)ai是廣義表，那么稱它為L(zhǎng)s的子表。一個(gè)表展開(kāi)后所含括號(hào)的層數(shù)稱為廣義表的深度注意：廣義表通常用圓括號(hào)括起來(lái)，用逗號(hào)分隔其中的元素。為了區(qū)分原子和廣義表，書(shū)寫(xiě)時(shí)用大寫(xiě)字母表示廣義表，用小寫(xiě) 字母表示原子。假設(shè)廣義表Ls非空(nl),那么a

2、l是LS的表頭(head),其余元素組 成的表(al, a2 ，,an)稱為L(zhǎng)s的表尾(tail)。廣義表是遞歸定義的【例】(1)A=()-A是一個(gè)空表，其長(zhǎng)度為零，深度為10(2)B=(a)-B是一個(gè)只有一個(gè)原子的廣義表，其長(zhǎng)度為1 ,深度為lo(3)C=(a , (b , c)-C是一個(gè)長(zhǎng)度為2的廣義表，第一個(gè)元素是原 子，第二個(gè)元素是子表，深度為2。(4)D=(A , B , C)=() , (a) , (a , (b , c)-D 是一個(gè)長(zhǎng)度為 3 的廣 義表，其中三個(gè)元素均為子表，深度為3。(5)E=(C , d)=(a , (b , c) , d)-E是一個(gè)長(zhǎng)度為2的廣義表,第一

3、個(gè)元素是子表，第二個(gè)元素是原子，深度為30(6)F=(e , F)=(e , (e , (e ,.)-F是一個(gè)遞歸的表,它的長(zhǎng)度為2,第一個(gè)元素是原子，第二個(gè)元素是表自身，展開(kāi)后它是一個(gè)無(wú)限的 廣義表,深度為8。2、廣義表的幾個(gè)重要性質(zhì)：(1 )廣義表的元素可以是子表，而子表又可以含有子表，因此廣 義表是一個(gè)多層次結(jié)構(gòu)的表，它可以用圖來(lái)形象地表示。=(0, (a), (a, (b, c)Ao=(0, (a), (a, (b, c)A=()(2)廣義表具有遞歸和共享的性質(zhì)，例如，表F就是一個(gè)遞歸的 廣義表，D表是共享的表，在表D中可以不必列出子表的值，而是通 過(guò)子表的名字來(lái)引用。二、廣義表的基本

4、運(yùn)算廣義表是對(duì)線性表和樹(shù)的推廣，廣義表的大局部運(yùn)算與這些數(shù)據(jù)結(jié)構(gòu)上的運(yùn)算類似。 在此，只討論廣義表的兩個(gè)特殊的基本運(yùn)算： 取表頭head(Ls)和取表尾tail(Ls)。任何一個(gè)非空的廣義表其表頭可能 是原子,也可能是子表,而其表尾一定是子表?！纠坑幸韵碌膹V義表，試求出下面廣義表的表頭head。、表 尾 tail。、表長(zhǎng) length。和深度 depth()0(1) A=(a , (b , c , d) , e , (f, g) ;( 2 ) B=(a);(3 ) C=(y , (z , w) , (x , (z , w) , a) ; (4) D=(x , (y) , B),D)o隱藏答案

5、【解答】(1) head(A)=a , tail(A)=(b , c , d) , e , (f, g), length(A)=4 , depth(A)=2 ;(2 ) head(B) = (a) , tail(B)=() , length(B) = l , depth(B)=2 ;(3 ) head(C)=y , tail(C) = (z , w) , (x , (z , w) , a)length(C)=3 , depth(C) = 3 ;(4 ) head(D)=x , tail(D)=(y) , B) , D) , length(D)=3 , depth(D)=ooo【例】取出廣義表A

6、=(x , y , z) , (a , b , c , d)中原子b的函數(shù)是 o隱藏答案【解析】要從廣義表A中取出原子b ,需要先對(duì)A取尾運(yùn)算: tail(A)= (a , b , c , d) z然后再對(duì)tai I (A)結(jié)果進(jìn)行取表頭運(yùn)算head(tail(A)= ( a , b , c , d ),然后再對(duì)結(jié)果進(jìn)行取表尾運(yùn)算tail (head (tai I (A) = ( b , c , d ),最后再進(jìn)行取表頭運(yùn)算tail (head(tail(A) = bo【答案】tail( head(tail(A)真題選解(例題填空題)1、廣義表如下：A=(B,y) B = (x , L) L=

7、(a , b)要求：(1)寫(xiě)出以下操作的結(jié)果tail(A)=.head(B)=。(2)請(qǐng)畫(huà)出廣義表A對(duì)應(yīng)的圖形表示。隱藏答案【答案】(1) (y) x【解析】根據(jù)head ()運(yùn)算和tail ()運(yùn)算的規(guī)那么很容易計(jì)算第(1)問(wèn)，tail(A)= tail(B,y)= ( y ) , head(B)= head(x , L)=xo 第(2 )問(wèn)畫(huà)出廣義表A對(duì)應(yīng)的圖形表示，方法見(jiàn)前面講解。(例題填空題)2、廣義表C=(a , (b , c) , d),那么：tail(head(tail(C)=o隱藏答案【解析】tail(head(tail(C)=tail(head(tail(a , (b , c

8、) , d) = tail(head (b , c), d) = tail(b , c)=(c)【答案】(c)三、廣義表的存儲(chǔ)結(jié)構(gòu)1、結(jié)點(diǎn)結(jié)構(gòu)tagdata slinklink說(shuō)明：(1) tag標(biāo)志位,tag = l ,該結(jié)點(diǎn)是子表，第二個(gè)域?yàn)?slink,用以存放子表的地址；當(dāng)tag=0時(shí)，該結(jié)點(diǎn)是原子結(jié)點(diǎn)，第二 個(gè)域?yàn)閐ata ,用以存放元素值。(2 ) link域是用來(lái)存放與本元素同一層的下一個(gè)元素對(duì)應(yīng)結(jié)點(diǎn)的 地址，當(dāng)該元素是所在層的最后一個(gè)元素時(shí)，link的值為NULLO【例】A=() A=NULLE=(a)C= (a, (b, c)D=(A B, C)= (), (a) 9 (a, (b c)運(yùn)算的實(shí)現(xiàn)考試大綱沒(méi)做要求，不講。當(dāng)前講授本章小結(jié)前兩章討論的線性表、棧和隊(duì)列都是典型的線性結(jié)構(gòu)，結(jié)構(gòu)中數(shù)據(jù) 元素都是不能分解的非結(jié)構(gòu)的原子類型。它們的邏輯特征是：每個(gè)數(shù) 據(jù)元素至多有一個(gè)直接前趨和直接后續(xù)。而多維數(shù)組和廣義表是一種 復(fù)雜的非線性結(jié)構(gòu)，它們的邏輯特征是：一個(gè)數(shù)據(jù)元素可能有多個(gè)直 接前趨和直接后繼。多維數(shù)組可以看成是線性表的推廣。因?yàn)橐坏┐_定數(shù)組是按行或按 列優(yōu)先順序存儲(chǔ)之后，每個(gè)數(shù)組元素之間的關(guān)系就同一維數(shù)