[轉]算法與數據結構——入門總結與自學資料推薦

本文轉自（http://www.cnblogs.com/jiahuix/p/4868881.html）

一、大綱

博客：董西城、Vamei

思維導圖下載地址：http://pan.baidu.com/s/1gdCqW8r

二、數據結構資料推薦

數組：查找快O(1)，插入刪除慢O(n)

鏈表：查找慢O(n)，插入刪除快O(1)

塊狀鏈表：查找插入刪除O(sqrt(n))；數組+鏈表；

隊列：先進先出

堆棧：先進后出

雙端隊列：隊列與堆棧結合，有head與tail的數組，隊首隊尾都可以增刪。

哈希表：

• 集合A到集合B的映射；
• 哈希函數：MD5, SHA；
• 應用：文件對比，密碼存儲；
• 碰撞解決：open hashing -> 鏈表；closed hashing -> 數組下標移動到空位（rehashing移動到更大的新數組） hash table

Bit-Map：一個bit代表一個數字，比如10bit可以代表1~10 bitmap

二叉堆/堆：高度為(lg^2)n，數組 資料2

最小堆：每個父節點均比子節點小

字典樹（前綴樹）：適合用于字符串檢索、字符串最長公共前綴、按字典排序 資料

插入、查找O(N):N為字符串長度，空間O(26^n)

后綴樹：適合復雜的字符串操作

后綴樹組：適合復雜的字符串操作

二叉查找樹：增刪查的復雜度等于深度，深度最多為n，最少為log(n)

數列有序，將會退化成為線性表，即獨苗的時候。

刪除操作時如果刪除節點同時有左右節點，使用刪除節點的左子樹的最大值或右子樹的最小值替換。

B樹：性能總等于二分法，沒有平衡問題。

B+樹：適合文件索引系統，只在葉子結點命中

B*樹：在B+樹基礎上增加兄弟節點指針，增加空間利用率

AVL：平衡二叉樹、深度為O(lgn)、子樹深度相差不超過1、單旋轉與雙旋轉 資料

最小深度Math.ceil( log(2)(N+1) )

Treap：堆樹、性能位于普通二叉樹與AVL之間

紅黑樹：統計性能比AVL好 資料

splay樹：伸展樹，每次搜索都會進行一次旋轉操作，搜索頻率大的結點會旋轉至根節點。m次搜索復雜度O(mlgn)

線段樹：高效地詢問和修改一個數列中某個區間的信息

樹狀數組：樹狀數組通過將線性結構轉換成偽樹狀結構（線性結構只能逐個掃描元素，而樹狀結構可以實現跳躍式掃描），使得修改和求和復雜度均為O(lgn)

圖：圖的表示：二維數組、鄰接表

并查集：并查集常作為另一種復雜的數據結構或者算法的存儲結構。常見的應用有：求無向圖的連通分量個數，最近公共祖先（LCA），帶限制的作業排序，實現Kruskar算法求最小生成樹等。

三、算法資料推薦

基本思想：動態規劃、剪枝、回溯法

排序：快速排序、歸并排序、堆排序、桶排序、七大排序對比

字符串：KMP、KMP、KMP

數論：排列組合

樹：

遍歷：每個節點都檢查

先序遍歷：上、左、右

中序遍歷：左、上、右

后序遍歷：左、右、上

深度優先搜索DFS通過棧來實現

廣度優先搜索BFS通過隊列來實現

*圖片來源于網絡~>_<~