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

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

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

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

圖：鄰接矩陣、鄰接表

外部存儲：順序存儲、索引文件、B-樹、哈希方法

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

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

1.1 速度與算法

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

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

處理器速度因素

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

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

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

Java引用的優(yōu)點

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

數(shù)組

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

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

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

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

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

鏈表

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

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

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

二叉搜索樹

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

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

平衡樹

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

哈希表

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

哈希表對插入的順序并不敏感，因此可以取代平衡樹。但是哈希表的編程比平衡樹簡單多了。

哈希表需要有額外的存儲空間，尤其是對于開放地址法，因為哈希表用數(shù)組作為基本結(jié)構(gòu)，所以，必須預(yù)先精確地知道待存儲的數(shù)據(jù)量。

用鏈地址法處理沖突的哈希表是最健壯的實現(xiàn)方法，若能預(yù)先精確地知道數(shù)據(jù)量，在這種情況下，用開放地址法編程最簡單，因為不需要用到鏈表類。

哈希表并不能提供任何形式的有序遍歷，或?qū)Υ笾怠⒆钚≈颠M行存取，如果這些功能很重要，使用二叉樹更好些。

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

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

專用數(shù)據(jù)結(jié)構(gòu)有棧、隊列和優(yōu)先級隊列。這些結(jié)構(gòu)不是為了用戶可訪問的數(shù)據(jù)庫而建立的，通常用它們在程序中輔助實現(xiàn)一些算法。

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

對于棧：最后被插入的數(shù)據(jù)項

對于隊列：最先被插入的數(shù)據(jù)項

對于優(yōu)先級隊列：具有高優(yōu)先級的數(shù)據(jù)項

棧

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

棧往往通過數(shù)組或鏈表實現(xiàn)，通過數(shù)組實現(xiàn)很有效率，因為最后被插入的數(shù)據(jù)總是在數(shù)組的最后，這個位置的數(shù)據(jù)很容易被刪除。棧的溢出有可能出現(xiàn)，但當數(shù)組的大小被合理規(guī)劃后，溢出并不常見，因為棧很少會擁有大量的數(shù)據(jù)。

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

隊列

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

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

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

優(yōu)先級隊列

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

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

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

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

3 排序

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

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

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

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

然而，快速排序在處理非隨機性能數(shù)據(jù)時性能不大可靠，因為那時它的速度有可能退化至O(N^2)級。

對那些有可能是非隨機性的數(shù)據(jù)來說，堆排序更加可靠，當快速排序沒有被正確地實現(xiàn)時，它會產(chǎn)生微小偏差，在代碼中細小的錯誤會使它對按某些順序排列的數(shù)據(jù)無能為力，而診斷這種情況又相當難。

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

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

新聞名稱：建站教程：網(wǎng)站建設(shè)中數(shù)據(jù)結(jié)構(gòu)和算法的選擇
本文地址：http://m.rwnh.cn/news23/169023.html

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

廣告

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