數(shù)據(jù)結(jié)構(gòu)一天速成

絕大部分學校的數(shù)據(jù)結(jié)構(gòu)課程應該是：

作者：不吃魚的喵醬

鏈接：https://www.zhihu.com/question/303208441/answer/538673362

先說第一塊，線性結(jié)構(gòu)。這里涉及的主要知識點就是順序表和鏈表，以及衍生出來的棧和隊列。順序表不必多說，就是內(nèi)存中一塊連續(xù)的區(qū)域，緊密排列了若干個相同類型的數(shù)據(jù)。顯然，這種設計需要事先知道同樣的元素一共有多少，不然就無法開辟出合適的內(nèi)存區(qū)域（即會存在浪費或者不足）。為了解決數(shù)組這種元素數(shù)量不靈活的缺點而提出的方法就是鏈表。鏈表的基本單位是節(jié)點，每個節(jié)點擁有一個數(shù)據(jù)區(qū)和一個next指針，其中數(shù)據(jù)區(qū)用于存放數(shù)據(jù)，next指針指向下一個節(jié)點。與順序表相比，鏈表可以根據(jù)需要自由選擇節(jié)點的數(shù)量，從而解決了內(nèi)存分配不合適的問題。

但是鏈表并不是萬能的，是否選用鏈表要根據(jù)實際情況進行斟酌（后面是重點）。第一，順序表可以隨機訪問其中的元素，也就是說，使用順序表可以以一個恒定的小代價訪問其中的任意一個元素，即查找的時間復雜度為O(1)；鏈表查找其中某一個位置的特定元素則必須從頭開始一個一個的沿著next指針數(shù)過去，即查找的時間復雜度為O(N)。第二，順序表在插入和刪除元素的時候需要找到特定位置的元素，然后將其后面的全部元素都向前移動或者向后移動，以填補或騰出空位，因此順序表的插入和刪除的時間復雜度都是O(N)；但是鏈表只需要摘去或者掛上一個節(jié)點就行了，因此鏈表的插入和刪除的時間復雜度都是O(1)。

順序表的構(gòu)造思路十分簡單，只要一個一個往里塞就行。在實踐中，一般使用一個下標保存當前順序表的結(jié)尾位置，插入元素時直接在這里插入，然后讓下標向后移動。鏈表一般分為頭插法和尾插法兩種方式。頭插法就是把新節(jié)點直接插在節(jié)點鏈的頭部，比較適合構(gòu)造棧；尾插法把新節(jié)點插在鏈表末尾，比較適合構(gòu)造隊列，而且需要額外的指針指向尾節(jié)點。插入過程如下：

第一步，將新節(jié)點的next指針指向要插入的位置的后一個節(jié)點（new_node->next = p->next;） 第二步，把要插入的位置的前一個節(jié)點的next指針指向新節(jié)點（p->next = new_node;）

刪除節(jié)點過程如下：

第一步，將要刪除的節(jié)點的上一個節(jié)點的next指針指向被刪除的節(jié)點的下一個節(jié)點（p->next = deleted_node->next;） 第二步，釋放被刪除的節(jié)點（free(delete_node);）

雙鏈表在單鏈表的基礎上增加了一個前向指針previous，即對于每一個節(jié)點可以同時找到它的上一個和下一個節(jié)點。這能讓鏈表在構(gòu)造的時候代碼更好寫，具體情況參考書上。雙鏈表一般不怎么考，根據(jù)需要選用。

隊列和棧是被特化了規(guī)則的線性結(jié)構(gòu)，屬于邏輯結(jié)構(gòu)的范疇，并不拘泥于某種特定的物理結(jié)構(gòu)實現(xiàn)。換句話說，任何滿足先進先出（FIFO）的結(jié)構(gòu)都可以被描述成隊列，而任何滿足后進先出（LIFO）的結(jié)構(gòu)都可以被描述成棧。

