數(shù)據(jù)結(jié)構(gòu)ppt課件chap(已修改)
2025-08-02 22:05 本頁(yè)面
【正文】 數(shù)組的類型定義 稀疏矩陣的壓縮存儲(chǔ) 數(shù)組的順序表示和實(shí)現(xiàn) 廣義表的類型定義 廣義表的表示方法 廣義表操作的遞歸函數(shù) 數(shù)組的類型定義 ADT Array { 數(shù)據(jù)對(duì)象 ： D＝ {aj1,j2, ...,ji,jn| ji =0,...,bi 1, i=1,2,..,n } 數(shù)據(jù)關(guān)系 ： R＝ {R1, R2, ..., Rn} Ri＝ {aj1,... ji,... jn , aj1, ...ji +1, ...jn | 0 ? jk ? bk 1, 1 ? k ? n 且 k ? i, 0 ? ji ? bi 2, i=2,...,n } } ADT Array 基本操作 : 二維數(shù)組的定義 : 數(shù)據(jù)對(duì)象 : D = {aij | 0≤i≤b11, 0 ≤j≤b21} 數(shù)據(jù)關(guān)系 : R = { ROW, COL } ROW = {ai,j,ai+1,j| 0≤i≤b12, 0≤j≤b21} COL = {ai,j,ai,j+1| 0≤i≤b11, 0≤ j≤b22} 基本操作 ： InitArray(amp。A, n, bound1, ..., boundn) DestroyArray(amp。A) Value(A, amp。e, index1, ..., indexn) Assign(amp。A, e, index1, ..., indexn) InitArray(amp。A, n, bound1, ..., boundn) 操作結(jié)果： 若維數(shù) n 和各維長(zhǎng)度合法， 則構(gòu)造相應(yīng)的數(shù)組 A，并 返回 OK。 DestroyArray(amp。A) 操作結(jié)果： 銷(xiāo)毀數(shù)組 A。 Value(A, amp。e, index1, ..., indexn) 初始條件： A是 n維數(shù)組， e為元素變量， 隨后是 n 個(gè)下標(biāo)值。 操作結(jié)果： 若各下標(biāo)不超界，則 e賦值為 所指定的 A 的元素值，并返 回 OK。 Assign(amp。A, e, index1, ..., indexn) 初始條件： A是 n維數(shù)組， e為元素變量， 隨后是 n 個(gè)下標(biāo)值。 操作結(jié)果： 若下標(biāo)不超界，則將 e的值賦 給所指定的 A的元素，并返回 OK。 數(shù)組的順序表示和實(shí)現(xiàn) 類型特點(diǎn) : 1) 只有引用型操作，沒(méi)有加工型操作 。 2) 數(shù)組是多維的結(jié)構(gòu)，而存儲(chǔ)空間是 一個(gè)一維的結(jié)構(gòu)。 有兩種順序映象的方式 : 1)以行序?yàn)橹餍?(低下標(biāo)優(yōu)先 )。 2)以列序?yàn)橹餍?(高下標(biāo)優(yōu)先 )。 例如： 稱為 基地址 或基址。 以“行序?yàn)橹餍颉钡拇鎯?chǔ)映象 二維數(shù)組 A中任一元素 ai,j 的存儲(chǔ)位置 LOC(i,j) = LOC(0,0) + (b2 i＋ j) a0,1 a0,0 a0,2 a1,0 a1,1 a1,2 a0,1 a0,0 a0,2 a1,0 a1,1 a1,2 L L 推廣到一般情況，可得到 n 維數(shù)組數(shù)據(jù)元素存儲(chǔ)位置的映象關(guān)系 稱為 n 維數(shù)組的映象函數(shù)。 數(shù)組元素 的存儲(chǔ)位置是其下標(biāo)的線性函數(shù) 其中 = L， ci1 = bi ci , 1 i ? n。 LOC(j1, j2, ..., jn ) = LOC(0,0,...,0) + ∑ ci ji i =1 n 假設(shè) m 行 n 列 的矩陣含 t 個(gè)非零元素 ，則稱 為 稀疏因子 通常認(rèn)為 ? ? 的矩陣為稀疏矩陣 nm t??? 稀疏矩陣的壓縮存儲(chǔ) 何謂稀疏矩陣？ 以常規(guī)方法，即以二維數(shù)組表示 高階的稀疏矩陣時(shí)產(chǎn)生的 問(wèn)題 : 1) 零值元素占了很大空間 。 2) 計(jì)算中進(jìn)行了很多和零值的運(yùn)算， 遇除法，還需判別除數(shù)是否為零 。 1) 盡可能少存或不存零值元素 。 解決問(wèn)題的原則 : 2) 盡可能減少?zèng)]有實(shí)際意義的運(yùn)算 。 3) 操作方便 。 即 : 能盡可能快地找到 與下標(biāo)值 (i, j) 對(duì)應(yīng)的元素 。 能盡可能快地找到 同一行或同一列的非零值元 。 1) 特殊矩陣 非零元在矩陣中的分布有一定規(guī)則 例如 : 三角矩陣 對(duì)角矩陣 2) 隨機(jī)稀疏矩陣 非零元在矩陣中隨機(jī)出現(xiàn) 有兩類稀疏矩陣 ： 隨機(jī)稀疏矩陣的壓縮存儲(chǔ)方法 : 一、三元組順序表 二、行邏輯聯(lián)接的順序表 三、 十字鏈表 define MAXSIZE 12500 typedef struct { int i, j。 //該非零元的行下標(biāo)和列下標(biāo) ElemType e。 // 該非零元的值 } Triple。 // 三元組類型 一、三元組順序表 typedef union { Triple data[MAXSIZE + 1]。 int mu, nu, tu。 } TSMatrix。 // 稀疏矩陣類型 如何求轉(zhuǎn)置矩陣？ ????????????028003600070500140??????????????????005280000007143600用常規(guī)的二維數(shù)組表示時(shí)的算法 其時(shí)間復(fù)雜度為 : O(mu nu) for (col=1。 col=nu。 ++col) for (row=1。 row=mu。 ++row) T[col][row] = M[row][col]。 用“三元組”表示時(shí)如何實(shí)現(xiàn)？ 1 2 14 1 5 5 2 2 7 3 1 36 3 4 28 2 1 14 5 1 5 2 2 7 1 3 36 4 3 28 首先應(yīng)該確定轉(zhuǎn)置矩陣中 每一行的第一個(gè)非零元在三元組中的位置 。 1 2 151 5 52 2 73 1 363 4 28 co l 1 2 3 4 5N u m [ p os] 1 2 0 1 1C p ot [ c ol ] 1 2 4 4 5 cpot[1] = 1。 for (col=2。 col=。 ++col) cpot[col] = cpot[col1] + num[col1]。 Status FastTransposeSMatrix(TSMatrix M, TSMatrix amp。T){ = 。 = 。 = 。 if () { for (col=1。 col=。 ++col) num[col] = 0。 for (t=1。 t=。 ++t) ++num[[t].j]。 cpot[1] = 1。 for (col=2。 col=。 ++col) cpot[col] = cpot[col1] + num[col1]。 for (p=1。 p=。 ++p) { } } // if return OK。 } // FastTransposeSMatrix 轉(zhuǎn)置矩陣元素 Col = [p].j。 q = cpot[col]。 [q].i = [p].j。 [q].j = [p].i
電大資料相關(guān)推薦
鄂ICP備17016276號(hào)-1