數(shù)據(jù)結構：數(shù)據(jù)之間相互存在的一種或多種特定關系的元素的集合惯吕。

邏輯結構分類：集合結構细诸，線性結構沛贪，樹形結構，圖形結構震贵。

物理結構分類：順序存儲利赋，鏈式存儲 。

1.二叉樹

先來看看什么是樹屏歹。樹中基本單位是結點隐砸，結點之間的鏈接，稱為分支蝙眶。一棵樹最上面的結點稱之為根節(jié)點，而下面的結點為子結點褪那。一個結點可以有0個或多個子結點幽纷，沒有子結點的結點我們稱之為葉結點。

二叉樹是指子結點數(shù)目不超過2個的樹博敬，它是一種很經(jīng)典的數(shù)據(jù)結構友浸。而二叉搜索樹(BST)是有序的二叉樹，BST需要滿足如下條件：

若任意結點的左子樹不空偏窝，則左子樹上所有節(jié)點的值均小于它的根節(jié)點的值收恢；

若任意結點的右子樹不空，則右子樹上所有節(jié)點的值均大于或等于它的根節(jié)點的值祭往；(有些書里面定義為BST不能有相同值結點伦意，本文將相同值結點插入到右子樹)

任意結點的左、右子樹也分別為二叉查找樹

typedef struct BTNode {

? ? int value;

? ? struct BTNode *left;

? ? struct BTNode *right;

} BTNode;

* 每個節(jié)點最多只有一個父節(jié)點硼补。

* 節(jié)點擁有子樹數(shù)稱為節(jié)點的度驮肉。

* 度為0的節(jié)點稱為葉子節(jié)點。

* 樹的度是樹內部個節(jié)點度的最大值已骇。

* 節(jié)點的層次從根開始定義离钝，根為第一層票编。總層數(shù)即為樹的深度 。

* 森林是不相交的樹的集合

* **滿二叉樹**：每個節(jié)點都有個子節(jié)點卵渴，所有葉子都在同一層上

* **完全二叉樹**： 完全二叉樹是由滿二叉樹而引出來的慧域。對于深度為K的，有n個結點的二叉樹浪读，當且僅當其每一個結點都與深度為K的滿二叉樹中編號從1至n的結點一一對應時稱之為完全二叉樹昔榴。

* 前序遍歷（根節(jié)點-左節(jié)點-右節(jié)點） ，中序遍歷（左節(jié)點-根節(jié)點-右節(jié)點）瑟啃，后序遍歷（左節(jié)點-右節(jié)點-根節(jié)點）论泛。

* 除了迭代，棧也可以實現(xiàn)二叉樹的遍歷

* **搜索（查找）二叉樹**：任何一個結點蛹屿，它的左子樹的所有結點都比這個根結點要小屁奏，它的右子樹的所有結點都比這個根結點要大。

* 如果一棵二叉樹按照中序遍歷得到的序列時有序的错负，那么這棵二叉樹一定是搜索二叉樹坟瓢。

*

* TreeSet:

* 內部填裝數(shù)據(jù)需要繼承Comparable<>方法，并實現(xiàn)compareto方法犹撒。

* compareto方法返回1折联，表示新插入的元素比被比較元素大，會插在樹的右側;如果為0表示相同识颊，會舍棄該值诚镰。

* TreeMap:

* 本質為紅黑樹

2.棧

* 后進先出

* 棧的經(jīng)典應用：

* 波蘭表達式 : 中綴表達式轉后綴表達式（數(shù)字輸出，運算符進展祥款，括號匹配出戰(zhàn)清笨，棧頂優(yōu)先級低出棧）。

* 后綴表達式的計算刃跛。

*

* 通過維護 Node 連接來實現(xiàn)

3.隊列

* LinkedList實現(xiàn)了Queue的接口

* 先進先出抠艾。先出的一端為隊頭，另一端為隊尾桨昙。

* LinkedList就是天生的隊列實現(xiàn)检号。

4.順序存儲方式線性表（ArrayList）

* 順序存儲方式線性表（ArrayList）：查找效率高，插入刪除效率低（ArrayList刪除元素后蛙酪，后面元素會向前位移）

* ArrayList的本質是維護了一個對象數(shù)組齐苛，對ArrayList的增刪改查即對數(shù)組進行操作

* 1. List接口中有sort方法，需要實現(xiàn)Comparator方法就能進行排序

* 2. List接口繼承Collection滤否，Collection集成Iterable

* 3. System.arraycopy? 是用于復制數(shù)組的native方法脸狸，應學會使用。

*

*? Vector：

*? 矢量隊列，它是JDK1.0版本添加的類炊甲。

*? 和ArrayList類似泥彤，內部維護一個對象數(shù)組。

*? Vector 實現(xiàn)了RandmoAccess接口卿啡，即提供了隨機訪問功能吟吝。

*? Vector中的操作是線程安全的,但比ArrayList稍微慢。

