數(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)用之二 隊(duì)列 專題：遞歸1.1+2+100 的和2. 求階乘3. 漢諾塔4. 走迷宮模塊二：非線性結(jié)構(gòu)樹圖模塊三：查找和排序折半查找歸并排序排序：冒泡 插入 選擇 快速排序補(bǔ)錄： 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)實(shí)中大量而復(fù)雜的問題以 特定的數(shù)據(jù)類型 和特定的存儲結(jié)構(gòu) 保存到主存儲器（內(nèi)存）中，以及在此基礎(chǔ)上為實(shí)現(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ù)的操作 + 可以被計(jì)算機(jī)執(zhí)行的語言預(yù)備知識：指針結(jié)構(gòu)體動態(tài)內(nèi)存的分配和釋放指針：指針的重要性：表示一些復(fù)

3、雜的數(shù)據(jù)結(jié)構(gòu)快速的傳送數(shù)據(jù)使函數(shù)返回一個以上的值能否直接訪問硬件能夠方便的使用數(shù)組和字符串是理解面向?qū)ο笳Z言中引用的基礎(chǔ)定義地址內(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 *類型?？偨Y(jié)：1、如何一個指針變量 (假定為 p) 存放了某個普通變量 (假定為 i) 的地址，那我 們就可以說：“ p指向了 i”，但p與i是兩個不同的變量，修改p的值不影 響 i 的值，修改 i 的值不影響 p 的值 .2、*p等價于i或者說*p可以與i在任何地方互換3、如果一個指針變量指向了某個普通變量，則

5、*指針變量 就完全等價于該普 通變量指針變量也是變量，只不過它存放的不能是內(nèi)存單元的內(nèi)容，只能存放內(nèi) 存單元的地址普通變量前不能加 *常量和表達(dá)式前不能加 &如何通過被調(diào)函數(shù)修改主調(diào)函數(shù)中普通變量的值I實(shí)參為相關(guān)變量的地址n形參為以該變量的類型為類型的指針變量IH在被調(diào)函數(shù)中通過*形參變量名的方式就可以修改主函數(shù)相關(guān)變量的值Eg:void f(int * p) /II *p = 100;/III int main(void)int i = 9;f(&i); /Iprintf( “i = %dn ”, i); 指針和數(shù)組的關(guān)系指針 和 一維數(shù)組數(shù)組名一維數(shù)組名是個指針常量， 它存

6、放的是一維數(shù)組第一個元素的地址， 它的值不能被改變一維數(shù)組名指向的是數(shù)組的第一個元素 下標(biāo)和指針的關(guān)系ai <<=>> *（a+i）*a+3 = a0+3 假設(shè)指針變量的名字為 p則 p+i 的值是 p+i*（p 所指向的變量所占的字節(jié)數(shù) ） 指針變量的運(yùn)算指針變量不能相加，不能相乘，不能相除 如果兩指針變量屬于同一數(shù)組，則可以相減 指針變量可以加減一整數(shù)，前提是最終結(jié)果不能超過指針允許指向的范圍p+i 的值是 p + i*（p 所指向的變量所占的字節(jié)數(shù) ）p-i 的值是 p - i*(p所指向的變量所占的字節(jié)數(shù) )p+<=>p+1p-<=>p-

7、1舉例如何通過被調(diào)函數(shù)修改主調(diào)函數(shù)中一維數(shù)組的內(nèi)容【如何界定一維數(shù)組】兩個參數(shù)存放數(shù)組首元素的指針變量存放數(shù)組元素長度的整型變量所有的指針變量只占 4 個子節(jié) 用第一個字節(jié)的地址表示整個變量的地址動態(tài)內(nèi)存分配和釋放： 程序在運(yùn)行過程中可以動態(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、mall

8、oc 函數(shù)能且只能返回第一個字節(jié)的地址 ，所以我們需要把 類型不一樣。 即所占的字節(jié)數(shù)也不確定 這個無任何實(shí)際意義的第一個字節(jié)的地址(俗稱干地 址)轉(zhuǎn)化為一個有實(shí)際意義的地址，因此 malloc 前面必須加(數(shù)據(jù)類型 * ), 表示把這個無實(shí)際意義的第一個字節(jié)的地址轉(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 就是

9、第一個元素， 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就指向了第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)存【重點(diǎn)：動態(tài)分配數(shù)組內(nèi)存】int * pArr =

10、(int *) malloc (sizeof(int) * len);(最后一個 *代表了乘 分配了 4 * len 個字節(jié))28模塊一：線性結(jié)構(gòu) 【把所有的結(jié)點(diǎn)用一根直線穿起來】 連續(xù)存儲 數(shù)組 1. 什么叫數(shù)組元素類型離散結(jié)構(gòu) 鏈表線性結(jié)構(gòu)中兩種常用應(yīng)用之一棧定義一種可以實(shí)現(xiàn)“先進(jìn)后出”的存儲結(jié)構(gòu)只能從棧尾（棧頂）進(jìn)和出。棧類似于箱子，局部變量都是在棧中存儲的。分類靜態(tài)棧【以數(shù)組為內(nèi)核】動態(tài)?！疽枣湵頌閮?nèi)核】算法出棧 pTop向下移一個，pBottom不變壓棧（入棧）pTop向上移一個，pBottom不變應(yīng)用函數(shù)調(diào)用中斷表達(dá)式求值（例如計(jì)算器的編寫）內(nèi)存分配緩沖處理/2018/5/20線性

11、結(jié)構(gòu)中兩種常用應(yīng)用之二 隊(duì)列定義：一種可以實(shí)現(xiàn)“先進(jìn)先出”的存儲結(jié)構(gòu)分類：變量名： front （頭部） 和 rear （尾部）鏈?zhǔn)疥?duì)列 - 用鏈表實(shí)現(xiàn)靜態(tài)隊(duì)列 - 用數(shù)組實(shí)現(xiàn)注：在隊(duì)首的位置刪除元素，然后隊(duì)首指針指向下一個元素 在隊(duì)尾的位置添加元素，然后隊(duì)尾指針指向下一個元素 【重點(diǎn)】 Rear 指向的是隊(duì)列最后一個元素的下一個元素 【重點(diǎn)】 Front 指向的是隊(duì)列的第一個元素 隊(duì)列算法：入隊(duì)出隊(duì)隊(duì)列的具體應(yīng)用：所有和時間及有關(guān)的操作都有隊(duì)列的影子。靜態(tài)隊(duì)列：注：將數(shù)組的部分功能給去掉，然后再加入一些功能。 靜態(tài)隊(duì)列通常都必須是循環(huán)隊(duì)列。 問題：如果按照普通的數(shù)組來存儲隊(duì)列的話。每次刪掉一

