數據結構和算法總結

數據+數據元之間的關系+數據上的操作（增刪改查排）

線性表

按照存儲方式分類

1.順序存儲：順序表、棧、隊列。隨機訪問效率高，隨機插入效率低。

2.鏈式存儲：鏈表。隨機訪問效率低，隨機插入效率高。（只需要定位+修改指針）

按照訪問方式分類

1.可以隨機訪問：一般的線性表。鏈表、順序表

2.受限訪問：受限線性表。棧、隊列

各結構細節

1.鏈表

數據結構里面的入門結構，是樹和圖的基礎，還可以實現棧和隊列

1.1常用操作：插入（頭插和尾插），刪除節點，查找，排序，反轉

1.2單鏈表中帶頭結點的好處、循環鏈表中帶尾節點的好處

1.3衍生出的復雜結構：雙向鏈表、循環鏈表、跳躍鏈表

2.棧

只有一端可以操作的數據結構，如棧變量，是最普遍的變量，還有函數棧，遞歸的時候肯定是要考慮函數棧的大小的，可能遇到的棧溢出（stackoverflow）

2.1常用操作：入棧和出棧

2.2衍生結構：順序棧（數組形成的棧）、鏈棧（用鏈表形成的棧）、共享棧（兩個棧但是公用一個區塊內存，從兩端取）

2.3棧與遞歸的關系：用遞歸的函數其實就是在調用函數棧，在一定程度上遞歸可以理解為就是在使用函數棧

棧的應用（數值表達式計算、前綴、中綴、后綴表達式，括號匹配）

3.隊列

兩端分別只能進行插入和刪除操作，在操作系統中廣泛使用，如就緒隊列，阻塞隊列等進程的調用

3.1常用操作：入隊和出隊

3.2判空判滿條件：（針對循環隊列）標志位法、犧牲元素空間法

3.3衍生結構：循環隊列、雙端隊列、鏈隊

4.樹-二叉樹為主

基本概念及結論：

1.深度、高度、層次、最多、最少節點數，度（n0=n2+1），（帶權）路徑長度，滿二叉樹，完全二叉樹

2.存儲方式：順序存儲（數組，父子結點下標規律），鏈式存儲（二叉鏈表）

遍歷：

1.按照順序分類：先序、中序、后序遍歷、層次遍歷

2.按照編碼方式分類：遞歸和非遞歸

其他知識點：

1.最優二叉樹（哈弗曼樹，帶權路徑長度最短），用于數據壓縮和編碼

2.樹和森林的轉換

3.變態二叉樹

3.1二叉排序樹（二叉搜索樹）

3.2二叉平衡樹（二叉排序樹的強化版）有平衡性，能夠自平衡，避免二叉排序樹退化成一個鏈表，將查找性能變成O(N)的最壞情況，而不是想要的logn，其插入、查找、刪除的最好最壞時間復雜度都為O(logn)。

3.3紅黑樹、敗者樹、KD樹、線段樹

3.4堆：區分開數據結構里面的堆和內存里面的堆，數據結構里面是所有父節點的值都不大于（小于）子節點的值的完全二叉樹稱為小（大）頂堆

3.5非二叉樹的經典：B樹（B-tree）、B+樹（B+樹所有的值都在葉子層）、B*樹，加了指向兄弟節點的指針，使得索引更快(B-樹就是B樹)，數據庫的索引很多都是依賴于B+樹的，保證了每一個節點上的結點數，保證了層次，還有Trie樹、R樹、M樹

5.圖

分類：有向圖&無向圖，完全圖、（強）連通圖

存儲結構：

鄰接矩陣：n階方陣，適用范圍是稠密圖；對于無向圖是一個對稱矩陣，只用存儲上三角，對于有向圖：行數出度，列是入度

鄰接表：適合稀疏圖，不唯一表示的，頂點表+鄰接表，是一個數組+很多鏈表

遍歷：

深度優先遍歷（一直找到他不能去的頂點，然后再回一步繼續找，借助棧來實現）

廣度優先遍歷（對于一個頂點全部遍歷完，借助的是隊列的結構）

和圖相關的重要算法：

最小生成樹算法：能夠權值最小的生成樹，PRim算法和kruskal算法

拓撲排序：怎么保證應該在前面，是不唯一的，對于有向圖來說是可以有多個拓撲排序序列的

最短路徑:Dijkstra算法、Floyd算法

關鍵路徑

算法

1.排序

評判排序好不好的標準：時間復雜度、空間復雜度、穩定性（相同鍵值在同一情況下有沒有被改變）

1.1基于關鍵字比較排序

  1.1.1時間復雜度為O（n^2）,空間O(1)：插入排序（數據量小并且基本有序，效率較高），冒泡排序（可以優化，最好的情況下能夠到O(n)），選擇排序（不穩定）

  1.1.2時間復雜度為O(nlogn)：

快速排序（不穩定，平均情況下時間復雜度是O(nlogn)，平均空間O（logn），這個時候并不是普通意義上申請的空間，而是在遞歸情況下形成的棧空空間，遞歸深度，最壞情況時間是O（n^2），空間是O(n)，會退化和冒泡差不多，關鍵在于樞紐元素的選取）

歸并排序：穩定，平均和最壞都是時間O(nlogn)，空間O（n），分而治之的思想，一般在平時不選用的原因是空間復雜度永遠都是O(n)

堆排序：最好最壞時間復雜度都是O(nlogn)，空間是O(1)，但是不穩定的排序，topK的問題用堆是最快的-->在大量數據中選出前100使用貪心思想：維護一個你認為最好的100個元素，一直往后遍歷一遍就出來了

  1.1.3特殊排序

希爾排序：特點-->書上的是步長:每次除以二  當是100個元素的時候步長為50 25 12 6

時間復雜度O(n^(4/3)),當你所選擇的步長O（nlogn）-O(N^2),空間是O(1)，不穩定

1.2非基于關鍵字比較的排序

桶排序

計數排序

基數排序

Bitmap排序：時間復雜度是O(n)，在一個很小的內存中實現一個整個數的排序

2.查找

1.順序查找

2.數組中的二分查找：邊界問題等

3.二叉排序樹中的二分查找

4.多路平衡樹中的多路/二分查找：B樹是其中的一種

5.Trie樹的查找（也是多路查找）

6.串的查找（KMP算法）

3.散列

散列函數

沖突處理：如何處理映射到同一地址的   二次映射/拉鏈法/公共池法

用途：文件校驗 md5/SHA1值、數字簽名、數字加密可以認為是不可逆的（一般情況）， 可以加鹽

4.附加

貪心、動歸、分治

java

Collection（List、set）、Map