數(shù)據(jù)結(jié)構(gòu)筆記

1、/2018/5/23數(shù)據(jù)結(jié)構(gòu)概述：預(yù)備知識模塊一：線性結(jié)構(gòu) 連續(xù)存儲數(shù)組 離散結(jié)構(gòu)鏈表 線性結(jié)構(gòu)的兩種常見應(yīng)用之一 棧（堆棧） 線性結(jié)構(gòu)的兩種常見應(yīng)用之二 隊列 專題：遞歸 1.1+2.+100的和 2.求階乘 3.漢諾塔 4.走迷宮模塊二：非線性結(jié)構(gòu) 樹 圖模塊三：查找和排序 折半查找 排序：冒泡 插入 選擇 快速排序 歸并排序補錄：java中容器和數(shù)據(jù)結(jié)構(gòu)相關(guān)知識 iterator接口 map 哈希表嚴(yán)蔚敏-高一凡-黃國瑜/2018/5/24數(shù)據(jù)結(jié)構(gòu)概述 定義我們?nèi)绾伟熏F(xiàn)實中大量而復(fù)雜的問題以特定的數(shù)據(jù)類型和特定的存儲結(jié)構(gòu)保存到主存儲器（內(nèi)存）中，以及在此基礎(chǔ)上為實現(xiàn)某個功能（比如查找或刪

2、除某個元素，對所有元素進(jìn)行排序）而執(zhí)行的相應(yīng)操作，這個相應(yīng)操作叫做算法。特定的數(shù)據(jù)類型:個體如何保存特定的存儲結(jié)構(gòu):個體與個體的關(guān)系如何保存數(shù)據(jù)結(jié)構(gòu) = 個體的存儲 + 個體關(guān)系的存儲算法（狹義） = 對存儲數(shù)據(jù)的操作算法：即解題的方法和步驟 衡量算法的標(biāo)準(zhǔn)1. 時間復(fù)雜度重要大概程序要執(zhí)行的次數(shù)，而非執(zhí)行的時間2. 空間復(fù)雜度重要算法執(zhí)行過程中大概所占用的最大內(nèi)存3. 難易程度4. 健壯性 數(shù)據(jù)結(jié)構(gòu)的地位 數(shù)據(jù)結(jié)構(gòu)是軟件中最核心的課程。程序 = 數(shù)據(jù)的存儲 + 數(shù)據(jù)的操作 + 可以被計算機執(zhí)行的語言預(yù)備知識： 指針 結(jié)構(gòu)體 動態(tài)內(nèi)存的分配和釋放 指針：指針的重要性:表示一些復(fù)雜的數(shù)據(jù)結(jié)構(gòu) 快

3、速的傳送數(shù)據(jù) 使函數(shù)返回一個以上的值能否直接訪問硬件 能夠方便的使用數(shù)組和字符串是理解面向?qū)ο笳Z言中引用的基礎(chǔ)指針是c語言的靈魂定義地址內(nèi)存單元的編號從0開始的非負(fù)整數(shù)范圍0-ffffffff 【0 到 4g-1】 注：無論一個變量有多大，其地址只用第一個字節(jié)的地址表示，均只占四個字節(jié)。指針指針就是地址 地址就是指針指針變量就是存放內(nèi)存單元地址的變量指針本質(zhì)上就是一個操作受限的非負(fù)整數(shù)分類1、基本類型指針【略】基本概念int i=10;int *p = &i; /等價于 int *p;p = &i;詳解這兩部操作：1）p存放了i的地址，所以我們說p指向了i2）p和i是完全不同的兩個變量，修改其