12、個元素，頭部指針都 會指向下一個元素，會造成原來元素的位置空間浪費(fèi)，只能被使用一次而不能 重復(fù)被使用。只能增不能減。循環(huán)隊(duì)列的講解：1. 靜態(tài)隊(duì)列為什么必須是循環(huán)隊(duì)列問題：如果按照普通的數(shù)組來存儲隊(duì)列的話。每次刪掉一個元素， 頭部指針都會指向下一個元素，會造成原來元素的位置空間浪費(fèi)， 只能被使用一次而不能重復(fù)被使用。只能增不能減。解決方法：當(dāng)front和rear移動到頂部（隊(duì)尾）時，下一次移動 時可以讓它再移動到底部（隊(duì)首），首尾相連，這實(shí)際就是循環(huán)隊(duì) 列。front1 妗態(tài)叭半小為卄總蟲匕換基昭環(huán)嘰茨KL禺扯的敷紐比貳食僅杵+權(quán)會導(dǎo)破 劇 逹 兒蠱麗l'j rrji 'I &

13、amp;水,込兒刃 樁禾姬他川.從噪fit進(jìn)樣設(shè)il駅 列足不行的，解Jfe涉法是:雪OnnSl rear1穆動 捌頂柳吋、下一次抽功時呵味讓 千：再棒創(chuàng)河屋ffif*白居fflit”眩 丈際我足懈耳限刑2. 循環(huán)隊(duì)列需要幾個參數(shù)來確定需要兩個參數(shù)來確定frontrear3. 循環(huán)隊(duì)列各個參數(shù)的含義這兩個參數(shù)在不同場合有不同的含義建議初學(xué)者先記住，然后慢慢體會1）隊(duì)列初始化front和rear的值都是02）隊(duì)列非空Fro nt代表的是隊(duì)列的第一個元素Rear代表的是隊(duì)列的最后一個有效元素的下一個元素3）隊(duì)列空front和rear的值相等，但不一定為04.循環(huán)隊(duì)列入隊(duì)偽算法講解兩步完成，詳解見圖

