數(shù)據(jù)結(jié)構(gòu)和算法到底有什么用？

數(shù)據(jù)結(jié)構(gòu)是對(duì)在計(jì)算機(jī)內(nèi)存中（有時(shí)在磁盤中）的數(shù)據(jù)的一種安排。數(shù)據(jù)結(jié)構(gòu)包括數(shù)組、鏈表、棧、二叉樹(shù)、哈希表等等。算法對(duì)這些結(jié)構(gòu)中的數(shù)據(jù)進(jìn)行各種處理。例如，查找一條特殊的數(shù)據(jù)項(xiàng)或?qū)?shù)據(jù)進(jìn)行排序。

掌握這些知識(shí)以后可以解決哪些問(wèn)題呢？

現(xiàn)實(shí)世界數(shù)據(jù)存儲(chǔ)

程序員的工具

建模

數(shù)據(jù)結(jié)構(gòu)的特性：

數(shù)組：優(yōu)點(diǎn)是插入快，如果知道下標(biāo)，可以非常快地存取。缺點(diǎn)是查找慢，刪除慢，大小固定。

有序數(shù)組：優(yōu)點(diǎn)是比無(wú)序的數(shù)據(jù)查找快。缺點(diǎn)是刪除和插入慢，大小固定。

棧：優(yōu)點(diǎn)是提供后進(jìn)先出方式的存取。缺點(diǎn)是存取其他項(xiàng)很慢。

隊(duì)列：提供先進(jìn)先出方式的存取。缺點(diǎn)是存取其他項(xiàng)很慢。

鏈表：優(yōu)點(diǎn)是插入快，刪除快。缺點(diǎn)是查找慢。

二叉樹(shù)：優(yōu)點(diǎn)是查找、插入、刪除都快（如果樹(shù)保持平衡）。缺點(diǎn)是刪除算法復(fù)雜。

紅－黑樹(shù)：查找、插入、刪除都快。樹(shù)總是平衡的。缺點(diǎn)是算法復(fù)雜。

2-3-4樹(shù)：優(yōu)點(diǎn)是查找、插入、刪除都快。樹(shù)總是平衡的。類似的樹(shù)對(duì)磁盤存儲(chǔ)有用。缺點(diǎn)是算法復(fù)雜。

哈希表：優(yōu)點(diǎn)是如果關(guān)鍵字已知?jiǎng)t存取極快。插入快。缺點(diǎn)是刪除慢，如果不知道關(guān)鍵字則存取很慢，對(duì)存儲(chǔ)空間使用不充分。

堆：優(yōu)點(diǎn)是插入、刪除快，對(duì)最大數(shù)據(jù)項(xiàng)的存取很快。缺點(diǎn)是對(duì)其他數(shù)據(jù)項(xiàng)存取慢。

圖：優(yōu)點(diǎn)是對(duì)現(xiàn)實(shí)世界建模。缺點(diǎn)是有些算法且復(fù)雜。

對(duì)于大多數(shù)數(shù)據(jù)結(jié)構(gòu)來(lái)說(shuō)，都需要知道如何插入一條新的數(shù)據(jù)項(xiàng)，如何尋找某一特定的數(shù)據(jù)項(xiàng)，如何刪除某一特定的數(shù)據(jù)項(xiàng)，還需要知道如何迭代地訪問(wèn)某一數(shù)據(jù)結(jié)構(gòu)中的各數(shù)據(jù)項(xiàng)，以便進(jìn)行顯示或其他操作。另一種重要的算法范疇是排序。

一、通用數(shù)據(jù)結(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)）。

通用數(shù)據(jù)結(jié)構(gòu)可以完全按照速度的快慢來(lái)分類：

數(shù)組和鏈表是最慢的，樹(shù)相對(duì)較快，哈希表是最快的。

但并不是使用最快的結(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)卻比較困難。

數(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)的單元，平均半數(shù)以上的數(shù)組元素要被移動(dòng)。在有序數(shù)組中的遍歷是很快的，而在無(wú)序的數(shù)組不支持這種功能。

向量（如Java中的向量類）是一種當(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ǔ)“空洞”。

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

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

四、圖：鄰接矩陣，鄰接表

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

本文來(lái)自CSDN博客，轉(zhuǎn)載請(qǐng)標(biāo)明出處：http://blog.csdn.net/adcxf/archive/2008/08/06/2775636.aspx