一、常見的數(shù)據(jù)結構

數(shù)組，棧，隊列，鏈表，散列表，二叉樹，堆，跳表，圖，樹。

1. 數(shù)組：

數(shù)組的元素在內(nèi)存中存儲是連續(xù)存放的，占有連續(xù)的存儲單元（連續(xù)的內(nèi)存空間）；且容量固定（定容）；只能存儲一種類型的數(shù)據(jù)；添加、刪除操作慢，因為要移動其他元素（提供隨機訪問，但插入刪除操作慢）。

訪問的時間復雜度：O（1）；

插入/刪除的時間復雜度：O（n）。

2. 棧：

后進先出，棧頂入棧，棧頂出棧。棧常應用于實現(xiàn)遞歸功能方面的場景，如斐波那契數(shù)列。

棧常由一維數(shù)組或鏈表表示，分別叫做順序棧和鏈式棧。

不同的出棧排列個數(shù)：

常用的操作有：入棧push，出棧pop。

訪問的時間復雜度：O（n）（最壞）；

插入/刪除的時間復雜度：O（1）。

應用：瀏覽器的倒退和前進；檢查符號是否成對出現(xiàn)（如果是左括號就直接push到stack中，否則將stack的棧頂元素與該括號做比較，不相等就直接返回false）；翻轉(zhuǎn)字符串；維護函數(shù)調(diào)用等。

3. 隊列：

先進先出，在多線程阻塞隊列管理中非常適用。

隊列用數(shù)組或鏈表實現(xiàn)，分別叫做順序隊列和鏈式隊列。

訪問的時間復雜度：O（n）（最壞）；

插入/刪除的時間復雜度：O（1）。

單隊列：順序隊列（由數(shù)組實現(xiàn)，會出現(xiàn)假溢出現(xiàn)象）和鏈式隊列。

循環(huán)隊列：解決假溢出和越界問題。循環(huán)隊列判斷隊滿的常用方法是①設置flag標志位；②使用一個空閑位。

雙端隊列：元素可以從隊頭出隊和入隊，也可以從隊尾出隊和入隊。

優(yōu)先隊列：由堆實現(xiàn)。

***循環(huán)隊列中元素個數(shù)求法：（rear-front+m）?% m（取余） ，其中，rear：隊列尾指針，front：隊列頭指針，m：隊列容量。

***循環(huán)隊列中區(qū)分隊空和隊滿的方法：

（1）犧牲一個存儲單元（入隊時少用一個隊列單元）：

隊滿條件：（q.rear+1）%maxsize == q.front

隊空條件：q.front == q.rear

（2）增設表示元素個數(shù)的數(shù)據(jù)成員：

隊滿條件：q.size == MaxSize

隊空條件：q.front == q.rear

（3）增設tag數(shù)據(jù)成員：

隊滿條件：tag == 1

隊空條件：tag == 0

4.鏈表：

物理存儲單元上非連續(xù)的，非順序的存儲結構；每個元素包含兩個節(jié)點：數(shù)據(jù)域和指針域；不需要初始化容量，可以任意加減元素，只需要改變前后2個元素節(jié)點的指針域指向地址即可。

***如何判斷鏈表是否有環(huán)？

（1）窮舉遍歷：設一個檢測指針k和一個遍歷指針q，count記錄q走的步數(shù)，q每走一步，k就走q之前走過的節(jié)點，若發(fā)現(xiàn)相同的節(jié)點就說明有環(huán)。q=NULL時遍歷完整個鏈表。時間復雜度是O(n^2)，空間復雜度是O(1)。

（2）標記法：設置一個標記變量，每走一個節(jié)點，就判斷一次，若visit=true則有環(huán)，反之無環(huán)。時間復雜度是O(n)，空間復雜度是O(n)。

5. 散列表（哈希表）：

根據(jù)鍵（key）而直接訪問在內(nèi)存存儲位置的數(shù)據(jù)結構。哈希表建立了關鍵字和存儲地址之間的一種直接映射關系。

• 構造方法：

（1）直接定址法：直接取關鍵字的某個線性函數(shù)為哈希地址。

（2）除留余數(shù)法：假定哈希表長度為m，取一個不大于m但最接近于/等于m的質(zhì)數(shù)P，利用公式H(key)=key%P將關鍵字轉(zhuǎn)化為哈希地址。

（3）數(shù)據(jù)分析法：設關鍵字是r進制數(shù)，選取數(shù)碼分布較為均勻的若干位作為哈希地址。

（4）平方取中法：取關鍵字的平方值的中間幾位作為哈希地址。

• 哈希沖突的解決方法：

