【正文】 因為子表與元素內(nèi)容不同時出現(xiàn) ， 所以 pSub與pElem可以共享存儲區(qū) 。 pSub：指向結(jié)點對應(yīng)的子表的頭 。 next：指向同層中下個結(jié)點 。 name：結(jié)點名稱 。 }。 TGListNode *pSub。 TGListNode *next。 class TGListNode { char tag。 鏈式結(jié)構(gòu)的高級語言描述 這里，僅從數(shù)據(jù)結(jié)構(gòu)方面給出廣義表的分枝單鏈表的 C++描述。 tag … pElem next 下面給出上例中給出的一個廣義表序列中的五個廣義表所對應(yīng)的分枝單鏈表存貯結(jié)構(gòu)（圖 80）。 (c) 直接元素構(gòu)成的單鏈表 ， 根據(jù)具體問題的需要 ， 可以是帶頭結(jié)點的 ， 或循環(huán)式的 ， 或雙向鏈式的或這些的組合 。 pElem：若 αi為單元素 ， 則指向 αi的內(nèi)容 ， 否則指向 αi對應(yīng)的廣義表 (可以用第一個頭結(jié)點 H1的指針代表廣義表 ). next：單鏈表鏈指針 ， 即指向 Hi+1。在這種方法中，為廣義表的每個直接元素設(shè)置一個表結(jié)點（稱為元素的頭結(jié)點），各頭結(jié)點依它們的邏輯次序鏈接成一個單鏈表，每個頭結(jié)點設(shè)一個指針指向它所對應(yīng)的直接元素的內(nèi)容（若此直接元素為單元素），或指向它所對應(yīng)的直接元素的廣義表的頭（若此直接元素為子表）。 下面給出一種通用的鏈式存貯結(jié)構(gòu) ── 分枝單鏈表法 ， 它可滿足廣義表的三個邏輯特性的要求 ， 是一種常用的方法 。 給出的廣義表的順序存儲為： ( ( ( a b ) ) ( ( a b ) c ) ( c d e ) ( e ) ) (二 ) 鏈式存儲 鏈式存儲也可以有多種形式 ， 具體使用時 ， 應(yīng)根據(jù)具體問題的要求選擇不同的存貯結(jié)構(gòu) 。為了使存儲的內(nèi)容有統(tǒng)一的長度，對基本元素的存儲，可以存儲它們的地址（一般是相對地址，即序號）。 (一 ) 順序存儲方法 廣義表的順序存儲，也只能是 “ 廣義 ” 的順序存儲，因為我們不可能只存儲基本元素，也不可能將各種元素（包括子表）用一個統(tǒng)一方法存儲。 廣義表的存貯結(jié)構(gòu) 167。著名的人工智能語言 LISP和 Prolog其實就是以廣義表為數(shù)據(jù)結(jié)構(gòu)，通過求表頭和表尾實現(xiàn)對象的操作。 基本操作 廣義表兼有線性表和樹的特性 ， 因此 ， 它的基本操作也兼有線性表和樹的一些操作 ， 此外 ， 還有一些特有操作 ， 如求表頭和表尾 。 對多次出現(xiàn)的元素 ， 顯然可以從不同的位置 （ 路徑 ） 訪問它們 ，因此 ， 具有該特性的表也稱 再入表 (Reentrant List)。 在其他數(shù)據(jù)結(jié)構(gòu)中 ， 并不把復(fù)合元素看作元素 。 因此 ， 廣義表元素的類型不統(tǒng)一 。 ? 元素復(fù)合性 ：廣義表中的元素分兩種：單元素和復(fù)合元素 （ 子表 ） 。 ? 元素分層性 ：如果將廣義表中不同出現(xiàn)的元素看作不同的元素 ， 則廣義表是層次結(jié)構(gòu) ， 即對任一元素 ， 它只直屬層號比它大 1的元素 。 ? 元素遞歸性 ：廣義表的任一元素，又可以是一個廣義表（其它廣義表或自身）。 例如 ， 對廣義表 L=A(a, B(c, C(a, b), d), E(e,F(f)) ) 深度優(yōu)先 （ 前序 ） 結(jié)果為 （ 共享元素按不同元素列出 ） ： a, c, a, b, d, e, f 167。 所示的廣義表圖 ， 廣度優(yōu)先遍歷結(jié)果為： L A C D E B c d e a b 如果只訪問單元素 ， 則結(jié)果為： c d e a b 有時侯 ， 將共享元素做為不同出現(xiàn)列出 。 例如 ， 對 錯誤 ！ 未找到引用源 。 廣義表的遍歷 對廣義表的遍歷，如圖結(jié)構(gòu)類似，也有兩種方式：深度優(yōu)先和廣度優(yōu)先。 廣義表圖與樹相似 ， 只是 由于存在共享元素 ， 使得 廣義表圖中某些結(jié)點 的 “ 父親 ” 不唯一 。 顯然 ， 廣義表圖中畫出了廣義表的所有結(jié)點 。 錯誤 ！ 未找到引用源 。 廣義表邏輯圖 為了表達廣義表的邏輯結(jié)構(gòu)，這里用一種圖形來形象地表示廣義表，稱為廣義表圖。 ① A=( )：空表 ， 無頭 ， 無尾 ， 長度為 0， 深度為 1. ② B=(a,b,c)：單元素表 ， 頭為 a， 尾為 (b,c)， 長度為 3， 深度為 1. ③ C=(a, (b, c, a) )：非單元素表 ， 頭為 a， 尾為 ((b,c,d))， 長度為 2， 深度為 2. ④ D=(B, ((a,b), c ) )：非單元素表 ， 頭為 B， 尾為 ( ((a,b),c)) )，長度為 2， 深度為 3. ⑤ E=(a, E)：非單元素表 ， 頭為 a， 尾為 (E)， 長度為 2， 深度為 ∞ ， 事實上 ， E=(a, E) = (a, (a (,… ) ) )是個遞歸表 。 在同一個廣義表系列中 ， 相同字母表示同一對象 。 它們稱可追溯到同屬于某一廣義表的各廣義表的全體為一個廣義表系列 （ 或系列廣義表 ） 。 顯然 ， Ls的深度等于它中層號最大的元素的層號 。 層號相同者稱為 同層結(jié)點 。 ? 層： 對任一表 Ls， 我們稱 Ls為 Ls的第 1層 （ 層號為 1） ， Ls的各直接元素均為 Ls的第二層元素 （ 層號均為 2） 。 ? 深度： Ls的深度 Depth(Ls)遞歸地定義為： 0 ：若 Ls為單元素 Depth(Ls) = 1 ：若 Ls為空表 1 + MAXi (Depth(α i)) ：其它情況 從定義知 ， 廣義表的深度 ， 相當于廣義表表達式中括號的最大嵌套層數(shù) 。 顯然 ， 表尾一定是表 ， 但表頭不一定 。 ? 表頭 ：稱 Ls的第 1個元素為 Ls的表頭 。 ? 單元素 、 單元素表： 若數(shù)據(jù)元素為非表元素 （ 即 數(shù)據(jù)對象成員 ， 或說 簡單元素 ， 如基本數(shù)據(jù)類型 、 結(jié)構(gòu) /記錄等 ） ， 則稱其為 單元素； 若 Ls中的元素均為 單元素 ， 則稱其為 單元素表 。 ? 子表 ：若某廣義表 L的某元素結(jié)點 a本身也是一個廣義表 ，則稱 a為廣義表 L的子表 。 但若考慮到 α i的內(nèi)部結(jié)構(gòu) ， Ls 可能是非常復(fù)雜的 。 例如 ， 下面的 L = ((a,b), c, (d, (e)) ) 就是一個合法的廣義表表達式 。 di∈ D0或?qū)儆谀硰V義表 ， D0是數(shù)據(jù)對象 } R={LR} LR={di1, di | di∈ D, 1≤ i≤ n} 廣義表也常簡稱為表 。 基本概念 廣義表 (Lists)是一個二元組 Lists=(D, R) 其中 ， D={di | i=1, 2, … , n。 167。從各層元素各自具有的線性關(guān)系講，它應(yīng)該是線性表的拓廣；從元素的分層方面講，它有樹結(jié)構(gòu)的特點，但從元素的遞歸性和共享性等方面講，它應(yīng)該屬于圖結(jié)構(gòu)。 多元多項式的表示 167。 遍歷操作 167。 基本存儲方法 廣義表對象模型 * 167。 廣義表的復(fù)制與求尾 167。 167。 鏈式結(jié)構(gòu)的高級語言描述 167。 基本概念 167。 廣義表的存貯結(jié)構(gòu) 167。 廣義表操作的實現(xiàn) * 167。 結(jié)點對象 167。 分枝單鏈表對象 167。 167。 基本操作 167。 167。 廣義表元素接口 167。 一般問題 167。 廣義表的遍歷 167。 廣義表邏輯圖 167。 廣義表的串行化與逆串行化 167。 廣義表接口 167。 廣義表的邏輯結(jié)構(gòu) 167。 廣義表的分枝單鏈表對象 * 167。 廣義表結(jié)構(gòu)的應(yīng)用 167。 層次結(jié)構(gòu)的表示 第 8 章 廣義表 廣義表是一種特殊的結(jié)構(gòu)，它兼有線性表、樹、圖等結(jié)構(gòu)的特點?？傊?，它是一種更為復(fù)雜的非線性結(jié)構(gòu)。 廣義表的邏輯結(jié)構(gòu) 167。 n≥ 0。 通常 ， 廣義表記為 （ 稱為廣義表表達式 ） ： Ls=(α 1,α 2, … , α n) 其中 ， 每個 α i稱為 Ls的一個 直接元素 （ 也稱 α i直屬Ls） ， 其或為數(shù)據(jù)對象成員 ， 或為滿足本定義的廣義表 。 由上列定義知 ， 若不考慮 α i的內(nèi)部結(jié)構(gòu) ， 則 Ls是一種線性表 。 下面給出幾個相關(guān)概念 。 ? 長度 ：我們?nèi)匀环Q Ls中的元素個數(shù) （ 即各 αi的個數(shù) ， 不計αi內(nèi)部的元素個數(shù) ） 為廣義表 Ls的 長度 ， 它與線性表的長度的概念是相同的 。 ? 空表 ：表內(nèi)無元素 （ 長度為 0） 的表稱為空表 。 ? 表尾 ：稱 Ls中除去表頭后其余元素構(gòu)成的表為表尾 。 ? 遞歸表 : 若表 Ls中某成員含有自己 (即 Ls)， 則稱 Ls為遞歸表 。 這里的定義 ， 為了遞歸 ， 我們將單元素也看作表 。對任意其他元素 x，它的直接元素的層號就等于它的層號加 1。 在這個定義中 ， 我們將 不同出現(xiàn) （ 是不同時出現(xiàn)嗎 ？？？ 答：正確 ， 是指不同位置的出現(xiàn) ） 的相同元素也看作是不同元素 ， 因此 ， 同一個對象 ， 就可能有不同的層號 。 ? 系列廣義表 ：由于廣義表的元素往往也是廣義表 ， 所以需要一同考慮 。 下面的敘述中 ， 我們用大寫字母表示具體的廣義表 ， 用小寫字母代表數(shù)據(jù)對象的成員 （ 單元素 ） 。 下面給出了一個廣義表系列 。 有時 ， 為了強調(diào)廣義表名稱 ， 可將表名寫在表的左括號前面 ， 如上例中的 D可寫為： D( B(a, b, c), F( G(a, b), c) ) 167。設(shè)廣義表為 L(A1,A2, … , An)，則它的廣義表圖形成方法為： n 畫一結(jié)點，標為 L，稱其為廣義表 L的根； n 對每個 Ai，若其為單元素，則畫一個結(jié)點，標為 Ai的值（或值的名稱），稱該結(jié)點為終結(jié)結(jié)點，其即為 Ai的根； n 對每個 Ai，若其為子表，則按該規(guī)則畫出 Ai的廣義表圖； n 從 L的根到各 Ai的根分別畫一條邊，將各 Ai的根連在一起。 給出了廣義表圖的一個例子 。 圖中結(jié)點之間的邊表示 “ 包含 /屬于 ” 關(guān)系 ， 即若結(jié)點 A到 B有邊 ，則表示 B是 A的子表之一 （ A包含 B） 。 L A C D E B a b c d e 圖 80 廣義表 L（見下式） 的邏輯圖 L(A(B(a,b)), C(B(a,b), c), D(c,d,e), E(e) ) 167。具體遍歷方式是把廣義表對應(yīng)的廣義表圖看作圖結(jié)構(gòu)，在該圖結(jié)構(gòu)上進行相應(yīng)的遍歷。 所示的廣義表圖 ， 深度優(yōu)先遍歷結(jié)果為： L A B a b C c D d e E 如果只訪問單元素 ， 則結(jié)果為： a b