4、中的任意一個變量的值，不會影響另一變量的值3）p指向i，*p就是i變量本身。更形象的說所有出現(xiàn) *p的地方都可以換成i，所有出現(xiàn)i的地方都可以換成*p4）int * p，不是定義了*p的參數(shù)，而是定義了一個變量p，為int *類型。總結(jié)：1、如何一個指針變量(假定為p)存放了某個普通變量(假定為i)的地址，那我們就可以說：“p指向了i”， 但p與i是兩個不同的變量，修改p的值不影響i的值，修改i的值不影響p的值.2、*p等價于i 或者說*p可以與i在任何地方互換3、如果一個指針變量指向了某個普通變量，則*指針變量 就完全等價于該普通變量注意：指針變量也是變量，只不過它存放的不能是內(nèi)存單元的內(nèi)容

5、，只能存放內(nèi)存單元的地址普通變量前不能加*常量和表達(dá)式前不能加&如何通過被調(diào)函數(shù)修改主調(diào)函數(shù)中普通變量的值 實參為相關(guān)變量的地址 形參為以該變量的類型為類型的指針變量 在被調(diào)函數(shù)中通過 *形參變量名 的方式就可以修改主函數(shù)相關(guān)變量的值eg:void f(int * p) /ii *p = 100; /iiiint main(void)int i = 9; f(&i); /iprintf(“i = %dn”, i);指針和數(shù)組的關(guān)系指針 和 一維數(shù)組數(shù)組名一維數(shù)組名是個指針常量，它存放的是一維數(shù)組第一個元素的地址， 它的值不能被改變一維數(shù)組名指向的是數(shù)組的第一個元素下標(biāo)和指針的關(guān)系ai *(a+

6、i) *a+3 = a0+3假設(shè)指針變量的名字為p則p+i的值是p+i*(p所指向的變量所占的字節(jié)數(shù))指針變量的運算指針變量不能相加，不能相乘，不能相除如果兩指針變量屬于同一數(shù)組，則可以相減指針變量可以加減一整數(shù)，前提是最終結(jié)果不能超過指針允許指向的范圍p+i的值是p + i*(p所指向的變量所占的字節(jié)數(shù))p-i的值是p - i*(p所指向的變量所占的字節(jié)數(shù))p+ p+1p- p-1舉例如何通過被調(diào)函數(shù)修改主調(diào)函數(shù)中一維數(shù)組的內(nèi)容【如何界定一維數(shù)組】兩個參數(shù)存放數(shù)組首元素的指針變量 存放數(shù)組元素長度的整型變量所有的指針變量只占4個子節(jié) 用第一個字節(jié)的地址表示整個變量的地址動態(tài)內(nèi)存分配和釋放：程

7、序在運行過程中可以動態(tài)的增加或減少內(nèi)存分配動態(tài)構(gòu)造一維數(shù)組假設(shè)動態(tài)構(gòu)造一個int型數(shù)組int *p = (int *)malloc(int len);1、malloc只有一個int型的形參，表示要求系統(tǒng)分配的字節(jié)數(shù)2、malloc函數(shù)的功能是請求系統(tǒng)len個字節(jié)的內(nèi)存空間，如果請求分配成功，則返回第一個字節(jié)的地址，如果分配不成功，則返回null3、malloc函數(shù)能且只能返回第一個字節(jié)的地址，所以我們需要把類型不一樣。即所占的字節(jié)數(shù)也不確定這個無任何實際意義的第一個字節(jié)的地址（俗稱干地址）轉(zhuǎn)化為一個有實際意義的地址，因此malloc前面必須加（數(shù)據(jù)類型 *）,表示把這個無實際意義的第一個字節(jié)的

8、地址轉(zhuǎn)化為相應(yīng)類型的地址。如：int *p = (int *)malloc(50); 表示將系統(tǒng)分配好的50個字節(jié)的第一個字節(jié)的地址轉(zhuǎn)化為int *型的地址，更準(zhǔn)確的說是把第一個字節(jié)的地址轉(zhuǎn)化為四個字節(jié)的地址，這樣p就指向了第一個的四個字節(jié)，p+1就指向了第2個的四個字節(jié)，p+i就指向了第i+1個的4個字節(jié)。p0就是第一個元素， pi就是第 i+1個元素double *p = (double *)malloc(80); 表示將系統(tǒng)分配好的80個字節(jié)的第一個字節(jié)的地址轉(zhuǎn)化為double *型的地址，更準(zhǔn)確的說是把第一個字節(jié)的地址轉(zhuǎn)化為8個字節(jié)的地址，這樣p就指向了第一個的8個字節(jié)，p+1就指向了

