數(shù)據(jù)結(jié)構(gòu)課件：廣義表的概念及存儲結(jié)構(gòu)

廣義表的

概念及存儲結(jié)構(gòu)

本講要點(diǎn)哪些實(shí)際問題可以抽象成廣義表結(jié)構(gòu)？什么是廣義表？廣義表如何存儲？導(dǎo)學(xué)案例：本科生創(chuàng)新實(shí)踐項(xiàng)目中的人員關(guān)系為培養(yǎng)本科生的綜合實(shí)踐與研究創(chuàng)新能力，從國家到各高校都實(shí)施了大學(xué)生創(chuàng)新實(shí)踐項(xiàng)目。在項(xiàng)目實(shí)施過程中，教師指導(dǎo)n個本科生，如果教師是碩導(dǎo)或博導(dǎo)，本科生可接收教師的直接指導(dǎo)，部分本科生也可以在碩士研究生或博士研究生的指導(dǎo)下進(jìn)行項(xiàng)目研究。本科生創(chuàng)新實(shí)踐項(xiàng)目中的人員關(guān)系具有如下形式：（1）若導(dǎo)師不帶研究生：

(導(dǎo)師,(本科生1,…,本科生k))（2）若導(dǎo)師帶研究生：

(導(dǎo)師,((研究生1,(本科生1,…,本科生m)),(本科生1,…,本科生n),…))請?jiān)O(shè)計(jì)一種數(shù)據(jù)結(jié)構(gòu)，存儲以上人員關(guān)系，為簡單起見，各類人員信息僅保留姓名。1.問題抽象(本科生1,…,本科生k)是一個線性表(導(dǎo)師,(本科生1,…,本科生k))是一個擴(kuò)充的線性表數(shù)據(jù)元素是一個線性表單個數(shù)據(jù)元素(導(dǎo)師,(研究生1,(本科生1,…,本科生m)))也是一個擴(kuò)充的線性表數(shù)據(jù)元素是一個線性表數(shù)據(jù)元素是一個線性表單個數(shù)據(jù)元素1.問題抽象(導(dǎo)師,(研究生1,(本科生1,…,本科生m))，(本科生1,…,本科生n),…))也是一個擴(kuò)充的線性表(本科生1,…,本科生k)(導(dǎo)師,(本科生1,…,本科生k))(導(dǎo)師,(研究生1,(本科生1,…,本科生m)))這種對線性表中數(shù)據(jù)元素進(jìn)行擴(kuò)充，但元素類型可以不同的線性表就是廣義表屬于一種非線性結(jié)構(gòu)。線性表及相關(guān)形式運(yùn)算受限元素受限元素?cái)U(kuò)展2.廣義表的基本概念廣義表：n（n≥0）個數(shù)據(jù)元素的有限序列，記作：GList＝(a1，a2，……，an)其中：GList是廣義表的名稱，ai（1≤i≤n）是GList的成員（或直接元素），它可以是單個的數(shù)據(jù)元素，也可以是一個廣義表，分別稱為GList的單元素（或原子）和子表。長度：廣義表中直接元素的個數(shù)。深度：廣義表中括號的最大嵌套層數(shù)。表頭：廣義表非空時(shí)，稱第一個元素為表頭。表尾：廣義表中除表頭外其余元素組成的廣義表。表頭、表尾概念的重要性體現(xiàn)在，它們既是廣義表的元素存取方法、廣義表的分解方法，也暗示了廣義表的構(gòu)造方法。2.廣義表的基本概念A(yù)＝()B＝(a,b,c)C＝(a,(b,c,d),e)D＝((a,b),c,(d,(e,f),g))E＝(a,(),((),()),b)長度深度表頭表尾01空()31a(b,c)32a((b,c,d),e)33(a,b)(c,(d,(e,f),g))43a((),((),()),b)3.廣義表的存儲結(jié)構(gòu)廣義表可以采用順序存儲結(jié)構(gòu)嗎？由于廣義表的非線性特征，且定義中對各個子表的長度沒有任何限制，因此若試圖采用順序存儲結(jié)構(gòu)，必將引入許多繁雜的人為約束，使廣義表的存儲、應(yīng)用復(fù)雜化。所以廣義表一般采用鏈?zhǔn)酱鎯Y(jié)構(gòu)。如何采用鏈接存儲結(jié)構(gòu)存儲廣義表？若廣義表不空，則可分解為表頭和表尾；反之，一對確定的表頭和表尾可唯一地確定一個廣義表。

采用頭尾表示法存儲廣義表3.廣義表的存儲結(jié)構(gòu)廣義表中的數(shù)據(jù)元素既可以是廣義表也可以是單元素頭尾表示法中的結(jié)點(diǎn)結(jié)構(gòu)？

表結(jié)點(diǎn)——存儲廣義表；元素結(jié)點(diǎn)——存儲單元素3.廣義表的存儲結(jié)構(gòu)A＝()B＝(a,b,c)C＝(a,(b,c,d),e)D＝((a,b),c,(d,(e,f),g))E＝(a,(),((),()),b)3.廣義表的存儲結(jié)構(gòu)A＝()B＝(a,b,c)C＝(a,(b,c,d),e)D＝((a,b),c,(d,(e,f),g))E＝(a,(),((),()),b)3.廣義表的存儲結(jié)構(gòu)A＝()B＝(a,b,c)C＝(a,(b,c