5.??鏈式存儲方式線性表（linkedList）

* 鏈式存儲方式線性表（linkedList）：插入效率高颈娜，查詢效率低

* 通過內部維護連接 Node對象 來實現(xiàn)鏈式存儲結構

6.哈希表

* key存在Set集合中（Set中數(shù)據(jù)不能相同）剑逃，Value存在Collection中（可以相同）。

* 無序集合官辽，多線程下不安全

* Hashmap默認初始化大小16蛹磺，負載因子0.75

* hashmap元素的key可以為空，key對應的index可以相同（鏈表）

* JDK 1.8 以前 HashMap的實現(xiàn)是數(shù)組+鏈表同仆，即使哈希函數(shù)取得再好萤捆，也很難達到元素百分百均勻分布。

* 針對這種情況俗批，JDK 1.8 中引入了 紅黑樹（查找時間復雜度為O(logn)）來優(yōu)化這個問題,

* 紅黑樹是自動平衡的二叉查找樹俗或，通過變色，左轉岁忘，右轉來實現(xiàn)平衡辛慰。

7.鏈式哈希表

* Node<K, V> 每個節(jié)點添加頭尾指針，構成雙向鏈表

* LruCache的實現(xiàn)（Linkedhashmap默認插入排序干像，需要配置一個布爾值accessOrder來設置調用排序）帅腌。

* LinkedHashMap的實現(xiàn)就是HashMap+LinkedList的實現(xiàn)方式，以HashMap維護數(shù)據(jù)結構麻汰，以LinkList的方式維護數(shù)據(jù)插入順序狞膘。

* next是用于維護HashMap指定table位置上連接的Entry的順序的，before什乙、After是用于維護Entry插入的先后順序的。

* 迭代HashMap的順序并不是HashMap放置的順序已球，Linkedhashmap有順序臣镣，插入順序或者調用順序，默認采用插入智亮。

* 線程不安全

*

* 該循環(huán)雙向鏈表的頭部存放的是最久訪問的節(jié)點或最先插入的節(jié)點忆某，尾部為最近訪問的或最近插入的節(jié)點，迭代器遍歷方向是從鏈表的頭部開始到鏈表尾部結束阔蛉，在鏈表尾部有一個空的header節(jié)點弃舒，該節(jié)點不存放key-value內容，為LinkedHashMap類的成員屬性，循環(huán)雙向鏈表的入口聋呢。

* header的目的是為了記錄第一個插入的元素是誰苗踪，在遍歷的時候能夠找到第一個元素。

* 注意這個header削锰，hash值為-1通铲，其他都為null，也就是說這個header不放在數(shù)組中器贩，就是用來指示開始元素和標志結束元素的颅夺。

*/

8.圖

* 圖的鄰接表的實現(xiàn)

* 圖中的元素稱為頂點，頂點之間的連線叫做邊蛹稍，邊分為無向邊和有向邊吧黄，有向邊也稱為弧，弧有弧頭和弧尾唆姐。

* 弧有與之對應的數(shù)字拗慨，成為權。

* 任意兩點之間是聯(lián)通的厦酬，稱為連通圖胆描。

* 圖中一個頂點可以連接無數(shù)個頂點

* 無向圖定點的邊數(shù)叫度，有向圖頂點的邊數(shù)叫出度和入度仗阅。

* 圖的實現(xiàn)：1. 鄰接矩陣（一個一維數(shù)組表示頂點信息昌讲，一個二維數(shù)組存儲弧的信息）。

* 圖的實現(xiàn)：2.? 鄰接表（散鏈列表）

* 圖-臨接矩陣實現(xiàn)

* 圖的兩種遍歷：深度優(yōu)先遍歷减噪，廣度優(yōu)先遍歷

* 圖的最小生成樹的兩種算法：普利姆算法短绸，克魯斯卡爾算法

* 最短路徑：迪杰斯特拉算法

/**

? * 最小生成樹：

? * 普利姆算法：

? * 獲取一個頂點A和它連接的頂點數(shù)組X，然后連接權值最小的頂點B筹裕，并將B連接的頂點數(shù)組合并到X醋闭，

? * 仍從X中找出權值最小的頂點連接，以此類推朝卒。

*/

/**

? * 最小生成樹

? * 克魯斯卡爾算法：

? * Edge edge0 = new Edge(int begin,int end, int weight);

? * begin為邊的起始頂點证逻，end為邊的結束頂點，weight為邊的權重

? * 通過構建邊的數(shù)組來進行計算抗斤。

? * 思想：按權重從小到大遍歷囚企，構成回環(huán)的邊舍棄

? *

*/

/**

? * 最短路徑：

? * 迪杰斯特拉算法：

? * 獲取一個頂點A和它連接的頂點數(shù)組X，然后連接最小權值(M)的頂點B瑞眼，然后將B頂點的數(shù)組P整合到數(shù)組X(數(shù)組P相加M和數(shù)組X取最小值)

*/