使用順序表構(gòu)造隊列需要一個頭指針和一個尾指針。進入的元素在尾指針處插入，取出的元素從頭指針處去除；使用鏈表構(gòu)造隊列需要使用尾插法，并從頭部移除元素。隊列就是簡單的排隊，在諸如計算機網(wǎng)絡的分組交換、CPU時間片輪轉(zhuǎn)等場合有廣泛的應用。

使用順序表構(gòu)造棧只需要一個棧頂指針。元素從棧頂指針處入棧（push），同樣從棧頂指針處出棧（pop）。使用鏈表構(gòu)造棧需要使用頭插法，并從頭部移除元素（此時指向鏈表頭結(jié)點本身的指針即為棧頂指針）。棧在諸如編譯時的括號匹配、程序運行時的函數(shù)跳轉(zhuǎn)等場合有廣泛的應用。

在上文中，我們會發(fā)現(xiàn)，在使用順序表實現(xiàn)隊列，并頻繁地插入和移除元素后，兩個指針漸漸會來到表的結(jié)尾，這時候我們就需要邏輯上的環(huán)來避免這一問題。將節(jié)點自增從pointer ;改成( pointer)%length;即可解決這一問題。當指針來到結(jié)尾處時會由于模運算回到開頭。鏈表則需要把尾節(jié)點的next從懸空改成指向頭結(jié)點，并且讓原來指向頭結(jié)點的指針指向尾節(jié)點即可。這樣一來，p即為末尾，而p->next即為開頭。

塊狀表是一種結(jié)合了順序表和鏈表的結(jié)構(gòu)。塊狀表吸收了鏈表的next指針所帶來的動態(tài)優(yōu)勢，同時把鏈表的數(shù)據(jù)區(qū)擴展成一個小的順序表。這樣一來，既可以滿足動態(tài)請求內(nèi)存的需要，又可以避免查找元素時O(N)復雜度的困擾（事實上可以把O(N)降低到O(N/M 1)，M是小順序表的長度）。塊狀表是一種相對折中的方案，可根據(jù)需要選取，并且一般考試不會考。

伴隨著線性結(jié)構(gòu)而來的就是常用的各種排序算法，我這里只說思路不說實現(xiàn)，并且只提供平均時間復雜度。

最基礎的就是冒泡排序，基于交換思想。其想法是將每一個元素與它后邊的元素相比，如果前面的更大就交換位置。對于每一個元素來講，當交換停止時，都滿足前面的元素小于它，后面的元素大于它，因此整個數(shù)組有序。冒泡排序的平均復雜度是O(N2）。

除了交換的思想，還有一種常用的思想是插入?；谶@種思想的排序法是插入排序和選擇排序。插入排序會維護一個小的有序隊列，在排序開始時這個隊列的長度是0，此后，每一次將一個新的元素插入這個有序隊列中合適的位置，則當全部的元素都插入這個隊列時排序完成。插入排序平均復雜度是O(N2)。選擇排序則是每一次都遍歷所有未排序的元素，從中選出最小的或者最大的元素插入有序隊列的頭或者尾，平均復雜度同樣是O(N2)。

同樣基于插入思想?yún)s又與上兩者不同的方法是希爾排序和桶排序。希爾排序與插入排序基本相同，但是在開始時會規(guī)定一個增量（一般是數(shù)組長度的一半），并且每一趟將這個增量縮小至之前的一半，直至增量變?yōu)?。希爾排序根據(jù)增量把每隔N個的所有元素分為同一組，對每一組內(nèi)使用插入排序。當增量為1時，對整組元素逐個排序。盡管希爾排序的平均復雜度也是O(N2)，但是在實踐中一般比插入排序更快（因為每一次處理的都是部分有序的數(shù)列，移動元素的次數(shù)較少）。桶排序則更好的體現(xiàn)了插入的思想，事先將最小值到最大值之間的區(qū)間分成N個桶，每個桶涵蓋了相同的數(shù)據(jù)范圍。每次從數(shù)組中取出一個元素放入對應的桶內(nèi)，并將其插入到桶內(nèi)的所有元素組成的小數(shù)組中的合適位置，以此完成排序。最后只需要按順序把每個桶中的所有元素倒出來就行了。桶排序?qū)τ诳臻g的需求相對較大，但是相應的會減少時間上的需求，平均復雜度我懶得算了，但是可以確定是log級別平方級別之間的，但是在桶劃分不合理時會退化到O(N2)。

