本部分總結(jié)在網(wǎng)站建設(shè)中數(shù)據(jù)結(jié)構(gòu)和算法，并討論在不同的情況下如何進(jìn)行選擇。

通用數(shù)據(jù)結(jié)構(gòu)：數(shù)組、鏈表、樹(shù)、哈希表

專用數(shù)據(jù)結(jié)構(gòu)：棧、隊(duì)列、優(yōu)先級(jí)隊(duì)列

排序：插入排序、希爾排序、快速排序、歸并排序、堆排序

圖：鄰接矩陣、鄰接表

外部存儲(chǔ)：順序存儲(chǔ)、索引文件、B-樹(shù)、哈希方法

1 通用數(shù)據(jù)結(jié)構(gòu)

若想存儲(chǔ)真實(shí)世界中的類似人事記錄、存貨目錄、合同表或銷售業(yè)績(jī)等數(shù)據(jù)，則只需要一般用途的數(shù)據(jù)結(jié)構(gòu)。在本書中屬于這種類型的結(jié)構(gòu)有數(shù)組、鏈表、樹(shù)和哈希表。他們被稱之為通用的數(shù)據(jù)結(jié)構(gòu)是因?yàn)樗鼈兺ㄟ^(guò)關(guān)鍵字的值來(lái)存儲(chǔ)并查找數(shù)據(jù)，這一點(diǎn)在通用數(shù)據(jù)庫(kù)程序中常見(jiàn)到(棧等特殊結(jié)構(gòu)正好相反，它們只允許存取一定的數(shù)據(jù)項(xiàng))。

1.1 速度與算法

通用數(shù)據(jù)結(jié)構(gòu)可以完全按照速度的快慢來(lái)分類:數(shù)組和鏈表是最慢的，樹(shù)相對(duì)較快，哈希表是最快的。

但是不要有這樣的結(jié)論:使用最快的結(jié)構(gòu)永遠(yuǎn)是最好的方案。這些最快的結(jié)構(gòu)也有缺陷。首先，它們的程序在不同程度上比數(shù)組和鏈表的復(fù)雜;其次，哈希表要求預(yù)先知道要存儲(chǔ)多少數(shù)據(jù)，數(shù)據(jù)對(duì)存儲(chǔ)空間的利用率也不是非常高。普通的二叉樹(shù)對(duì)順序的數(shù)據(jù)來(lái)說(shuō)，會(huì)變成緩慢的O(N)級(jí)操作，而平衡樹(shù)雖然避免了上述的問(wèn)題，但是它的程序編制起來(lái)卻比較困難。

處理器速度因素

快速的結(jié)構(gòu)都有缺陷，而計(jì)算機(jī)的另一個(gè)發(fā)展因素卻能使低速的結(jié)構(gòu)更加具有吸引力。新計(jì)算機(jī)的CPU和存取速度每一年都有提升。Moore定律聲明了CPU的速度每18個(gè)月翻一倍。這造成了早期計(jì)算機(jī)和現(xiàn)代應(yīng)用的計(jì)算機(jī)在性能方面的驚人差異，而且目前沒(méi)有任何理由能忍我這個(gè)增長(zhǎng)速度會(huì)減慢。

幾年前一臺(tái)電腦可以在一個(gè)可接受的時(shí)間內(nèi)處理100個(gè)對(duì)象的數(shù)組，而現(xiàn)在的計(jì)算機(jī)則快多了，因此可以在同樣的時(shí)間里處理含有10000個(gè)對(duì)象的數(shù)組。

