[教育學]第五章數(shù)組與廣義表-資料下載頁
2025-10-05 11:12本頁面
【正文】 、廣義表表示 （ 1）廣義表常用表示 （ 2）廣義表的深度 （ 1）廣義表常用表示 ? ① E=() E是一個空表，其長度為 0。 ② L=(a， b) L是長度為 2的廣義表，它的兩個元素都是原子，因此它是一個線性表 ③ A=(x， L)=(x， (a， b)) A是長度為 2的廣義表，第一個元素是原子 x，第二個元素是子表 L。 ④ B=(A， y)=((x， (a， b))， y) B是長度為 2的廣義表，第一個元素是子表 A，第二個元素是原子 y。 廣義表示（ 2） ? ⑤ C=(A， B)=((x， (a， b))， ((x， (a， b))，y)) C的長度為 2，兩個元素都是子表。 ⑥ D=(a， D)=(a， (a， (a， (…)))) D的長度為 2，第一個元素是原子，第二個元素是 D自身，展開后它是一個無限的廣義表。 （ 2）廣義表的深度 一個表的 深度 是指表展開后所含括號的層數(shù)。 【例】表 L、 A、 B、 C的深度為分別為 4，表 D的深度為 ∞。 （ 3）帶名字的廣義表表示 ? 如果規(guī)定任何表都是有名字的，為了既表明每個表的名字，又說明它的組成，則可以在每個表的前面冠以該表的名字，于是上例中的各表又可以寫成： ① E() ② L(a， b) ③ A(x， L(a， b)) ④ B(A(x， L(a， b))， y) ⑤ C(A(x， l(a， b))， B(A(x， L(a， b))， y)) ⑥ D(a， D(a， D(…))) （ 4）廣義表的圖形表示 （ a） 廣義表的圖形表示： ①圖中的分支結點對應廣義表 ②非分支結點一般是原子 ③但空表對應的也是非分支結點。 【例】下圖給出了幾個廣義表的圖形表示。 （ b） 廣義表的圖形形狀劃分 ①與樹對應的廣義表稱為純表，它限制了表中成分的共享和遞歸 ②允許結點共享的表稱再入表 ③允許遞歸的表稱為遞歸表 （ 5）遞歸表、再人表、純表、線性表之間的關系滿足 ? 廣義表不僅是線性表的推廣，也是樹的推廣。 廣義表運算 ? 由于廣義表是對線性表和樹的推廣，并且具有共享和遞歸特性的廣義表可以和有向圖 (見第 7章 )建立對應，因此廣義表的大部分運算與這些數(shù)據(jù)結構上的運算類似。 在此，只討論廣義表的兩個特殊的基本運算：取表頭 head(Ls)和取表尾 tail(Ls)。 根據(jù)表頭、表尾的定義可知：任何一個非空廣義表的表頭是表中第一個元素，它可以是原子，也可以是子表，而其表尾必定是子表。 【例】 ? head(L)=a， tail(L)=(b) head(B)=A， tail(B)=(y) 由于 tail(L)是非空表，可繼續(xù)分解得到： head(tail(L))=b， tail(tail(L))=() 對非空表 A和 (y)， 也可繼續(xù)分解。 注意 : 廣義表 ()和 (())不同。前者是長度為 0的空表，對其不能做求表頭和表尾的運算；而后者是長度為 l的非空表 (只不過該表中惟一的一個元素是空表 )，對其可進行分解，得到的表頭和表尾均是空表 ()。 5
教學課件相關推薦
鄂ICP備17016276號-1