快速排序則是基于分治法，屬于最難理解的一個?？焖倥判驈木植繑?shù)組中（在第一趟中，這個局部指的是整個數(shù)組）隨機選取一個中間數(shù)，然后將大于它的數(shù)全部移動到右邊，小于它的數(shù)全部移動到左邊，再對左右兩個局部數(shù)組遞歸進行上述操作，直至在某一趟中每個局部數(shù)組都只有一個元素。在交換結(jié)束時，每一個數(shù)都滿足左邊的比它小，右邊的比它大，因此整個數(shù)組有序?？炫诺钠骄鶑碗s度是O(N*logN)，因此叫快速排序，但是在整個數(shù)組已經(jīng)有序時會退化為O(N2)。

歸并排序同樣基于分治法，也是上述所有排序法中唯一一個外部排序法。歸并排序的基本思想是合并N個有序數(shù)組，當N為1時排序完成。歸并排序主要分為兩步，第一步把大數(shù)據(jù)集分成N個小數(shù)據(jù)集，并使用任意一種內(nèi)部排序法對每一個小數(shù)據(jù)集進行排序；第二步是每次將其中的K個已經(jīng)有序的小數(shù)據(jù)集進行合并（稱為K路歸并）。歸并排序的平均復雜度是O(MNlogN)，其中M為每個小數(shù)據(jù)集中數(shù)據(jù)的個數(shù)，N為小數(shù)據(jù)集的數(shù)量，log的底數(shù)為K。

基數(shù)排序則是最無聊的一種排序法。假設有一個數(shù)據(jù)集是{456, 123, 789}，基數(shù)排序先比較個位數(shù)字并排列有序，再比較十位數(shù)字并排列有序，最后比較百位數(shù)字并排列有序。人類在查找紙質(zhì)字典的目錄時就是在進行基數(shù)排序?；鶖?shù)排序不太容易衡量復雜度，也不太可能考。

還有一些常用的排序方法，比如堆排序和二叉排序樹，我們會在后面討論。另外，要是有人跟你說睡排序和猴子排序，請直接把他打死。

講完線性結(jié)構(gòu)，我們再來講講樹狀結(jié)構(gòu)。樹狀結(jié)構(gòu)最基礎的就是二叉樹，我們就從這里入手，順便看看復雜度中的log是怎么來的。

首先要先普及一些概念：每一棵樹有唯一的根節(jié)點，在此基礎上向下生長。每一個節(jié)點的所有直接后代稱為它的孩子節(jié)點，孩子的直接先代稱為父親節(jié)點。沒有孩子的節(jié)點稱為葉子節(jié)點。樹中不能有環(huán)，每一個節(jié)點都必須有且僅有一個父親節(jié)點（根節(jié)點除外）。根據(jù)定義我們同樣可以推理出，以每個非葉節(jié)點的每一個孩子節(jié)點作為根節(jié)點，都可以得到一棵子樹。從根節(jié)點到葉子結(jié)點的最長路徑稱為樹的度（或者深度）。

在此基礎上，每個非葉節(jié)點至多只有兩個孩子的樹稱為二叉樹。顯然二叉樹的深度介于log?N與N之間。當深度為N時，二叉樹退化為線性表。二叉樹節(jié)點的兩個孩子分別稱為左孩子和右孩子，同理會衍生出左子樹和右子樹的概念。