請(qǐng)從簡(jiǎn)單數(shù)據(jù)結(jié)構(gòu)入手考慮:除非它們明顯是太慢了，否則就用數(shù)組或鏈表編寫程序，看看結(jié)構(gòu)究竟怎樣。如果能在一個(gè)可接受的時(shí)間內(nèi)運(yùn)行完畢，那么就采用它，不必再找別的。沒(méi)有人會(huì)留意用的是數(shù)組或別的什么結(jié)構(gòu)，為什么一定要拼命地寫出一個(gè)平衡樹(shù)的算法?甚至必須面對(duì)成千上萬(wàn)、百萬(wàn)的數(shù)據(jù)項(xiàng)進(jìn)行操作時(shí)，不妨先看一看數(shù)組或鏈表處理表現(xiàn)的情況，這也還是值得的。只有在實(shí)驗(yàn)中發(fā)現(xiàn)這些簡(jiǎn)單結(jié)構(gòu)的性能太慢時(shí)，才回過(guò)頭來(lái)采用哪些更加復(fù)雜的數(shù)據(jù)結(jié)構(gòu)。

Java引用的優(yōu)點(diǎn)

在操作對(duì)象的速度上，Java與其他語(yǔ)言相比有極大的優(yōu)勢(shì)，那是由于對(duì)于大多數(shù)數(shù)據(jù)結(jié)構(gòu)來(lái)說(shuō)，Java數(shù)據(jù)結(jié)構(gòu)只存儲(chǔ)引用而不是實(shí)際的對(duì)象，因此相對(duì)于那些在數(shù)據(jù)結(jié)構(gòu)中實(shí)際為對(duì)象開(kāi)辟了空間的語(yǔ)言來(lái)說(shuō)，大多數(shù)Java算法的執(zhí)行速度更快。在分析算法時(shí)，不是從對(duì)象的真實(shí)存儲(chǔ)空間出發(fā)，因而移動(dòng)對(duì)象的速度也不依賴于對(duì)象的大小，而只是考慮對(duì)象引用的移動(dòng)，因此對(duì)象本身的大小就不重要了。

數(shù)組

當(dāng)存儲(chǔ)和操作數(shù)據(jù)時(shí)，在大多數(shù)情況下數(shù)組是首先應(yīng)該考慮的結(jié)構(gòu)，數(shù)組在下列情況下很有用:

數(shù)據(jù)量較小

數(shù)據(jù)量的大小事先可預(yù)測(cè)

如果存儲(chǔ)空間足夠大的話，可以放松第二條，創(chuàng)建一個(gè)足夠大的數(shù)組來(lái)應(yīng)付所有可以預(yù)見(jiàn)的數(shù)據(jù)輸入。

如果插入速度很重要的話，使用無(wú)序數(shù)組，如果查找速度很重要的話，使用有序數(shù)組，并用二分查找。數(shù)組元素的刪除總是很慢，這是由于未來(lái)填充空出來(lái)的單元，平均半數(shù)以上的數(shù)組元素要被移動(dòng)，在有序數(shù)組中的遍歷是很快的，而在無(wú)序數(shù)組不支持這種功能。向量類是一種當(dāng)數(shù)據(jù)太滿時(shí)可以自己擴(kuò)展空間的數(shù)組，向量可以應(yīng)用于數(shù)據(jù)量不可預(yù)知的情況下，然而，在向量擴(kuò)充時(shí)，要將舊的數(shù)據(jù)拷入一個(gè)新的空間中，這一過(guò)程會(huì)造成程序明顯的周期性暫停。

鏈表

如果需要存儲(chǔ)的數(shù)據(jù)量不能預(yù)知或者需要頻繁地插入刪除數(shù)據(jù)元素時(shí)，考慮使用鏈表。當(dāng)有新的元素加入時(shí)，鏈表就開(kāi)辟新的所需要的空間，所以它甚至可以占滿全部可用的內(nèi)存;在刪除過(guò)程中，沒(méi)必要像數(shù)組那樣填補(bǔ)"空白"

在一個(gè)無(wú)序的鏈表中，插入是相當(dāng)快的，查找和刪除卻很慢，因此，與數(shù)組一樣，鏈表最好也應(yīng)用于數(shù)據(jù)量相對(duì)較小的情況。

對(duì)于編程而言，鏈表比數(shù)組復(fù)雜，但它比樹(shù)或哈希表簡(jiǎn)單。