14、中Cban國1將值存入所代表的位竟2.錯溟的寫法：r=r+ 1;正確的寫法是.r(r* 1)% 組的長度如果front和rear的值相等,則該隊(duì)列就一定為空。7.如何判斷循環(huán)隊(duì)列是否為滿判斷隊(duì)列已滿:如舉r和的值索憑右.則衣叨駅列已謀 用（:語吉偽算法嵌朮就墾：if （ （r+lW數(shù)殂長度=f ）已滿else不滿預(yù)備知識:front的值可能比rear大,也完全有可能比rear 小, 當(dāng)然也可能相等。兩種方式：1. 多增加一個標(biāo)志位參數(shù)2. 少用一個元素【通常使用第二種元素】隊(duì)列中有n個元素，只要放到n-1個元素，即認(rèn)為隊(duì)列已滿/2018/5/21專題：遞歸定義：一個函數(shù)自己直接或間接調(diào)用自己函

15、數(shù)的調(diào)用當(dāng)在一個函數(shù)的運(yùn)行期間調(diào)用另一個函數(shù)時，在運(yùn)行被調(diào)函數(shù)之前，系 統(tǒng)需要完成二件事：1. 將所有的窩際塞數(shù).亟冋地址譽(yù)信息傳遞辭被調(diào)嘲數(shù)保存2. 為被調(diào)函數(shù)的局郡變輦(也包括形參)分配存儲空間3”將控制轉(zhuǎn)移到艘調(diào)函數(shù)的入口從被調(diào)函數(shù)返冋主調(diào)函數(shù)之前，系統(tǒng)也要完成三件事;1”保存被調(diào)函數(shù)的理回結(jié)果監(jiān)釋放被調(diào)胞數(shù)所占的存皤空同3依照被調(diào)函數(shù)保存的返回地址將控制轉(zhuǎn)林劍調(diào)用函數(shù)當(dāng)有多個函數(shù)相互調(diào)用時，按照農(nóng)后調(diào)用先返回粹的原則，上述函數(shù)Z間信息傳遞和輕制轉(zhuǎn)移仍須借助想棧”來實(shí)見 即系統(tǒng)將整個程序運(yùn)行 時所需的數(shù)據(jù)空問安拝在一個棧巾，每當(dāng)調(diào)用一個函數(shù)時，就在棧頂分配一個存鑄區(qū)，進(jìn)行壓棧操作，毎當(dāng)一

16、個函數(shù)退出時F就釋放它的存儲區(qū)，就行出棧操作，當(dāng)前運(yùn)If的函數(shù)永遠(yuǎn)稱在棧頂位置遞歸滿足的三個條件:1. 遞歸必須得有一個明確的終止條件2. 遞歸的值可以是遞增的，但所處理的數(shù)據(jù)規(guī)模必須在遞減(n->n-1->n-2 )3. 這個轉(zhuǎn)化必須是可解的循環(huán)和遞歸所有的循環(huán)都可以用遞歸實(shí)現(xiàn)，但所有的遞歸不一定都可以用循環(huán)實(shí)現(xiàn)遞歸：循環(huán)：易于理解不易理解速度慢速度快存儲空間大（步驟麻煩）存儲空間小漢諾塔的由來漢諾塔是源自卬度神姑里的玩具“上帝倉丿造世界的時候做了三根金剛石柱子，在-根柱f卜.從 下往上安大小順序援著64片黃金圓盤。上帯命令婆羅門把圜盤從下面開始按人小順呼重新擺放在另 一根柱子匕

