本部分總結在網站建設中數據結構和算法，并討論在不同的情況下如何進行選擇。

通用數據結構：數組、鏈表、樹、哈希表

專用數據結構：棧、隊列、優(yōu)先級隊列

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

圖：鄰接矩陣、鄰接表

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

1 通用數據結構

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

1.1 速度與算法

通用數據結構可以完全按照速度的快慢來分類:數組和鏈表是最慢的，樹相對較快，哈希表是最快的。

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

處理器速度因素

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

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

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

Java引用的優(yōu)點

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

數組

當存儲和操作數據時，在大多數情況下數組是首先應該考慮的結構，數組在下列情況下很有用:

數據量較小

數據量的大小事先可預測

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

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

鏈表

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

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

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

二叉搜索樹

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

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

平衡樹

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

哈希表

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

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

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

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

哈希表并不能提供任何形式的有序遍歷，或對大值、最小值進行存取，如果這些功能很重要，使用二叉樹更好些。

通用數據存儲結構的比較

2 專用數據結構

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

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

對于棧：最后被插入的數據項

對于隊列：最先被插入的數據項

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

棧

棧用在最后被插入數據項訪問的時候，它是一個后進先出的結構。

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

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

隊列

隊列用在只對最先被插入數據項訪問的時候，它是一個先進先出的結構。

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

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

優(yōu)先級隊列

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

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

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

專用結構的比較

3 排序

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

插入排序對幾乎已排好的文件也很有效，如果沒有太多的元素處于亂序的位置上，操作的時間復雜度大約在O(N)級，這通常發(fā)生在往一個已排好序的文件中插入一些新的數據元素的情況。

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

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

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

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

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

對于網站建設中數據結構和算法的選擇，看到這里，相信你已經學會了。

新聞名稱：建站教程：網站建設中數據結構和算法的選擇
本文地址：http://jinyejixie.com/news23/169023.html

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

廣告

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