二叉搜索樹(shù)

當(dāng)確認(rèn)數(shù)組和鏈表過(guò)慢時(shí)，二叉搜索樹(shù)是最先應(yīng)該考慮的結(jié)果，樹(shù)可以提供快速的O(logN)級(jí)的插入、查找和刪除。遍歷的時(shí)間復(fù)雜度是O(N)級(jí)的，這是任何數(shù)據(jù)結(jié)構(gòu)遍歷的大值(根據(jù)定義，必須訪問(wèn)所有的數(shù)據(jù))。對(duì)于遍歷一定范圍內(nèi)的數(shù)據(jù)可以很快得出訪問(wèn)數(shù)據(jù)的大值或最小值。

對(duì)于程序來(lái)說(shuō)，不平衡的二叉搜索樹(shù)要比平衡的二叉樹(shù)簡(jiǎn)單得多，但不幸的是，有序數(shù)據(jù)能將它的性能降至O(N)級(jí)，不比一個(gè)鏈表好多歲，然而如果可以保證數(shù)據(jù)是隨機(jī)進(jìn)入的，就不需要用平衡二叉樹(shù)。

平衡樹(shù)

在眾多平衡樹(shù)中，我們討論了紅黑樹(shù)和2-3-4樹(shù)，它們都是平衡樹(shù)，并且無(wú)論輸入數(shù)據(jù)是否有序，它們都能保證性能為O(logN)。然而對(duì)于實(shí)現(xiàn)來(lái)說(shuō)，平衡樹(shù)是很復(fù)雜的，特別是紅黑樹(shù)。如果利用樹(shù)的商用類，可以降低復(fù)雜性。

哈希表

哈希表在數(shù)據(jù)存儲(chǔ)結(jié)構(gòu)中速度最快，這使它成為計(jì)算機(jī)而不是人與數(shù)據(jù)交互時(shí)的必需。哈希表通常用于拼寫檢查器和作為計(jì)算機(jī)語(yǔ)言編譯器的符號(hào)表，這些應(yīng)用中，程序必須在幾分之一秒的時(shí)間里檢查上千的詞或符號(hào)。

哈希表對(duì)插入的順序并不敏感，因此可以取代平衡樹(shù)。但是哈希表的編程比平衡樹(shù)簡(jiǎn)單多了。

哈希表需要有額外的存儲(chǔ)空間，尤其是對(duì)于開(kāi)放地址法，因?yàn)楣１碛脭?shù)組作為基本結(jié)構(gòu)，所以，必須預(yù)先精確地知道待存儲(chǔ)的數(shù)據(jù)量。

用鏈地址法處理沖突的哈希表是最健壯的實(shí)現(xiàn)方法，若能預(yù)先精確地知道數(shù)據(jù)量，在這種情況下，用開(kāi)放地址法編程最簡(jiǎn)單，因?yàn)椴恍枰玫芥湵眍悺?/p>

哈希表并不能提供任何形式的有序遍歷，或?qū)Υ笾?、最小值進(jìn)行存取，如果這些功能很重要，使用二叉樹(shù)更好些。

通用數(shù)據(jù)存儲(chǔ)結(jié)構(gòu)的比較

2 專用數(shù)據(jù)結(jié)構(gòu)

專用數(shù)據(jù)結(jié)構(gòu)有棧、隊(duì)列和優(yōu)先級(jí)隊(duì)列。這些結(jié)構(gòu)不是為了用戶可訪問(wèn)的數(shù)據(jù)庫(kù)而建立的，通常用它們?cè)诔绦蛑休o助實(shí)現(xiàn)一些算法。

棧、隊(duì)列和優(yōu)先級(jí)隊(duì)列是抽象數(shù)據(jù)類型，它們由一些更加基礎(chǔ)的數(shù)據(jù)結(jié)構(gòu)如數(shù)組、鏈表或堆來(lái)實(shí)現(xiàn)。這些ADT只提供給用戶間的的接口，一般僅允許插入和訪問(wèn)或者刪除一個(gè)數(shù)據(jù)項(xiàng)。這些數(shù)據(jù)項(xiàng)是：

