java數(shù)據(jù)結構第五章數(shù)組和廣義表(參考版)
2025-05-15 22:26本頁面
【正文】 結點結構 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 。 若 廣義表不空 ，則可分解為 表頭 和 表尾 ；反之，一對確定的表頭和表尾可唯一地確定一個廣義表。 實訓 3： 求下列廣義表操作的結果 (k, p, h) （ b） (a,b) 5. GetTail【 （ e） 】 ＝ 。 3. GetTail【 ( (a,b), (c,d) )】 ＝ 。 1. GetTail【 (b, k, p, h)】 ＝ 。 廣義表 ( )和廣義表 (( ))不同？ ():長度為 0，深度為 1。 （設 代表原子， 代表子表） ① D=(A,B,C)=( ( ),(e),( a, (b,c,d) ) ) A a b ① 的長度為 3，深度為 3 ② 的長度為 2，深度為 ∞ 深度＝括號的層數(shù)＝ 結點的層數(shù) 兩種特殊的基本操作： GetHead( L) —— 取表頭 (可能是原子或列表 )。 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： 求下列廣義表的長度。 常用術語： 長度： 廣義表 LS中的 直接元素的個數(shù) ； 深度： 廣義表 LS中括號的 最大嵌套層數(shù) 。 n是表長 在廣義表中約定： 討論： 廣義表與線性表的區(qū)別和聯(lián)系？ 廣義表中元素既可以是原子類型，也可以是列表； 當每個元素都為原子且類型相同時，就是線性表。 則每個非零元素既是行鏈表中的一個結點；又是列鏈表中的一個結點，即 呈十字鏈狀 。 –三元組單鏈表 –行 /列的單鏈表 方法二： 用 三元組鏈表 表示 方法三： 用 十字鏈表 表示 用途： 方便 稀疏矩陣的加減 運算； 方法： 每個 非 0元素 占用 5個域 。 實現(xiàn)方法： 1)三元組法 2)十字鏈表法 如 :將每個非零元素用一個三元組 （ i， j， aij）來表示，則每個 稀疏矩陣可用一個 三元組表 來表示。 特殊矩陣的壓縮存儲 —— 三角矩陣 3 c c c c 6 2 c c c 4 8 1 c c 7 4 6 0 c 8 2 9 5 7 (a) 下三角矩陣 3 4 8 1 0 c 2 9 4 6 c c １ 5 7 c c c 0 8 c c c c 7 (b) 上三角矩陣 矩陣中任一元素 aij在數(shù)組中的下標 k與 i、 j的對應關系： i (i＋ 1)/2＋ j 當 i≥j n (n＋ 1)/2 當 i＜ j k= 0 1 2 3 4 5 k n(n+1)/2 第 1行 第 0行 a00 a10 a11 a20 a21 aij … an1n1 … 第 2行 c a22 存儲 下三角 元素 對角線上方的常數(shù) —— 只存一個 如何只存儲非零元素？ 注意：稀疏矩陣中的非零元素的分布沒有規(guī)律。 （２） 下三角矩陣 ：是指矩陣的上三角（不包括對角線）中的元均為常數(shù)Ｃ或零的 n階矩陣。 若計算 aij存放地址，則可以利用以下公式獲得： LOC[aij]=LOC[a00]+（ i(i+1)/2
環(huán)評公示相關推薦
鄂ICP備17016276號-1