17、。并H規(guī)定.在小鬪盤的上面?zhèn)€能族大鬪盤.在 三根柱子之間一次只能移動一個圓盤._有預(yù)言說，這件事完成時字宙會在一瞬刨閃電式毀火也有 人相倍婆羅門至今還在一刻不停地搬動著刪盤。如何杞At而吋“個岳子僧助曲動刖C上燙職1 一朋只能務(wù)動一個掘子£移動比1程當(dāng)中大盤子水遠(yuǎn)不能觸在小盤子F面5偽韓法while (n > 1)先把A柱子上茁的n”4個監(jiān)護(hù)從A借助日移到C 將A柱子上的第n亍盤子芳接移到C 再將日柱子上的nJ個& 了悟助A移到Cn -> n-1 -> n-2 ->-> 1舉例：1. 求階乘2. 1+2+100的和3. 漢諾塔4. 走迷宮遞歸的應(yīng)

18、用：樹和森林就是以遞歸的方式定義的樹和圖的很多算法就是以遞歸來實(shí)現(xiàn)的很多數(shù)學(xué)公式就是以遞歸的方式定義的(例如：斐波拉切數(shù)列)線性結(jié)構(gòu)總復(fù)習(xí):邏輯結(jié)構(gòu)線性 數(shù)組 鏈表?xiàng)：完?duì)列是一種特殊的線性結(jié)構(gòu)，算線性結(jié)構(gòu)的應(yīng)用非線性 樹物理結(jié)構(gòu)/2018/5/22模塊二：非線性結(jié)構(gòu)樹定義：專業(yè)定義：1. 有且只有一個稱為 根 的節(jié)點(diǎn)2. 有若干個互補(bǔ)相交的子樹，這些子樹本身也是一棵樹 通俗定義：1. 樹是由 節(jié)點(diǎn)和邊組成2. 每個節(jié)點(diǎn)只有一個父節(jié)點(diǎn)但可以有多個子節(jié)點(diǎn)3. 但有一個節(jié)點(diǎn)例外，該節(jié)點(diǎn)沒有父節(jié)點(diǎn)，此節(jié)點(diǎn)成為 根節(jié)點(diǎn)專業(yè)術(shù)語節(jié)點(diǎn) 父節(jié)點(diǎn) 子節(jié)點(diǎn) 子孫 堂兄弟深度 ：從根節(jié)點(diǎn)到最底層節(jié)點(diǎn)的層數(shù)稱之為深度

19、（根節(jié)點(diǎn)是第一層） 葉子節(jié)點(diǎn) ：沒有子節(jié)點(diǎn)的節(jié)點(diǎn)。非終端節(jié)點(diǎn) ：實(shí)際就是非葉子節(jié)點(diǎn)。度：子節(jié)點(diǎn)的個數(shù)成為度。分類：一般樹 ：任意一個節(jié)點(diǎn)的子節(jié)點(diǎn)的個數(shù)都不受限制二叉樹 ：任意一個節(jié)點(diǎn)的子節(jié)點(diǎn)的個數(shù)最多兩個，且子節(jié)點(diǎn)的位置不可更改分類：一般二叉樹滿二叉樹 （完全二叉樹的特例）在不增加樹的層數(shù)的前提下，無法再多添加 一個節(jié)點(diǎn)的二叉樹就是滿二叉樹完全二叉樹 （用數(shù)組存儲樹時，必須是完全二叉樹）如果只是刪除了滿二叉樹最底層最后邊的連續(xù) 若干個節(jié)點(diǎn)，這樣形成的二叉樹就是完全二叉 樹。優(yōu)點(diǎn)：1. 根據(jù)節(jié)點(diǎn)編號可以知道在第幾層2. 可以知道父節(jié)點(diǎn)和子節(jié)點(diǎn)森林：n個互不相交的樹的集合樹的存儲：二叉樹的存儲連續(xù)

