資料結構 | 從哪裡開始？

資料結構：把資料放入結構裡，通過結構裡最基本的計算方法（增、删、改、查）操作資料。

是什麼

程式設計要想寫好程式，就需要學習資料結構；可資料結構是什麼呢，我們以畫畫來舉個例子。

一般人畫畫通常就直接畫 --- 如畫水裡的兩條金魚就直接從某一個部分開始，從外形畫起來了。

一般人的畫法結果經常是，畫到後來比例不對，而且常常畫得不像；而專業人士就是畫什麼像什麼、細節特别突出！！！

專業人士又是如何做到的呢 ？？？

百思不得其解，先看看梵高的作品吧（素描）：

就是那個畫向日葵的梵高。

問一下才明白，專業人士畫的畫都講究架構。

這是國中美術書上的《美杜莎之伐》，美術書上還有一副設計初稿：

這副畫最高層的構圖設計就是倆個金字塔形狀，《美杜莎之伐》就是靠着倆個三角形的金字塔，畫面保持了平衡。

那麼，您再看看梵高的作品，能不能看出什麼呢 ？

除了畫畫之外，我們學習寫作不也講究結構，像總分總......

專業畫家畫畫，他們會把金魚分解成幾個簡單的幾何圖形 --- 如頭是一個大圓（頭）和兩個小圓（兩個眼睛），身子是一個橢圓，鳍和尾巴是幾個三角形。

對于程式設計來說，寫一個能夠完成特定功能的程式，就相當于是作一幅畫、一篇文章。

是以，也有兩種方法，

• 一般人程式設計：直接就用一行行代碼去實作功能，這是低水準的做法，有些時候看上去做得快，實際上Bug多，回頭需要修補；
• 專業人士寫：了解需求之後，抽象出作品需要的基本幾何圖形，而後用算法将這些子產品進行組合，寫出符合需求的程式。

這些基本子產品也像繪畫和文章中作為輪廓的幾何圖形一樣，需要根據畫面需求平滑過渡，而不是照搬照抄。

這些程式中基本的幾何圖形，就是計算機的資料結構。

基本的幾何圖形有（一系列的點被連成了一種規則的形狀）：

• 三角形
• 長方形
• 金字塔形
• 圓形
• 橢圓形

程式設計也有基礎結構（一系列的資料被組織為一種抽象的形狀）：

• 集合
• 線性表
• 樹
• 圖

資料就等同于點，資料結構就是點中常用的具體關系。

曆史

第一種資料結構是集合，因為計算機起源于數學，是以資料結構也有數學部分的。

集合，就是我們數學上定義的，也是高中數學裡學過的。

集合在資料結構中一般隻是一個輔助，是某個複雜的資料結構的一部分。

集合的特點是元素分類且不重複。

第二種資料結構是線性表，這相當于幾何圖形中的直線，也是最基本的資料結構。

線性表這種抽象的資料結構并非起源于科學計算本身，而是計算機早期的應用——辦公自動化。

我們知道，雖然發明計算機的目的是為了科學計算，但是TA最早期的商業應用則是在管理和商業方面。

在商業上，報表是一種最常見的資料組織形式，而在管理上，最多見的則是人員或者物資的記錄等等。

TA們都可以被抽象為線性的資料，然後按照 1、2、3、4、5 的順序排列出來。

比如一所大學所有學生的檔案，就是這樣一個個按照順序排列的，而他們的編号就是學号。

是以，很有必要設計一種抽象的資料結構概括所有這些順序排列和儲存的資料，TA就是線性表。

當然，随着計算機資料規模的擴張，未必能夠給所有的資料都賦予一個編号順序，結構化地存儲，但是TA們依然遵循一個順序的特征。

比如一個電商交易的日志記錄，TA是按照所發生的時間順序，一條條線性地記錄下來，是以，線性表的性質TA們也有。

實作線性表的方法有三種：

• 數組
• 連結清單
• 散列

線性表結構關系是一對一。

第三種資料結構是樹。

計算機科學家們正面臨着一個大問題：在我們真實的世界裡，到底是具體的數值重要，還是數值之間相對的大小更重要，或者說相對的次序更重要？

相對大小：在實體上，水的冰點不到 0 度是無法結冰的；

相對次序：在程式設計裡，AlphaGo 和别人下棋的時候經常會說，這一步棋可以赢取了多少目，可AlphaGo 卻不走 ？這是因為計算機隻看相對的輸赢，是以才走一步穩妥。

在計算機中，由于經常要做的事情是判斷真假、比較大小、排序、挑選最大值這類的操作，而它們在計算機的世界裡又如此重要，是以相對次序比相對大小更重要；于是計算機科學家們專門設計一種資料結構，這種資料結構被稱為二叉樹。

二叉樹都有一個根，二叉樹的根就是圖中頂上紅色的那個點。

這是為了将來把二叉樹一層層擴充，二叉樹的根畫在了最頂端，而不是下面，您把自然界的大樹轉180度就可以了。

從根開始都有分叉，隻不過二叉樹為了簡單起見，隻能有兩個分叉，不能更多，這一點和自然界的樹不同。

每一個分叉也有一個自己的根結點，就是圖中藍色的那些點，可以把TA們想象成大樹各級主幹分叉前的部分。

當然，您可能會問，如果遇到一個特殊的問題，需要三個分支怎麼辦？

在數學上，兩個分支和 N 個分支是等價的，或者說 N 個分支的情況可以通過倆個分支來實作。

是以，為了簡單起見，也為了更好的通用性，我們隻研究二叉樹就可以了。

最後，我們知道一棵樹的樹杈還能再分叉，二叉樹也是如此，任何一個枝杈都可以再分出兩枝，這個過程可以無限持續下去。

