[[377374]]

本文轉(zhuǎn)載自微信公眾號「淺羽的IT小屋」，作者淺羽Eric 。轉(zhuǎn)載本文請聯(lián)系淺羽的IT小屋公眾號。

這段時間在圈子里也認識了很多大佬們，從他們身上看到的是事業(yè)有成，感情幸福，還都很年輕。不禁感嘆，年輕人都這么有規(guī)劃，成為了別人眼中的人生贏家模樣。我覺得不要太在意與別人的橫向比較，更多的應(yīng)該是與自己的縱向比較。因為普通人更多，我們都是在為工作、生活努力的那群人。這句話更多的是想送給一部分關(guān)注我號，目前比較焦慮的小伙伴，你要堅信只要努力，沒有辦不成的事。

今天給大家介紹的是常見的幾種數(shù)據(jù)結(jié)構(gòu)，主要針對一些剛?cè)腴T數(shù)據(jù)結(jié)構(gòu)以及需要系統(tǒng)復(fù)習數(shù)據(jù)結(jié)構(gòu)的小伙伴們!身為程序員的我們，每天都在和不同的數(shù)據(jù)打交道。那么你真的對數(shù)據(jù)結(jié)構(gòu)一清二楚了么?

小羽從各數(shù)據(jù)結(jié)構(gòu)的定義、特點、使用和方法實現(xiàn)來給大家進行介紹。每種都配有圖文進行詳解，幫助大家來更好地掌握對應(yīng)知識。如果你對這個問題有困惑，快來看看~

棧 stack

棧(stack)是限制插入和刪除只能在一個位置上進行的表，該位置是表的末端，叫做棧頂(top)。它是后進先出(LIFO)的。對棧的基本操作只有 push(進棧)和 pop(出棧)兩種，前者相當于插入，后者相當于刪除最后的元素。

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

隊列 queue

隊列是一種特殊的線性表，特殊之處在于它只允許在表的前端(front)進行刪除操作，而在表的后端(rear)進行插入操作，和棧一樣，隊列是一種操作受限制的線性表。進行插入操作的端稱為隊尾，進行刪除操作的端稱為隊頭。

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

鏈表 Link

鏈表是一種數(shù)據(jù)結(jié)構(gòu)，和數(shù)組同級。比如，Java 中我們使用的 ArrayList，其實現(xiàn)原理是數(shù)組。而LinkedList 的實現(xiàn)原理就是鏈表了。鏈表在進行循環(huán)遍歷時效率不高，但插入和刪除時優(yōu)勢明顯。

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

散列表 Hash Table

散列表(Hash table，也叫哈希表)是一種查找算法，與鏈表、樹等算法不同的是，散列表算法在查找時不需要進行一系列和關(guān)鍵字(關(guān)鍵字是數(shù)據(jù)元素中某個數(shù)據(jù)項的值，用以標識一個數(shù)據(jù)元素)的比較操作。

散列表算法希望能盡量做到不經(jīng)過任何比較，通過一次存取就能得到所查找的數(shù)據(jù)元素，因而必須要在數(shù)據(jù)元素的存儲位置和它的關(guān)鍵字(可用 key 表示)之間建立一個確定的對應(yīng)關(guān)系，使每個關(guān)鍵字和散列表中一個唯一的存儲位置相對應(yīng)。因此在查找時，只要根據(jù)這個對應(yīng)關(guān)系找到給定關(guān)鍵字在散列表中的位置即可。這種對應(yīng)關(guān)系被稱為散列函數(shù)(可用 h(key)表示)。

用的構(gòu)造散列函數(shù)的方法有：

直接定址法：取關(guān)鍵字或關(guān)鍵字的某個線性函數(shù)值為散列地址。即：h(key) = key 或 h(key) = a * key + b，其中 a 和 b 為常數(shù)。

數(shù)字分析法：數(shù)字分析法又稱數(shù)字選擇法，其方法是收集所有可能出現(xiàn)的鍵值，排列在一起，對鍵值的每一位進行分析，選擇分布較均勻若干位組成散列地址。

平方取值法：取關(guān)鍵字平方后的中間幾位為散列地址。

折疊法：將關(guān)鍵字分割成位數(shù)相同的幾部分，然后取這幾部分的疊加和作為散列地址。

