《數(shù)據(jù)結(jié)構(gòu)與算法》課件

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