第5章數(shù)組和廣義表(參考版)
2024-10-21 13:12本頁面
【正文】 4. 掌握廣義表的結(jié)構(gòu)特點及其存儲表示方法，讀者可根據(jù)自己的習慣熟練掌握任意一種結(jié)構(gòu)的鏈表，學會對非空廣義表進行分解的兩種分析方法：即可將一個非空廣義表分解為表頭和表尾兩部分或者分解為 n個子表。 2. 掌握對特殊矩陣進行壓縮存儲時的下標變換公式。 6) 任何一個非空廣義表 LS = ( a 1, a 2, …, a n) 均可分解為： 表頭 Head(LS) = a 1 和表尾 Tail(LS) = ( a 2, …, a n)兩部分。 5) 廣義表可以是一個 遞歸 的表 。 “空表”的深度為 1。 3) 廣義表的 深度 定義為所含括弧的重數(shù) 。 第 5章 數(shù)組和廣義表 例如： E = (a, (b, c)) F = (d, (e)) D = (E, F) 其它如： A = ( ) //空表，長度為 0 B = (a, B) = (a, (a, (a, ... , ) ) ) //這是一個遞歸的表，長度為 2 C = (A, D, F) //長度為 3 第 5章 數(shù)組和廣義表 廣義表 LS = (a1,a 2, …,a n ) 的結(jié)構(gòu)特點 : 1) 廣義表中的數(shù)據(jù)元素有相對 次序 。 一般情況下，廣義表寫成 LS = ( a 1,a 2, ... , a n ) 其中： a i 或為 原子 或為 廣義表， 第一個元素 a 1為表頭，其余元素組成的表 ( a 2, ... , a n )是 LS的 表尾 。 n≥0。同一行的非零元通過 right 域鏈接成一個線性鏈表，同一列的非零元通過 down 域鏈接成一個線性鏈表，每個非零元既是某個行鏈表中的一個結(jié)點，又是某個列鏈表中的一個結(jié)點，整個矩陣構(gòu)成了一個十字交叉的鏈表，故稱這樣的存儲結(jié)構(gòu)為十字鏈表，可用兩個分別存儲行鏈表的頭指針和列鏈表的頭指針的一維數(shù)組表示之。為此，對這種類型的矩陣，采用 鏈式存儲結(jié)構(gòu) 表示三元組的線性表更為恰當。} 其時間復雜度為： O(m1* n1* n2) 第 5章 數(shù)組和廣義表 三、 十字鏈表 ? 當矩陣的非零元個數(shù)和位置在操作過程中變化較大時，就不宜采用順序存儲結(jié)構(gòu)來表示三元組的線性表。 k=n1。 ++j) { Q[i][j] = 0。 ++i) f or
教學課件相關推薦
鄂ICP備17016276號-1