算法导论之数据结构
數(shù)據(jù)結(jié)構(gòu)
集合,是數(shù)學(xué)也是計(jì)算機(jī)科學(xué)的基礎(chǔ),在表示和操縱有窮、動(dòng)態(tài)集合上,動(dòng)態(tài)集合中每個(gè)元素由對象來表示,并有指向?qū)ο蟮闹羔?。對?dòng)態(tài)集合的操作分為兩類:查詢和修改,操作以指針為導(dǎo)航,涉及元素對象內(nèi)的關(guān)鍵字和衛(wèi)星數(shù)據(jù)。
數(shù)據(jù)結(jié)構(gòu)和動(dòng)態(tài)集合的關(guān)系,可以這么理解,把集合中的元素根據(jù)相互間關(guān)系用某種結(jié)構(gòu)組織起來,方便查詢和修改。數(shù)據(jù)結(jié)構(gòu)是指相互之間存在一種或多種特定關(guān)系的數(shù)據(jù)元素的集合,是計(jì)算機(jī)存儲(chǔ)和數(shù)據(jù)組織的方式,是邏輯上的。
1.1基礎(chǔ)數(shù)據(jù)結(jié)構(gòu)
指針,在編程世界中,扮演著一個(gè)很重要的角色。指針,是一個(gè)變量,指向存儲(chǔ)地址,指向存儲(chǔ)的值。通過指針來表示動(dòng)態(tài)集合的數(shù)據(jù)結(jié)構(gòu),包括棧、隊(duì)列、鏈表及樹。
棧的后進(jìn)先出和隊(duì)列的先進(jìn)先出并未太多可著筆之處,日常應(yīng)用時(shí),較多關(guān)注所分配空間的管理,避免溢出。數(shù)組是用下標(biāo)來表示線性,而鏈表則是用對象中的指針。鏈表有單、雙、環(huán)形等特性,主要是根據(jù)指針的指向來定義。
在不提供指針和對象數(shù)據(jù)類型的語言中,可以通過二維數(shù)組來表示鏈表,隊(duì)列和棧也是一樣。一般一維用來存儲(chǔ)位置,下標(biāo),另一維刻畫前后指針和關(guān)鍵字值(也可包括衛(wèi)星數(shù)據(jù))。
對于樹,二叉樹和k節(jié)點(diǎn)樹,都可分別用指針和數(shù)組來表示。
1.2散列表
散列表是集合域之間,通過散列函數(shù)構(gòu)造映射的一種數(shù)據(jù)結(jié)構(gòu)??梢园哑胀〝?shù)組理解為一個(gè)全域映射的散列表,存儲(chǔ)空間允許下,可直接尋址。但一般情況下,全域映射所分配的存儲(chǔ)空間是浪費(fèi),于是構(gòu)造散列表,將關(guān)鍵字域映射到散列表的槽中。散列映射,最大的問題是碰撞,就是兩個(gè)關(guān)鍵字通過散列函數(shù)獲得了相同的散列值,從而歸到同一個(gè)槽位。
解決碰撞,除了構(gòu)造優(yōu)秀散列函數(shù),還可通過鏈接法來解決。所謂鏈接法,就是把散列到同一槽位的所有元素按照鏈表串聯(lián)起來,即每一個(gè)槽位存儲(chǔ)不是單個(gè)對象,而是一個(gè)鏈表。對于待鏈接的散列表,其
對于構(gòu)造散列函數(shù),提出好的散列函數(shù)特點(diǎn):應(yīng)近似地滿足簡單一致散列的原則,即n個(gè)關(guān)鍵字中每個(gè)關(guān)鍵字等可能地散列到m個(gè)槽位的任何一個(gè)中,且與其他關(guān)鍵字已被散列的槽位無關(guān)。一般很難滿足這個(gè)原則,因?yàn)橐话汴P(guān)鍵字的分布未知,且不可能完全相互獨(dú)立。
構(gòu)造散列函數(shù)一般有關(guān)鍵字映射為自然數(shù)、除法散列法(質(zhì)數(shù))、乘法散列法(字長位數(shù))、全域散列等。全域散列是提供有限的一組散列函數(shù),將給定的關(guān)鍵字域n個(gè)元素映射到m個(gè)槽中,這個(gè)函數(shù)組就是全域的,而全域散列就是可以隨機(jī)從這組函數(shù)中選擇散列函數(shù),獨(dú)立于存儲(chǔ)的關(guān)鍵字。假設(shè)k和l是關(guān)鍵字域中的元素,且不相同,使h(k)=h(l)出現(xiàn)的散列函數(shù),即k和l發(fā)生碰撞的概率小于1/m。文中提出利用質(zhì)數(shù)和模來構(gòu)造全域散列函數(shù)類。
解決映射碰撞,除了鏈接法還有開放尋址法。所謂開放尋址法,就是不設(shè)定映射域大小,而是根據(jù)關(guān)鍵字動(dòng)態(tài)增長,把所有元素都放在散列表中。當(dāng)要插入一個(gè)元素時(shí),連續(xù)地探查散列表中的各項(xiàng),直到找到一個(gè)空槽來存放,當(dāng)然如果槽位已滿,則擴(kuò)展。開放尋址法,插入、刪除、查找元素都要處理空槽,即槽位中沒有包含動(dòng)態(tài)集合中元素的可能。開放尋址法通過線性探查、二次探查、雙重探查來檢查散列表,尋找操作所需的項(xiàng)。線性探查就是定位到散列表中某個(gè)具體項(xiàng),然后循環(huán)一圈;二次探查是在此基礎(chǔ)上增加偏移量;這兩者性能取決于初始探查位置和偏移量的選擇,會(huì)導(dǎo)致群集現(xiàn)象出現(xiàn)。群集現(xiàn)象是指隨著時(shí)間的推移,連續(xù)被占用的槽不斷增加,平均查找時(shí)間也隨著不斷增加。雙重探查則對初始探查位置和偏移量都設(shè)立函數(shù)(自變量都為關(guān)鍵字),使之可變,具有隨機(jī)產(chǎn)生探查序列的性質(zhì)。
文中對散列的描述,從散列表定義,到構(gòu)造散列函數(shù)的方法,接著引入解決碰撞沖突的鏈表法和開放尋址法,并對相關(guān)操作進(jìn)行性能分析。對于如何構(gòu)造好的散列函數(shù),以及如何解決沖突是散列表的關(guān)鍵。在解決沖突上,對于固定、靜態(tài)的關(guān)鍵字集合,可以采用完全散列。完全散列是將第一次散列映射出現(xiàn)沖突的關(guān)鍵字,再進(jìn)行二次散列,確保不出現(xiàn)碰撞。顯然,很關(guān)鍵就是兩次散列函數(shù)的選擇。
對于散列,發(fā)現(xiàn)CSDN博客有一篇博文介紹的比較全面,還有代碼驗(yàn)證性能,很有參考價(jià)值。
http://blog.csdn.net/jn1158359135/article/details/7205688
1.3二叉樹
二叉樹在數(shù)據(jù)組織上來說,有一種技術(shù)的藝術(shù)美,在樹形視圖結(jié)構(gòu)中運(yùn)算。導(dǎo)論中,二叉樹介紹了二叉查找樹、紅黑樹以及B樹。
1)二叉查找樹
二叉查找樹,二叉樹結(jié)構(gòu),可用鏈表結(jié)構(gòu)表示,每個(gè)節(jié)點(diǎn)存儲(chǔ)一個(gè)對象。結(jié)點(diǎn)中除了數(shù)據(jù)域(含key和衛(wèi)星數(shù)據(jù)),還包括左域left、右域right、父域parent,分別指向結(jié)點(diǎn)在樹中的左子、右子及父結(jié)點(diǎn)。
二叉查找樹按照數(shù)據(jù)域中關(guān)鍵字的順序來存儲(chǔ),滿足以下性質(zhì):
設(shè)x為二叉查找樹種的一個(gè)結(jié)點(diǎn),如y為x的左子樹中的一個(gè)節(jié)點(diǎn),則key[y]<=key[x],如y是為x的右子樹中的一個(gè)節(jié)點(diǎn),則key[y]>=key[x]。即結(jié)點(diǎn)左樹小于結(jié)點(diǎn),右樹大于結(jié)點(diǎn)。
二叉查找樹的查詢就圍繞這個(gè)性質(zhì)進(jìn)行,查找指定值、最小、最大、前趨、后續(xù),在一個(gè)高度為h的二叉查找樹種進(jìn)行查詢,運(yùn)行時(shí)間為O(h)。
二叉查找樹的插入和刪除,都是在二叉樹中結(jié)點(diǎn)發(fā)生變化,需要保持二叉查找樹右大于左的性質(zhì)。插入和刪除的動(dòng)態(tài)集合操作運(yùn)行時(shí)間也為O(h)。
導(dǎo)論中介紹了隨機(jī)構(gòu)造二叉查找樹,并通過隨機(jī)變量概率分析證明其期望高度為O(lgn),其中n為結(jié)點(diǎn)數(shù)。理解隨機(jī)構(gòu)造二叉查找樹,主要是要理解輸入的關(guān)鍵字隊(duì)列中任何一個(gè)關(guān)鍵字都等可能成為根節(jié)點(diǎn),而不同的根節(jié)點(diǎn),在保持二叉查找樹性質(zhì)下,將構(gòu)造出不同的高度的樹,且這個(gè)數(shù)的期望高度是O(lgn)。隨機(jī)構(gòu)造,也就是從關(guān)鍵字中等可能選擇一個(gè)節(jié)點(diǎn)開始構(gòu)造。
2)紅黑樹
紅黑樹也是一棵二叉查找樹,只是在每個(gè)節(jié)點(diǎn)上增加一個(gè)存儲(chǔ)域表示節(jié)點(diǎn)的顏色。構(gòu)造紅黑樹的目的是克服二叉查找樹在樹高度較高時(shí)性能不佳而變形,通過對任何一條從根到葉子的路徑上各個(gè)結(jié)點(diǎn)著色方式的限制,確保沒有一條路徑比其他路徑長出兩倍,使其接近平衡。
紅黑樹每個(gè)節(jié)點(diǎn)包括五個(gè)域:數(shù)據(jù)域key、左域left、右域right、父域parent、顏色域color,這個(gè)顏色域就是比二叉查找樹多處的域,那么可稱之為紅黑樹需滿足怎樣的性質(zhì)呢?
一顆二叉查找樹滿足:每個(gè)節(jié)點(diǎn)或紅或黑;根節(jié)點(diǎn)和葉子節(jié)點(diǎn)為黑色;如結(jié)點(diǎn)為紅色,則其左右兒子都是黑色;對每個(gè)結(jié)點(diǎn),從該結(jié)點(diǎn)到其子孫結(jié)點(diǎn)的所有路徑上包含相同數(shù)目的黑結(jié)點(diǎn)。這些性質(zhì)保持了二叉樹的平衡性質(zhì),使在構(gòu)造二叉查找樹時(shí),避免出現(xiàn)樹高度最壞情況。
紅黑樹是在二叉查找樹基礎(chǔ)上擴(kuò)展的數(shù)據(jù)結(jié)構(gòu),在進(jìn)行動(dòng)態(tài)集合操作時(shí),在保持二叉查找樹的基礎(chǔ)上,還要保持自己的紅黑性質(zhì)。而要保持紅黑樹性質(zhì),最重要的算法就是旋轉(zhuǎn)。
旋轉(zhuǎn)是保持樹高度平衡的重要算法,以左旋來說,主要是將父節(jié)點(diǎn)調(diào)整到左節(jié)點(diǎn),而將右節(jié)點(diǎn)調(diào)整為父節(jié)點(diǎn),相應(yīng)將右節(jié)點(diǎn)的左子樹調(diào)整到原父節(jié)點(diǎn)的右子樹,這樣一來降低樹的高度。
紅黑樹的插入是在二叉查找樹插入基礎(chǔ)上,對新增節(jié)點(diǎn)著紅色。著紅色后可能會(huì)改變紅黑樹性質(zhì)中結(jié)點(diǎn)為紅色左右結(jié)點(diǎn)要是黑色的性質(zhì),即一個(gè)紅結(jié)點(diǎn)不能有紅色子女,于是需要調(diào)整著色并旋轉(zhuǎn)保持樹高度平衡。紅黑樹的刪除,如果是刪除紅色結(jié)點(diǎn)則不影響紅黑樹性質(zhì),但刪除黑色節(jié)點(diǎn),則要調(diào)整著色并旋轉(zhuǎn)。
具體算法也很有意思,鍛煉程序每個(gè)步驟的邏輯,可以具體代碼實(shí)現(xiàn)下。
紅黑樹是二叉查找樹數(shù)據(jù)結(jié)構(gòu)的擴(kuò)展,這種擴(kuò)展就是在基礎(chǔ)和標(biāo)準(zhǔn)的數(shù)據(jù)結(jié)構(gòu)中增加一些信息,用于既定場合。如紅黑樹增加了結(jié)點(diǎn)的顏色域;為了動(dòng)態(tài)順序統(tǒng)計(jì),導(dǎo)論中還給出紅黑樹增加size域,統(tǒng)計(jì)左右子樹的個(gè)數(shù),這樣就可以直接定位到具體結(jié)點(diǎn)的位置;為了支持區(qū)間數(shù)據(jù)維護(hù),在紅黑樹基礎(chǔ)上,擴(kuò)展區(qū)間域,每個(gè)結(jié)點(diǎn)的值是一個(gè)區(qū)間。
在一些實(shí)際應(yīng)用中,對基礎(chǔ)數(shù)據(jù)結(jié)構(gòu)的改進(jìn)基本都能滿足,因?yàn)榛A(chǔ)數(shù)據(jù)結(jié)構(gòu)已經(jīng)是經(jīng)過實(shí)踐累積出來的具有模型意義,具有很強(qiáng)的適應(yīng)性。當(dāng)然必要還是可以創(chuàng)新數(shù)據(jù)結(jié)構(gòu)來滿足。這個(gè)章節(jié)主要是描述,因?yàn)樵瓉矶加写a實(shí)現(xiàn)過具體算法,所以算法及分析沒有進(jìn)一步描述和理解。總結(jié)
- 上一篇: eclipse+adt下开发androi
- 下一篇: MapReduce基础开发之一词汇统计和