先聲明一下：首先，這里講的都是普通的數(shù)據(jù)結(jié)構(gòu)，咱不是搞算法競賽的，自學(xué)野路子出生，很多厲害的知識我不會，我只會解決常規(guī)的問題。另外，以下是我個人的經(jīng)驗的總結(jié)，沒有哪本書會寫這些東西，所以請讀者試著理解我的角度，如果不是嚴(yán)重的邏輯錯誤，沒必要糾結(jié)于細(xì)節(jié)問題，因為這篇文章就是希望對數(shù)據(jù)結(jié)構(gòu)和算法建立一個框架性的認(rèn)識。相信大家能從這篇文章里學(xué)到點東西。

如果你沒時間細(xì)看，不要錯過第四點。

一、數(shù)據(jù)結(jié)構(gòu)千變?nèi)f化，但不離其宗

最高層的抽象，數(shù)據(jù)結(jié)構(gòu)只有兩種：數(shù)組和鏈表。

這句話怎么理解，不是還有散列表、棧、隊列、堆、樹、圖等等各種數(shù)據(jù)結(jié)構(gòu)嗎？

我們分析問題，一定要有遞歸的思想，自頂向下，從抽象到具體。你列出的這么多，都屬于「上層建筑」，而數(shù)組和鏈表才是「結(jié)構(gòu)基礎(chǔ)」。因為那些多樣化的數(shù)據(jù)結(jié)構(gòu)，究其源頭，都是在鏈表或者數(shù)組上的特殊操作，API 不同而已。

比如說「隊列」、「?！惯@兩種數(shù)據(jù)結(jié)構(gòu)既可以使用鏈表也可以使用數(shù)組實現(xiàn)。用數(shù)組實現(xiàn)，就要處理擴(kuò)容縮容的問題；用鏈表實現(xiàn)，沒有這個問題，但需要更多的空間存儲節(jié)點指針。

「圖」的兩種表示方法，鄰接表就是鏈表，鄰接矩陣就是二維數(shù)組。鄰接矩陣判斷連通性迅速，并可以進(jìn)行矩陣運(yùn)算解決一些問題，但是一般比較耗費(fèi)空間。鄰接表比較節(jié)省空間，但是時間上肯定不如鄰接矩陣快。

「散列表」就是通過散列函數(shù)把鍵映射到一個大數(shù)組里。而且對于解決散列沖突的方法，拉鏈法需要鏈表特性，操作簡單，但需要空間；線性探查法就需要數(shù)組特性，以便連續(xù)尋址，省空間，但操作稍微復(fù)雜些。

「樹」，用數(shù)組實現(xiàn)就是「堆」，因為「堆」是一個完全二叉樹，用數(shù)組存儲不需要節(jié)點指針，操作也比較簡單；用鏈表實現(xiàn)就是很常見的那種「樹」，因為不一定是完全二叉樹，所以不適合用數(shù)組存儲。為此，在這種鏈表「樹」結(jié)構(gòu)之上，又衍生出各種巧妙的設(shè)計，比如二叉搜索樹、AVL 樹、紅黑樹、區(qū)間樹、B 樹等等，以應(yīng)對不同的問題。

以上也可以看出，沒有完美的數(shù)據(jù)結(jié)構(gòu)，沒有一勞永逸的解決方案。

二、數(shù)據(jù)結(jié)構(gòu)的操作,無非遍歷 + 訪問

遍歷 + 訪問，再具體一點就是：增刪查改。

數(shù)據(jù)結(jié)構(gòu)種類很多，但它們存在的目的都是在不同的應(yīng)用場景，盡可能高效地增刪查改。試問，除此之外還有其他嗎？

如何遍歷 + 訪問？我們?nèi)匀粡淖罡邔觼砜矗鞣N數(shù)據(jù)結(jié)構(gòu)的遍歷 + 訪問無非兩種形式，線性的和非線性的。

線性就是 for/while 為代表，非線性就是遞歸為代表。無非以下兩種框架：

數(shù)組遍歷框架，典型的線性遍歷結(jié)構(gòu)：

二叉樹遍歷框架，典型的非線性遞歸遍歷結(jié)構(gòu)：

void traverse(TreeNode root) {
    traverse(root.left)
    traverse(root.right)
}

以上兩個框架可以隨意改造。