對(duì)于棧：最后被插入的數(shù)據(jù)項(xiàng)

對(duì)于隊(duì)列：最先被插入的數(shù)據(jù)項(xiàng)

對(duì)于優(yōu)先級(jí)隊(duì)列：具有高優(yōu)先級(jí)的數(shù)據(jù)項(xiàng)

棧

棧用在最后被插入數(shù)據(jù)項(xiàng)訪問(wèn)的時(shí)候，它是一個(gè)后進(jìn)先出的結(jié)構(gòu)。

棧往往通過(guò)數(shù)組或鏈表實(shí)現(xiàn)，通過(guò)數(shù)組實(shí)現(xiàn)很有效率，因?yàn)樽詈蟊徊迦氲臄?shù)據(jù)總是在數(shù)組的最后，這個(gè)位置的數(shù)據(jù)很容易被刪除。棧的溢出有可能出現(xiàn)，但當(dāng)數(shù)組的大小被合理規(guī)劃后，溢出并不常見(jiàn)，因?yàn)闂：苌贂?huì)擁有大量的數(shù)據(jù)。

如果棧擁有許多數(shù)據(jù)，并且數(shù)量不可精確預(yù)測(cè)(當(dāng)用棧實(shí)現(xiàn)遞歸時(shí))，用鏈表比數(shù)組更好一些，這是由于從表頭的位置刪除或插入一個(gè)元素很方便，除非整個(gè)內(nèi)存滿了，棧的溢出不可能出現(xiàn)。鏈表比數(shù)組稍慢一些，因?yàn)閷?duì)于插入一個(gè)新鏈結(jié)必須分配內(nèi)存，從表中某個(gè)鏈結(jié)點(diǎn)上刪除元素后回收分配內(nèi)存亦是必須的。

隊(duì)列

隊(duì)列用在只對(duì)最先被插入數(shù)據(jù)項(xiàng)訪問(wèn)的時(shí)候，它是一個(gè)先進(jìn)先出的結(jié)構(gòu)。

同棧相比，隊(duì)列同樣可以通過(guò)數(shù)組和鏈表實(shí)現(xiàn)，這兩種方法都很有效率。數(shù)組需要附加的程序來(lái)處理隊(duì)在數(shù)組尾部回繞的情況。鏈表必須是雙端的，這樣才能從一端插入到另一端刪除。

用數(shù)組還是鏈表來(lái)實(shí)現(xiàn)隊(duì)列的選擇是通過(guò)數(shù)據(jù)量是否可以被很好地預(yù)測(cè)來(lái)決定的，如果知道會(huì)有多少數(shù)據(jù)量的話，就使用數(shù)組，否則的話就用鏈表。

優(yōu)先級(jí)隊(duì)列

優(yōu)先級(jí)隊(duì)列用在只對(duì)訪問(wèn)高優(yōu)先級(jí)數(shù)據(jù)項(xiàng)訪問(wèn)的時(shí)候，高優(yōu)先級(jí)數(shù)據(jù)項(xiàng)就是含有大(有時(shí)最小)的關(guān)鍵字的項(xiàng)。

優(yōu)先級(jí)隊(duì)列可以用有序數(shù)組或堆來(lái)實(shí)現(xiàn)，向有序數(shù)組中插入是很慢的，但是刪除很快，使用堆來(lái)實(shí)現(xiàn)優(yōu)先級(jí)隊(duì)列，插入和刪除的時(shí)間復(fù)雜度都是O(logN)級(jí)

當(dāng)插入速度不重要時(shí)，可以使用數(shù)組或雙端鏈表，當(dāng)數(shù)據(jù)量可以被預(yù)測(cè)時(shí)，使用數(shù)組，當(dāng)數(shù)據(jù)量未知時(shí)，可以使用鏈表，如果速度很重要的話，選擇堆更好一些。