除留余數(shù)法：取關(guān)鍵字被某個不大于散列表表長 m 的數(shù) p 除后所得的余數(shù)為散列地址，即：h(key) = key MOD p p ≤ m

隨機數(shù)法：選擇一個隨機函數(shù)，取關(guān)鍵字的隨機函數(shù)值為它的散列地址，即：h(key) = random(key)

用散列函數(shù)h將關(guān)鍵字映射到散列表中

排序二叉樹

首先如果普通二叉樹每個節(jié)點滿足：左子樹所有節(jié)點值小于它的根節(jié)點值，且右子樹所有節(jié)點值大于它的根節(jié)點值，則這樣的二叉樹就是排序二叉樹。

插入操作

首先要從根節(jié)點開始往下找到自己要插入的位置(即新節(jié)點的父節(jié)點);具體流程是：新節(jié)點與當前節(jié)點比較，如果相同則表示已經(jīng)存在且不能再重復(fù)插入;如果小于當前節(jié)點，則到左子樹中尋找，如果左子樹為空則當前節(jié)點為要找的父節(jié)點，新節(jié)點插入到當前節(jié)點的左子樹即可;如果大于當前節(jié)點，則到右子樹中尋找，如果右子樹為空則當前節(jié)點為要找的父節(jié)點，新節(jié)點插入到當前節(jié)點的右子樹即可。

從左到右，從下到上(7次插入操作)

刪除操作

刪除操作主要分為三種情況，即要刪除的節(jié)點無子節(jié)點，要刪除的節(jié)點只有一個子節(jié)點，要刪除的節(jié)點有兩個子節(jié)點。

1. 對于要刪除的節(jié)點無子節(jié)點可以直接刪除，即讓其父節(jié)點將該子節(jié)點置空即可。

2. 對于要刪除的節(jié)點只有一個子節(jié)點，則替換要刪除的節(jié)點為其子節(jié)點。

3. 對于要刪除的節(jié)點有兩個子節(jié)點，則首先找該節(jié)點的替換節(jié)點(即右子樹中最小的節(jié)點)，接著替換要刪除的節(jié)點為替換節(jié)點，然后刪除替換節(jié)點。

三種情況

查詢操作

查找操作的主要流程為：先和根節(jié)點比較，如果相同就返回，如果小于根節(jié)點則到左子樹中遞歸查找，如果大于根節(jié)點則到右子樹中遞歸查找。因此在排序二叉樹中可以很容易獲取最大(最右最深子節(jié)點)和最小(最左最深子節(jié)點)值。

紅黑樹

R-B Tree，全稱是 Red-Black Tree，又稱為“紅黑樹”，它一種特殊的二叉查找樹。紅黑樹的每個節(jié)點上都有存儲位表示節(jié)點的顏色，可以是紅(Red)或黑(Black)。

紅黑樹的特性

1. 每個節(jié)點或者是黑色，或者是紅色。

2. 根節(jié)點是黑色。

3. 每個葉子節(jié)點(NIL)是黑色。[注意：這里葉子節(jié)點，是指為空(NIL 或NULL)的葉子節(jié)點!] (4)如果一個節(jié)點是紅色的，則它的子節(jié)點必須是黑色的。

4. 從一個節(jié)點到該節(jié)點的子孫節(jié)點的所有路徑上包含相同數(shù)目的黑節(jié)點。

左旋

對 x 進行左旋，意味著，將“x 的右孩子”設(shè)為“x 的父親節(jié)點”;即，將 x 變成了一個左節(jié)點(x成了為 z 的左孩子)!。因此，左旋中的“左”，意味著“被旋轉(zhuǎn)的節(jié)點將變成一個左節(jié)點”。

左旋

LEFT-ROTATE(T, x)  
y ← right[x] // 前提：這里假設(shè) x 的右孩子為 y。下面開始正式操作 
right[x] ← left[y] // 將 “y 的左孩子” 設(shè)為 “x 的右孩子”，即 將β設(shè)為 x 的右孩子 
p[left[y]] ← x // 將 “x” 設(shè)為 “y 的左孩子的父親”，即 將β的父親設(shè)為 x 
p[y] ← p[x] // 將 “x 的父親” 設(shè)為 “y 的父親” 
if p[x] = nil[T]  
then root[T] ← y // 情況 1：如果 “x 的父親” 是空節(jié)點，則將 y 設(shè)為根節(jié)點 
else if x = left[p[x]]  
 then left[p[x]] ← y // 情況 2：如果 x 是它父節(jié)點的左孩子，則將 y 設(shè)為“x 的父節(jié)點 
