【大总结1】数据结构与传统算法总结
由于時間和水平有限，肯定有錯誤或者寫得不好的地方
歡迎在文章下評論指出。
?
涉及語言：
py3：注重算法本身的知識
c/c++：實現基礎數據結構和算法
java：實現較復雜數據結構
?
?
一、概述
? ? ? ? ? ? ? ? ? ? ? ???c語言知識體系
? ? ? ? ? ? ? ? ? ? ? ??算法體系參考
? ? ? ? ? ? ? ? ? ? ? ??課上筆記1（復習c、課程概述）
? ? ? ? ? ? ? ? ? ? ? ??課上筆記2（基本概念、時空復雜度）
? ? ? ? ? ? ? ? ? ? ? ??時空復雜度
? ? ? ? ? ? ? ? ? ? ? ??淺析P/NP/NPC
? ? ? ? ? ? ? ? ? ? ? ??引入：算法優化
提高篇
? ? ? ? ? ? ? ? ? ? ? ??基礎動態規劃
? ? ? ? ? ? ? ? ? ? ? ??摔手機：借一道水題打開思路
二、線性表
? ? ? ? 筆記：
? ? ? ? ? ? ? ? ? ? ? ??課上筆記3（線性表及順序表示）
? ? ? ? ? ? ? ? ? ? ? ??課上筆記5（鏈表概述）
? ? ? ? ? ? ? ? ? ? ? ??課上筆記6（鏈表選講、靜態鏈表）
? ? ? ? ? ? ? ? ? ? ? ??作業1講解（最大子數組二維多維）
? ? ? ? 基礎代碼實現：
? ? ? ? ? ? ? ? ? ? ? ??順序存儲實現（靜/動）
? ? ? ? ? ? ? ? ? ? ? ??單鏈表不帶頭（標準實現）
? ? ? ? ? ? ? ? ? ? ? ??單鏈表不帶頭（壓縮代碼）
? ? ? ? ? ? ? ? ? ? ? ??雙鏈表帶頭
? ? ? ? 應用：
? ? ? ? ? ? ? ? ? ? ? ??約瑟夫環（順序、鏈式、數學）
? ? ? ? ? ? ? ? ? ? ? ??線性表表示集合
? ? ? ? ? ? ? ? ? ? ? ??線性表表示一元多項式
? ? ? ? ? ? ? ? ? ? ? ??鏈表環相關問題
? ? ? ? ? ? ? ? ? ? ? ??鏈表coding能力練習：歸并排序
? ? ? ? ? ? ? ? ? ? ? ??LRU介紹和實現
?提高篇
? ? ? ? ? ? ? ? ? ? ??鏈表coding能力練習：相交問題
三、棧和隊列
? ? ? ? 筆記：
? ? ? ? ? ? ? ? ? ? ? ??課上筆記7（棧、隊列基礎）
? ? ? ? 基礎代碼實現：
? ? ? ? ? ? ? ? ? ? ? ??數組實現棧
? ? ? ? ? ? ? ? ? ? ? ??鏈表實現棧
? ? ? ? ? ? ? ? ? ? ? ??數組實現隊列（易懂實現循環）
? ? ? ? ? ? ? ? ? ? ? ??鏈表實現隊列
? ? ? ? ? ? ? ? ? ? ? ??雙棧
? ? ? ? ? ? ? ? ? ? ? ??棧和隊列的互相模擬
? ? ? ? 應用：
? ? ? ? ? ? ? ? ? ? ? ??棧排序
? ? ? ? ? ? ? ? ? ? ? ??括號匹配
? ? ? ? ? ? ? ? ? ? ? ??表達式求值
? ? ? ? ? ? ? ? ? ? ? ??簡單迷宮問題
? ? ? ? ? ? ? ? ? ? ? ??借漢諾塔理解棧與遞歸
? ? ? ? ? ? ? ? ? ? ? ??手動維護棧實現二叉樹三種遍歷
? ? ? ? ? ? ? ? ? ? ? ???深搜、廣搜與棧、隊列
? ? ? ? 相關算法：
? ? ? ? ? ? ? ? ? ? ? ??單調棧
? ? ? ? ? ? ? ? ? ? ? ??單調雙端隊列
提高篇
? ? ? ? ? ? ? ? ? ? ? ??雙端隊列優化的背包問題
四、串
? ? ? ? 筆記：
? ? ? ? ? ? ? ? ? ? ? ??課上筆記8（串基礎）
? ? ? ? 基礎代碼實現：
? ? ? ? ? ? ? ? ? ? ? ??串的定長表示
? ? ? ? ? ? ? ? ? ? ? ??串的堆分配
? ? ? ? ? ? ? ? ? ? ? ??為何py整數不會溢出
? ? ? ? ? ? ? ? ? ? ? ??c語言文件操作
? ? ? ? 相關算法：
? ? ? ? ? ? ? ? ? ? ? ??一文讀懂KMP
? ? ? ? ? ? ? ? ? ? ? ??一文讀懂Manacher
? ? ? ? ? ? ? ? ? ? ? ??KMP題集1
? ? ? ? ? ? ? ? ? ? ? ??KMP題集2
? ? ? ? ? ? ? ? ? ? ? ??KMP+DP入門
? ? ? ? ? ? ? ? ? ? ? ??字符串上的動態規劃
? ? ? ? ? ? ? ? ? ? ? ??前綴樹
? ? ? ? ? ? ? ? ? ? ? ??后綴樹/后綴數組概述
? ? ? ? ? ? ? ? ? ? ? ??AC自動機
五、數組和廣義表
注：題目慢慢添加
? ? ? ? 筆記：
? ? ? ? ? ? ? ? ? ? ? ??課上筆記9（數組、廣義表）
? ? ? ? 部分題目實現：
? ? ? ? ? ? ? ? ? ? ? ??二維數組基操四連
? ? ? ? ? ? ? ? ? ? ? ??數組基本操作三連（1）
? ? ? ? ? ? ? ? ? ? ? ??數組基本操作三連（2）
? ? ? ? ? ? ? ? ? ? ? ??數組基本操作三連（3）
? ? ? ? ? ? ? ? ? ? ? ??數組基本操作三連（4）
? ? ? ? ? ? ? ? ? ? ? ??數組精選操作（5）
? ? ? ? ? ? ? ? ? ? ? ??數組精選操作（6）
? ? ? ? 應用：
? ? ? ? ? ? ? ? ? ? ? ??2048小游戲實現
? ? ? ? ? ? ? ? ? ? ? ??吃豆人
? ? ? ? ? ? ? ? ? ? ? ??貪吃蛇
六、樹
? ? ? ? 筆記：
? ? ? ? ? ? ? ? ? ? ? ??課上筆記10（樹和二叉樹概述）
? ? ? ? ? ? ? ? ? ? ? ??二叉樹概述
? ? ? ? ? ? ? ? ? ? ? ??課上筆記11（滿二叉樹、完全二叉樹）
? ? ? ? ? ? ? ? ? ? ? ??課上筆記12（二叉樹存儲與遍歷）
? ? ? ? ? ? ? ? ? ? ? ??課上筆記13（樹的存儲）
? ? ? ? 基礎代碼實現：
? ? ? ? ? ? ? ? ? ? ? ??理解二叉樹遍歷
? ? ? ? ? ? ? ? ? ? ? ??二叉樹序列化/反序列化
? ? ? ? ? ? ? ? ? ? ? ??先序中序后序兩兩結合重建二叉樹
? ? ? ? ? ? ? ? ? ? ? ??先序中序數組推后序數組
? ? ? ? ? ? ? ? ? ? ? ??直觀打印二叉樹
? ? ? ? ? ? ? ? ? ? ? ??根據數組建立平衡二叉搜索樹
? ? ? ? ? ? ? ? ? ? ? ??平衡二叉樹的判斷
? ? ? ? ? ? ? ? ? ? ? ??完全二叉樹的判斷
? ? ? ? ? ? ? ? ? ? ? ??搜索二叉樹的判斷
? ? ? ? ? ? ? ? ? ? ? ??二叉樹最長路徑
? ? ? ? ? ? ? ? ? ? ? ??時間低于O(N)求完全二叉樹結點個數
? ? ? ? 應用：
? ? ? ? ? ? ? ? ? ? ? ??二叉搜索樹
? ? ? ? ? ? ? ? ? ? ? ??堆
? ? ? ? ? ? ? ? ? ? ? ??堆應用例題三連
? ? ? ? ? ? ? ? ? ? ? ??并查集
? ? ? ? ? ? ? ? ? ? ? ??并查集入門題集
? ? ? ? ? ? ? ? ? ? ? ??線段樹
? ? ? ? ? ? ? ? ? ? ? ??樹狀數組
? ? ? ? 相關算法：
? ? ? ? ? ? ? ? ? ? ? ??最大搜索子樹
? ? ? ? ? ? ? ? ? ? ? ??morris遍歷 空間O(1)
七、圖
? ? ? ? 筆記：
? ? ? ? ? ? ? ? ? ? ? ??課上筆記14（圖基礎）
? ? ? ? ? ? ? ? ? ? ? ??課上筆記15（存儲、遍歷）
? ? ? ? 基礎：
? ? ? ? ? ? ? ? ? ? ? ??最小生成樹
? ? ? ? ? ? ? ? ? ? ? ??拓撲排序
? ? ? ? ? ? ? ? ? ? ? ??最短路
? ? ? ? 相關算法：
? ? ? ? ? ? ? ? ? ? ? ??迷宮
? ? ? ? ? ? ? ? ? ? ? ??棋盤簡單深搜廣搜
? ? ? ? ? ? ? ? ? ? ? ??皇后問題（位運算）
? ? ? ? ? ? ? ? ? ? ? ??旅行商問題（認識狀態壓縮）
八、動態存儲
九、查找
? ? ? ? 基礎代碼實現：
? ? ? ? ? ? ? ? ? ? ? ??二分及拓展
? ? ? ? ? ? ? ? ? ? ? ??二叉搜索樹實現
? ? ? ? ? ? ? ? ? ? ? ??數組建立二叉搜索樹
? ? ? ? ? ? ? ? ? ? ? ??自平衡二叉搜索樹
? ? ? ? ? ? ? ? ? ? ? ??AVL Tree
? ? ? ? 相關算法：
? ? ? ? ? ? ? ? ? ? ? ??HashMap記錄的動態規劃
? ? ? ? ? ? ? ? ? ? ? ??跳表介紹和實現
十、排序
? ? ? ? 基礎代碼實現：
? ? ? ? ? ? ? ? ? ? ? ??八種排序
? ? ? ? 相關算法：
? ? ? ? ? ? ? ? ? ? ? ??快排-荷蘭國旗
? ? ? ? ? ? ? ? ? ? ? ??快排-前m大元素
? ? ? ? ? ? ? ? ? ? ? ??歸并-求逆序數
? ? ? ? ? ? ? ? ? ? ? ??桶思想-相鄰數最大差值
? ? ? ? ? ? ? ? ? ? ? ??堆
? ? ? ? ? ? ? ? ? ? ? ??堆應用例題三連
? ? ? ? ? ? ? ? ? ? ? ??BFPRT
?
總結
以上是生活随笔為你收集整理的【大总结1】数据结构与传统算法总结的全部內容，希望文章能夠幫你解決所遇到的問題。
- 上一篇： leetcode283. 移动零 比官方
- 下一篇： 多进程与多线程通信同步机制