java數(shù)據(jù)結構第五章數(shù)組和廣義表-資料下載頁
2025-05-11 22:26本頁面
【正文】 是列表； 當每個元素都為原子且類型相同時，就是線性表。 廣義表的 邏輯結構 ：直接元素之間是線性關系 ， 1對 1。 常用術語： 長度： 廣義表 LS中的 直接元素的個數(shù) ； 深度： 廣義表 LS中括號的 最大嵌套層數(shù) 。 表頭： 廣義表 LS非空時，稱 第一個元素 為 LS的表頭； 表尾： 廣義表 LS中除表頭外 其余元素組成的廣義表 。 E=(a,E)=(a,(a,E))= (a,(a,(a,…….))) ， E為遞歸表 1） A =( ) 2） B = ( e ) 3） C =( a ,( b , c , d ) ) 4） D=( A , B ,C ) 5） E=(a, E) 實訓 1： 求下列廣義表的長度。 n=0， 因為 A是空表 n=1，表中元素 e是原子類型 n=2， a 為原子， (b,c,d)為子表 n=3， 3個元素都是子表 n=2， a 為原子， E為子表 D=(A,B,C)=(( ),(e),(a,(b,c,d)))， 共享表 A B D C e a b c d ② A=( a , (b, A) ) 實訓 2： 試用圖形表示下列廣義表。 （設 代表原子， 代表子表） ① D=(A,B,C)=( ( ),(e),( a, (b,c,d) ) ) A a b ① 的長度為 3，深度為 3 ② 的長度為 2，深度為 ∞ 深度＝括號的層數(shù)＝ 結點的層數(shù) 兩種特殊的基本操作： GetHead( L) —— 取表頭 (可能是原子或列表 )。 GetTail(L ) —— 取表尾 (一定是列表 ) 。 廣義表 ( )和廣義表 (( ))不同？ ():長度為 0，深度為 1。 (()):長度為 1,深度為 2。 1. GetTail【 (b, k, p, h)】 ＝ 。 2. GetHead【 ( (a,b), (c,d) )】 ＝ 。 3. GetTail【 ( (a,b), (c,d) )】 ＝ 。 4. GetTail【 GetHead【 ((a,b),(c,d))】】 ＝ 。 實訓 3： 求下列廣義表操作的結果 (k, p, h) （ b） (a,b) 5. GetTail【 （ e） 】 ＝ 。 6. GetHead 【 ( ( ) )】 ＝ . 7. GetTail【 ( ( ) ) 】 ＝ . ( ) (a,b) ( ) ( ) ((c,d)) 廣義表的存儲結構 廣義表可以采用順序存儲結構嗎？ 由于廣義表中的數(shù)據(jù)元素的 類型不統(tǒng)一 （原子或廣義表），因此難以采用順序存儲結構來存儲。 若 廣義表不空 ，則可分解為 表頭 和 表尾 ；反之，一對確定的表頭和表尾可唯一地確定一個廣義表。 注：采用 頭尾表示 法存儲廣義表 如何采用 鏈接存儲結構 存儲廣義表？ 廣義表的存儲結構 —— 頭尾表示法 廣義表中的數(shù)據(jù)元素既可以是廣義表也可以是單元素 頭尾表示法中的結點結構？ 表結點 —— 存儲廣義表； 元素結點 —— 存儲單元素 tag=1 hp tp tag=0 data 表結點 元素結點 tag：區(qū)分表結點和元素結點的標志； hp：指向 表頭結點 的指針； tp： 指向 表尾結點 的指針； data：數(shù)據(jù)域 ， 存放單元素 。 結點結構 A ＝ ( ) B ＝ (e) C ＝ (a, (b， c， d)) NULL A 實例如下： ^ 1 0 e C =( a ,( b , c , d ) ) 1 ^ 1 1 0 a 0 b 0 d 0 c 1 ^ 1 B=( e ) E ＝ (a, E) F ＝ (( )) 1 E 0 a 1 ∧ 1 F ∧ ∧ tp data tag=0 標志域 值域 指針 擴展表示 ：三個域結點結構 指向下一結點 tp hp tag=1 標志域 表頭指針 指針 原子結點 表結點 如 :C =( a ,( b , c , d ) ) ^ 1 ^ 1 0 c ^ 0 d 0 a ^ 0 b
環(huán)評公示相關推薦
鄂ICP備17016276號-1