9、第2個的8個字節(jié)，p+i就指向了第i+1個的8個字節(jié)。p0就是第一個元素， pi就是第i+1個元素free（p）：動態(tài)分配的內(nèi)存，必須free()釋放，系統(tǒng)不會自動釋放。釋放p所指向的內(nèi)存，而不是釋放p本身所占用的內(nèi)存【重點：動態(tài)分配數(shù)組內(nèi)存】 int * parr = (int *) malloc (sizeof(int) * len); (最后一個*代表了乘 分配了4 * len個字節(jié))模塊一：線性結(jié)構(gòu)【把所有的結(jié)點用一根直線穿起來】連續(xù)存儲數(shù)組1.什么叫數(shù)組 元素類型離散結(jié)構(gòu)鏈表線性結(jié)構(gòu)中兩種常用應(yīng)用之一 棧 定義 一種可以實現(xiàn)“先進(jìn)后出”的存儲結(jié)構(gòu) 只能從棧尾（棧頂）進(jìn)和出。 棧類似于

10、箱子，局部變量都是在棧中存儲的。 分類 靜態(tài)棧【以數(shù)組為內(nèi)核】 動態(tài)?！疽枣湵頌閮?nèi)核】 算法 出棧 ptop向下移一個，pbottom不變 壓棧（入棧） ptop向上移一個，pbottom不變應(yīng)用 函數(shù)調(diào)用 中斷 表達(dá)式求值（例如計算器的編寫） 內(nèi)存分配 緩沖處理 /2018/5/20線性結(jié)構(gòu)中兩種常用應(yīng)用之二 隊列 定義： 一種可以實現(xiàn)“先進(jìn)先出”的存儲結(jié)構(gòu) 分類： 變量名：front（頭部） 和 rear（尾部） 鏈?zhǔn)疥犃?用鏈表實現(xiàn) 靜態(tài)隊列-用數(shù)組實現(xiàn) 注：在隊首的位置刪除元素，然后隊首指針指向下一個元素在隊尾的位置添加元素，然后隊尾指針指向下一個元素 【重點】rear指向的是隊列最后

11、一個元素的下一個元素【重點】front指向的是隊列的第一個元素隊列算法：入隊出隊隊列的具體應(yīng)用： 所有和時間及有關(guān)的操作都有隊列的影子。靜態(tài)隊列：注：將數(shù)組的部分功能給去掉，然后再加入一些功能。靜態(tài)隊列通常都必須是循環(huán)隊列。問題：如果按照普通的數(shù)組來存儲隊列的話。每次刪掉一個元素，頭部指針都會指向下一個元素，會造成原來元素的位置空間浪費，只能被使用一次而不能重復(fù)被使用。只能增不能減。循環(huán)隊列的講解：1. 靜態(tài)隊列為什么必須是循環(huán)隊列問題：如果按照普通的數(shù)組來存儲隊列的話。每次刪掉一個元素，頭部指針都會指向下一個元素，會造成原來元素的位置空間浪費，只能被使用一次而不能重復(fù)被使用。只能增不能減。解

