數(shù)據(jù)結(jié)構(gòu)chapter5數(shù)組和廣義表-資料下載頁
2025-05-09 01:00本頁面
【正文】 )= (D,F) a tail(B)= (B) 任何一個非空廣義表其 表頭可能是原 子或廣義表，而其表尾必定為廣義表 。 35 數(shù) 據(jù) 結(jié) 構(gòu) 廣義表 第 5 章 數(shù)組和廣義表 結(jié)構(gòu)特點： 1） 廣義表中的數(shù)據(jù)元素有 相對次序 ； 2）廣義表的 長度 定義為 最外層包含元素個數(shù) ； 3） 廣義表的 深度 定義為所含 括弧的重數(shù) ； 4） 廣義表可以 共享 ； 5） 廣義表可以是一個 遞歸的表 。 遞歸表的 深度是無窮值 ， 長度是有限值。 注意：“原子”的深度為 0 “空表”的深度為 1 36 數(shù) 據(jù) 結(jié) 構(gòu) 廣義表 第 5 章 數(shù)組和廣義表 存儲方式： 由于廣義表 (a1,a2,a3,…an) 中的數(shù)據(jù)元素可以具有不同的結(jié)構(gòu)，（或是原子，或是廣義表），因此，難以用順序存儲結(jié)構(gòu)表示，通常采用 鏈式存儲結(jié)構(gòu) 來表示。 ① 頭、尾鏈表存儲結(jié)構(gòu)； ② 擴展線性鏈表存儲結(jié)構(gòu)。 37 數(shù) 據(jù) 結(jié) 構(gòu) 廣義表 第 5 章 數(shù)組和廣義表 存儲方式： ① 頭、尾鏈表存儲結(jié)構(gòu) 每個元素用一個結(jié)點表示 ,需要用兩種結(jié)構(gòu)的結(jié)點 : 表結(jié)點 原子結(jié)點 標(biāo)志域 表頭指針 表尾指針 tag=1 hp tp 標(biāo)志域 值域 tag=0 atom typedef enum {ATOM, LIST} ElemTag。 typedef struct GLNode { ElemTag tag。 union { AtomType atom。 struct { struct GLNode*hp,*tp。 }htp。 }atom_htp。 }GLNode,*GList。 38 數(shù) 據(jù) 結(jié) 構(gòu) 廣義表 第 5 章 數(shù)組和廣義表 存儲方式： ① 頭、尾鏈表存儲結(jié)構(gòu) 分析方法： 表頭、表尾分析 若表頭為原子，則用 原子結(jié)點 : 空表 L=NIL ( L為頭指針 ) 非空表 L 指向表頭 指向表尾 否則用表結(jié)點 。表尾總是用表結(jié)點或空 。 子表結(jié)構(gòu)依次類推。 tag=1 tag=0 atom 39 數(shù) 據(jù) 結(jié) 構(gòu) 廣義表 第 5 章 數(shù)組和廣義表 存儲方式： ① 頭、尾鏈表存儲結(jié)構(gòu) 分析方法： 表頭、表尾分析 例如 : A = ( ) B = (e) C = (a,(b,c,d)) D = (A, B, C) E = (a, E) = (a, (a, (a, ??? , ) ) ) A=NIL B 0 e ? 1C 0 a 1 1 1 ∧ 0 b 10 c 10 d ∧40 數(shù) 據(jù) 結(jié) 構(gòu) 廣義表 第 5 章 數(shù)組和廣義表 存儲方式： ① 頭、尾鏈表存儲結(jié)構(gòu) 分析方法： 表頭、表尾分析 D 1 ∧ 1B 0 e ? 11 1 E 0 a ? 0 a 1 1 1 ∧ 0 b 10 c 10 d ∧C 41 數(shù) 據(jù) 結(jié) 構(gòu) 廣義表 第 5 章 數(shù)組和廣義表 存儲方式： ① 頭、尾鏈表存儲結(jié)構(gòu) 分析方法： 子表分析 非空表 1 1 ls … 指向子表 1 指向子表 2 指向子表 n 1 ? 若子表為原子，則為 否則，為表結(jié)點，依次類推。 tag=0 atom 42 數(shù) 據(jù) 結(jié) 構(gòu) 廣義表 第 5 章 數(shù)組和廣義表 存儲方式： ① 頭、尾鏈表存儲結(jié)構(gòu) 分析方法： 子表分析 例如 : L=(a,(x,y),((x))) L 1 1 1 ∧ a 0 1 1 ∧ x 0 y 0 1 ∧ 1 ∧ 43 數(shù) 據(jù) 結(jié) 構(gòu) 廣義表 第 5 章 數(shù)組和廣義表 存儲方式： ② 擴展線性鏈表存儲結(jié)構(gòu) 表結(jié)點 原子結(jié)點 標(biāo)志域 表頭指針 表尾指針 tag=1 hp tp 標(biāo)志域 值域 tag=0 atom 表尾指針 tp typedef enum {ATOM, LIST} ElemTag。 typedef struct GLNode { ElemTag tag。 union { AtomType atom。 struct GLNode*hp。 }atom_htp。 struct GLNode *tp。 }GLNode,*GList。 44 數(shù) 據(jù) 結(jié) 構(gòu) 作業(yè) 第 5 章 數(shù)組和廣義表 P146. ， ， ， ，
法律信息相關(guān)推薦
鄂ICP備17016276號-1