數(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é)

以上是生活随笔為你收集整理的算法导论之数据结构的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。