《數據結構與算法》課件

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