專用結(jié)構(gòu)的比較

3 排序

當(dāng)選擇數(shù)據(jù)結(jié)構(gòu)時(shí)，可以先嘗試一種較慢但簡(jiǎn)單的排序，例如插入排序。如果采用了這些方法，現(xiàn)代計(jì)算機(jī)的快速處理速度也有可能在恰當(dāng)?shù)臅r(shí)間內(nèi)將較大的數(shù)據(jù)量排序。

插入排序?qū)缀跻雅藕玫奈募埠苡行В绻麤](méi)有太多的元素處于亂序的位置上，操作的時(shí)間復(fù)雜度大約在O(N)級(jí)，這通常發(fā)生在往一個(gè)已排好序的文件中插入一些新的數(shù)據(jù)元素的情況。

如果插入排序顯得太慢，下一步可以嘗試希爾排序，它很容易實(shí)現(xiàn)，并且使用起來(lái)不會(huì)因?yàn)闂l件不同而性能變化差距太大：Sedgewick估計(jì)它的數(shù)據(jù)量為5000以下時(shí)很有用。

只有當(dāng)希爾排序變得很慢時(shí)，你才應(yīng)該使用那些更復(fù)雜但更快速的排序方法：歸并排序、堆排序或快速排序。歸并排序需要輔助存儲(chǔ)空間，堆排序需要有一個(gè)堆的數(shù)據(jù)結(jié)構(gòu)，前兩者都比快速排序在某些程度上慢，所以當(dāng)需要最短的排序時(shí)間時(shí)經(jīng)常選擇快速排序。

然而，快速排序在處理非隨機(jī)性能數(shù)據(jù)時(shí)性能不大可靠，因?yàn)槟菚r(shí)它的速度有可能退化至O(N^2)級(jí)。

對(duì)那些有可能是非隨機(jī)性的數(shù)據(jù)來(lái)說(shuō)，堆排序更加可靠，當(dāng)快速排序沒(méi)有被正確地實(shí)現(xiàn)時(shí)，它會(huì)產(chǎn)生微小偏差，在代碼中細(xì)小的錯(cuò)誤會(huì)使它對(duì)按某些順序排列的數(shù)據(jù)無(wú)能為力，而診斷這種情況又相當(dāng)難。

下面是幾種排序算法的時(shí)間復(fù)雜度級(jí)別

對(duì)于網(wǎng)站建設(shè)中數(shù)據(jù)結(jié)構(gòu)和算法的選擇，看到這里，相信你已經(jīng)學(xué)會(huì)了。

網(wǎng)站標(biāo)題：建站教程：網(wǎng)站建設(shè)中數(shù)據(jù)結(jié)構(gòu)和算法的選擇
轉(zhuǎn)載注明：http://jinyejixie.com/news/169023.html

網(wǎng)站建設(shè)、網(wǎng)絡(luò)推廣公司-創(chuàng)新互聯(lián)，是專注品牌與效果的網(wǎng)站制作，網(wǎng)絡(luò)營(yíng)銷seo公司；服務(wù)項(xiàng)目有網(wǎng)站建設(shè)等

廣告

聲明：本網(wǎng)站發(fā)布的內(nèi)容（圖片、視頻和文字）以用戶投稿、用戶轉(zhuǎn)載內(nèi)容為主，如果涉及侵權(quán)請(qǐng)盡快告知，我們將會(huì)在第一時(shí)間刪除。文章觀點(diǎn)不代表本網(wǎng)站立場(chǎng)，如需處理請(qǐng)聯(lián)系客服。電話：028-86922220；郵箱：631063699@qq.com。內(nèi)容未經(jīng)允許不得轉(zhuǎn)載，或轉(zhuǎn)載時(shí)需注明來(lái)源： 創(chuàng)新互聯(lián)