數據結構和算法到底有什么用？

數據結構是對在計算機內存中（有時在磁盤中）的數據的一種安排。數據結構包括數組、鏈表、棧、二叉樹、哈希表等等。算法對這些結構中的數據進行各種處理。例如，查找一條特殊的數據項或對數據進行排序。

掌握這些知識以后可以解決哪些問題呢？

現實世界數據存儲

程序員的工具

建模

數據結構的特性：

數組：優點是插入快，如果知道下標，可以非常快地存取。缺點是查找慢，刪除慢，大小固定。

有序數組：優點是比無序的數據查找快。缺點是刪除和插入慢，大小固定。

棧：優點是提供后進先出方式的存取。缺點是存取其他項很慢。

隊列：提供先進先出方式的存取。缺點是存取其他項很慢。

鏈表：優點是插入快，刪除快。缺點是查找慢。

二叉樹：優點是查找、插入、刪除都快（如果樹保持平衡）。缺點是刪除算法復雜。

紅－黑樹：查找、插入、刪除都快。樹總是平衡的。缺點是算法復雜。

2-3-4樹：優點是查找、插入、刪除都快。樹總是平衡的。類似的樹對磁盤存儲有用。缺點是算法復雜。

哈希表：優點是如果關鍵字已知則存取極快。插入快。缺點是刪除慢，如果不知道關鍵字則存取很慢，對存儲空間使用不充分。

堆：優點是插入、刪除快，對最大數據項的存取很快。缺點是對其他數據項存取慢。

圖：優點是對現實世界建模。缺點是有些算法且復雜。

對于大多數數據結構來說，都需要知道如何插入一條新的數據項，如何尋找某一特定的數據項，如何刪除某一特定的數據項，還需要知道如何迭代地訪問某一數據結構中的各數據項，以便進行顯示或其他操作。另一種重要的算法范疇是排序。

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

它們被稱之為通用的數據結構是因為它們通過關鍵字的值來存儲并查找數據，這一點在通用數據庫程序中常見到（棧等特殊結構正好相反，它們只允許存取一定的數據項）。

通用數據結構可以完全按照速度的快慢來分類：

數組和鏈表是最慢的，樹相對較快，哈希表是最快的。

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

數組在下列情況下很有用：

數據量較小

數據量的大小事先可預測

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

如果插入速度很重要的話，使用無序數組。如果查找速度很重要的話，使用有序數組，并用二分查找。數組元素的刪除總是很慢，這是由于為了填充空出來的單元，平均半數以上的數組元素要被移動。在有序數組中的遍歷是很快的，而在無序的數組不支持這種功能。

向量（如Java中的向量類）是一種當數據太滿時可以自己擴充空間的數組。向量可以應用于數據量不可預知的情況下。然而，在向量擴充時，要將舊的數據拷入一個新的空間中，這一過程會造成程序明顯的周期性暫停。

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

二、專用數據結構：棧，隊列，優先級隊列

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

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

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

本文來自CSDN博客，轉載請標明出處：http://blog.csdn.net/adcxf/archive/2008/08/06/2775636.aspx