數(shù)據(jù)結(jié)構(gòu)一天速成
[導(dǎo)讀]絕大部分學(xué)校的數(shù)據(jù)結(jié)構(gòu)課程應(yīng)該是：作者：不吃魚的喵醬鏈接：https://www.zhihu.com/question/303208441/answer/538673362先說第一塊，線性結(jié)構(gòu)。這里涉及的主要知識點(diǎn)就是順序表和鏈表，以及衍生出來的棧和隊(duì)列。順序表不必多說，就是內(nèi)存...
絕大部分學(xué)校的數(shù)據(jù)結(jié)構(gòu)課程應(yīng)該是：
但是鏈表并不是萬能的，是否選用鏈表要根據(jù)實(shí)際情況進(jìn)行斟酌（后面是重點(diǎn)）。第一，順序表可以隨機(jī)訪問其中的元素，也就是說，使用順序表可以以一個恒定的小代價(jià)訪問其中的任意一個元素，即查找的時(shí)間復(fù)雜度為O(1)；鏈表查找其中某一個位置的特定元素則必須從頭開始一個一個的沿著next指針數(shù)過去，即查找的時(shí)間復(fù)雜度為O(N)。第二，順序表在插入和刪除元素的時(shí)候需要找到特定位置的元素，然后將其后面的全部元素都向前移動或者向后移動，以填補(bǔ)或騰出空位，因此順序表的插入和刪除的時(shí)間復(fù)雜度都是O(N)；但是鏈表只需要摘去或者掛上一個節(jié)點(diǎn)就行了，因此鏈表的插入和刪除的時(shí)間復(fù)雜度都是O(1)。順序表的構(gòu)造思路十分簡單，只要一個一個往里塞就行。在實(shí)踐中，一般使用一個下標(biāo)保存當(dāng)前順序表的結(jié)尾位置，插入元素時(shí)直接在這里插入，然后讓下標(biāo)向后移動。鏈表一般分為頭插法和尾插法兩種方式。頭插法就是把新節(jié)點(diǎn)直接插在節(jié)點(diǎn)鏈的頭部，比較適合構(gòu)造棧；尾插法把新節(jié)點(diǎn)插在鏈表末尾，比較適合構(gòu)造隊(duì)列，而且需要額外的指針指向尾節(jié)點(diǎn)。插入過程如下：
作者：不吃魚的喵醬鏈接：https://www.zhihu.com/question/303208441/answer/538673362先說第一塊，線性結(jié)構(gòu)。這里涉及的主要知識點(diǎn)就是順序表和鏈表，以及衍生出來的棧和隊(duì)列。順序表不必多說，就是內(nèi)存中一塊連續(xù)的區(qū)域，緊密排列了若干個相同類型的數(shù)據(jù)。顯然，這種設(shè)計(jì)需要事先知道同樣的元素一共有多少，不然就無法開辟出合適的內(nèi)存區(qū)域（即會存在浪費(fèi)或者不足）。為了解決數(shù)組這種元素?cái)?shù)量不靈活的缺點(diǎn)而提出的方法就是鏈表。鏈表的基本單位是節(jié)點(diǎn)，每個節(jié)點(diǎn)擁有一個數(shù)據(jù)區(qū)和一個next指針，其中數(shù)據(jù)區(qū)用于存放數(shù)據(jù)，next指針指向下一個節(jié)點(diǎn)。與順序表相比，鏈表可以根據(jù)需要自由選擇節(jié)點(diǎn)的數(shù)量，從而解決了內(nèi)存分配不合適的問題。
但是鏈表并不是萬能的，是否選用鏈表要根據(jù)實(shí)際情況進(jìn)行斟酌（后面是重點(diǎn)）。第一，順序表可以隨機(jī)訪問其中的元素，也就是說，使用順序表可以以一個恒定的小代價(jià)訪問其中的任意一個元素，即查找的時(shí)間復(fù)雜度為O(1)；鏈表查找其中某一個位置的特定元素則必須從頭開始一個一個的沿著next指針數(shù)過去，即查找的時(shí)間復(fù)雜度為O(N)。第二，順序表在插入和刪除元素的時(shí)候需要找到特定位置的元素，然后將其后面的全部元素都向前移動或者向后移動，以填補(bǔ)或騰出空位，因此順序表的插入和刪除的時(shí)間復(fù)雜度都是O(N)；但是鏈表只需要摘去或者掛上一個節(jié)點(diǎn)就行了，因此鏈表的插入和刪除的時(shí)間復(fù)雜度都是O(1)。順序表的構(gòu)造思路十分簡單，只要一個一個往里塞就行。在實(shí)踐中，一般使用一個下標(biāo)保存當(dāng)前順序表的結(jié)尾位置，插入元素時(shí)直接在這里插入，然后讓下標(biāo)向后移動。鏈表一般分為頭插法和尾插法兩種方式。頭插法就是把新節(jié)點(diǎn)直接插在節(jié)點(diǎn)鏈的頭部，比較適合構(gòu)造棧；尾插法把新節(jié)點(diǎn)插在鏈表末尾，比較適合構(gòu)造隊(duì)列，而且需要額外的指針指向尾節(jié)點(diǎn)。插入過程如下：
第一步，將新節(jié)點(diǎn)的next指針指向要插入的位置的后一個節(jié)點(diǎn)（new_node->next = p->next;） 第二步，把要插入的位置的前一個節(jié)點(diǎn)的next指針指向新節(jié)點(diǎn)（p->next = new_node;）刪除節(jié)點(diǎn)過程如下：
第一步，將要刪除的節(jié)點(diǎn)的上一個節(jié)點(diǎn)的next指針指向被刪除的節(jié)點(diǎn)的下一個節(jié)點(diǎn)（p->next = deleted_node->next;） 第二步，釋放被刪除的節(jié)點(diǎn)（free(delete_node);）雙鏈表在單鏈表的基礎(chǔ)上增加了一個前向指針previous，即對于每一個節(jié)點(diǎn)可以同時(shí)找到它的上一個和下一個節(jié)點(diǎn)。這能讓鏈表在構(gòu)造的時(shí)候代碼更好寫，具體情況參考書上。雙鏈表一般不怎么考，根據(jù)需要選用。隊(duì)列和棧是被特化了規(guī)則的線性結(jié)構(gòu)，屬于邏輯結(jié)構(gòu)的范疇，并不拘泥于某種特定的物理結(jié)構(gòu)實(shí)現(xiàn)。換句話說，任何滿足先進(jìn)先出（FIFO）的結(jié)構(gòu)都可以被描述成隊(duì)列，而任何滿足后進(jìn)先出（LIFO）的結(jié)構(gòu)都可以被描述成棧。使用順序表構(gòu)造隊(duì)列需要一個頭指針和一個尾指針。進(jìn)入的元素在尾指針處插入，取出的元素從頭指針處去除；使用鏈表構(gòu)造隊(duì)列需要使用尾插法，并從頭部移除元素。隊(duì)列就是簡單的排隊(duì)，在諸如計(jì)算機(jī)網(wǎng)絡(luò)的分組交換、CPU時(shí)間片輪轉(zhuǎn)等場合有廣泛的應(yīng)用。使用順序表構(gòu)造棧只需要一個棧頂指針。元素從棧頂指針處入棧（push），同樣從棧頂指針處出棧（pop）。使用鏈表構(gòu)造棧需要使用頭插法，并從頭部移除元素（此時(shí)指向鏈表頭結(jié)點(diǎn)本身的指針即為棧頂指針）。棧在諸如編譯時(shí)的括號匹配、程序運(yùn)行時(shí)的函數(shù)跳轉(zhuǎn)等場合有廣泛的應(yīng)用。在上文中，我們會發(fā)現(xiàn)，在使用順序表實(shí)現(xiàn)隊(duì)列，并頻繁地插入和移除元素后，兩個指針漸漸會來到表的結(jié)尾，這時(shí)候我們就需要邏輯上的環(huán)來避免這一問題。將節(jié)點(diǎn)自增從pointer ;改成( pointer)%length;即可解決這一問題。當(dāng)指針來到結(jié)尾處時(shí)會由于模運(yùn)算回到開頭。鏈表則需要把尾節(jié)點(diǎn)的next從懸空改成指向頭結(jié)點(diǎn)，并且讓原來指向頭結(jié)點(diǎn)的指針指向尾節(jié)點(diǎn)即可。這樣一來，p即為末尾，而p->next即為開頭。塊狀表是一種結(jié)合了順序表和鏈表的結(jié)構(gòu)。塊狀表吸收了鏈表的next指針?biāo)鶐淼膭討B(tài)優(yōu)勢，同時(shí)把鏈表的數(shù)據(jù)區(qū)擴(kuò)展成一個小的順序表。這樣一來，既可以滿足動態(tài)請求內(nèi)存的需要，又可以避免查找元素時(shí)O(N)復(fù)雜度的困擾（事實(shí)上可以把O(N)降低到O(N/M 1)，M是小順序表的長度）。塊狀表是一種相對折中的方案，可根據(jù)需要選取，并且一般考試不會考。伴隨著線性結(jié)構(gòu)而來的就是常用的各種排序算法，我這里只說思路不說實(shí)現(xiàn)，并且只提供平均時(shí)間復(fù)雜度。最基礎(chǔ)的就是冒泡排序，基于交換思想。其想法是將每一個元素與它后邊的元素相比，如果前面的更大就交換位置。對于每一個元素來講，當(dāng)交換停止時(shí)，都滿足前面的元素小于它，后面的元素大于它，因此整個數(shù)組有序。冒泡排序的平均復(fù)雜度是O(N2）。除了交換的思想，還有一種常用的思想是插入?；谶@種思想的排序法是插入排序和選擇排序。插入排序會維護(hù)一個小的有序隊(duì)列，在排序開始時(shí)這個隊(duì)列的長度是0，此后，每一次將一個新的元素插入這個有序隊(duì)列中合適的位置，則當(dāng)全部的元素都插入這個隊(duì)列時(shí)排序完成。插入排序平均復(fù)雜度是O(N2)。選擇排序則是每一次都遍歷所有未排序的元素，從中選出最小的或者最大的元素插入有序隊(duì)列的頭或者尾，平均復(fù)雜度同樣是O(N2)。同樣基于插入思想?yún)s又與上兩者不同的方法是希爾排序和桶排序。希爾排序與插入排序基本相同，但是在開始時(shí)會規(guī)定一個增量（一般是數(shù)組長度的一半），并且每一趟將這個增量縮小至之前的一半，直至增量變?yōu)?。希爾排序根據(jù)增量把每隔N個的所有元素分為同一組，對每一組內(nèi)使用插入排序。當(dāng)增量為1時(shí)，對整組元素逐個排序。盡管希爾排序的平均復(fù)雜度也是O(N2)，但是在實(shí)踐中一般比插入排序更快（因?yàn)槊恳淮翁幚淼亩际遣糠钟行虻臄?shù)列，移動元素的次數(shù)較少）。桶排序則更好的體現(xiàn)了插入的思想，事先將最小值到最大值之間的區(qū)間分成N個桶，每個桶涵蓋了相同的數(shù)據(jù)范圍。每次從數(shù)組中取出一個元素放入對應(yīng)的桶內(nèi)，并將其插入到桶內(nèi)的所有元素組成的小數(shù)組中的合適位置，以此完成排序。最后只需要按順序把每個桶中的所有元素倒出來就行了。桶排序?qū)τ诳臻g的需求相對較大，但是相應(yīng)的會減少時(shí)間上的需求，平均復(fù)雜度我懶得算了，但是可以確定是log級別平方級別之間的，但是在桶劃分不合理時(shí)會退化到O(N2)。快速排序則是基于分治法，屬于最難理解的一個?？焖倥判驈木植繑?shù)組中（在第一趟中，這個局部指的是整個數(shù)組）隨機(jī)選取一個中間數(shù)，然后將大于它的數(shù)全部移動到右邊，小于它的數(shù)全部移動到左邊，再對左右兩個局部數(shù)組遞歸進(jìn)行上述操作，直至在某一趟中每個局部數(shù)組都只有一個元素。在交換結(jié)束時(shí)，每一個數(shù)都滿足左邊的比它小，右邊的比它大，因此整個數(shù)組有序?？炫诺钠骄鶑?fù)雜度是O(N*logN)，因此叫快速排序，但是在整個數(shù)組已經(jīng)有序時(shí)會退化為O(N2)。歸并排序同樣基于分治法，也是上述所有排序法中唯一一個外部排序法。歸并排序的基本思想是合并N個有序數(shù)組，當(dāng)N為1時(shí)排序完成。歸并排序主要分為兩步，第一步把大數(shù)據(jù)集分成N個小數(shù)據(jù)集，并使用任意一種內(nèi)部排序法對每一個小數(shù)據(jù)集進(jìn)行排序；第二步是每次將其中的K個已經(jīng)有序的小數(shù)據(jù)集進(jìn)行合并（稱為K路歸并）。歸并排序的平均復(fù)雜度是O(MNlogN)，其中M為每個小數(shù)據(jù)集中數(shù)據(jù)的個數(shù)，N為小數(shù)據(jù)集的數(shù)量，log的底數(shù)為K。基數(shù)排序則是最無聊的一種排序法。假設(shè)有一個數(shù)據(jù)集是{456, 123, 789}，基數(shù)排序先比較個位數(shù)字并排列有序，再比較十位數(shù)字并排列有序，最后比較百位數(shù)字并排列有序。人類在查找紙質(zhì)字典的目錄時(shí)就是在進(jìn)行基數(shù)排序?；鶖?shù)排序不太容易衡量復(fù)雜度，也不太可能考。還有一些常用的排序方法，比如堆排序和二叉排序樹，我們會在后面討論。另外，要是有人跟你說睡排序和猴子排序，請直接把他打死。講完線性結(jié)構(gòu)，我們再來講講樹狀結(jié)構(gòu)。樹狀結(jié)構(gòu)最基礎(chǔ)的就是二叉樹，我們就從這里入手，順便看看復(fù)雜度中的log是怎么來的。首先要先普及一些概念：每一棵樹有唯一的根節(jié)點(diǎn)，在此基礎(chǔ)上向下生長。每一個節(jié)點(diǎn)的所有直接后代稱為它的孩子節(jié)點(diǎn)，孩子的直接先代稱為父親節(jié)點(diǎn)。沒有孩子的節(jié)點(diǎn)稱為葉子節(jié)點(diǎn)。樹中不能有環(huán)，每一個節(jié)點(diǎn)都必須有且僅有一個父親節(jié)點(diǎn)（根節(jié)點(diǎn)除外）。根據(jù)定義我們同樣可以推理出，以每個非葉節(jié)點(diǎn)的每一個孩子節(jié)點(diǎn)作為根節(jié)點(diǎn)，都可以得到一棵子樹。從根節(jié)點(diǎn)到葉子結(jié)點(diǎn)的最長路徑稱為樹的度（或者深度）。在此基礎(chǔ)上，每個非葉節(jié)點(diǎn)至多只有兩個孩子的樹稱為二叉樹。顯然二叉樹的深度介于log?N與N之間。當(dāng)深度為N時(shí)，二叉樹退化為線性表。二叉樹節(jié)點(diǎn)的兩個孩子分別稱為左孩子和右孩子，同理會衍生出左子樹和右子樹的概念。鏈?zhǔn)酱鎯?/strong>的二叉樹十分直接，每個節(jié)點(diǎn)包含一個數(shù)據(jù)區(qū)和兩個孩子指針。數(shù)據(jù)區(qū)用于存儲數(shù)據(jù)，孩子指針分別指向兩個孩子，如果沒有孩子就懸空。這一節(jié)的重難點(diǎn)其實(shí)在二叉樹的線性存儲，即將二叉樹保存在順序表中。這種方式會成為堆排序的理論基礎(chǔ)，并且在存儲完全二叉樹時(shí)有明顯的優(yōu)勢。下面我們將展開來講。在說明線性存儲之前，我們必須要引入滿二叉樹的概念。根據(jù)定義，除最后一層無任何子節(jié)點(diǎn)外，每一層上的所有結(jié)點(diǎn)都有兩個子結(jié)點(diǎn)二叉樹被稱為滿二叉樹。如下圖
第一步，在邏輯上建堆。這一步要求我們根據(jù)實(shí)際情況（即數(shù)組下標(biāo)從1或者0開始）來推演父親節(jié)點(diǎn)與孩子節(jié)點(diǎn)真實(shí)的下標(biāo)關(guān)系，在腦海中建立這個堆。第二步，滿足堆的性質(zhì)。這一步我們要對所有的非葉子節(jié)點(diǎn)從下到上進(jìn)行調(diào)整，使其滿足大頂堆或者小頂堆的性質(zhì)。具體做法是找到第一個非葉子節(jié)點(diǎn)，并對它與它的孩子節(jié)點(diǎn)進(jìn)行調(diào)整，使其滿足堆的性質(zhì)；然后從這個節(jié)點(diǎn)開始向前線性地調(diào)整每一個非葉子節(jié)點(diǎn)，直至根節(jié)點(diǎn)。此時(shí)整個堆都滿足性質(zhì)。第三步，取得堆頂元素。這一步會把堆頂元素與堆內(nèi)序號最大的元素進(jìn)行交換，并且堆內(nèi)元素?cái)?shù)量減一。顯然這個堆頂元素滿足剩余未排序元素都比它小或比它大，而前面的已排序元素都比它大或比它小，因此它在已排序隊(duì)列中的相對位置是確定的，即頭或尾。第四步，恢復(fù)堆的性質(zhì)。由于剛才把一個無序元素插入了堆頂，導(dǎo)致堆的性質(zhì)被破壞，接下來我們需要恢復(fù)它的性質(zhì)。這一步不需要逆序遍歷，而是從堆頂開始，將剛插入的元素逐步向下落，直至停在合適的位置。舉例來講，對于大頂堆，要保證堆頂元素是最大的，因此要把它分別與左右孩子進(jìn)行比較，并且把三者中最大的一個升上堆頂。由于左右孩子在剛才的操作中都沒有變動，因此各自滿足在子樹中是最大的的性質(zhì)，此時(shí)若堆頂元素比他們兩個都大，便能推理出堆頂元素是最大的。同理，升上去的三者中最大的元素也能滿足這個推理。將堆頂元素向下落的操作要遞歸地進(jìn)行到該元素不需要再進(jìn)行交換為止，此時(shí)整個堆恢復(fù)性質(zhì)。第五步，重復(fù)第三步和第四步的操作，直至堆被清空。此時(shí)，整個數(shù)列有序。堆排序非常喜歡考，不僅考方法論還要考實(shí)現(xiàn)，而且這東西略抽象，不是很好掌握。剛才突然心血來潮寫了個實(shí)現(xiàn)，湊合著看一下吧。我比較懶，用CPU時(shí)間換了內(nèi)存，數(shù)組下標(biāo)里面各種運(yùn)算。其實(shí)可以拿臨時(shí)變量裝一下來節(jié)省CPU的。C語言需要事先聲明函數(shù)才能使用，我也沒照顧可讀性寫函數(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]? 
下載文檔
