【正文】 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。 } 對于一個 m 行 n 列 ， 并且有 t 個非零元的稀疏矩陣 ， CreateSMatrix_OL 算法執(zhí)行時間為 O(t s) ， 其中 s = max{m, n}。 這是因為：每建立一個非零元的結(jié)點時都需要尋查它在行表和列表中的插入位置 ， 此算法對非零元輸入的先后次序沒有任何要求 。 反之 ， 若按以行序為主序的次序依次輸入三元組 ，即可以將建立十字鏈表表示的算法改寫成 O(t) 數(shù)量級的 （ t 為非零元個數(shù) ） 的算法 。 ② 算法分析 50 廣義表 (generalized list) 是線性表的推廣 ， 有時也稱為列表 （ lists， 用復(fù)數(shù)形式以示與統(tǒng)稱的表 list 的區(qū)別 ） 。 廣泛地應(yīng)用于人工智能等領(lǐng)域的 LISP（ 表處理語言 ） ， 把廣義表作為基本的數(shù)據(jù)結(jié)構(gòu) ， 就連程序也表示為一系列的廣義表 。 51 廣義表 廣義表的邏輯結(jié)構(gòu) 和數(shù)組一樣 ， 廣義表也可以看成是線性表在下述含義上的擴展：表中的數(shù)據(jù)元素本身也是一種數(shù)據(jù)結(jié)構(gòu) 。 52 廣義表的存儲結(jié)構(gòu) 53 廣義表的邏輯結(jié)構(gòu) 廣義表一般記作： GL = ( a1 , a2 , … , an ) 其中： n 是廣義表 GL 的長度； ai 可以是單個元素 ， 也可以是廣義表 ， 分別稱為廣義表 GL 的原子和子表 ， 習(xí)慣上用大寫字母表示廣義表的名稱 ， 用小寫字母表示原子的名稱 。 GL 是廣義表 ( a1 , a2 , … , an ) 的名稱； 1. 廣義表的定義 54 當(dāng)廣義表 GL為非空時 ， 稱第一個元素 a1 為 GL的表頭 （ head） ， 其余元素組成的表 ( a2 , a3 , … , an ) 是 GL的表尾 （ tail） 。 顯然 ，廣義表的定義是一個遞歸的定義 ， 因為在描述廣義表時又用到了廣義表的概念 。 例 51 A = ( )， A 是一個空表 ， 它的長度為零 。 例 52 B = (e)， B 只有一個原子 e， 它的長度為 1。 例 53 C = (a, (b, c, d))， C 的長度為 2， 兩個元素分別為原子 a 和子表 (b, c, d)。 例 54 D = (A, B, C)， D 的長度為 3， 三個元素分別為 A、 B 和 C， 都是廣義表 。 顯然 ， 將上面所述三個子表的值代入以后 ， 則有 D = (( ), (e), (a, (b, c, d)))。 例 55 E = (a, E)， 這是一個遞歸表 ， 它的長度為 2，E 相當(dāng)于一個無限的廣義表 E = (a, (a, (a, … )))。 55 2. 廣義表的三個重要結(jié)論 從上述定義和例子推出如下廣義表的三個重要結(jié)論 (1) 廣義表的元素可以是子表 ， 而子表的元素還可以是子表 ， … 。 由此 ， 廣義表是一個多層次結(jié)構(gòu) 。 (2) 廣義表可以為其他廣義表所共享 。 例如在上述例子中 ， 廣義表 A、 B 和 C 為 D 的子表 ， 則在 D 中可以不必列出廣義表的值 ， 而是通過子表的名稱引用 。 (3) 廣義表可以是一個遞歸表 ， 即廣義表也可以是其本身的一個子表 。 例如廣義表 E 就是一個遞歸的表 。 56 e c d b a B A C D 表示廣義表 表示原子 57 和線性表相類似 ， 可以對廣義表進行的操作有查找 、插入 、 刪除和取表元素等 。 由于廣義表在結(jié)構(gòu)上較線性表復(fù)雜的多 ， 因此 ， 廣義表操作的實現(xiàn)也不如線性表簡單 。 在這些操作中 ， 最重要的兩個基本操作是： (1) 取廣義表表頭 GetHead： 表中的第一個元素為此表的表頭 。 (2) 取廣義表表尾 GetTail： 表中除第一個元素外的其余元素組成的表為此表的表尾 。 58 3. 廣義表的兩個基本操作 (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) 任何一個非空廣義表的表頭可能是原子 ， 也可能是廣義表；而其表尾必定是廣義表 。 例如 ， 廣義表如下： 對定義表 B， C， D 取表頭和取表尾的操作結(jié)果： 59 廣義表 ( ) 和廣義表 (( )) 不同 。 ( ) 為空表 ， 長度 n = 0， 不能分解成表頭和表尾； (( )) 不是空表 ， 長度 n = 1， 可以分解得到其表頭是空表 ( )， 表尾是空表 ( )。 60 由于廣義表 （ a1, a2, … , an ） 中的數(shù)據(jù)元素可以具有不同的結(jié)構(gòu) （ 或是原子 ， 或是廣義表 ） ， 因此很難用順序結(jié)構(gòu)表示 ， 通常采用鏈?zhǔn)酱鎯Y(jié)構(gòu) 。 在這種結(jié)構(gòu)中 ， 需要兩種結(jié)構(gòu)的結(jié)點 。 61 廣義表的存儲結(jié)構(gòu) tag = 1 hp tp 標(biāo)志域 頭指針域 指向下一個結(jié)點 (1) 表結(jié)點：用以表示廣義表 。 由 3 個域組成：標(biāo)志域 、 指示表頭的指針域和指示下一個元素結(jié)點的指針域 。 (2) 原子結(jié)點：用以表示原子 。 由 3 個域組成：標(biāo)志域 、 值域及指示下一個元素結(jié)點的指針域 。 指向下一個結(jié)點 標(biāo)志域 tag = 0 atom tp 值域 62 廣義表的擴展線性鏈表存儲結(jié)構(gòu) typedef enum { ATOM, LIST } ElemTag。 // ATOM = = 0 : 原子； LIST = = 1 : 子表 typedef struct GLNode { ElemTag tag。 // 公共部分 ， 用于區(qū)分原子結(jié)點和表結(jié)點 union { // 原子結(jié)點和表結(jié)點的聯(lián)合部分 AtomType atom。 // 原子結(jié)點的值域 struct GLNode *hp。 // 表結(jié)點的表頭指針 }。 struct GLNode *tp。 // 相當(dāng)于線性鏈表的 next， 指向下一個元素結(jié)點 } GLNode,*GList。 // 廣義表擴展線性鏈表類型名 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