數(shù)據(jù)結(jié)構(gòu)和算法總結(jié)

數(shù)據(jù)+數(shù)據(jù)元之間的關(guān)系+數(shù)據(jù)上的操作（增刪改查排）

線性表

按照存儲方式分類

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

2.鏈?zhǔn)酱鎯Γ烘湵怼ｋS機(jī)訪問效率低，隨機(jī)插入效率高。（只需要定位+修改指針）

按照訪問方式分類

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

2.受限訪問：受限線性表。棧、隊(duì)列

各結(jié)構(gòu)細(xì)節(jié)

1.鏈表

數(shù)據(jù)結(jié)構(gòu)里面的入門結(jié)構(gòu)，是樹和圖的基礎(chǔ)，還可以實(shí)現(xiàn)棧和隊(duì)列

1.1常用操作：插入（頭插和尾插），刪除節(jié)點(diǎn)，查找，排序，反轉(zhuǎn)

1.2單鏈表中帶頭結(jié)點(diǎn)的好處、循環(huán)鏈表中帶尾節(jié)點(diǎn)的好處

1.3衍生出的復(fù)雜結(jié)構(gòu)：雙向鏈表、循環(huán)鏈表、跳躍鏈表

2.棧

只有一端可以操作的數(shù)據(jù)結(jié)構(gòu)，如棧變量，是最普遍的變量，還有函數(shù)棧，遞歸的時(shí)候肯定是要考慮函數(shù)棧的大小的，可能遇到的棧溢出（stackoverflow）

2.1常用操作：入棧和出棧

2.2衍生結(jié)構(gòu)：順序棧（數(shù)組形成的棧）、鏈棧（用鏈表形成的棧）、共享?xiàng)＃▋蓚€(gè)棧但是公用一個(gè)區(qū)塊內(nèi)存，從兩端取）

2.3棧與遞歸的關(guān)系：用遞歸的函數(shù)其實(shí)就是在調(diào)用函數(shù)棧，在一定程度上遞歸可以理解為就是在使用函數(shù)棧

棧的應(yīng)用（數(shù)值表達(dá)式計(jì)算、前綴、中綴、后綴表達(dá)式，括號匹配）

3.隊(duì)列

兩端分別只能進(jìn)行插入和刪除操作，在操作系統(tǒng)中廣泛使用，如就緒隊(duì)列，阻塞隊(duì)列等進(jìn)程的調(diào)用

3.1常用操作：入隊(duì)和出隊(duì)

3.2判空判滿條件：（針對循環(huán)隊(duì)列）標(biāo)志位法、犧牲元素空間法

3.3衍生結(jié)構(gòu)：循環(huán)隊(duì)列、雙端隊(duì)列、鏈隊(duì)

4.樹-二叉樹為主

基本概念及結(jié)論：

1.深度、高度、層次、最多、最少節(jié)點(diǎn)數(shù)，度（n0=n2+1），（帶權(quán)）路徑長度，滿二叉樹，完全二叉樹

2.存儲方式：順序存儲（數(shù)組，父子結(jié)點(diǎn)下標(biāo)規(guī)律），鏈?zhǔn)酱鎯Γǘ骀湵恚?/p>

遍歷：

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

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

其他知識點(diǎn)：

1.最優(yōu)二叉樹（哈弗曼樹，帶權(quán)路徑長度最短），用于數(shù)據(jù)壓縮和編碼

2.樹和森林的轉(zhuǎn)換

3.變態(tài)二叉樹

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

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

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

3.4堆：區(qū)分開數(shù)據(jù)結(jié)構(gòu)里面的堆和內(nèi)存里面的堆，數(shù)據(jù)結(jié)構(gòu)里面是所有父節(jié)點(diǎn)的值都不大于（小于）子節(jié)點(diǎn)的值的完全二叉樹稱為小（大）頂堆

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

5.圖

分類：有向圖&無向圖，完全圖、（強(qiáng)）連通圖

存儲結(jié)構(gòu)：

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

鄰接表：適合稀疏圖，不唯一表示的，頂點(diǎn)表+鄰接表，是一個(gè)數(shù)組+很多鏈表

遍歷：

深度優(yōu)先遍歷（一直找到他不能去的頂點(diǎn)，然后再回一步繼續(xù)找，借助棧來實(shí)現(xiàn)）

廣度優(yōu)先遍歷（對于一個(gè)頂點(diǎn)全部遍歷完，借助的是隊(duì)列的結(jié)構(gòu)）

和圖相關(guān)的重要算法：

最小生成樹算法：能夠權(quán)值最小的生成樹，PRim算法和kruskal算法

拓?fù)渑判颍涸趺幢ＷC應(yīng)該在前面，是不唯一的，對于有向圖來說是可以有多個(gè)拓?fù)渑判蛐蛄械?/p>

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

關(guān)鍵路徑

算法

1.排序

評判排序好不好的標(biāo)準(zhǔn)：時(shí)間復(fù)雜度、空間復(fù)雜度、穩(wěn)定性（相同鍵值在同一情況下有沒有被改變）

1.1基于關(guān)鍵字比較排序

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

  1.1.2時(shí)間復(fù)雜度為O(nlogn)：

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

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

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

  1.1.3特殊排序

希爾排序：特點(diǎn)-->書上的是步長:每次除以二  當(dāng)是100個(gè)元素的時(shí)候步長為50 25 12 6

時(shí)間復(fù)雜度O(n^(4/3)),當(dāng)你所選擇的步長O（nlogn）-O(N^2),空間是O(1)，不穩(wěn)定

1.2非基于關(guān)鍵字比較的排序

桶排序

計(jì)數(shù)排序

基數(shù)排序

Bitmap排序：時(shí)間復(fù)雜度是O(n)，在一個(gè)很小的內(nèi)存中實(shí)現(xiàn)一個(gè)整個(gè)數(shù)的排序

2.查找

1.順序查找

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

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

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

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

6.串的查找（KMP算法）

3.散列

散列函數(shù)

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

用途：文件校驗(yàn) md5/SHA1值、數(shù)字簽名、數(shù)字加密可以認(rèn)為是不可逆的（一般情況）， 可以加鹽

4.附加

貪心、動歸、分治

java

Collection（List、set）、Map