線性表的基本運算
查找、插入、刪除

4. 哈希表

散列表（Hash table，也叫哈希表），是根據(jù)關(guān)鍵碼值(Key value)而直接進(jìn)行訪問的數(shù)據(jù)結(jié)構(gòu)。也就是說，它通過把關(guān)鍵碼值映射到表中一個位置來訪問記錄，以加快查找的速度。這個映射函數(shù)叫做散列函數(shù)，理想情況下它應(yīng)該計算起來簡單，并且應(yīng)該保證任何兩個不同的關(guān)鍵字映射到不停的單元。存放記錄的數(shù)組叫做散列表。
給定表M，存在函數(shù)f(key)，對任意給定的關(guān)鍵字值key，代入函數(shù)后若能得到包含該關(guān)鍵字的記錄在表中的地址，則稱表M為哈希(Hash）表，函數(shù)f(key)為哈希(Hash) 函數(shù)。
若關(guān)鍵字為k，則其值存放在f(k)的存儲位置上。由此，不需比較便可直接取得所查記錄。稱這個對應(yīng)關(guān)系f為散列函數(shù)，按這個思想建立的表為散列表。對不同的關(guān)鍵字可能得到同一散列地址，即k1≠k2，而f(k1)=f(k2)，這種現(xiàn)象稱為碰撞。
若對于關(guān)鍵字集合中的任一個關(guān)鍵字，經(jīng)散列函數(shù)映象到地址集合中任何一個地址的概率是相等的，則稱此類散列函數(shù)為均勻散列函數(shù)，這就是使關(guān)鍵字經(jīng)過散列函數(shù)得到一個“隨機(jī)的地址”，從而減少碰撞。
選取散列函數(shù)的常用方法：
<1> 直接尋址法。
<2> 平方取中法。
<3> 除留余數(shù)法。
處理沖突的常用方法：
<1> 開放尋址法。
<2> 鏈地址法（拉鏈法）。
<3> 再散列法。
查找性能：
查找過程中，關(guān)鍵碼的比較次數(shù)，取決于產(chǎn)生沖突的多少，產(chǎn)生的沖突少，查找效率就高，產(chǎn)生的沖突多，查找效率就低。因此，影響產(chǎn)生沖突多少的因素，也就是影響查找效率的因素。
如果輸入的關(guān)鍵字是整數(shù)，則一般合理的方法就是直接返回 key mod tableSize。如果關(guān)鍵字是字符串，一種選擇方法是把字符串中字符的ASCII碼(或Unicode碼)值加起來之后再對tableSize取余。

5. 棧

棧作為一種限定性的線性表，是一種先進(jìn)后出(LIFO)的線性表，是將線性表的插入和刪除運算限制為僅在表的一端進(jìn)行。
通常將表中允許進(jìn)行插入和刪除操作的一端稱為棧頂，它由一個稱為棧頂指針的位置指示器指示，另一端稱為棧底，插入操作稱為進(jìn)?；蛉霔?，刪除操作稱為出棧或退棧。
棧的兩種存儲結(jié)構(gòu)：順序棧是用順序存儲結(jié)構(gòu)實現(xiàn)的棧，即利用一組地址連續(xù)的存儲單元依次存放自棧底到棧頂?shù)臄?shù)據(jù)元素。鏈棧即采用鏈表作為存儲結(jié)構(gòu)實現(xiàn)的棧，為便于操作，這里采用帶頭結(jié)點的單鏈表實現(xiàn)棧，采用鏈棧不必預(yù)先估計棧的最大容量，只要系統(tǒng)有可用空間，鏈棧就不會出現(xiàn)溢出。
棧的應(yīng)用：
<1> 括號匹配問題
<2> 表達(dá)式求值問題
<3> 十進(jìn)制正整數(shù)轉(zhuǎn)換為R進(jìn)制。

6. 隊列

隊列是另一種限定性的線性表，它只允許在表的一端(隊尾)插入元素，而在另一端(隊頭)刪除元素，所以隊列具有先進(jìn)先出(FIFO)的特性。
用鏈表表示的隊列簡稱為鏈隊列。隊列的一種順序存儲稱為順序隊列，由于它存在假溢出的問題，可以使用循環(huán)隊列解決該問題，為了區(qū)分循環(huán)隊列是空隊還是滿隊的兩種方法是：第一是損失一個元素空間，第二種方法是增設(shè)標(biāo)志量tag。

7. 串

字符串是由零個或多個字符組成的有限序列。串也是一種特定的線性表。串的順序存儲結(jié)構(gòu)：定長順序串與堆串。串也可以采用鏈?zhǔn)酱鎯Y(jié)構(gòu)稱為塊鏈串。