鏈式存儲的二叉樹十分直接，每個節(jié)點包含一個數(shù)據(jù)區(qū)和兩個孩子指針。數(shù)據(jù)區(qū)用于存儲數(shù)據(jù)，孩子指針分別指向兩個孩子，如果沒有孩子就懸空。這一節(jié)的重難點其實在二叉樹的線性存儲，即將二叉樹保存在順序表中。這種方式會成為堆排序的理論基礎，并且在存儲完全二叉樹時有明顯的優(yōu)勢。下面我們將展開來講。

在說明線性存儲之前，我們必須要引入滿二叉樹的概念。根據(jù)定義，除最后一層無任何子節(jié)點外，每一層上的所有結(jié)點都有兩個子結(jié)點二叉樹被稱為滿二叉樹。如下圖

對于一棵滿二叉樹，我們按照從左到右，從上到下的順序給每一個節(jié)點編上號（我的教材是從1開始編號，因為方便運算），就能輕易發(fā)現(xiàn)一個事實：假設某一個節(jié)點的編號是N，那它的的兩個孩子節(jié)點的序號分別是2N和2N 1。下面，我們把這個編號作為數(shù)組下標，就可以得到二叉樹的線性存儲方式了。

對于不滿的二叉樹，我們要先把它補齊成滿二叉樹，然后把補上的節(jié)點空出來，就可以完成線性存儲。存儲一棵二叉樹所需的總的線性空間與它的度有關(guān)，即2的N次方。顯然，滿二叉樹極少浪費線性空間，而偏差較大的二叉樹會極大地浪費線性空間。

建立一棵二叉樹十分簡單，一般有兩種方式：從根向葉子和從葉子向根。前者可以被用來建立二叉排序樹，一會兒會講到；后者可以用來建立哈夫曼樹，網(wǎng)上資料很多，有看不明白的地方自己再查一下。這兩種樹都屬于?？純?nèi)容，應用也十分廣泛。

正常的樹都是從根向葉子生長，所以逆生長的哈夫曼樹就顯得比較特別。哈夫曼樹一般用于壓縮算法，可以用來生成前綴碼。前綴碼指的是，在一套編碼體系中，任何一個字的密文都不是其他字的密文的前綴，或者說對于任何一個字的密文，從頭開始連續(xù)截取任意長度，得到的結(jié)果都不能構(gòu)成另外一個字的密文。不是前綴這個特性保證了編碼沒有歧義，因此可以按順序處理而不必擔心出現(xiàn)錯誤。摩斯電碼是非前綴碼，因此每兩個字之間需要提供明顯的停頓用以顯示表明這是不同的兩個字。如果這個停頓不夠明顯，也就是發(fā)報速度比較快，就比較容易造成歧義。

前綴碼的一個特性就是每個字長短不一，顯然出現(xiàn)頻率更高的字使用更短的密文能獲得較大的空間和時間優(yōu)勢。所以，哈夫曼樹的第一步就是從統(tǒng)計字頻開始的。這一步只需要遍歷文本流就可以，很簡單，按下不表。

第二步就要開始建樹了。由于哈夫曼樹是逆生長樹，采取的是合并子樹的思想，所以最先被選擇的一定是最深的子樹。合并子樹的方法如下：在最開始的時候，把每一個節(jié)點都視為一棵只有一個根節(jié)點的樹。每一次迭代，選取頻率最低的兩棵子樹進行合并，直到最后只剩下一棵樹為止。舉例來說，假設剛開始有a，b，c三棵子樹，頻率分別是0.1，0.2，0.7，那么第一次迭代就會選擇0.1跟0.2進行合并，得到一棵頻率為0.3的新子樹，然后再把這棵新子樹與0.7合并完成建樹。顯然，從根節(jié)點開始，尋找c只需要一步，而尋找a和b各需要兩步，平均字長為1.3。

