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