12、決方法：當(dāng)front和rear移動到頂部（隊尾）時，下一次移動時可以讓它再移動到底部（隊首），首尾相連，這實際就是循環(huán)隊列。2. 循環(huán)隊列需要幾個參數(shù)來確定需要兩個參數(shù)來確定 front rear3. 循環(huán)隊列各個參數(shù)的含義這兩個參數(shù)在不同場合有不同的含義建議初學(xué)者先記住，然后慢慢體會1） 隊列初始化front和rear的值都是02） 隊列非空front代表的是隊列的第一個元素rear代表的是隊列的最后一個有效元素的下一個元素3） 隊列空front和rear的值相等，但不一定為04. 循環(huán)隊列入隊偽算法講解兩步完成，詳解見圖5. 循環(huán)隊列出隊偽算法講解6. 如何判斷循環(huán)隊列是否為空如果fron

13、t和rear的值相等，則該隊列就一定為空。7. 如何判斷循環(huán)隊列是否為滿預(yù)備知識：front的值可能比rear大，也完全有可能比rear小，當(dāng)然也可能相等。兩種方式：1.多增加一個標(biāo)志位參數(shù) 2.少用一個元素【通常使用第二種元素】隊列中有n個元素，只要放到n-1個元素，即認(rèn)為隊列已滿。/2018/5/21專題：遞歸 定義：一個函數(shù)自己直接或間接調(diào)用自己遞歸滿足的三個條件：1. 遞歸必須得有一個明確的終止條件2. 遞歸的值可以是遞增的，但所處理的數(shù)據(jù)規(guī)模必須在遞減（n-n-1-n-2）3. 這個轉(zhuǎn)化必須是可解的循環(huán)和遞歸所有的循環(huán)都可以用遞歸實現(xiàn)，但所有的遞歸不一定都可以用循環(huán)實現(xiàn)。遞歸： 循環(huán)

14、：易于理解 不易理解速度慢 速度快存儲空間大（步驟麻煩） 存儲空間小n - n-1 - n-2 - - 1舉例：1. 求階乘2. 1+2+100的和3. 漢諾塔4. 走迷宮遞歸的應(yīng)用： 樹和森林就是以遞歸的方式定義的 樹和圖的很多算法就是以遞歸來實現(xiàn)的 很多數(shù)學(xué)公式就是以遞歸的方式定義的(例如：斐波拉切數(shù)列)線性結(jié)構(gòu)總復(fù)習(xí)： 邏輯結(jié)構(gòu) 線性 數(shù)組 鏈表 棧和隊列是一種特殊的線性結(jié)構(gòu)，算線性結(jié)構(gòu)的應(yīng)用 非線性 樹 圖 物理結(jié)構(gòu)/2018/5/22模塊二：非線性結(jié)構(gòu) 樹定義： 專業(yè)定義：1. 有且只有一個稱為根的節(jié)點 2. 有若干個互補相交的子樹，這些子樹本身也是一棵樹 通俗定義：1. 樹是由節(jié)點

15、和邊組成2. 每個節(jié)點只有一個父節(jié)點但可以有多個子節(jié)點3. 但有一個節(jié)點例外，該節(jié)點沒有父節(jié)點，此節(jié)點成為根節(jié)點。專業(yè)術(shù)語 節(jié)點 父節(jié)點 子節(jié)點 子孫 堂兄弟深度：從根節(jié)點到最底層節(jié)點的層數(shù)稱之為深度（根節(jié)點是第一層）葉子節(jié)點：沒有子節(jié)點的節(jié)點。非終端節(jié)點：實際就是非葉子節(jié)點。度：子節(jié)點的個數(shù)成為度。分類：一般樹：任意一個節(jié)點的子節(jié)點的個數(shù)都不受限制二叉樹：任意一個節(jié)點的子節(jié)點的個數(shù)最多兩個，且子節(jié)點的位置不可更改。 分類： 一般二叉樹 滿二叉樹（完全二叉樹的特例）在不增加樹的層數(shù)的前提下，無法再多添加一個節(jié)點的二叉樹就是滿二叉樹 完全二叉樹（用數(shù)組存儲樹時，必須是完全二叉樹） 如果只是刪除了