建立哈夫曼樹的目的是為了進行哈夫曼編碼。前文也提到了，這是一種壓縮算法。壓縮的過程就是建立上述的哈夫曼樹，然后遍歷哈夫曼樹寫出每個字的密文，再按照查字典的方式把每個字轉(zhuǎn)換過去。而解壓縮的時候，則需要先重建哈夫曼樹，再一位一位對照密文從樹根開始向下尋找，找到葉子結(jié)點就可以認為解碼出了一個字，然后下一位回到樹根重新尋找。解碼的過程比較類似狀態(tài)機模型，要寫成模塊化的模式還真不是太好寫，反而是面向過程的方式比較好寫。在具體編碼過程中，指定左孩子的編碼為1或是右孩子的編碼為1都不會影響結(jié)果，事實上也沒什么標準，甚至在中途隨意翻轉(zhuǎn)都可以。不同的程序員跑出來的哈夫曼編碼結(jié)果不同是很正常的一件事，只要不影響編碼和解碼的使用就行。

說完了不正常生長的哈夫曼樹，再來說說正常生長的二叉排序樹。二叉排序樹的定義是：每一個節(jié)點的左孩子小于它，而右孩子大于它（等于的情況事先聲明一下放左還是放右就行，對于結(jié)果無實質(zhì)影響）。根據(jù)這個定義，我們可以遞歸地得出性質(zhì)：對于每一個節(jié)點，其左子樹全部小于它，其右子樹全部大于它。因此，為了滿足性質(zhì)，在建立二叉排序樹時只需要從根節(jié)點開始，遞歸地比較每一層元素，如果其比要插入的元素大則走向其左孩子，反之走向其右孩子，直至最終來到葉子結(jié)點，并把該元素插入。當全部的元素都被插入了，二叉排序樹就建立完成了。

接下來就要取出其中的有序數(shù)列了，也就是進行二叉樹的遍歷。二叉樹的遍歷一般分為先序遍歷、中序遍歷和后序遍歷三種。先序遍歷即先訪問根節(jié)點，再尋找左孩子，最后尋找右孩子。中序遍歷是先尋找左孩子，再訪問根節(jié)點，最后尋找右孩子。后序遍歷先尋找左孩子，再尋找右孩子，最后訪問根節(jié)點?？梢哉f，先中后指的是訪問根節(jié)點的時機。由于遍歷是遞歸的，使用中序遍歷一路尋找到的最“左”的左孩子就是二叉排序樹中的最小元素，且中序遍歷的輸出順序就是從小到大的順序。根據(jù)前序遍歷和中序遍歷或后序遍歷和中序遍歷可以重建整棵樹，這也是考試的熱點和難點。

二叉排序樹的平均復雜度是O(N*logN)，其中的log就來自于二叉樹的深度。當數(shù)組已經(jīng)有序時二叉排序樹會退化為O(N2)，而且絕大部分時候都建不出漂亮的二叉樹，所以這個log其實是有很大水分的。

為了盡量建出漂亮的二叉樹，人們想出了很多辦法，其中一項就是平衡二叉樹（AVL樹）。平衡二叉樹是指每一個節(jié)點滿足左子樹的度與右子樹的度相差不超過1的二叉排序樹。由于其限制了節(jié)點的左右孩子，因此能讓整棵樹更加緊湊，從而大量擠出了log中的水分。建立AVL樹需要用到復雜的旋轉(zhuǎn)操作，幾乎不會考到，所以我不講了。

使用二叉排序樹排序盡管復雜度較低，而且十分容易理解，但是需要O(N)級別的輔助空間，并不是很劃算。仔細想一想，既然能把二叉樹存放在順序表里，那順序表本身是不是也能被看成是線性存儲的二叉樹呢？答案是肯定的。一張順序表可以被看做是一個完全二叉樹，即除了最后一層外每一層元素都是滿的，且最后一層的元素全都集中在左邊的二叉樹。顯然，滿二叉樹是完全二叉樹。

