[工學(xué)]第5章數(shù)組和廣義表-資料下載頁(yè)
2024-10-19 00:24本頁(yè)面
【正文】 。 由表頭、表尾的定義易知：任何一個(gè)非空列表 其表頭可能是原子，也可能是列表，而其表尾必定 是列表。 廣義表的長(zhǎng)度：表中元素的個(gè)數(shù)，深度：層次數(shù)，即括號(hào)的個(gè)數(shù)。例如： ① A = ( )—— A是一個(gè)空表，它的長(zhǎng)度為零，深度為 1。 ② B = (e)—— 列表 B只有一個(gè)原子 e， B的長(zhǎng)度為 1，深度也為 1。 ③ C = (a, (b, c, d))—— 列表 C的長(zhǎng)度為 2，深度為 2，兩個(gè)元素分 別為原子 a和子表 (b, c, d)。 ④ D = (A, B, C)—— 列表 D的長(zhǎng)度為 3，深度為 1， 3個(gè)元素都是 列表。將子表的值帶入后，則有 D = (( ), (e), (a, (b, c, d)))。 ⑤ E = (a, E)—— 這是一個(gè)遞歸的表，它的長(zhǎng)度為 2，深度為 ∞。 E相當(dāng)于一個(gè)無(wú)限的列表 E = (a, (a, (a, …))) 。 （ 2）廣義表的抽象數(shù)據(jù)類(lèi)型定義 ADT GList { 數(shù)據(jù)對(duì)象： D={ ei| i=1,2,…,n ； n≥0； ei∈ AtomSet 或 ei∈ GList。} 數(shù)據(jù)關(guān)系： R1＝ { ei1, ei |ei1, ei ∈ D, 2≤i≤n} 基本操作： InitGList (amp。L)。 操作結(jié)果：創(chuàng)建空的廣義表 L。 CreateGList(amp。L, S)。 初始條件： S是廣義表的書(shū)寫(xiě)形式串。 操作結(jié)果：由 S創(chuàng)建廣義表 L。 DestroyGList(amp。L)。 初始條件：廣義表 L已存在。 操作結(jié)果：銷(xiāo)毀廣義表 L。 CopyGList(amp。T, L)。 初始條件：廣義表 L已存在。 操作結(jié)果：由廣義表 L復(fù)制得到廣義表 T。 GListLength(L)。 初始條件：廣義表 L已存在。 操作結(jié)果：求廣義表 L的長(zhǎng)度，即元素個(gè)數(shù)。 GListDepth(L)。 初始條件：廣義表 L已存在。 操作結(jié)果：求廣義表 L的深度。 GListEmpty(L)。 初始條件：廣義表 L已存在。 操作結(jié)果：判定廣義表 L是否為空。 GetHead(L)。 初始條件：廣義表 L已存在。 操作結(jié)果：取廣義表 L的頭。 GetTail(L)。 初始條件：廣義表 L已存在。 操作結(jié)果：取廣義表 L的尾。 InsertFirst_GL(amp。L, e)。 初始條件：廣義表 L已存在。 操作結(jié)果：插入元素 e作為廣義表 L的第一個(gè)元素。 DeleteFirst_GL (amp。L, amp。e)。 初始條件：廣義表 L已存在。 操作結(jié)果：刪除廣義表 L的第一個(gè)元素，并用 e返回其值。 Traverse_GL(L, visit())。 初始條件：廣義表 L已存在。 操作結(jié)果：遍歷廣義表 L，用函數(shù) visit處理每個(gè)元素， }ADT GList ① 列表的元素可以是子表，而子表的元素還可以 是子表 …… 故，列表是一個(gè)多層次的結(jié)構(gòu)。如圖 示的列表 D。圖中圓圈表示列表，以方塊表示原子。 ② 列表可為其他列表所共享。 ③ 列表可以是一個(gè)遞歸的表，即列表也可以是其 本身的一個(gè)子表。 （ 3） 3個(gè)重要結(jié)論： D A B C E e a b c d 圖 列表的圖形表示 廣義表的存儲(chǔ)結(jié)構(gòu) 因?yàn)閺V義表的數(shù)據(jù)元素是不定的，所以通常采用鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)來(lái)表示。 （ 1）頭尾鏈表存儲(chǔ)表示 ① 結(jié)點(diǎn)結(jié)構(gòu) 原子結(jié)點(diǎn) tag = 0 atom tag = 1 hp tp 表結(jié)點(diǎn) tag：標(biāo)志域。 tag＝ 1表示表結(jié)點(diǎn)； tag＝ 0表示原子結(jié)點(diǎn)。 hp：指示表頭的指針域。 tp：指示表尾的指針域。 atom：值域。 ② C語(yǔ)言描述 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。 //atom是原子結(jié)點(diǎn)的值域， AtomType由用戶定義 struct {struct GLNode *hp, *tp。} ptr。 //ptr是表結(jié)點(diǎn)的指針域， 和表尾 }。 } *GList。 ③ 圖形表示 例 1， D = (A, B, C)，其中 A = ( )， B = (e)， C = (a, (b, c, d))。如圖 (a)所示。 例 2， E = (a, E) 。如圖 (b)所示。 A = NULL (b) 廣義表的鏈表表示 —— 遞歸表（ P109 圖 ) 0 b 0 c 0 d D 1 1 1 B 1 C 1 1 0 e 0 a 1 1 1 (a) 例 1 E 1 1 0 a 圖 廣義表的存儲(chǔ)結(jié)構(gòu)示例 ④ 特點(diǎn) 1．除空表的表頭指針為空外，對(duì)任何非空表，其表頭指針均指向一個(gè)表結(jié)點(diǎn)。 2．容易分清列表中原子和子表所在層次。 3．最高層的表結(jié)點(diǎn)個(gè)數(shù)即為列表的長(zhǎng)度。 （ 2）擴(kuò)展性鏈表存儲(chǔ)表示 ① 結(jié)點(diǎn)結(jié)構(gòu) tag = 1 hp tp 表結(jié)點(diǎn) tag = 0 atom tp 原子結(jié)點(diǎn) tag：標(biāo)志域。 tag＝ 1表示表結(jié)點(diǎn)； tag＝ 0表示原子結(jié)點(diǎn)。 hp：指示表頭的指針域。 tp：指示表尾的指針域。 atom：值域。 ② C語(yǔ)言描述 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。 //atom是原子結(jié)點(diǎn)的值域， AtomType由用戶定義 struct GLNode *hp。 //表結(jié)點(diǎn)的表頭指針 }。 struct GLNode *tp。 //相當(dāng)于線性鏈表的 next，指向下一個(gè)元素結(jié)點(diǎn) } *GList。 //廣義表類(lèi)型 GList是一種擴(kuò)展的線性鏈表 ③ 圖形表示 A 1 D 1 0 b 0 c 0 d 1 1 1 B 1 C 1 0 e 0 a 1 0 a 1 E
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號(hào)-1