聲明：本文內(nèi)容純屬博主自己查找和歸納的個人所需的知識點，僅作參考，如有錯誤，博主強烈希望您指出。如果您是某個知識點的原創(chuàng)博主，如有需要，可聯(lián)系本人加上鏈接。本文內(nèi)容會根據(jù)博主所需進行更新，希望大家多多關(guān)照。
你所知道的數(shù)據(jù)結(jié)構(gòu)
線性：數(shù)組 (Array)、棧 (Stack)、隊列 (Queue)、鏈表 (Linked List)
樹： 堆(heap)、（B-樹、B+樹、）二叉查找樹、AVL樹、紅黑樹、二叉樹、哈夫曼樹
圖 (Graph)
散列表 (Hash)
數(shù)組：有序的元素序列，固定大小
棧：是一種運算受限的線性表，先進后出
隊列：一種操作受限制的線性表，先進先出
鏈表：非連續(xù)、非順序的存儲結(jié)構(gòu)，邏輯順序是通過鏈表中的指針實現(xiàn)的
1.頭插法：新插入的數(shù)據(jù)的指針指向最后的數(shù)據(jù)
2.尾插法：最后的數(shù)據(jù)的指針指向新插入的數(shù)據(jù)堆：堆通常是一個可以被看做一棵完全二叉樹的數(shù)組對象
B-樹：B樹，是一種平衡的多路搜索樹（這里的平衡指根節(jié)點到葉子節(jié)點的高度一樣）
B+樹：B+樹是應(yīng)文件系統(tǒng)所需而出的一種B-樹的變型樹
（B-樹和B+樹比較復(fù)雜，暫時不作拓展，多用在文件和數(shù)據(jù)庫種，不說出來應(yīng)該也不會問到）二叉查找樹：每個節(jié)點的左子樹比該節(jié)點小，右子樹比該節(jié)點大，子樹同樣是二叉查找樹
平衡二叉樹：基于二叉查找樹，又叫AVL樹（這里的平衡指左右子樹深度差的絕對值不超過1）
紅黑樹：一種特化的AVL樹
二叉樹：二叉樹是每個結(jié)點最多有兩個子樹的樹結(jié)構(gòu)
1.完全二叉樹：若設(shè)二叉樹的深度為h，除第h層外，其它各層(1～h-1)的結(jié)點數(shù)都達到最大個數(shù)，第h層所有的結(jié)點都連續(xù)集中在最左邊，這就是完全二叉樹。
2.滿二叉樹：除了葉結(jié)點外每一個結(jié)點都有左右子葉且葉子結(jié)點都處在最底層的二叉樹
3.二叉樹遍歷：前序中序后序分別是根左右、左根右、左右根哈夫曼樹：一種帶權(quán)路徑長度最短的二叉樹，也稱為最優(yōu)二叉樹
圖：一些頂點的集合，節(jié)點之間的關(guān)系可以是任意的
散列表：又叫哈希表（Hash Table），是能夠通過給定的關(guān)鍵字的值直接訪問到具體對應(yīng)的值的一個數(shù)據(jù)結(jié)構(gòu)
樹與二叉樹的區(qū)別
二叉樹每個節(jié)點最多有2個子節(jié)點，樹則無限制。
二叉樹中節(jié)點的子樹分為左子樹和右子樹，即使某節(jié)點只有一棵子樹，也要指明該子樹是左子樹還是右子樹，即二叉樹是有序的。
樹決不能為空，它至少有一個節(jié)點，而一棵二叉樹可以是空的。
平衡二叉樹的性質(zhì)
???????平衡二叉樹又叫AVL樹，它的左子樹上的所有節(jié)點的值都比根節(jié)點的值小，而右子樹上的所有節(jié)點的值都比根節(jié)點的值大，且左子樹與右子樹的高度差最大為1
???????至于旋轉(zhuǎn)的方法博主是參考這篇文章學(xué)習(xí)的：今天終于懂了AVL樹怎樣旋轉(zhuǎn)(帶圖理解)，但是具體代碼實現(xiàn)還需要進一步研究
紅黑樹的性質(zhì)
???????紅黑樹基于AVL樹，但沒有追求左子樹與右子樹的高度差最大為1這個性質(zhì)，而追求以下性質(zhì)：
- 每個結(jié)點是紅色或黑色
- 根結(jié)點是黑色
- 每個葉子結(jié)點都是黑色的空結(jié)點
- 每個紅色結(jié)點的兩個子結(jié)點是黑色（從每個葉子到根的所有路徑上不能有兩個連續(xù)的紅色節(jié)點）
- 從任意結(jié)點到其每個葉子結(jié)點的路徑包含相同數(shù)目的黑色結(jié)點
這些性質(zhì)構(gòu)造出紅黑樹的關(guān)鍵性質(zhì)：從根到葉子的最長的可能路徑不多于最短的可能路徑的兩倍長
紅黑樹在任何不平衡的情況只需要最多三次旋轉(zhuǎn)就能達到平衡，插入和刪除的次數(shù)比AVL樹少，查詢效率稍遜于AVL樹
一棵有n個結(jié)點的紅黑樹的高度至多為為2lg(n+1)
STL容器中map、multimap、set、multiset都用到紅黑樹
???????至于變色和旋轉(zhuǎn)的方法博主是參考這篇文章學(xué)習(xí)的：紅黑樹的旋轉(zhuǎn)與變色，但是具體代碼實現(xiàn)還需要進一步研究
哈夫曼樹
- 哈夫曼樹通常用作通信的二進制編碼
-
哈夫曼樹的構(gòu)建：
哈夫曼樹的構(gòu)建
???????其中小于等于和的元素放左邊，大于和的放右邊，例如圖中(d)B和7的和為14，D為13，D就放左邊
-
哈夫曼樹的編碼生成：
哈夫曼樹的編碼生成
???????樹中從根到每個葉子節(jié)點都有一條路徑，對路徑上的各分支約定指向左子樹的分支表示”0”碼，指向右子樹的分支表示“1”碼，取每條路徑上的“0”或“1”的序列作為各個葉子節(jié)點對應(yīng)的字符編碼，即是哈夫曼編碼。
???????就拿上圖例子來說：A，B，C，D對應(yīng)的哈夫曼編碼分別為：111，10，110，0
圖的性質(zhì)
圖通常分為有向圖和無向圖，而其表示基本的表示方式分為鄰接矩陣、鄰接表，還有另外的十字鏈表
鄰接矩陣就是把2個點的關(guān)系用一個二維表表示出來
鄰接表每個節(jié)點存放數(shù)據(jù)、權(quán)重和下一個鄰接點，每個鄰接表都表示出此頂點的所有鄰接點
十字鏈表就是把有向圖的鄰接表和逆鄰接表整合在一起
有向圖分出度和入度，無向圖的度就是鄰邊的數(shù)目
圖的深度和廣度優(yōu)先遍歷
深度優(yōu)先遍歷
???????又稱為深度優(yōu)先搜索，簡稱DFS。其實，就像是一棵樹的前序遍歷。它從圖中某個結(jié)點開始訪問，然后訪問下一個鄰接點，一直訪問到最后沒有未被訪問到的鄰接點，如果圖中還有頂點未被訪問，則回溯此路徑，另選第一個點的未曾被訪問的鄰接點作起始點，重復(fù)上述過程，直至圖中的所有頂點都被訪問到為止。廣度優(yōu)先遍歷
???????又稱為廣度優(yōu)先搜索，簡稱BFS。圖的廣度優(yōu)先遍歷就類似于樹的層序遍歷，頂點為第一層，與頂點連通的為第二層，以此類推逐層訪問兩種遍歷在時間復(fù)雜度上是一樣的，不同之處僅僅在于對頂點的訪問順序不同
常用的哈希函數(shù)
直接尋址法：取關(guān)鍵字或關(guān)鍵字的某個線性函數(shù)值為散列地址。
數(shù)字分析法：通過對數(shù)據(jù)的分析，發(fā)現(xiàn)數(shù)據(jù)中沖突較少的部分，并構(gòu)造散列地址。
平方取中法：當(dāng)無法確定關(guān)鍵字里哪幾位的分布相對比較均勻時，可以先求出關(guān)鍵字的平方值，然后按需要取平方值的中間幾位作為散列地址。這是因為：計算平方之后的中間幾位和關(guān)鍵字中的每一位都相關(guān)，所以不同的關(guān)鍵字會以較高的概率產(chǎn)生不同的散列地址。
取隨機數(shù)法：使用一個隨機函數(shù)，取關(guān)鍵字的隨機值作為散列地址，這種方式通常用于關(guān)鍵字長度不同的場合。
除留取余法：取關(guān)鍵字被某個不大于散列表的表長 n 的數(shù) m 除后所得的余數(shù) p 為散列地址。這種方式也可以在用過其他方法后再使用。該函數(shù)對 m 的選擇很重要，一般取素數(shù)或者直接用 n
解決哈希表沖突的常用方法
開放地址法（也叫開放尋址法）：對計算出來的地址進行一個探測再哈希，比如往后移動一個地址，如果沒人占用，就用這個地址。
再哈希法：在產(chǎn)生沖突之后，使用關(guān)鍵字的其他部分繼續(xù)計算地址，如果還有沖突，則繼續(xù)使用其他部分再計算地址。這種方式的缺點是時間增加了。
鏈地址法：鏈地址法其實就是對Key通過哈希之后落在同一個地址上的值，做一個鏈表。其實在很多高級語言的實現(xiàn)當(dāng)中，也使用這種方式處理沖突。
建立一個公共溢出區(qū)：這種方式是建立一個公共溢出區(qū)，當(dāng)?shù)刂反嬖跊_突時，把新的地址放在公共溢出區(qū)里。
九種排序
直接插入排序：從第二個數(shù)開始，前面相鄰的數(shù)進行比較，把大的數(shù)換到后面，如此循環(huán)
折半插入排序：在前面的有序區(qū)內(nèi)不斷使用二分法，即比本身小則low=mid+1，比本身大則high=mid-1，當(dāng)low<=high時表示找到第一個比本身大的數(shù)，然后交換
希爾排序：實質(zhì)為分組插入法，不斷縮小步長進行插入排序
直接選擇排序：從后面的數(shù)找出最小的數(shù)與本身交換
堆排序：選擇排序的一種，近似完全二叉樹，下標(biāo)為n/2-1的元素才有子樹，構(gòu)造大頂堆，即結(jié)點都比子樹大，最后根節(jié)點就為最大的數(shù)，將最大的數(shù)和最后的數(shù)互換，繼續(xù)將剩下的數(shù)構(gòu)造大頂堆，如此循環(huán)
冒泡排序：交換排序的一種，每次都從第一個數(shù)開始，相鄰的數(shù)進行比較，將最大的數(shù)后移，不斷縮小比較次數(shù)
快速排序：交換排序的一種，先拿第一個數(shù)作為分界點，把數(shù)組排列成前半部分的數(shù)都比分界點小，后半部分的數(shù)都比分界點大，然后這2半部分繼續(xù)同樣的操作，遞歸完成
歸并排序：分組歸并，分組從最小的組開始進行過比較和交換，比如10個數(shù)，比較的區(qū)間為[0,1] [0,2] [3,4] [0,4] [5,6] [5,7] [8,9] [5,9] [0,9]
桶排序：將元素按大小分到固定長度的區(qū)間也就是桶中排序，再拿出來放回數(shù)組
???????九種排序的具體實現(xiàn)代碼請看：九種排序具體實現(xiàn)代碼
???????穩(wěn)定的排序算法有冒泡排序、插入排序和歸并排序，而選擇排序、希爾排序、快速排序和堆排序都是不穩(wěn)定的。
???????各種排序的時間復(fù)雜度和空間復(fù)雜度為下圖所示：
???????注：Ο(1)＜Ο(logn)＜Ο(n)＜Ο(nlogn)＜Ο(n2)＜Ο(n3)＜…＜Ο(2^n)和Ο(n!)
常用算法
- 基礎(chǔ)：枚舉，遞歸，分治，模擬，貪心，動態(tài)規(guī)劃，剪枝，回溯
- 排序：冒泡、快速、直接選擇和堆、直接插入和希爾排序、歸并排序
- 查找：順序查找、二分查找、索引查找、二叉排序樹、哈希查找
- 圖算法：深度優(yōu)先遍歷與廣度優(yōu)先遍歷， 最短路徑，最小生成樹，拓?fù)渑判?/li>
???????博主掌握的數(shù)據(jù)結(jié)構(gòu)與算法在上面已歸納完畢，這里列出的常用算法還有些博主沒怎么研究，還有哪些在服務(wù)端開發(fā)中常用和重要的算法希望有熱心網(wǎng)友提醒！