堆就是完全二叉樹的一種應用，硬要說的話也屬于反向生長。常用的堆分為大頂堆和小頂堆兩種，前者滿足父親節(jié)點大于孩子節(jié)點，后者滿足父親節(jié)點小于孩子節(jié)點。根據(jù)遞歸我們可以推算出，大頂堆堆頂?shù)脑厥亲畲蟮?/strong>，小頂堆堆頂?shù)脑厥亲钚〉?/strong>。堆排序就是在不斷地重復建堆并移走堆頂元素的過程，顯然平均復雜度是O(N*logN)，而且由于完全二叉樹的性質(zhì)，這個log沒有水分。

堆排序最神奇的地方就是它不需要借助一個鏈式的二叉樹的輔助，而是直接在順序表中操作元素，因此它的空間復雜度是O(1)級別的?；叵胍幌露鏄涞木€性存儲相關(guān)的內(nèi)容，我們會猛然想起父親節(jié)點與孩子節(jié)點的序號之間的關(guān)系，從而明白為什么不需要輔助樹。

第一步，在邏輯上建堆。這一步要求我們根據(jù)實際情況（即數(shù)組下標從1或者0開始）來推演父親節(jié)點與孩子節(jié)點真實的下標關(guān)系，在腦海中建立這個堆。第二步，滿足堆的性質(zhì)。這一步我們要對所有的非葉子節(jié)點從下到上進行調(diào)整，使其滿足大頂堆或者小頂堆的性質(zhì)。具體做法是找到第一個非葉子節(jié)點，并對它與它的孩子節(jié)點進行調(diào)整，使其滿足堆的性質(zhì)；然后從這個節(jié)點開始向前線性地調(diào)整每一個非葉子節(jié)點，直至根節(jié)點。此時整個堆都滿足性質(zhì)。第三步，取得堆頂元素。這一步會把堆頂元素與堆內(nèi)序號最大的元素進行交換，并且堆內(nèi)元素數(shù)量減一。顯然這個堆頂元素滿足剩余未排序元素都比它小或比它大，而前面的已排序元素都比它大或比它小，因此它在已排序隊列中的相對位置是確定的，即頭或尾。第四步，恢復堆的性質(zhì)。由于剛才把一個無序元素插入了堆頂，導致堆的性質(zhì)被破壞，接下來我們需要恢復它的性質(zhì)。這一步不需要逆序遍歷，而是從堆頂開始，將剛插入的元素逐步向下落，直至停在合適的位置。舉例來講，對于大頂堆，要保證堆頂元素是最大的，因此要把它分別與左右孩子進行比較，并且把三者中最大的一個升上堆頂。由于左右孩子在剛才的操作中都沒有變動，因此各自滿足在子樹中是最大的的性質(zhì)，此時若堆頂元素比他們兩個都大，便能推理出堆頂元素是最大的。同理，升上去的三者中最大的元素也能滿足這個推理。將堆頂元素向下落的操作要遞歸地進行到該元素不需要再進行交換為止，此時整個堆恢復性質(zhì)。第五步，重復第三步和第四步的操作，直至堆被清空。此時，整個數(shù)列有序。

堆排序非常喜歡考，不僅考方法論還要考實現(xiàn)，而且這東西略抽象，不是很好掌握。剛才突然心血來潮寫了個實現(xiàn)，湊合著看一下吧。我比較懶，用CPU時間換了內(nèi)存，數(shù)組下標里面各種運算。其實可以拿臨時變量裝一下來節(jié)省CPU的。C語言需要事先聲明函數(shù)才能使用，我也沒照顧可讀性寫函數(shù)原型，看的時候記得倒著看。

#include?

void?reconstruct_heap(int?a[],?int?index,?int?last)
{
????int?tmp;
????
????if(index?*?2? ?1?>?last)??//?檢查是否有孩子
????{
????????return;
????}
????
????if(index?*?2? ?1?==?last)??//?檢查是否只有左孩子
????{
????????if(a[last]?>?a[index])
????????{
????????????tmp?=?a[index];
????????????a[index]?=?a[last];
????????????a[last]?=?tmp;
????????}
????}
????else
????{
????????if(a[2?*?index? ?1]?>?a[index]?