的左孩子” 
 else right[p[x]] ← y // 情況 3：(x 是它父節(jié)點的右孩子) 將 y 設(shè)為“x 的父節(jié)點的右孩 
子” 
left[y] ← x // 將 “x” 設(shè)為 “y 的左孩子” 
p[x] ← y // 將 “x 的父節(jié)點” 設(shè)為 “y 

節(jié)點左旋演示

右旋

對 x 進行右旋，意味著，將“x 的左孩子”設(shè)為“x 的父親節(jié)點”;即，將 x 變成了一個右節(jié)點(x成了為 y 的右孩子)!因此，右旋中的“右”，意味著“被旋轉(zhuǎn)的節(jié)點將變成一個右節(jié)點”。

右旋

RIGHT-ROTATE(T, y)  
x ← left[y] // 前提：這里假設(shè) y 的左孩子為 x。下面開始正式操作 
left[y] ← right[x] // 將 “x 的右孩子” 設(shè)為 “y 的左孩子”，即 將β設(shè)為 y 的左孩子 
p[right[x]] ← y // 將 “y” 設(shè)為 “x 的右孩子的父親”，即 將β的父親設(shè)為 y 
p[x] ← p[y] // 將 “y 的父親” 設(shè)為 “x 的父親” 
if p[y] = nil[T]  
then root[T] ← x // 情況 1：如果 “y 的父親” 是空節(jié)點，則將 x 設(shè)為根節(jié)點 
else if y = right[p[y]]  
 then right[p[y]] ← x // 情況 2：如果 y 是它父節(jié)點的右孩子，則將 x 設(shè)為“y 的父節(jié) 
點的左孩子” 
 else left[p[y]] ← x // 情況 3：(y 是它父節(jié)點的左孩子) 將 x 設(shè)為“y 的父節(jié)點的左孩 
子” 
right[x] ← y // 將 “y” 設(shè)為 “x 的右孩子” 
p[y] ← x // 將 “y 的父節(jié)點” 設(shè)為 “x” 

添加

第一步: 將紅黑樹當作一顆二叉查找樹，將節(jié)點插入。

第二步：將插入的節(jié)點著色為"紅色"。根據(jù)被插入節(jié)點的父節(jié)點的情況，可以將"當節(jié)點 z 被著色為紅色節(jié)點，并插入二叉樹"劃分為三種情況來處理。

當被插入的節(jié)點是根節(jié)點時間，直接把此節(jié)點涂為黑色。

當被插入的節(jié)點的父節(jié)點是黑色，什么也不需要做。節(jié)點被插入后，仍然是紅黑樹。

當被插入的節(jié)點的父節(jié)點是紅色。這種情況下，被插入節(jié)點是一定存在非空祖父節(jié)點的;進一步的講，被插入節(jié)點也一定存在叔叔節(jié)點(即使叔叔節(jié)點為空，我們也視之為存在，空節(jié)點本身就是黑色節(jié)點)。理解這點之后，我們依據(jù)"叔叔節(jié)點的情況"，將這種情況進一步劃分為 3 種情況(Case)。

3種情況(case)

第三步: 通過一系列的旋轉(zhuǎn)或著色等操作，使之重新成為一顆紅黑樹。

刪除

第一步：將紅黑樹當作一顆二叉查找樹，將節(jié)點刪除。

這和"刪除常規(guī)二叉查找樹中刪除節(jié)點的方法是一樣的"。分 3 種情況：

1. 被刪除節(jié)點沒有兒子，即為葉節(jié)點。那么，直接將該節(jié)點刪除就 OK 了。

2. 被刪除節(jié)點只有一個兒子。那么，直接刪除該節(jié)點，并用該節(jié)點的唯一子節(jié)點頂替它的位置。

3. 被刪除節(jié)點有兩個兒子。那么，先找出它的后繼節(jié)點;然后把“它的后繼節(jié)點的內(nèi)容”復(fù)制給“該節(jié)點的內(nèi)容”;之后，刪除“它的后繼節(jié)點”。