（1）開放尋址法：線性探查法，平方探查法，雙重散列探查法，偽隨機探查法。

（2）拉鏈法（鏈地址法）

（3）再哈希法

6. 非線性數(shù)據(jù)結構——圖：

圖的存儲使用：①鄰接矩陣：二維矩陣，如A[i][j]=n（權值）或者A[i][j]=0/1，無線圖的鄰接矩陣是對稱矩陣。鄰接矩陣比較浪費空間。

②鄰接表：如下圖所示，在無向圖中，鄰接表元素的個數(shù)=邊的條數(shù)*2；在有向圖中，鄰接表元素的個數(shù)=邊的條數(shù)。

7. 非線性數(shù)據(jù)結構——堆：?

堆不一定是完全二叉樹，任意一個節(jié)點的值都?≥（或≤）所有子節(jié)點的值，堆通常用數(shù)組表示。

堆的插入和刪除效率高，時間復雜度是O（logn），初始化的時間復雜度是O（n）。

***若根節(jié)點的序號為1，那么樹中任意節(jié)點 i，其左子節(jié)點序號為 2i，右子節(jié)點為 2i+1。

①自底向上堆化：會產(chǎn)生“氣泡”浪費存儲空間，用于插入元素，即先將元素放至數(shù)組末尾，上浮。

②自頂向下堆化：用于刪除堆頂元素，將末尾元素放至堆頂，再向下堆化，下沉。

根的下標一定為0，最后一個元素的下標一定為size-1.

已知一個節(jié)點下標為index，那么，他的雙親下標為（index-1）/2，左孩子的下標為2*index+1，右孩子的下標為左孩子下標+1。

8. 非線性數(shù)據(jù)結構——樹：??

n個節(jié)點，n-1條邊。

高度：該節(jié)點到葉子節(jié)點的最長路徑所包含的邊數(shù)。

深度：根節(jié)點到該節(jié)點的路徑所包含的邊數(shù)。

層數(shù)：節(jié)點的深度+1。

二叉樹（鏈式存儲或順序存儲）：第 i 層至多有 2^（i-1）?個節(jié)點，深度為k的二叉樹至多共有 2^(k+1)-1 個節(jié)點（滿二叉樹），至少共有 2^k 個節(jié)點。

完全二叉樹：除最后一層外，若其余層都是滿的，并且最后一層或者是滿的，或者是在右邊缺少連續(xù)若干節(jié)點，則這個二叉樹就是?完全二叉樹?。

平衡二叉樹：空或者左右子樹的高度差絕對值不超過1，且左右子樹都是一顆平衡二叉樹。平衡二叉樹的常用實現(xiàn)方法有?紅黑樹、AVL 樹、替罪羊樹、加權平衡樹、伸展樹?等。

紅黑樹：每個節(jié)點非紅即黑，根節(jié)點是黑色節(jié)點，葉節(jié)點都是黑色的空節(jié)點。

二叉樹的存儲主要分為?鏈式存儲?和?順序存儲?兩種：

（1）鏈式存儲：和鏈表類似，二叉樹的鏈式存儲依靠指針將各個節(jié)點串聯(lián)起來，不需要連續(xù)的存儲空間。

每個節(jié)點包括三個屬性：

• 數(shù)據(jù) data。data 不一定是單一的數(shù)據(jù)，根據(jù)不同情況，可以是多個具有不同類型的數(shù)據(jù)。
• 左節(jié)點指針 left
• 右節(jié)點指針 right。

（2） 順序存儲：利用數(shù)組進行存儲，數(shù)組中的每一個位置僅存儲節(jié)點的 data，不存儲左右子節(jié)點的指針，子節(jié)點的索引通過數(shù)組下標完成。根結點的序號為 1，對于每個節(jié)點 Node，假設它存儲在數(shù)組中下標為 i 的位置，那么它的左子節(jié)點就存儲在 2i 的位置，它的右子節(jié)點存儲在下標為 2i+1 的位置。如：

樹的存儲方式圖片來自：樹 | JavaGuide(Java面試 + 學習指南)?

二叉樹的遍歷：

（1）先序遍歷（根左右）；（2）中序遍歷（左根右）；（3）后序遍歷（左右根）。

注：由先序序列和后序序列不能重現(xiàn)一顆二叉樹。先序、后序、層序序列的兩兩組合無法唯一確定一棵二叉樹。

可以通過①先序+中序；②后序+中序；或者③層序+中序 序列構造一顆二叉樹。

二、常用算法

遞歸，排序，二分查找，搜索，哈希算法，分治算法，動態(tài)規(guī)劃，字符串匹配算法等。