自學(xué)數(shù)據(jù)結(jié)構(gòu)大綱筆記

數(shù)據(jù)結(jié)構(gòu)概述（教材選用嚴(yán)蔚敏、吳偉民，該書(shū)程序是偽算法具體地程序是高一凡，西電地，大牛，只有程序.還有一本書(shū)，臺(tái)灣地黃國(guó)瑜自己寫地只有思路，程序是另外一個(gè)合作地清華地寫地，可惜很多錯(cuò)地.）學(xué)完數(shù)據(jù)結(jié)構(gòu)之后會(huì)對(duì)面向過(guò)程地函數(shù)有一個(gè)更深地了解定義我們?nèi)绾伟熏F(xiàn)實(shí)中大量而復(fù)雜地問(wèn)題以特定地?cái)?shù)據(jù)類型（單個(gè)數(shù)據(jù)怎樣存儲(chǔ)？）和特定地存儲(chǔ)結(jié)構(gòu)（個(gè)體地關(guān)系）保存到主存儲(chǔ)器（內(nèi)存）中，以及在此基礎(chǔ)上為實(shí)現(xiàn)某個(gè)功能（比如查找某個(gè)元素，刪除某個(gè)元素，對(duì)所有元素進(jìn)行排序）而執(zhí)行地相應(yīng)操作，這個(gè)相應(yīng)地操作也叫算法.（比如班里有個(gè)人，其信息量也許一個(gè)數(shù)組就搞定了，但是假如個(gè)，怎么辦？?jī)?nèi)存也許沒(méi)有這么多連續(xù)地空間，所以我們改用鏈表，這就是與存儲(chǔ)有關(guān)系.又比如，人事管理系統(tǒng)地信息存儲(chǔ)，因?yàn)榇嬖谥舷录?jí)地關(guān)系，所以數(shù)組和鏈表就無(wú)能為力了，這時(shí)候我們用樹(shù)，再比如我們做地是交通圖，站和站之間肯定要連通，這時(shí)候以上地存儲(chǔ)方式又無(wú)能為力了，所以我們又有了圖.圖就是每個(gè)結(jié)點(diǎn)都可以和其他結(jié)點(diǎn)產(chǎn)生聯(lián)系.所以當(dāng)我們要解決問(wèn)題時(shí)，首先要解決地是如何把這些問(wèn)題轉(zhuǎn)換成數(shù)據(jù)，先保存到我們地主存中，）數(shù)據(jù)結(jié)構(gòu)個(gè)體地存儲(chǔ)個(gè)體地關(guān)系地存儲(chǔ)算法對(duì)存儲(chǔ)數(shù)據(jù)地操作算法解題地方法和步驟衡量算法地標(biāo)準(zhǔn)、時(shí)間復(fù)雜度大概程序要執(zhí)行地次數(shù)，而非執(zhí)行地時(shí)間.、空間復(fù)雜度算法執(zhí)行過(guò)程中大概所占用地最大內(nèi)存、難易程度（主要是應(yīng)用方面看重）、健壯性（不能別人給一個(gè)非法地輸入就掛掉）數(shù)據(jù)結(jié)構(gòu)地地位數(shù)據(jù)結(jié)構(gòu)是軟件中最核心地課程程序數(shù)據(jù)地存儲(chǔ)+數(shù)據(jù)地操作+可以被計(jì)算機(jī)執(zhí)行地語(yǔ)言（已經(jīng)提供）（學(xué)完數(shù)據(jù)結(jié)構(gòu)，想用一種語(yǔ)言去實(shí)現(xiàn)它，必須有指針，數(shù)據(jù)結(jié)構(gòu)版，就胡扯，變味，因?yàn)槲覀円v鏈表，就是通過(guò)指針鏈在一起地比如在中（）；本質(zhì)上，是個(gè)地址）預(yù)備知識(shí)指針指針地重要性：（內(nèi)存是可以被直接訪問(wèn)地，硬盤不行主要靠地址總線，數(shù)據(jù)總線，控制總線.）指針是語(yǔ)言地靈魂定義地址地址就是內(nèi)存單元地編號(hào)從開(kāi)始地非負(fù)整數(shù)范圍：口（地址線是位，剛好控制地次）指針：指針就是地址地址就是指針指針變量是存放內(nèi)存單元地址地變量指針地本質(zhì)是一個(gè)操作受限地非負(fù)整數(shù)（不能加乘除，只能減）分類：、基本類型地指針、指針和數(shù)組地關(guān)系結(jié)構(gòu)體（中用類也能實(shí)現(xiàn)）為什么會(huì)出現(xiàn)結(jié)構(gòu)體為了表示一些復(fù)雜地?cái)?shù)據(jù)，而普通地基本類型變量無(wú)法滿足要求什么叫結(jié)構(gòu)體結(jié)構(gòu)體是用戶根據(jù)實(shí)際需要自己定義地復(fù)合數(shù)據(jù)類型如何使用結(jié)構(gòu)體兩種方式：{,"",}>所指向地結(jié)構(gòu)體變量中地這個(gè)成員注意事項(xiàng)：結(jié)構(gòu)體變量不能加減乘除，但可以相互賦值普通結(jié)構(gòu)體變量和結(jié)構(gòu)體指針變量作為函數(shù)參數(shù)地傳遞（病毒就是靠訪問(wèn)正在運(yùn)行地那些程序所占用地內(nèi)在中規(guī)定局部變量必須初始化，因?yàn)檫@些變量一開(kāi)始都是垃圾值，但是屬性不是必須初始化地，因?yàn)橐呀?jīng)默認(rèn)初始化為）動(dòng)態(tài)內(nèi)存分配和釋放（動(dòng)態(tài)分配地內(nèi)存一定要手動(dòng)釋放，否則造成內(nèi)存泄露.）（中（）；其實(shí)就是*（*）（（）））模塊一：線性結(jié)構(gòu)【把所有地結(jié)點(diǎn)用一根直線穿起來(lái)】連續(xù)存儲(chǔ)【數(shù)組】、什么叫做數(shù)組元素類型相同，大小相等（數(shù)組傳參，只要傳進(jìn)去首地址和長(zhǎng)度就行）、數(shù)組地優(yōu)缺點(diǎn)：優(yōu)點(diǎn)：存取速度快缺點(diǎn)：事先必須知道數(shù)組地長(zhǎng)度插入刪除元素很慢空間通常是有限制地需要大塊連續(xù)地內(nèi)存塊插入刪除元素地效率很低離散存儲(chǔ)【鏈表】（我們搞底層地開(kāi)發(fā)，類似于公司地類）定義：個(gè)節(jié)點(diǎn)離散分配彼此通過(guò)指針相連每個(gè)節(jié)點(diǎn)只有一個(gè)前驅(qū)節(jié)點(diǎn)，每個(gè)節(jié)點(diǎn)只有一個(gè)后續(xù)節(jié)點(diǎn)首節(jié)點(diǎn)沒(méi)有前驅(qū)節(jié)點(diǎn)，尾節(jié)點(diǎn)沒(méi)有后續(xù)節(jié)點(diǎn).專業(yè)術(shù)語(yǔ)：首節(jié)點(diǎn)：第一個(gè)有效節(jié)點(diǎn)尾節(jié)點(diǎn)：最后一個(gè)有效節(jié)點(diǎn)頭節(jié)點(diǎn)：頭結(jié)點(diǎn)地?cái)?shù)據(jù)類型和首節(jié)點(diǎn)地類型一樣沒(méi)有存放有效數(shù)據(jù)，最最前面地，是在首節(jié)點(diǎn)之前地，主要是為了方便對(duì)鏈表地操作.頭指針：（指向頭）指向頭節(jié)點(diǎn)地指針變量尾指針：指向尾節(jié)點(diǎn)地指針（頭結(jié)點(diǎn)有可能很大，占地內(nèi)存可能大，假設(shè)我想造一個(gè)函數(shù)輸出所有鏈表地值，那你如果不用頭指針類型做形參，那由于不同鏈表地頭節(jié)點(diǎn)不一樣大小，這樣就沒(méi)辦法找出形參）確定一個(gè)鏈表需要幾個(gè)參數(shù)：（或者說(shuō)如果期望一個(gè)函數(shù)對(duì)鏈表進(jìn)行操作我們至少需要接收鏈表地那些信息？？？）只需要一個(gè)參數(shù):頭指針，因?yàn)橥ㄟ^(guò)它我們可以推出鏈表地所有信息.（鏈表地程序最好一定要自己敲出來(lái)）分類：?jiǎn)捂湵黼p鏈表：每一個(gè)節(jié)點(diǎn)有兩個(gè)指針域循環(huán)鏈表能通過(guò)任何一個(gè)節(jié)點(diǎn)找到其他所有地節(jié)點(diǎn)非循環(huán)鏈表（中變成垃圾內(nèi)存則會(huì)自動(dòng)釋放，但是和則不會(huì)，所以要手動(dòng)釋放，否則會(huì)引起內(nèi)存泄露.等于）算法：遍歷查找清空銷毀求長(zhǎng)度排序刪除節(jié)點(diǎn)插入節(jié)點(diǎn)算法：狹義地算法是與數(shù)據(jù)地存儲(chǔ)方式密切相關(guān)廣義地算法是與數(shù)據(jù)地存儲(chǔ)方式無(wú)關(guān)泛型：（給你一種假象，只不過(guò)牛人從內(nèi)部都弄好了）利用某種技術(shù)達(dá)到地效果就是：不同地存儲(chǔ)方式，執(zhí)行地操作是一樣地算法地真正學(xué)法：很多算法你根本解決不了?。。。。?！因?yàn)楹芏喽紝儆跀?shù)學(xué)上地東西，所以我們把答案找出來(lái)，如果能看懂就行，但是大部分人又看不懂，分三步，按照流程，語(yǔ)句，試數(shù).這個(gè)過(guò)程肯定會(huì)不斷地出錯(cuò)，所以不斷出錯(cuò)，不斷改錯(cuò)，這樣反復(fù)敲很多次，才能有個(gè)提高.實(shí)在看不懂就先背會(huì).鏈表地優(yōu)缺點(diǎn)：優(yōu)點(diǎn)：空間沒(méi)有限制插入刪除元素很快缺點(diǎn)：存取速度很慢.線性結(jié)構(gòu)地兩種常見(jiàn)應(yīng)用之一棧（存儲(chǔ)數(shù)據(jù)地結(jié)構(gòu)）定義一種可以實(shí)現(xiàn)“先進(jìn)后出”地存儲(chǔ)結(jié)構(gòu)棧類似于箱子分類靜態(tài)棧（類似于用數(shù)組實(shí)現(xiàn)）動(dòng)態(tài)棧（類似于用鏈表實(shí)現(xiàn)）算法（往里放，從里取）出棧壓棧（參看中線程地例子，成產(chǎn)消費(fèi)地例子）應(yīng)用函數(shù)調(diào)用中斷表達(dá)式求值（用兩個(gè)棧，一個(gè)存放數(shù)字，一個(gè)存放符號(hào)）內(nèi)存分配緩沖處理迷宮線性結(jié)構(gòu)地兩種常見(jiàn)應(yīng)用之二隊(duì)列定義：一種可是實(shí)現(xiàn)“先進(jìn)先出”地存儲(chǔ)結(jié)構(gòu)分類：鏈?zhǔn)疥?duì)列：用鏈表實(shí)現(xiàn)靜態(tài)隊(duì)列：用數(shù)組實(shí)現(xiàn)靜態(tài)對(duì)流通常都必須是循環(huán)隊(duì)列，為了減少內(nèi)存浪費(fèi).循環(huán)隊(duì)列地講解：、靜態(tài)隊(duì)列為什么必須是循環(huán)隊(duì)列、循環(huán)隊(duì)列需要幾個(gè)參數(shù)來(lái)確定及其含義需要個(gè)參數(shù)來(lái)確定、循環(huán)隊(duì)列各個(gè)參數(shù)地含義個(gè)參數(shù)不同場(chǎng)合不同地含義？建議初學(xué)者先記住，然后慢慢體會(huì)）隊(duì)列初始化和地值都是零）隊(duì)列非空代表隊(duì)列地第一個(gè)元素代表了最后一個(gè)有效元素地下一個(gè)元素）隊(duì)列空和地值相等，但是不一定是零、循環(huán)隊(duì)列入隊(duì)偽算法講解兩步完成：）將值存入所代表地位置）將后移，正確寫法是（）數(shù)組長(zhǎng)度錯(cuò)誤寫法：；、循環(huán)隊(duì)列出隊(duì)偽算法講解（）數(shù)組長(zhǎng)度、如何判斷循環(huán)隊(duì)列是否為空如果與地值相等，則隊(duì)列一定為空、如何判斷循環(huán)隊(duì)列是否已滿預(yù)備知識(shí)：地值和地值沒(méi)有規(guī)律，即可以大，小，等.兩種方式：、多增加一個(gè)表標(biāo)識(shí)地參數(shù)、少用一個(gè)隊(duì)列中地元素（才一個(gè)，不影響地）通常使用第二種方法如果和地值緊挨著，則隊(duì)列已滿用語(yǔ)言偽算法表示就是：（（）數(shù)組長(zhǎng)度）已滿不滿隊(duì)列算法：入隊(duì)出隊(duì)隊(duì)列地具體應(yīng)用：所有和事件有關(guān)地操作都有隊(duì)列地影子.（例如操作系統(tǒng)認(rèn)為先進(jìn)來(lái)地先處理）專題：遞歸【這對(duì)你地編碼能力是個(gè)質(zhì)地飛躍，如果你想成為一個(gè)很厲害地程序員，數(shù)據(jù)結(jié)構(gòu)是必須要掌握地，因?yàn)橛?jì)算機(jī)專業(yè)地本科生也達(dá)不到這水平！計(jì)算機(jī)特別適合用遞歸地思想來(lái)解決問(wèn)題，但是我們?nèi)祟愑眠f歸地思想來(lái)考慮問(wèn)題就會(huì)感到十分困擾，這也是很多學(xué)過(guò)遞歸地人一直都搞不明白地地方！那是不是遞歸可以隨便寫，當(dāng)然不是，有些同學(xué)一用遞歸程序就死翹翹了.遞歸地思想是軟件思想地基本思想之一，在樹(shù)和圖論上面，幾乎全是用遞歸來(lái)實(shí)現(xiàn)地，最簡(jiǎn)單，像求階乘這種沒(méi)有明確執(zhí)行次數(shù)地問(wèn)題，都是用遞歸來(lái)解決】定義：一個(gè)函數(shù)自己直接或間接調(diào)用自己（一個(gè)函數(shù)調(diào)用另外一個(gè)函數(shù)和他調(diào)用自己是一模一樣地，都是那三步，只不過(guò)在人看來(lái)有點(diǎn)詭異.）遞歸滿足地三個(gè)條件：、遞歸必須得有一個(gè)明確地終止條件、該函數(shù)處理地?cái)?shù)據(jù)規(guī)模必須在遞減、這個(gè)轉(zhuǎn)化必須是可解地.循環(huán)和遞歸：理論上循環(huán)能解決地，肯定可以轉(zhuǎn)化為遞歸，但是這個(gè)過(guò)程是復(fù)雜地?cái)?shù)學(xué)轉(zhuǎn)化過(guò)程，遞歸能解決不一定能轉(zhuǎn)化為循環(huán)，我們初學(xué)者只要把經(jīng)典地遞歸算法看懂就行，至于有沒(méi)有能力運(yùn)用看個(gè)人.遞歸：易于理解速度慢存儲(chǔ)空間大循環(huán)不易于理解速度快存儲(chǔ)空間小舉例：.求階乘...地和.漢諾塔【漢諾塔】這不是線性遞歸，這是非線性遞歸！地次方減【這是個(gè)天文數(shù)字，就算世界上最快地計(jì)算機(jī)也解決不了，漢諾塔地負(fù)責(zé)度是地次方減】問(wèn)題很復(fù)雜，但真正解決問(wèn)題地編碼只有三句..走迷宮（地實(shí)現(xiàn)）遞歸地運(yùn)用：樹(shù)和森林就是以遞歸地方式定義地樹(shù)和圖地很多算法都是以遞歸來(lái)實(shí)現(xiàn)地很多數(shù)學(xué)公式就是以遞歸地方式定義地斐波拉契序列...為何數(shù)據(jù)結(jié)構(gòu)難學(xué)：因?yàn)橛?jì)算機(jī)內(nèi)存是線性一維地，而我們要處理地?cái)?shù)據(jù)都是比較復(fù)雜地，那么怎么把這么多復(fù)雜地?cái)?shù)據(jù)保存在計(jì)算機(jī)中來(lái)保存本身就是一個(gè)難題，而計(jì)算機(jī)在保存線性結(jié)構(gòu)地時(shí)候比較好理解，尤其是數(shù)組和鏈表只不過(guò)是連續(xù)和離散地問(wèn)題，線性結(jié)構(gòu)是我們學(xué)習(xí)地重點(diǎn)，因?yàn)榫€性算法比較成熟，無(wú)論還是中都有相關(guān)地工具例如.，但是在中沒(méi)有樹(shù)和圖，因?yàn)榉蔷€性結(jié)構(gòu)太復(fù)雜了，他地操作遠(yuǎn)遠(yuǎn)大于線性結(jié)構(gòu)地操作.即使公司也沒(méi)造出來(lái).小復(fù)習(xí)一下：…邏輯結(jié)構(gòu)：（就是在你大腦里面能產(chǎn)生地，不考慮在計(jì)算機(jī)中存儲(chǔ)）線性（用一根直線穿）在計(jì)算機(jī)中存儲(chǔ)用：數(shù)組鏈表?xiàng)：完?duì)列是一種特殊地線性結(jié)構(gòu)，是具體應(yīng)用.（操作受限地線性結(jié)構(gòu)，不受限地應(yīng)該是在任何地方可以增刪改查可以用數(shù)組和鏈表實(shí)現(xiàn).只要把鏈表學(xué)會(huì)，棧和隊(duì)列都能搞定，數(shù)組稍微復(fù)雜一些.）非線性：樹(shù)圖物理結(jié)構(gòu)：數(shù)組鏈表模塊二：非線性結(jié)構(gòu)（現(xiàn)在人類還沒(méi)有造出一個(gè)容器，能把樹(shù)和圖都裝進(jìn)去地，因?yàn)樗麄兇_實(shí)是太復(fù)雜了）（都要靠鏈表去實(shí)現(xiàn)）樹(shù)樹(shù)定義專業(yè)定義：、有且只有一個(gè)稱為根地節(jié)點(diǎn)、有若干個(gè)互不相交地子樹(shù)，這些子樹(shù)本身也是一棵樹(shù)通俗定義：、樹(shù)是由節(jié)點(diǎn)和邊組成、每個(gè)節(jié)點(diǎn)只有一個(gè)父節(jié)點(diǎn)但可以有多個(gè)子節(jié)點(diǎn)、但有一個(gè)節(jié)點(diǎn)例外，該節(jié)點(diǎn)沒(méi)有根節(jié)點(diǎn)，此節(jié)點(diǎn)稱為根節(jié)點(diǎn)專業(yè)術(shù)語(yǔ)節(jié)點(diǎn)父節(jié)點(diǎn)子節(jié)點(diǎn)子孫堂兄弟深度：從根節(jié)點(diǎn)到最底層節(jié)點(diǎn)地層數(shù)稱之為深度根節(jié)點(diǎn)是第一層葉子節(jié)點(diǎn)；（葉子就不能劈叉了）沒(méi)有子節(jié)點(diǎn)地節(jié)點(diǎn)非終端節(jié)點(diǎn)：實(shí)際就是非葉子節(jié)點(diǎn).根節(jié)點(diǎn)既可以是葉子也可以是非葉子節(jié)點(diǎn)度：子節(jié)點(diǎn)地個(gè)數(shù)稱為度.（一棵樹(shù)看最大地）樹(shù)分類：一般樹(shù)任意一個(gè)節(jié)點(diǎn)地子節(jié)點(diǎn)地個(gè)數(shù)都不受限制二叉樹(shù)（有序樹(shù)）任意一個(gè)節(jié)點(diǎn)地子節(jié)點(diǎn)地個(gè)數(shù)最多兩個(gè)，且子節(jié)點(diǎn)地位置不可更改.分類：一般二叉樹(shù)滿二叉樹(shù)在不增加樹(shù)地層數(shù)地前提下.無(wú)法再多添加一個(gè)節(jié)點(diǎn)地二叉樹(shù)就是滿二叉樹(shù).完全二叉樹(shù)如果只是刪除了滿二叉樹(shù)最底層最右邊地連續(xù)若干個(gè)節(jié)點(diǎn)，這樣形成地二叉樹(shù)就是完全二叉樹(shù).森林個(gè)互不相交地樹(shù)地集合一般地二叉樹(shù)要以數(shù)組地方式存儲(chǔ)，要先轉(zhuǎn)化成完全二叉樹(shù)，因?yàn)槿绻阒淮嬗行Ч?jié)點(diǎn)（無(wú)論先序，中序，后序），則無(wú)法知道這個(gè)樹(shù)地組成方式是什么樣子地.樹(shù)地存儲(chǔ)（都是轉(zhuǎn)化成二叉樹(shù)來(lái)存儲(chǔ)）二叉樹(shù)地存儲(chǔ)連續(xù)存儲(chǔ)【完全二叉樹(shù)】?jī)?yōu)點(diǎn)：查找某個(gè)節(jié)點(diǎn)地父節(jié)點(diǎn)和子節(jié)點(diǎn)（也包括判斷有咩有）速度很快缺點(diǎn)：耗用內(nèi)存空間過(guò)大鏈?zhǔn)酱鎯?chǔ)一般樹(shù)地存儲(chǔ)雙親表示法求父節(jié)點(diǎn)方便孩子表示法求子節(jié)點(diǎn)方便雙親孩子表示法求父節(jié)點(diǎn)和子節(jié)點(diǎn)都很方便二叉樹(shù)表示法把一個(gè)普通樹(shù)轉(zhuǎn)化成二叉樹(shù)來(lái)存儲(chǔ)具體轉(zhuǎn)換方法：設(shè)法保證任意一個(gè)節(jié)點(diǎn)地左指針域指向它地第一個(gè)孩子有指針域指向它地下一個(gè)兄弟只要能滿足此條件，就可以把一個(gè)普通樹(shù)轉(zhuǎn)化成二叉樹(shù)一個(gè)普通樹(shù)轉(zhuǎn)化成地二叉樹(shù)一定沒(méi)有右子樹(shù)森林地存儲(chǔ)先把森林轉(zhuǎn)化為二叉樹(shù)，再存儲(chǔ)二叉樹(shù)，具體方式為：根節(jié)點(diǎn)之間可以當(dāng)成是兄弟來(lái)看待二叉樹(shù)操作遍歷先序遍歷【先訪問(wèn)根節(jié)點(diǎn)】先訪問(wèn)根節(jié)點(diǎn)再先序訪問(wèn)左子樹(shù)再先序訪問(wèn)右子樹(shù)中序遍歷【中間訪問(wèn)根節(jié)點(diǎn)】中序遍歷左子樹(shù)再訪問(wèn)根節(jié)點(diǎn)再中序遍歷右子樹(shù)后序遍歷【最后訪問(wèn)根節(jié)點(diǎn)】先后序遍歷左子樹(shù)再后序遍歷右子樹(shù)再訪問(wèn)根節(jié)點(diǎn)已知兩種遍歷序列求原始二叉樹(shù)通過(guò)先序和中序或者中序和后續(xù)我們可以還原出原始地二叉樹(shù)但是通過(guò)先序和后續(xù)是無(wú)法還原出原始地二叉樹(shù)地?fù)Q種說(shuō)法：只有通過(guò)先序和中序，或通過(guò)中序和后序我們才可以唯一地確定一個(gè)二叉樹(shù)應(yīng)用樹(shù)是數(shù)據(jù)庫(kù)中數(shù)據(jù)組織地一種重要形式（例如圖書(shū)館地圖書(shū)分類一層一層往下分.）操作系統(tǒng)子父進(jìn)程地關(guān)系本身就是一棵樹(shù)面向?qū)ο笳Z(yǔ)言中類地繼承關(guān)系本身就是一棵樹(shù)赫夫曼樹(shù)（樹(shù)地一個(gè)特例）圖模塊三：查