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

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

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

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

5、，只能存放內(nèi)存單元的地址普通變量前不能加*常量和表達(dá)式前不能加&如何通過(guò)被調(diào)函數(shù)修改主調(diào)函數(shù)中普通變量的值 實(shí)參為相關(guān)變量的地址 形參為以該變量的類型為類型的指針變量 在被調(diào)函數(shù)中通過(guò) *形參變量名 的方式就可以修改主函數(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ù)組名是個(gè)指針常量，它存放的是一維數(shù)組第一個(gè)元素的地址， 它的值不能被改變一維數(shù)組名指向的是數(shù)組的第一個(gè)元素下標(biāo)和指針的關(guān)系ai *(a+

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

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

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

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

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

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

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

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

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

15、和邊組成2. 每個(gè)節(jié)點(diǎn)只有一個(gè)父節(jié)點(diǎn)但可以有多個(gè)子節(jié)點(diǎn)3. 但有一個(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)的個(gè)數(shù)成為度。分類：一般樹(shù)：任意一個(gè)節(jié)點(diǎn)的子節(jié)點(diǎn)的個(gè)數(shù)都不受限制二叉樹(shù)：任意一個(gè)節(jié)點(diǎn)的子節(jié)點(diǎn)的個(gè)數(shù)最多兩個(gè)，且子節(jié)點(diǎn)的位置不可更改。 分類： 一般二叉樹(shù) 滿二叉樹(shù)（完全二叉樹(shù)的特例）在不增加樹(shù)的層數(shù)的前提下，無(wú)法再多添加一個(gè)節(jié)點(diǎn)的二叉樹(shù)就是滿二叉樹(shù) 完全二叉樹(shù)（用數(shù)組存儲(chǔ)樹(shù)時(shí)，必須是完全二叉樹(shù)） 如果只是刪除了

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

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

18、問(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ù)的一種遍歷方式是無(wú)法還原二叉樹(shù)的原貌的。已知兩種遍歷序列求原始二叉樹(shù)先中（可以） 中后（可以） 先后（不可以） 必須有一個(gè)中序已知先序和中序求后序例1：先序：abcdefgh 中序：bdceafhg 求后序講解：先序中第一個(gè)出現(xiàn)的一定是根節(jié)點(diǎn)，即a；所以中序中根節(jié)點(diǎn)a左邊的bdce是左子樹(shù)，右邊的fhg是右子樹(shù)；然后在先序序列中看左子樹(shù)bdce中哪個(gè)先出現(xiàn)，先出現(xiàn)的為根節(jié)點(diǎn)，即b；因?yàn)橹行蛑衐ce在b的右側(cè)，所以dce是b的右子樹(shù)，哪個(gè)在先序中先出現(xiàn)為根節(jié)點(diǎn)，即c；中序中，c左側(cè)是d，右側(cè)是e，即為c的左右子節(jié)點(diǎn)；a右子樹(shù)方法類同。方法總結(jié)：由先序找到根節(jié)點(diǎn)（先出現(xiàn)為根節(jié)點(diǎn)），由中序找到根節(jié)點(diǎn)的左右子樹(shù)（左側(cè)左子樹(shù)，右側(cè)右子樹(shù)）。后序：decbhgfa例2:先序: abdghcefi中序: gdhbaecif求后序: ghdbeifca已知中序和后序求先序例：中序：bdceafhg 后序：decbhgfa 求先序：講解：后序中第一個(gè)出