8. 樹

樹是n(n >= 0)個結(jié)點的有限集合T。當(dāng)n=0時，稱為空樹；當(dāng)n>0時，該集合滿足如下條件：
<1> 其中必有一個稱為根(root)的特定結(jié)點，它沒有直接前驅(qū)，但有零個或多個直接后繼。
<2> 其余n-1個節(jié)點可以劃分為m(m>=0)個互不相交的有限集。
樹的相關(guān)術(shù)語：
結(jié)點：包括一個數(shù)據(jù)元素及若干指向其他節(jié)點的分支信息。
結(jié)點的度：一個結(jié)點的子樹個數(shù)稱為此節(jié)點的度。
葉節(jié)點：度為零的節(jié)點。
分支結(jié)點：度不為零的節(jié)點。
結(jié)點的層次：從根結(jié)點開始定義，根結(jié)點的層次為1，跟的直接后繼的層次為2，以此類推。
結(jié)點的層序編號：將樹中的節(jié)點按從上層到下層，同層從左到右的次序排成一個線性序列，依次給它們編以連續(xù)的自然數(shù)。
樹的度：樹中所有節(jié)點的度的最大值。
樹的高度(深度)：樹中所有節(jié)點的層次的最大值。
森林：m(m>=0)棵互不相交的樹的集合。
孩子節(jié)點：一個結(jié)點的直接后繼稱為該節(jié)點的孩子節(jié)點。
雙親結(jié)點：一個結(jié)點的直接前驅(qū)稱為該節(jié)點的雙親結(jié)點。
兄弟結(jié)點：同一雙親結(jié)點的孩子節(jié)點之間互稱兄弟結(jié)點。

二叉樹：

二叉樹的定義：把滿足以下兩個條件的樹形結(jié)構(gòu)叫做二叉樹：
<1> 每個節(jié)點的度都不大于2
<2> 每個節(jié)點的孩子節(jié)點次序不能任一顛倒位于左邊的孩子叫做左孩子，右邊的叫做右孩子。
二叉樹的性質(zhì)：
<1> 在二叉樹的第i層上至多有2的(i-1)次方個節(jié)點(i>=1)。
<2> 深度為k的二叉樹至多有2的k次方減1個節(jié)點(k>=1)。
<3> 對任意一顆二叉樹T，若終端節(jié)點數(shù)為x，而其度數(shù)為2的節(jié)點數(shù)為y，則x=y+1。
滿二叉樹：
深度為k且有2的k次方減1個節(jié)點的二叉樹。
完全二叉樹：
深度為k，節(jié)點數(shù)為n的二叉樹，如果其節(jié)點1到n的位置序號分別與滿二叉樹的節(jié)點1到n的位置序號一一對應(yīng)，則為完全二叉樹。
二叉樹的存儲結(jié)構(gòu)：
<1> 順序存儲。
<2> 鏈?zhǔn)酱鎯?二叉鏈表)：每個節(jié)點至少包括三個域：數(shù)據(jù)域、左孩子域、右孩子域。
二叉樹的遍歷：
<1> 先序遍歷：訪問根結(jié)點---按先序遍歷左子樹---按先序遍歷右子樹。
<2> 中序遍歷：按中序遍歷左子樹---訪問根結(jié)點---按中序遍歷右子樹。
<3> 后序遍歷：按后序遍歷左子樹---按后序遍歷右子樹---訪問根結(jié)點。
<4>深度優(yōu)先遍歷：在深度優(yōu)先級中，我們希望從根結(jié)點訪問最遠(yuǎn)的結(jié)點。
<5>廣度優(yōu)先遍歷：廣度優(yōu)先遍歷會先訪問離根節(jié)點最近的節(jié)點。二叉樹的廣度優(yōu)先遍歷又稱按層次遍歷。算法借助隊列實現(xiàn)。
樹的主要存儲方法：
<1> 雙親表示法
<2> 孩子表示法
<3> 孩子兄弟表示法
將n叉樹轉(zhuǎn)換為二叉樹
一般有序樹可映射為二叉樹，但反之未必成立。
n叉樹轉(zhuǎn)換為二叉樹的方法：二叉樹中結(jié)點x的左子結(jié)點為n叉樹中結(jié)點x的左子結(jié)點；二叉樹中結(jié)點x的右子結(jié)點為n叉樹中結(jié)點x的第一個右邊的同級結(jié)點y。
二叉樹當(dāng)且僅當(dāng)根節(jié)點沒有右子結(jié)點時可轉(zhuǎn)換為n叉樹。
二叉查找樹
二叉排序樹（Binary Sort Tree），又稱二叉查找樹（Binary Search Tree），亦稱二叉搜索樹。二叉排序樹或者是一棵空樹，或者是具有下列性質(zhì)的二叉樹