16、滿二叉樹最底層最后邊的連續(xù)若干個節(jié)點，這樣形成的二叉樹就是完全二叉樹。 優(yōu)點：1.根據(jù)節(jié)點編號可以知道在第幾層 2.可以知道父節(jié)點和子節(jié)點森林：n個互不相交的樹的集合樹的存儲：二叉樹的存儲 連續(xù)存儲將二叉樹補充為完全二叉樹 以數(shù)組的形式存儲時，如果根據(jù)只保存有效節(jié)點的形式，無法推出全樹的樣子。 優(yōu)點：查找某個節(jié)點的父節(jié)點和子節(jié)點（也包括判斷有沒有父節(jié)點和子節(jié)點）速度很快。 缺點：耗用空間內(nèi)存過大 鏈?zhǔn)酱鎯σ话銟涞拇鎯?雙親表示法（求父節(jié)點方便） 把每一個節(jié)點編號，然后在每一個節(jié)點后標(biāo)記出其父節(jié)點的編號 孩子表示法（求子節(jié)點方便） 把每一個子節(jié)點都寫在每一個節(jié)點之后。 雙親孩子表示法（求父節(jié)點和

17、子節(jié)點都方便） 把每一個節(jié)點編號，然后在每一個節(jié)點后標(biāo)記出其父節(jié)點的編號，再把每一個子節(jié)點寫在之后。 二叉樹表示法 把一個普通樹轉(zhuǎn)化為二叉樹來存儲。 具體轉(zhuǎn)換方法： 設(shè)法保證任意一個節(jié)點的 左指針域指向它的第一個孩子 右指針域指向它下一個兄弟 只要滿足此條件，就可以把一個普通樹轉(zhuǎn)化為二叉樹 一個普通樹轉(zhuǎn)化成的二叉樹一定沒有右子樹森林的存儲先把森林轉(zhuǎn)化為二叉樹，再將二叉樹存儲 具體轉(zhuǎn)換方法： 1.設(shè)法保證其他樹的根節(jié)點當(dāng)成第一顆樹根節(jié)點的兄弟 2.設(shè)法保證其他任意一個節(jié)點的 左指針域指向它的第一個孩子 右指針域指向它下一個兄弟 只要滿足此條件，就可以把一片森林轉(zhuǎn)化為二叉樹 操作：遍歷先序遍歷先訪

18、問根節(jié)點中左右 先訪問根節(jié)點 再先序訪問左子樹 再先序訪問右子樹中序遍歷中間訪問根節(jié)點左中右 中序遍歷左子樹 再訪問根節(jié)點 再中序遍歷右子樹后序遍歷最后訪問根節(jié)點左右中 先后序遍歷左子樹 再后序遍歷右子樹 再訪問根節(jié)點只知道一顆二叉樹的一種遍歷方式是無法還原二叉樹的原貌的。已知兩種遍歷序列求原始二叉樹先中（可以） 中后（可以） 先后（不可以） 必須有一個中序已知先序和中序求后序例1：先序：abcdefgh 中序：bdceafhg 求后序講解：先序中第一個出現(xiàn)的一定是根節(jié)點，即a；所以中序中根節(jié)點a左邊的bdce是左子樹，右邊的fhg是右子樹；然后在先序序列中看左子樹bdce中哪個先出現(xiàn)，先出現(xiàn)的為根節(jié)點，即b；因為中序中dce在b的右側(cè)，所以dce是b的右子樹，哪個在先序中先出現(xiàn)為根節(jié)點，即c；中序中，c左側(cè)是d，右側(cè)是e，即為c的左右子節(jié)點；a右子樹方法類同。方法總結(jié)：由先序找到根節(jié)點（先出現(xiàn)為根節(jié)點），由中序找到根節(jié)點的左右子樹（左側(cè)左子樹，右側(cè)右子樹）。后序：decbhgfa例2:先序: abdghcefi中序: gdhbaecif求后序: ghdbeifca已知中序和后序求先序例：中序：bdceafhg 后序：decbhgfa 求先序：講解：后序中第一個出