第二步：通過"旋轉(zhuǎn)和重新著色"等一系列來修正該樹，使之重新成為一棵紅黑樹。

因為"第一步"中刪除節(jié)點之后，可能會違背紅黑樹的特性。所以需要通過"旋轉(zhuǎn)和重新著色"來修正該樹，使之重新成為一棵紅黑樹。選擇重著色 3 種情況。

當 x 是“紅+黑”節(jié)點，直接把 x 設(shè)為黑色，結(jié)束。此時紅黑樹性質(zhì)全部恢復(fù)。

當 x 是“黑+黑”節(jié)點，且 x 是根，什么都不做，結(jié)束。此時紅黑樹性質(zhì)全部恢復(fù)。

當 x 是“黑+黑”節(jié)點，且 x 不是根，這種情況又可以劃分為 4 種子情況。這 4 種子情況如下表所示：

4種情況(case)

B-TREE

B-tree 又叫平衡多路查找樹。一棵 m 階的 B-tree (m 叉樹)的特性如下(其中 ceil(x)是一個取上限的函數(shù))：

1. 樹中每個結(jié)點至多有 m 個孩子;

2. 除根結(jié)點和葉子結(jié)點外，其它每個結(jié)點至少有有 ceil(m / 2)個孩子;

3. 若根結(jié)點不是葉子結(jié)點，則至少有 2 個孩子(特殊情況：沒有孩子的根結(jié)點，即根結(jié)點為葉子結(jié)點，整棵樹只有一個根節(jié)點);

4. 所有葉子結(jié)點都出現(xiàn)在同一層，葉子結(jié)點不包含任何關(guān)鍵字信息(可以看做是外部結(jié)點或查詢失敗的結(jié)點，實際上這些結(jié)點不存在，指向這些結(jié)點的指針都為 null);

5. 每個非終端結(jié)點中包含有 n 個關(guān)鍵字信息：(n，P0，K1，P1，K2，P2，……，Kn，Pn)。其中：

Ki (i=1…n)為關(guān)鍵字，且關(guān)鍵字按順序排序 K(i-1)< Ki。

Pi 為指向子樹根的接點，且指針 P(i-1)指向子樹種所有結(jié)點的關(guān)鍵字均小于 Ki，但都大于 K(i-1)。

關(guān)鍵字的個數(shù) n 必須滿足：ceil(m / 2)-1 <= n <= m-1

b-tree

一棵 m 階的 B+tree 和 m 階的 B-tree 的差異在于：

1. 有 n 棵子樹的結(jié)點中含有 n 個關(guān)鍵字;(B-tree 是 n 棵子樹有 n-1 個關(guān)鍵字)

2. 所有的葉子結(jié)點中包含了全部關(guān)鍵字的信息，及指向含有這些關(guān)鍵字記錄的指針，且葉子結(jié)點本身依關(guān)鍵字的大小自小而大的順序鏈接。(B-tree 的葉子節(jié)點并沒有包括全部需要查找的信息)

3. 所有的非終端結(jié)點可以看成是索引部分，結(jié)點中僅含有其子樹根結(jié)點中最大(或最小)關(guān)鍵字。(B-tree 的非終節(jié)點也包含需要查找的有效信息)

差異

位圖

位圖的原理就是用一個 bit 來標識一個數(shù)字是否存在，采用一個 bit 來存儲一個數(shù)據(jù)，所以這樣可以大大的節(jié)省空間。bitmap 是很常用的數(shù)據(jù)結(jié)構(gòu)，比如用于 Bloom Filter 中;用于無重復(fù)整數(shù)的排序等等。bitmap 通?；跀?shù)組來實現(xiàn)，數(shù)組中每個元素可以看成是一系列二進制數(shù)，所有元素組成更大的二進制集合。

例如：unsigned int bit[N]，在這個數(shù)組里面，可以存儲 N * sizeof(int) * 8個數(shù)據(jù)，但是最大的數(shù)只能是N * sizeof(int) * 8 - 1。假如，我們要存儲的數(shù)據(jù)范圍為0-15，則我們只需要使得N=1，這樣就可以把數(shù)據(jù)存進去。如下圖：

數(shù)據(jù)為【5，1，7，15，0，4，6，10】，則存入這個結(jié)構(gòu)中的情況為