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