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

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