一、常見的數(shù)據(jù)結(jié)構(gòu)

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

1. 數(shù)組：

數(shù)組的元素在內(nèi)存中存儲是連續(xù)存放的，占有連續(xù)的存儲單元（連續(xù)的內(nèi)存空間）；且容量固定（定容）；只能存儲一種類型的數(shù)據(jù)；添加、刪除操作慢，因?yàn)橐苿悠渌?#xff08;提供隨機(jī)訪問，但插入刪除操作慢）。

訪問的時(shí)間復(fù)雜度：O（1）；

插入/刪除的時(shí)間復(fù)雜度：O（n）。

2. 棧：

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

棧常由一維數(shù)組或鏈表表示，分別叫做順序棧和鏈?zhǔn)綏！?/p>

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

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

訪問的時(shí)間復(fù)雜度：O（n）（最壞）；

插入/刪除的時(shí)間復(fù)雜度：O（1）。

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

3. 隊(duì)列：

先進(jìn)先出，在多線程阻塞隊(duì)列管理中非常適用。

隊(duì)列用數(shù)組或鏈表實(shí)現(xiàn)，分別叫做順序隊(duì)列和鏈?zhǔn)疥?duì)列。

訪問的時(shí)間復(fù)雜度：O（n）（最壞）；

插入/刪除的時(shí)間復(fù)雜度：O（1）。

單隊(duì)列：順序隊(duì)列（由數(shù)組實(shí)現(xiàn)，會出現(xiàn)假溢出現(xiàn)象）和鏈?zhǔn)疥?duì)列。

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

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

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

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

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

（1）犧牲一個(gè)存儲單元（入隊(duì)時(shí)少用一個(gè)隊(duì)列單元）：

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

隊(duì)空條件：q.front == q.rear

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

隊(duì)滿條件：q.size == MaxSize

隊(duì)空條件：q.front == q.rear

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

隊(duì)滿條件：tag == 1

隊(duì)空條件：tag == 0

4.鏈表：

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

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

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

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

5. 散列表（哈希表）：

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

• 構(gòu)造方法：

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

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

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

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

• 哈希沖突的解決方法：

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

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

（3）再哈希法

6. 非線性數(shù)據(jù)結(jié)構(gòu)——圖：

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

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

7. 非線性數(shù)據(jù)結(jié)構(gòu)——堆：?

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

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

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

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

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

根的下標(biāo)一定為0，最后一個(gè)元素的下標(biāo)一定為size-1.

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

8. 非線性數(shù)據(jù)結(jié)構(gòu)——樹：??

n個(gè)節(jié)點(diǎn)，n-1條邊。

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

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

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

二叉樹（鏈?zhǔn)酱鎯蝽樞虼鎯?#xff09;：第 i 層至多有 2^（i-1）?個(gè)節(jié)點(diǎn)，深度為k的二叉樹至多共有 2^(k+1)-1 個(gè)節(jié)點(diǎn)（滿二叉樹），至少共有 2^k 個(gè)節(jié)點(diǎn)。

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

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

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

二叉樹的存儲主要分為?鏈?zhǔn)酱鎯?/strong>?和?順序存儲?兩種：

（1）鏈?zhǔn)酱鎯?#xff1a;和鏈表類似，二叉樹的鏈?zhǔn)酱鎯σ揽恐羔槍⒏鱾€(gè)節(jié)點(diǎn)串聯(lián)起來，不需要連續(xù)的存儲空間。

每個(gè)節(jié)點(diǎn)包括三個(gè)屬性：

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

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

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

二叉樹的遍歷：

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

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

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

二、常用算法

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