數(shù)據(jù)結(jié)構(gòu)課件第5章數(shù)組和廣義表-資料下載頁(yè)
2025-04-29 08:39本頁(yè)面
【正文】 tcol j。 q = qright )。 right = qright。 qright = p。 if ( Mcol_head[j] = NULL ) { Mcol_head[j] = p。 pdown = NULL。} if ( col_head[j] NULL ) { Mcol_head[j] = p。 pdown = NULL。 }row_head[i] = = NULL ) { ow_head[i] = p。 right 。 = col_head[i 。 (qdown amp。amp。 qdownrowif ( Mrow_head[i] row_head[i] right NULL。 } 對(duì)于一個(gè) m 行 n 列 ， 并且有 t 個(gè)非零元的稀疏矩陣 ， CreateSMatrix_OL 算法執(zhí)行時(shí)間為 O(t s) ， 其中 s = max{m, n}。 這是因?yàn)椋好拷⒁粋€(gè)非零元的結(jié)點(diǎn)時(shí)都需要尋查它在行表和列表中的插入位置 ， 此算法對(duì)非零元輸入的先后次序沒(méi)有任何要求 。 反之 ， 若按以行序?yàn)橹餍虻拇涡蛞来屋斎肴M ，即可以將建立十字鏈表表示的算法改寫(xiě)成 O(t) 數(shù)量級(jí)的 （ t 為非零元個(gè)數(shù) ） 的算法 。 ② 算法分析 50 廣義表 (generalized list) 是線(xiàn)性表的推廣 ， 有時(shí)也稱(chēng)為列表 （ lists， 用復(fù)數(shù)形式以示與統(tǒng)稱(chēng)的表 list 的區(qū)別 ） 。 廣泛地應(yīng)用于人工智能等領(lǐng)域的 LISP（ 表處理語(yǔ)言 ） ， 把廣義表作為基本的數(shù)據(jù)結(jié)構(gòu) ， 就連程序也表示為一系列的廣義表 。 51 廣義表 廣義表的邏輯結(jié)構(gòu) 和數(shù)組一樣 ， 廣義表也可以看成是線(xiàn)性表在下述含義上的擴(kuò)展：表中的數(shù)據(jù)元素本身也是一種數(shù)據(jù)結(jié)構(gòu) 。 52 廣義表的存儲(chǔ)結(jié)構(gòu) 53 廣義表的邏輯結(jié)構(gòu) 廣義表一般記作： GL = ( a1 , a2 , … , an ) 其中： n 是廣義表 GL 的長(zhǎng)度； ai 可以是單個(gè)元素 ， 也可以是廣義表 ， 分別稱(chēng)為廣義表 GL 的原子和子表 ， 習(xí)慣上用大寫(xiě)字母表示廣義表的名稱(chēng) ， 用小寫(xiě)字母表示原子的名稱(chēng) 。 GL 是廣義表 ( a1 , a2 , … , an ) 的名稱(chēng)； 1. 廣義表的定義 54 當(dāng)廣義表 GL為非空時(shí) ， 稱(chēng)第一個(gè)元素 a1 為 GL的表頭 （ head） ， 其余元素組成的表 ( a2 , a3 , … , an ) 是 GL的表尾 （ tail） 。 顯然 ，廣義表的定義是一個(gè)遞歸的定義 ， 因?yàn)樵诿枋鰪V義表時(shí)又用到了廣義表的概念 。 例 51 A = ( )， A 是一個(gè)空表 ， 它的長(zhǎng)度為零 。 例 52 B = (e)， B 只有一個(gè)原子 e， 它的長(zhǎng)度為 1。 例 53 C = (a, (b, c, d))， C 的長(zhǎng)度為 2， 兩個(gè)元素分別為原子 a 和子表 (b, c, d)。 例 54 D = (A, B, C)， D 的長(zhǎng)度為 3， 三個(gè)元素分別為 A、 B 和 C， 都是廣義表 。 顯然 ， 將上面所述三個(gè)子表的值代入以后 ， 則有 D = (( ), (e), (a, (b, c, d)))。 例 55 E = (a, E)， 這是一個(gè)遞歸表 ， 它的長(zhǎng)度為 2，E 相當(dāng)于一個(gè)無(wú)限的廣義表 E = (a, (a, (a, … )))。 55 2. 廣義表的三個(gè)重要結(jié)論 從上述定義和例子推出如下廣義表的三個(gè)重要結(jié)論 (1) 廣義表的元素可以是子表 ， 而子表的元素還可以是子表 ， … 。 由此 ， 廣義表是一個(gè)多層次結(jié)構(gòu) 。 (2) 廣義表可以為其他廣義表所共享 。 例如在上述例子中 ， 廣義表 A、 B 和 C 為 D 的子表 ， 則在 D 中可以不必列出廣義表的值 ， 而是通過(guò)子表的名稱(chēng)引用 。 (3) 廣義表可以是一個(gè)遞歸表 ， 即廣義表也可以是其本身的一個(gè)子表 。 例如廣義表 E 就是一個(gè)遞歸的表 。 56 e c d b a B A C D 表示廣義表 表示原子 57 和線(xiàn)性表相類(lèi)似 ， 可以對(duì)廣義表進(jìn)行的操作有查找 、插入 、 刪除和取表元素等 。 由于廣義表在結(jié)構(gòu)上較線(xiàn)性表復(fù)雜的多 ， 因此 ， 廣義表操作的實(shí)現(xiàn)也不如線(xiàn)性表簡(jiǎn)單 。 在這些操作中 ， 最重要的兩個(gè)基本操作是： (1) 取廣義表表頭 GetHead： 表中的第一個(gè)元素為此表的表頭 。 (2) 取廣義表表尾 GetTail： 表中除第一個(gè)元素外的其余元素組成的表為此表的表尾 。 58 3. 廣義表的兩個(gè)基本操作 (1) A = ( ) (2) B = (e) (3) C = (a, (b, c, d)) (4) D = (A, B, C) (5) E = (a, E) GetHead (B) = e GetTail (B) = ( ) GetHead (C) = a GetTail (C) = ((b, c, d)) GetHead (D) = A GetTail (D) = (B, C) 由于 (B, C) 為非空廣義表 ， 令 F = (B, C)， 則可以繼續(xù)分解得到： GetHead (F) = B GetTail (F) = (C) 任何一個(gè)非空廣義表的表頭可能是原子 ， 也可能是廣義表；而其表尾必定是廣義表 。 例如 ， 廣義表如下： 對(duì)定義表 B， C， D 取表頭和取表尾的操作結(jié)果： 59 廣義表 ( ) 和廣義表 (( )) 不同 。 ( ) 為空表 ， 長(zhǎng)度 n = 0， 不能分解成表頭和表尾； (( )) 不是空表 ， 長(zhǎng)度 n = 1， 可以分解得到其表頭是空表 ( )， 表尾是空表 ( )。 60 由于廣義表 （ a1, a2, … , an ） 中的數(shù)據(jù)元素可以具有不同的結(jié)構(gòu) （ 或是原子 ， 或是廣義表 ） ， 因此很難用順序結(jié)構(gòu)表示 ， 通常采用鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu) 。 在這種結(jié)構(gòu)中 ， 需要兩種結(jié)構(gòu)的結(jié)點(diǎn) 。 61 廣義表的存儲(chǔ)結(jié)構(gòu) tag = 1 hp tp 標(biāo)志域 頭指針域 指向下一個(gè)結(jié)點(diǎn) (1) 表結(jié)點(diǎn)：用以表示廣義表 。 由 3 個(gè)域組成：標(biāo)志域 、 指示表頭的指針域和指示下一個(gè)元素結(jié)點(diǎn)的指針域 。 (2) 原子結(jié)點(diǎn)：用以表示原子 。 由 3 個(gè)域組成：標(biāo)志域 、 值域及指示下一個(gè)元素結(jié)點(diǎn)的指針域 。 指向下一個(gè)結(jié)點(diǎn) 標(biāo)志域 tag = 0 atom tp 值域 62 廣義表的擴(kuò)展線(xiàn)性鏈表存儲(chǔ)結(jié)構(gòu) typedef enum { ATOM, LIST } ElemTag。 // ATOM = = 0 : 原子； LIST = = 1 : 子表 typedef struct GLNode { ElemTag tag。 // 公共部分 ， 用于區(qū)分原子結(jié)點(diǎn)和表結(jié)點(diǎn) union { // 原子結(jié)點(diǎn)和表結(jié)點(diǎn)的聯(lián)合部分 AtomType atom。 // 原子結(jié)點(diǎn)的值域 struct GLNode *hp。 // 表結(jié)點(diǎn)的表頭指針 }。 struct GLNode *tp。 // 相當(dāng)于線(xiàn)性鏈表的 next， 指向下一個(gè)元素結(jié)點(diǎn) } GLNode,*GList。 // 廣義表擴(kuò)展線(xiàn)性鏈表類(lèi)型名 63 (1) A = ( ) 例： A 1 ∧ ∧ B 1 ∧ 0 e ∧ 0 b 0 d ∧ 0 a C 0 c 1 ∧ 1 ∧ 1 ∧ D 1 ∧ 1 1 ∧ 0 a 1 ∧ E 1 ∧ (2) B = ( e ) (3) C = ( a, ( b, c, d ) ) (4) D = ( A, B, C ) (5) E = ( a, E ) 64
醫(yī)療健康相關(guān)推薦
鄂ICP備17016276號(hào)-1