二叉樹雖然是一種抽象的東西，在自然界中并不存在，但是它卻濃縮了自然界很多事物的共性，那就是分叉、層層遞進和有序。而針對這些共性，科學家們又總結出一些具有普遍性的算法，能夠回過頭來，應用到各種實際問題中。

樹的結構關系是一對多。

樹主要分成倆類：二叉樹和非二叉樹。

• 二叉樹：二叉樹、堆、AVL樹、紅黑樹、默克爾樹。
• 非二叉樹：B樹、哈夫曼樹、字典樹、線段樹、伸展樹、VEB樹、哈希樹、KD樹、區間樹、B+樹、rang Tree、并查集、SBT樹、斯坦納樹、2-3樹、cover Tree、insider Tree。

第四種資料結構是圖。

圖這種資料結構起源于大數學家歐拉。

這是國小數學書上的一道題，好像是二年級..... （我當初試過，是以印象深刻）

圖論是生活中的一個抽象的概念或者說是工具，圍繞圖，計算機科學家們設計了很多算法，然後把很多實際問題抽象出來，用圖論的算法解決。

關于圖的算法有很多，但最重要的是圖的周遊算法，也就是如何從一個點出發，通過連接配接的線通路圖的各個點。

具體的數學推導，可以看看博文《爬蟲導論|如何下載下傳整個網際網路的網頁》。

圖要是學好了，您可以跨學科研究：社會網絡、資料分析、離散數學、網絡爬蟲、道路規劃、機器人導航......

圖的結構關系是多對多。

圖主要是算法：

• 搜尋算法：周遊樹、BFS、DFS、剪枝、雙向BFS、啟發式搜尋
• 比對問題：最大流、匈牙利
• 最短路徑：動态規劃設計思路、Dijkstra、Bellman-Ford、Floyd、A*、JohnSon、Spfa
• 最小生成樹：切分定理、Kruskal、Prim、Gabow+Spfa、BottleNeck、MstReucePrim、SecondaryMSt、Fredman-Tarjan、Chazelle
• 有向圖算法：拓撲排序、強聯通分量
• 網絡流：Ford Fulkerson架構、Edmonds-Kap 、Dinic、MPM、标簽ISPA、HopcaraftKarp、最大流最小割 
• 離散數學：歐拉路徑/回路、哈密爾頓路徑/回路
• 關鍵路徑：AOE網

擴充：圖論專題的《圖的大緻介紹》。

線性表、樹、圖是資料結構這門學科的主線：

• 一些計算機科學家求多，他們認為想要更多的功能，就需要更多的結構，關注的是結構的面值。

        比如，連結清單搗鼓了多個版本，如單向連結清單、雙向連結清單、循環連結清單。

        引入了 矩陣、字元串、哈希表 等結構。

        或者是通過基礎的順序存儲結構和鍊式存儲結構搭積木式組合形成了新的結構。

        還有排序和查找、各種算法設計思想（如遞歸）、各個領域的算法（如數論、計算幾何、圖論）、AI算法（如遺傳算法）。

        求多，越多越好，想要更多的功能，就需要更多的結構。

• 另一些計算機科學家儉省，他們認為結構本身是一回事，而人怎麼利用這個結構是另一回事。如果人能夠善加利用，就可以給任何結構創造新的價值。利用少的結構，擷取更多的功能，一個結構到了您的手裡，您能不能給TA增加一點創造性的附加值。

        他們給目前的結構設定了一個限制，逼着自己在一個架構之内尋找發揮，專注于給已有的結構開發新用途。

        從這種視角來看，線性表、樹、圖都是一個東西，線性表是一種受限制的樹，樹是一種受限制的圖，可以說都是圖。

        通過限制線性表，得到了新的邏輯結構：棧、隊列、堆。

        儉省，不需要太多，釋放少的潛能，取得多的成就。

差別

資料結構、資料類型，我經常分不清，特别是 C語言裡面需要自己實作的資料結構怎麼到了 Python 就變成了資料類型，他們是啥關系？

比如，我準備蓋棟房子：

• 需要各種已經做好并組合的物件，ta是房子的骨架，ta也是程式中的資料結構。
• 當使用各種不同尺寸和标号的鋼筋，如，按直徑分，鋼絲(直徑3~5mm)、細鋼筋(直徑6~10mm)、粗鋼筋(直徑大于22mm)，這些鋼筋即程式中的資料類型，做橫梁也許用10mm的鋼筋，做樓梯也許用22mm的鋼筋，這和程式的 int 與 unsigned int 類似。

其實資料結構還是資料結構，隻不過有些進階語言為了友善程式設計，把資料結構封裝好了，不用重複造輪子。

資料

資料結構，推薦從《大話資料結構》開始：

• 學的線性表的時候，補充《漫畫算法：小灰的算法之旅》
• 學到樹、圖的時候，補充《啊哈算法》
• 學算法的時候，多做算法題，具體可以檢視《算法訓練：噓，别人我不告訴TA》、《Leetcode題解索引》
• 想學好樹的時候，補充《進階資料結構》
• 如果想可視化線性表、樹、圖，看一下 dot 語言的資料即可，很簡單的，可以操作檔案的程式設計語言都可以畫出來。

二叉樹可視化[C 操作 dot]：

• dot 語言可視化，具體請見《圖的分類與模組化、跨語言可視化》。
• 資料結構可視化：https://visualgo.net/en
• 算法可視化：https://algorithm-visualizer.org/backtracking/hamiltonean-cycles

資料結構往往是和算法一起的，資料結構與算法這門課，難點也就是在算法上。

算法訓練，可以參考另一篇：

• 《算法訓練：噓，别人我不告訴TA》

這篇文章，是不是有什麼不可告人的密秘呢！！值得一看。