數(shù)據(jù)結(jié)構(gòu)與算法高效數(shù)據(jù)組織與問(wèn)題求解基礎(chǔ)課程目標(biāo)和學(xué)習(xí)要求掌握基本概念理解數(shù)據(jù)結(jié)構(gòu)和算法核心原理實(shí)現(xiàn)典型算法能獨(dú)立編寫常見(jiàn)數(shù)據(jù)結(jié)構(gòu)操作代碼分析算法效率評(píng)估時(shí)間和空間復(fù)雜度解決實(shí)際問(wèn)題數(shù)據(jù)結(jié)構(gòu)的基本概念數(shù)據(jù)結(jié)構(gòu)定義數(shù)據(jù)元素及其相互關(guān)系的集合邏輯結(jié)構(gòu)描述數(shù)據(jù)元素之間的邏輯關(guān)系物理結(jié)構(gòu)數(shù)據(jù)在計(jì)算機(jī)中的存儲(chǔ)表示抽象數(shù)據(jù)類型算法的定義和特性1定義解決問(wèn)題的明確步驟序列2有窮性算法必須在有限步驟內(nèi)結(jié)束3確定性每步操作清晰無(wú)歧義4可行性算法步驟可執(zhí)行輸入輸出時(shí)間復(fù)雜度和空間復(fù)雜度時(shí)間復(fù)雜度算法執(zhí)行時(shí)間與問(wèn)題規(guī)模關(guān)系常見(jiàn)：O(1)、O(logn)、O(n)、O(nlogn)、O(n2)空間復(fù)雜度算法執(zhí)行所需存儲(chǔ)空間與問(wèn)題規(guī)模關(guān)系輔助空間與輸入規(guī)模的函數(shù)漸進(jìn)符號(hào)和算法效率分析大O符號(hào)算法最壞情況時(shí)間復(fù)雜度上界大Ω符號(hào)算法最好情況時(shí)間復(fù)雜度下界大Θ符號(hào)算法平均情況時(shí)間復(fù)雜度確界線性表的定義和特征1概念有序數(shù)據(jù)元素集合2特點(diǎn)元素線性關(guān)系、前驅(qū)后繼3基本操作初始化、增刪改查4實(shí)現(xiàn)方式順序存儲(chǔ)、鏈?zhǔn)酱鎯?chǔ)順序表的實(shí)現(xiàn)單鏈表的定義和基本操作節(jié)點(diǎn)結(jié)構(gòu)數(shù)據(jù)域+指針域創(chuàng)建空表初始化頭指針為空插入節(jié)點(diǎn)調(diào)整前后節(jié)點(diǎn)指針刪除節(jié)點(diǎn)釋放節(jié)點(diǎn)空間并連接斷點(diǎn)雙向鏈表和循環(huán)鏈表雙向鏈表前驅(qū)指針+數(shù)據(jù)+后繼指針可雙向遍歷循環(huán)鏈表尾節(jié)點(diǎn)指向頭節(jié)點(diǎn)無(wú)需判斷結(jié)束棧的定義和特性定義后進(jìn)先出的線性表基本操作入棧、出棧、獲取棧頂特點(diǎn)只能在一端(棧頂)操作應(yīng)用函數(shù)調(diào)用、表達(dá)式求值、括號(hào)匹配棧的順序存儲(chǔ)實(shí)現(xiàn)存儲(chǔ)結(jié)構(gòu)一維數(shù)組+棧頂指針1入棧操作棧頂指針增加，元素入棧2出棧操作元素出棧，棧頂指針減少3棧空棧滿棧頂指針位置判斷4棧的鏈?zhǔn)酱鎯?chǔ)實(shí)現(xiàn)鏈棧結(jié)構(gòu)單鏈表表示，表頭為棧頂入棧操作頭插法添加新節(jié)點(diǎn)出棧操作移除頭節(jié)點(diǎn)并返回?cái)?shù)據(jù)特點(diǎn)不限制容量，按需分配空間棧的應(yīng)用：表達(dá)式求值中綴轉(zhuǎn)后綴使用棧轉(zhuǎn)換表達(dá)式操作符優(yōu)先級(jí)決定入棧出棧順序括號(hào)處理左括號(hào)入棧，右括號(hào)出棧后綴表達(dá)式求值遇操作數(shù)入棧，遇運(yùn)算符彈棧計(jì)算隊(duì)列的定義和特性定義先進(jìn)先出的線性表基本操作入隊(duì)、出隊(duì)、獲取隊(duì)頭特點(diǎn)一端入隊(duì)，另一端出隊(duì)?wèi)?yīng)用緩沖區(qū)、打印隊(duì)列、消息隊(duì)列隊(duì)列的順序存儲(chǔ)和循環(huán)隊(duì)列1順序隊(duì)列問(wèn)題假溢出現(xiàn)象2循環(huán)隊(duì)列思想首尾相接成環(huán)3狀態(tài)判斷隊(duì)空：front=rear4隊(duì)滿判斷(rear+1)%maxsize=front隊(duì)列的鏈?zhǔn)酱鎯?chǔ)實(shí)現(xiàn)1鏈隊(duì)結(jié)構(gòu)帶頭尾指針的單鏈表2入隊(duì)操作尾指針處添加新節(jié)點(diǎn)3出隊(duì)操作頭指針處移除節(jié)點(diǎn)4特點(diǎn)不限容量，無(wú)需判斷隊(duì)滿優(yōu)先隊(duì)列和堆優(yōu)先隊(duì)列按優(yōu)先級(jí)出隊(duì)不遵循先進(jìn)先出堆實(shí)現(xiàn)通常用二叉堆實(shí)現(xiàn)最大堆：父節(jié)點(diǎn)大于子節(jié)點(diǎn)最小堆：父節(jié)點(diǎn)小于子節(jié)點(diǎn)串的定義和基本操作定義由零個(gè)或多個(gè)字符組成的有限序列基本操作串比較、串連接、求子串模式匹配在主串中查找子串位置KMP算法原理普通匹配問(wèn)題回溯導(dǎo)致重復(fù)比較KMP核心思想利用已知信息避免回溯部分匹配表記錄模式串前綴后綴最長(zhǎng)公共元素長(zhǎng)度失配處理模式串向右移動(dòng)位數(shù)=已匹配字符數(shù)-失配前最長(zhǎng)共同前后綴KMP算法實(shí)現(xiàn)和優(yōu)化next數(shù)組構(gòu)建記錄每個(gè)位置失配時(shí)的回退位置KMP實(shí)現(xiàn)主體匹配過(guò)程無(wú)回溯nextval優(yōu)化處理字符相同的特殊情況樹(shù)的基本概念和術(shù)語(yǔ)1定義n個(gè)節(jié)點(diǎn)的有限集合2術(shù)語(yǔ)根、父節(jié)點(diǎn)、子節(jié)點(diǎn)、兄弟、葉子、層次、深度、高度3特點(diǎn)層次結(jié)構(gòu)、遞歸定義4應(yīng)用文件系統(tǒng)、組織結(jié)構(gòu)、語(yǔ)法樹(shù)二叉樹(shù)的定義和性質(zhì)定義每個(gè)節(jié)點(diǎn)最多有兩個(gè)子樹(shù)性質(zhì)1第i層最多有2^(i-1)個(gè)節(jié)點(diǎn)性質(zhì)2深度為k的二叉樹(shù)最多有2^k-1個(gè)節(jié)點(diǎn)性質(zhì)3葉子節(jié)點(diǎn)數(shù)等于度為2的節(jié)點(diǎn)數(shù)加1二叉樹(shù)的遍歷（先序、中序、后序）先序遍歷根→左→右中序遍歷左→根→右后序遍歷左→右→根遞歸實(shí)現(xiàn)利用棧實(shí)現(xiàn)非遞歸算法二叉樹(shù)的層次遍歷思路從根節(jié)點(diǎn)開(kāi)始逐層訪問(wèn)1算法實(shí)現(xiàn)利用隊(duì)列進(jìn)行寬度優(yōu)先搜索2處理過(guò)程隊(duì)頭出隊(duì)并訪問(wèn)，子節(jié)點(diǎn)入隊(duì)3應(yīng)用獲取層數(shù)、判斷完全二叉樹(shù)4二叉樹(shù)的存儲(chǔ)結(jié)構(gòu)順序存儲(chǔ)一維數(shù)組適合完全二叉樹(shù)隨機(jī)訪問(wèn)效率高鏈?zhǔn)酱鎯?chǔ)二叉鏈表：左右子樹(shù)指針三叉鏈表：增加父節(jié)點(diǎn)指針適用于一般二叉樹(shù)線索二叉樹(shù)1定義利用空指針存放前驅(qū)后繼信息2目的加快節(jié)點(diǎn)間遍歷速度3線索類型前序線索、中序線索、后序線索4標(biāo)記方式ltag和rtag標(biāo)識(shí)指針類型哈夫曼樹(shù)和哈夫曼編碼哈夫曼樹(shù)帶權(quán)路徑長(zhǎng)度最小的二叉樹(shù)構(gòu)建方法權(quán)值小的節(jié)點(diǎn)合并為新節(jié)點(diǎn)哈夫曼編碼變長(zhǎng)編碼，頻率高的用短碼二叉搜索樹(shù)定義左子樹(shù)小于根，右子樹(shù)大于根特點(diǎn)中序遍歷為升序序列查找比較節(jié)點(diǎn)值確定搜索方向插入刪除維持二叉搜索樹(shù)性質(zhì)平衡二叉樹(shù)（AVL樹(shù)）定義任何節(jié)點(diǎn)左右子樹(shù)高度差不超過(guò)1左旋處理右子樹(shù)高于左子樹(shù)右旋處理左子樹(shù)高于右子樹(shù)紅黑樹(shù)概述1定義一種自平衡二叉搜索樹(shù)2五個(gè)特性根黑、葉黑、紅節(jié)點(diǎn)子黑、黑高相同、新節(jié)點(diǎn)紅3操作顏色調(diào)整和旋轉(zhuǎn)維持平衡4應(yīng)用關(guān)聯(lián)數(shù)組、集合結(jié)構(gòu)實(shí)現(xiàn)B樹(shù)和B+樹(shù)B樹(shù)多路平衡查找樹(shù)所有葉子同層適合磁盤存儲(chǔ)B+樹(shù)所有數(shù)據(jù)都在葉子節(jié)點(diǎn)葉子節(jié)點(diǎn)形成鏈表非葉節(jié)點(diǎn)只存索引適合數(shù)據(jù)庫(kù)索引圖的基本概念和術(shù)語(yǔ)頂點(diǎn)和邊構(gòu)成，有向/無(wú)向，帶權(quán)/無(wú)權(quán)度、路徑、連通、環(huán)、樹(shù)等核心概念圖的存儲(chǔ)結(jié)構(gòu)（鄰接矩陣和鄰接表）鄰接矩陣二維數(shù)組表示連接關(guān)系適合稠密圖查詢快，空間占用大鄰接表頂點(diǎn)數(shù)組+邊鏈表適合稀疏圖節(jié)省空間，查詢慢圖的深度優(yōu)先搜索（DFS）思想盡可能深入探索圖的分支1實(shí)現(xiàn)方式遞歸或使用棧2應(yīng)用解迷宮問(wèn)題、拓?fù)渑判?時(shí)間復(fù)雜度O(V+E)鄰接表，O(V2)鄰接矩陣4圖的廣度優(yōu)先搜索（BFS）思想逐層訪問(wèn)節(jié)點(diǎn)實(shí)現(xiàn)方式使用隊(duì)列應(yīng)用最短路徑、網(wǎng)絡(luò)爬蟲時(shí)間復(fù)雜度O(V+E)鄰接表，O(V2)鄰接矩陣最小生成樹(shù)：Prim算法基本思想從單個(gè)頂點(diǎn)開(kāi)始構(gòu)建選擇邊選最小權(quán)值連接外部頂點(diǎn)的邊迭代過(guò)程重復(fù)直至包含所有頂點(diǎn)適用場(chǎng)景稠密圖效率更高最小生成樹(shù)：Kruskal算法1基本思想按權(quán)值升序選擇邊2選擇條件不形成環(huán)路的最小權(quán)值邊3判斷環(huán)路使用并查集檢測(cè)4適用場(chǎng)景稀疏圖效率更高最短路徑：Dijkstra算法解決問(wèn)題單源最短路徑基本思想貪心策略逐步確定最短路徑算法過(guò)程維護(hù)距離數(shù)組，選擇最小值更新限制不適用于負(fù)權(quán)邊最短路徑：Floyd算法解決問(wèn)題多源最短路徑基本思想動(dòng)態(tài)規(guī)劃逐步松弛路徑算法過(guò)程三重循環(huán)考慮中轉(zhuǎn)點(diǎn)時(shí)間復(fù)雜度O(V3)拓?fù)渑判蜻m用圖類型有向無(wú)環(huán)圖(DAG)基本思想按依賴關(guān)系排序頂點(diǎn)算法實(shí)現(xiàn)刪除入度為0頂點(diǎn)及其邊應(yīng)用任務(wù)調(diào)度、編譯依賴關(guān)鍵路徑AOE網(wǎng)絡(luò)中最長(zhǎng)路徑?jīng)Q定工程總時(shí)間的活動(dòng)序列計(jì)算各頂點(diǎn)最早/最晚時(shí)間查找算法概述1靜態(tài)查找表僅查找不修改2動(dòng)態(tài)查找表插入刪除查找3評(píng)價(jià)指標(biāo)查找長(zhǎng)度、平均查找長(zhǎng)度4常見(jiàn)算法順序查找、二分查找、散列查找順序查找和二分查找順序查找從頭到尾逐個(gè)比較適用任何查找表平均查找長(zhǎng)度n/2時(shí)間復(fù)雜度O(n)二分查找折半比較縮小范圍要求有序表平均查找長(zhǎng)度log?n時(shí)間復(fù)雜度O(logn)散列表的基本概念1核心思想直接尋址2散列函數(shù)將關(guān)鍵字映射到地址3沖突處理解決多個(gè)關(guān)鍵字映射到同一地址4性能分析裝填因子與查找性能關(guān)系散列函數(shù)的設(shè)計(jì)除留余數(shù)法h(key)=key%m乘法散列h(key)=?m(A·key-?A·key?)?折疊法將關(guān)鍵字分割后求和散列沖突的處理方法開(kāi)放定址法線性探測(cè)、二次探測(cè)、雙散列鏈地址法同一地址用鏈表存儲(chǔ)再散列法沖突多時(shí)用新散列函數(shù)建立公共溢出區(qū)沖突放入溢出表排序算法概述10+常見(jiàn)排序算法各具特點(diǎn)和適用場(chǎng)景2排序方式內(nèi)部排序與外部排序3評(píng)價(jià)指標(biāo)時(shí)間復(fù)雜度、空間復(fù)雜度、穩(wěn)定性冒泡排序和選擇排序冒泡排序相鄰元素比較交換最大元素逐漸上浮O(n2)，穩(wěn)定排序選擇排序選擇最小元素交換位置每輪確定一個(gè)元素位置O(n2)，不穩(wěn)定排序插入排序和希爾排序插入排序?qū)⒃夭迦胗行蛐蛄蓄愃茡淇伺普鞳(n2)，穩(wěn)定排序小數(shù)據(jù)集效率高希爾排序改進(jìn)的插入排序按間隔分組排序O(n^1.3)，不穩(wěn)定排序快速排序1基本思想分治法，劃分區(qū)間2實(shí)現(xiàn)步驟選基準(zhǔn)、劃分、遞歸排序3性能特點(diǎn)平均O(nlogn)，最壞O(n2)4優(yōu)化方法三數(shù)取中、小區(qū)間改用插入排序歸并排序基本思想分治法，合并有序子序列實(shí)現(xiàn)步驟分割為最小單元、兩兩合并性能特點(diǎn)穩(wěn)定O(nlogn)，空間O(n)適用場(chǎng)景鏈表排序、外部排序、大數(shù)據(jù)量堆排序基本思想利用堆數(shù)據(jù)結(jié)構(gòu)實(shí)現(xiàn)步驟建堆、交換堆頂、調(diào)整堆性能特點(diǎn)不穩(wěn)定O(nlogn)，原地排序適用場(chǎng)景n大時(shí)優(yōu)于快排，求TopK計(jì)數(shù)排序和桶排序計(jì)數(shù)排序計(jì)算元素出現(xiàn)次數(shù)適用范圍小的整數(shù)O(n+k)，穩(wěn)定排序桶排序?qū)⒃胤值接邢迶?shù)量的桶中單獨(dú)排序每個(gè)桶O(n+k)，取決于桶內(nèi)排序基數(shù)排序1234基本思想按位數(shù)分組多次排序?qū)崿F(xiàn)方式LSD從低位開(kāi)始或MSD從高位開(kāi)始性能特點(diǎn)O(d(n+r))，穩(wěn)定排序適用場(chǎng)景長(zhǎng)度相同的數(shù)字、字符串外部排序1適用場(chǎng)景內(nèi)存無(wú)法容納全部數(shù)據(jù)2基本思路分塊排序后歸并3多路歸并減少I/O次數(shù)4敗者樹(shù)優(yōu)化選擇最小元素過(guò)程動(dòng)態(tài)規(guī)劃基礎(chǔ)1基本思想將復(fù)雜問(wèn)題分解為簡(jiǎn)單子問(wèn)題2核心特征最優(yōu)子結(jié)構(gòu)、重疊子問(wèn)題3實(shí)現(xiàn)方式自底向上填表、自頂向下備忘錄4經(jīng)典問(wèn)題背包問(wèn)題、最長(zhǎng)公共子