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