1. 若左子樹不空，則左子樹上所有結(jié)點的值均小于它的根結(jié)點的值；
2. 若右子樹不空，則右子樹上所有結(jié)點的值均大于它的根結(jié)點的值；
3. 左、右子樹也分別為二叉排序樹；
4. 沒有鍵值相等的節(jié)點。

AVL樹
AVL樹是最先發(fā)明的自平衡二叉查找樹。在AVL樹中任何節(jié)點的兩個子樹的高度最大差別為1，所以它也被稱為高度平衡樹。增加和刪除可能需要通過一次或多次樹旋轉(zhuǎn)來重新平衡這個樹。AVL樹本質(zhì)上還是一棵二叉搜索樹，它的特點是

1. 本身首先是一棵二叉搜索樹。
2. 帶有平衡條件：每個結(jié)點的左右子樹的高度之差的絕對值（平衡因子）最多為1。
   也就是說，AVL樹，本質(zhì)上是帶了平衡功能的二叉查找樹（二叉排序樹，二叉搜索樹）。

紅黑樹
對紅黑樹的操作在最壞的情形下花費O(log N)時間。紅黑樹是具有下列著色性質(zhì)的二叉查找樹：

1. 每一個節(jié)點或者著成紅色，或者著成黑色；
2. 根是黑色的；
3. 如果一個節(jié)點是紅色的，那么他的子節(jié)點必須是黑色的；
4. 從一個節(jié)點到一個nu l l應(yīng)用的每一條路徑必須包含相同數(shù)目的黑色節(jié)點。

9. 堆

堆是一種特別的樹狀數(shù)據(jù)結(jié)構(gòu)。
若是滿足以下特性，即可稱為堆：“給定堆中任意節(jié)點 P 和 C，若 P 是 C 的母節(jié)點，那么 P 的值會小于等于（或大于等于） C 的值”。若母節(jié)點的值恒小于等于子節(jié)點的值，此堆稱為最小堆。反之，若母節(jié)點的值恒大于等于子節(jié)點的值，此堆稱為最大堆。在堆中最頂端的那一個節(jié)點，稱作根節(jié)點，根節(jié)點本身沒有母節(jié)點。

10. 圖

圖的定義：
圖(Graph)是一種網(wǎng)狀數(shù)據(jù)結(jié)構(gòu)，其形式化定義如下：
Graph=(V, R)
V={X | X屬于DataObject}
R={VR}
VR={<x, y> | P(x, y) ^ (x, y屬于V)}
DataObject為一個集合，該集合中所有的元素具有相同的特性。V中的數(shù)據(jù)元素通常稱為頂點，VR是兩個頂點之間的關(guān)系的集合。P(x, y)表示x和y之間有特定的關(guān)聯(lián)屬性P。
若<x, y>屬于VR，則<x, y>表示從頂點x到頂點y的一條弧(arc)，并稱x為弧尾(tail)或起始點，稱y為弧頭(head)或終端店，此時圖中的邊是有方向的，稱這樣的圖為有向圖。
<x, y>屬于VR，必有<y,x>屬于VR，及VR是對稱關(guān)系，這時以無序?qū)?x,y)來代替兩個有序?qū)?表示x和y之間的一條邊(edge)，此時的圖稱為無向圖。
基本術(shù)語：
設(shè)n表示圖中頂點的個數(shù)，用e表示圖中邊或者弧的數(shù)目，并且不考慮圖中每個頂點到自身的邊或弧。對于無向圖而言，其邊數(shù)e的取值范圍是0 ~ n(n-1) / 2，有n(n-1) / 2條邊(圖中每個頂點和其中n-1個頂點都有邊相連)的無向圖為無向完全圖。對于有向圖而言，其邊數(shù)e的取值范圍是0 ~ n(n-1) ，有n(n-1) 條邊(圖中每個頂點和其中n-1個頂點都有弧相連)的有向圖為有向完全圖。對于有很少條邊的圖稱為稀疏圖，反之稱為稠密圖。帶權(quán)的圖稱為網(wǎng)。有向無環(huán)圖(DAG)是指一個無環(huán)的有向圖。
圖的存儲結(jié)構(gòu)：
<1> 鄰接矩陣表示法。
<2> 鄰接表。
<3> 鄰接多重表。
<4> 十字鏈表。
圖的遍歷：
<1> 深度優(yōu)先搜索。
<2> 廣度優(yōu)先搜索。