20、存儲 將二叉樹補(bǔ)充為完全二叉樹 以數(shù)組的形式存儲時，如果根據(jù)只保存有效節(jié)點(diǎn)的形式，無 法推出全樹的樣子。優(yōu)點(diǎn)：查找某個節(jié)點(diǎn)的父節(jié)點(diǎn)和子節(jié)點(diǎn)（也包括判斷有沒有父節(jié)點(diǎn)和子 節(jié)點(diǎn)）速度很快。缺點(diǎn)：耗用空間內(nèi)存過大鏈?zhǔn)酱鎯σ话銟涞拇鎯﹄p親表示法（求父節(jié)點(diǎn)方便）把每一個節(jié)點(diǎn)編號，然后在每一個節(jié)點(diǎn)后標(biāo)記出其父節(jié)點(diǎn)的編號孩子表示法（求子節(jié)點(diǎn)方便）把每一個子節(jié)點(diǎn)都寫在每一個節(jié)點(diǎn)之后。雙親孩子表示法（求父節(jié)點(diǎn)和子節(jié)點(diǎn)都方便）把每一個節(jié)點(diǎn)編號，然后在每一個節(jié)點(diǎn)后標(biāo)記出其父節(jié)點(diǎn)的編號， 再把每一個子節(jié)點(diǎn)寫在之后。二叉樹表示法把一個普通樹轉(zhuǎn)化為二叉樹來存儲。具體轉(zhuǎn)換方法：設(shè)法保證任意一個節(jié)點(diǎn)的左指針域指向它的第一個孩

21、子右指針域指向它下一個兄弟只要滿足此條件，就可以把一個普通樹轉(zhuǎn)化為二叉樹一個普通樹轉(zhuǎn)化成的二叉樹一定沒有右子樹二叉樹裘示進(jìn)=把一個普通樹轉(zhuǎn)化為二叉楙來存儲森林的存儲先把森林轉(zhuǎn)化為二叉樹，再將二叉樹存儲具體轉(zhuǎn)換方法：1. 設(shè)法保證其他樹的根節(jié)點(diǎn)當(dāng)成第一顆樹根節(jié)點(diǎn)的兄弟2. 設(shè)法保證其他任意一個節(jié)點(diǎn)的左指針域指向它的第一個孩子右指針域指向它下一個兄弟只要滿足此條件，就可以把一片森林轉(zhuǎn)化為二叉樹將森林轉(zhuǎn)化為二又樹來存儲賣配劇畀科優(yōu)只ir sfdnnrmg 第下一十 je用尺旻憑足k豪As就即sue片普押芳/I 7證JHi«ar2 n、Tl匚用3n» *I>J厭攜站抽丸.F蘭

22、J 4MA操作：遍歷先序遍歷先訪問根節(jié)點(diǎn)中左右先訪問根節(jié)點(diǎn)再先序訪問左子樹再先序訪問右子樹a：|- ®*it«vmslrlii. «珂“I劃s第“型*rei-0； 73 iv ig< rr ttt-stut*作此講兩FTTQ北JT呻耳左于算 鼻右序呻自土 f H中序耳陽h弗為已知兩沖*內(nèi)序網(wǎng)£Eift二工肓叩J主丁 沖3"1 代“恃II和常陣r«nj# |iQit«>dKix. 4jf!ftaa,. |曽憲中冑廊聲鼻豳:加£31a 4fi*ik0lrS.iC1 F】Uff*任三- 叫:fl . :I CJ . 團(tuán)章植繪構(gòu)玄-._jF自已-I弓先甲暑時-I中序遍歷中間訪問根節(jié)點(diǎn)左中右中序遍歷左子樹再訪問根節(jié)點(diǎn)再中序遍歷右子樹后序遍歷最后訪問根節(jié)點(diǎn)左右中先后序遍歷左子樹 再后序遍歷右子樹再訪問根節(jié)點(diǎn)只知道一顆二叉樹的一種遍歷方式是無法還原二叉樹的原貌的。已知兩種遍歷序列求原始二叉樹先中（可以）中后（可以）先后（不可以）必須有一個中序已知先序和中序求后序例1:先序：ABCDEFGH中序：BDCEAFHG求后序講解：先序中第一個出現(xiàn)的一定是根節(jié)點(diǎn)，即 A;所以中序中根節(jié)點(diǎn)A左邊的 BDCE1左子樹，右邊的FHG是右子樹；然后在先序序列中看左子樹 BDC沖哪 個