數(shù)據(jù)結(jié)構(gòu)chapter5數(shù)組和廣義表(參考版)
2025-05-13 01:00本頁面
【正文】 44 數(shù) 據(jù) 結(jié) 構(gòu) 作業(yè) 第 5 章 數(shù)組和廣義表 P146. ， ， ， ， 。 struct GLNode *tp。 struct GLNode*hp。 typedef struct GLNode { ElemTag tag。 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é)點，依次類推。表尾總是用表結(jié)點或空 。 }GLNode,*GList。 }htp。 union { AtomType atom。 37 數(shù) 據(jù) 結(jié) 構(gòu) 廣義表 第 5 章 數(shù)組和廣義表 存儲方式： ① 頭、尾鏈表存儲結(jié)構(gòu) 每個元素用一個結(jié)點表示 ,需要用兩種結(jié)構(gòu)的結(jié)點 : 表結(jié)點 原子結(jié)點 標志域 表頭指針 表尾指針 tag=1 hp tp 標志域 值域 tag=0 atom typedef enum {ATOM, LIST} ElemTag。 注意：“原子”的深度為 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) 來表示。 35 數(shù) 據(jù) 結(jié) 構(gòu) 廣義表 第 5 章 數(shù)組和廣義表 結(jié)構(gòu)特點： 1） 廣義表中的數(shù)據(jù)元素有 相對次序 ； 2）廣義表的 長度 定義為 最外層包含元素個數(shù) ； 3） 廣義表的 深度 定義為所含 括弧的重數(shù) ； 4） 廣義表可以 共享 ； 5） 廣義表可以是一個 遞歸的表 。 表頭與表尾： LS不為空時，稱 d1為表頭 (head)， 稱 其余元素組成的子表 ( d2, d3， ???,dn ) 為表尾 (tail)。 row col value right down 32 數(shù) 據(jù) 結(jié) 構(gòu) 特殊矩陣的壓縮存儲 第 5 章 數(shù)組和廣義表 稀殊矩陣： ② 十字鏈表 的舉例 row col value down right 3 0 0 5 0 1 0 0 8 0 0 7 M= 1 1 3 1 4 5 2 2 1 ∧ ∧ 3 1 8 ∧ ∧ 3 4 7 ∧ ∧ 33 數(shù) 據(jù) 結(jié) 構(gòu) 廣義表 第 5 章 數(shù)組和廣義表 概念： 是 n=0個元素的有限序列 ，記作 LS = ( d1, d2, ???,dn ) 其中： di 或為 原子項 (原子，一般用小寫字母表示 ) 或為 廣義表 (子表，一般用大寫字母表示 )， n 為廣義表的長度。 int m,n,len。 }OLNode,* OLink。 int value。 row col value down right 每一行和每一列的頭指針，用兩個一維指針數(shù)組來存放。 right：用于鏈接同一 行 中的下一個元素； down：用于鏈接同一 列 中的下一個元素。 } col 1 2 3 4 5 num[col] 0 0 0 0 0 1 121 1position[col] 1 2 4 4 5 1 2 14 2 2 7 3 1 36 3 4 28 1
法律信息相關(guān)推薦
鄂ICP備17016276號-1