數(shù)據(jù)結構c語言版第五章課件嚴蔚敏-資料下載頁
2025-08-05 06:29本頁面
【正文】 廣義表的定義（列表） 廣義表是線性表的推廣，是由零個或多個單元素或子表所 組成的有限序列。 LS=(a1,a2,…,a i,…,a n) ai：是單個數(shù)據(jù)元素 ,則 ai是廣義表的 原子 ；如果 ai是一個廣義表 ,則 ai是廣義表的 子表 。 規(guī)定用小寫字母表示原子 ,用大寫字母表示廣義表的 表名。 ? 廣義表與線性表的區(qū)別： 線性表的成份都是結構上不可分的單個數(shù)據(jù)元素，而廣 義表的成份即可以是單元素，也可以是有結構的表，其定義 是遞歸的定義。 廣義表 ?廣義表的長度：廣義表中所含元素的個數(shù)n,n≥0。 ?廣義表的深度：廣義表展開后所含的括號的最大層數(shù)。（廣義表中括號嵌套的最大次數(shù)，廣義表中括弧的重數(shù)） ? D=( )空表，長度為 0，深度為 1。 ? A=(a, (b, c)) 長度為 2，第一個元素為原子 a，第二個元素為子表 (b, c)，深度為 2。 ? B=(A, A, D) 長度為 3， 其前兩個元素為表 A， 第三個元素為空表 D，深度為 3。 ? C=(a, C) 長度為 2遞歸定義的廣義表， C相當于無窮表 C=(a,(a, (a,…))) ，深度無限。 遞歸表的深度是無窮值 ,長度是有限值 。 ? F=((a, (a, b), ((a, b), c))) 長度為 1，深度為 4。 ?廣義表的 表頭 (Head)和 表尾 (Tail)： 當廣義表非空時，稱第一個元素 a1為廣義表的表頭， 其余元素組成的表 (a2, a3, …,a n)稱為廣義表的表尾。 表頭可能是原子，也可能是廣義表，但表尾一定是廣 義表。 ?廣義表的圖形表示 用方框表示原子，用圓圈表示廣義表。 A=( )。 B=(e)。 C=(a, (b, c, d)) D=(A, B, C)。 E=((a, (a, b), ((a, b), c))) c a b a b E d e a b c D A B C d b c C a B e A a 2. 廣義表的基本操作 ?取表頭 GetHead(LS) = a1。 ?取表尾 GetTail(LS) = (a2,a3,…,a n)。 ① B=(e) GetHead(B) = e。 GetTail(B) = ( ). ② A=(a, ((b, c), d, e)) GetHead( GetHead( GetTail(A))) = GetHead( GetHead( ( ((b, c), d, e) ) )) = GetHead( ((b, c), d, e) ) = (b, c). ③ A=( )。 B = ( ( ) ) A空表，長度 0，深度 1，無表頭和表尾； B長度 1，深度 2，表頭 ( )，表尾 ( )。 3. 廣義表的存儲結構 廣義表是一種遞歸的數(shù)據(jù)結構 ,因此很難為每個廣義表分配固定大小的存儲空間 ,所以其存儲結構只好采用動態(tài)鏈式結構 。 ?廣義表的頭尾鏈表存儲表示 ?廣義表的擴展線性鏈表存儲表示 C=(a, (b, c, d)) C 1 0 a 1 ∧ 1 1 1 ∧ 0 b 0 c 0 d (a, (b, c, d)) ((b, c, d)) (b, c, d) (c, d) (d) ?廣義表的頭尾鏈表存儲表示 C 1 ∧ 0 a 1 ∧ 0 b 0 c 0 d ∧ C=(a, (b, c, d)) (b, c, d) ?廣義表的擴展線性鏈表存儲表示（帶表頭結點） ?作業(yè)：
環(huán)評公示相關推薦
鄂ICP備17016276號-1