鏈表遍歷框架，兼具線性和非線性遍歷結(jié)構(gòu)：

二叉樹框架又可以具體擴(kuò)展為 N 叉樹的遍歷框架：

void traverse(TreeNode root) {
    for (TreeNode child : root.children)
        traverse(child)
}

N 叉樹的遍歷又可以擴(kuò)展為圖的遍歷，因為，圖就是好幾 N 叉棵樹的結(jié)合體。你說圖是可能出現(xiàn)環(huán)的？這個很好辦，用個布爾數(shù)組 visited 做標(biāo)記就行了，就不貼代碼了。

所謂框架，就是說不管具體問題是什么，這些代碼都是永遠(yuǎn)無法脫離的結(jié)構(gòu)，你可以把這個結(jié)構(gòu)作為大綱，根據(jù)具體問題在框架上添加代碼就行了。

三、為什么算法總是和數(shù)據(jù)結(jié)構(gòu)同時出現(xiàn)

數(shù)據(jù)結(jié)構(gòu)是工具，算法是通過合適的工具解決問題的方法。

拿原始人舉例，我們學(xué)會了數(shù)據(jù)結(jié)構(gòu)，就像原始人擁有了石刀，石斧等工具。而根據(jù)制造工具的工藝不同，石刀又分尖銳的石刀和鋸齒狀石刀，前者適合打獵，后者適合切割；就像「圖」這種數(shù)據(jù)結(jié)構(gòu)通過不同的實現(xiàn)方法（鏈表、數(shù)組），可以表示為鄰接表和鄰接矩陣，前者適合處理非稠密圖，后者適合處理稠密圖。

原始人想要造一棟房子，就要進(jìn)行規(guī)劃，石斧砍樹，石刀磨尖角等等；就像我們設(shè)計算法，發(fā)揮數(shù)據(jù)結(jié)構(gòu)的特性，去解決實際問題。

算法利用數(shù)據(jù)結(jié)構(gòu)，可以顯式利用，比如說前文講解的 單調(diào)棧，就是巧妙地直接利用了棧結(jié)構(gòu)先進(jìn)后出的特性。稍微高級一點的算法設(shè)計思路，就是隱式利用數(shù)據(jù)結(jié)構(gòu)，比如前文講過的 回溯算法、動態(tài)規(guī)劃，以及傳說中的的分治算法，都在利用樹這種結(jié)構(gòu)來解決問題。

但是，無論怎樣利用數(shù)據(jù)結(jié)構(gòu)，多么高大上的算法，其解法都逃不出第二點中相應(yīng)的框架，是不是？

四、最后總結(jié)（重要）

對于一個初學(xué)算法的人來說，一定要學(xué)會從框架上看問題，而不要糾結(jié)于細(xì)節(jié)問題。

啥叫細(xì)節(jié)問題？比如說 i 到底應(yīng)該加到 n 還是加到 n - 1 ？這個數(shù)組的大小到底應(yīng)該開 n 還是 n + 1 ？

啥叫從框架上看問題？比如說前文 動態(tài)規(guī)劃 中湊零錢的問題，如果你看了一眼代碼就自動排除細(xì)節(jié)問題，直接提取出 N 叉樹遍歷框架，那么你的框架思維就到位了。

當(dāng)然，如果細(xì)節(jié)出錯，你得不到正確的答案，但是只要有框架在，你再錯也錯不到哪去，因為你的方向是對的。

但是，你要是心中沒有框架，那么你根本無法解題，給了你答案，你也不會發(fā)現(xiàn)這就是個樹的遍歷問題。

這就是框架的力量，能夠保證你在快睡著的時候，依然能寫出正確的程序；就算你啥都不會，都能比別人高一個級別。

初學(xué)階段，沒到糾結(jié)細(xì)節(jié)的地步。細(xì)節(jié)出錯，可以有各種方法查出來，比如到處打 log，沒有找不到的 bug 。

相比之下，別人還束手無策的時候，你已經(jīng)做出了一個錯誤的答案；當(dāng)別人沒有框架的指導(dǎo)，被無限細(xì)節(jié)勸退數(shù)據(jù)結(jié)構(gòu)的時候，你已經(jīng)借助框架看穿了數(shù)據(jù)結(jié)構(gòu)的本質(zhì)。這不就是一種巨大的成功嗎？給你鼓掌。