數據結構是以某種形式將數據組織在一起的集合，它不僅存儲數據，還支持訪問和處理數據的操作。算法是為求解一個問題需要遵循的、被清楚指定的簡單指令的集合。下面是自己整理的常用數據結構與算法相關內容，如有錯誤，歡迎指出。

為了便于描述，文中涉及到的代碼部分都是用Java語言編寫的，其實Java本身對常見的幾種數據結構，線性表、棧、隊列等都提供了較好的實現，就是我們經常用到的Java集合框架，有需要的可以閱讀這篇文章。Java - 集合框架完全解析

一、線性表
1.數組實現
2.鏈表
二、棧與隊列
三、樹與二叉樹
1.樹
2.二叉樹基本概念
3.二叉查找樹
4.平衡二叉樹
5.紅黑樹
四、圖
五、總結
一、線性表

線性表是最常用且最簡單的一種數據結構，它是n個數據元素的有限序列。

實現線性表的方式一般有兩種，一種是使用數組存儲線性表的元素，即用一組連續(xù)的存儲單元依次存儲線性表的數據元素。另一種是使用鏈表存儲線性表的元素，即用一組任意的存儲單元存儲線性表的數據元素（存儲單元可以是連續(xù)的，也可以是不連續(xù)的）。

數組實現

數組是一種大小固定的數據結構，對線性表的所有操作都可以通過數組來實現。雖然數組一旦創(chuàng)建之后，它的大小就無法改變了，但是當數組不能再存儲線性表中的新元素時，我們可以創(chuàng)建一個新的大的數組來替換當前數組。這樣就可以使用數組實現動態(tài)的數據結構。

代碼1 創(chuàng)建一個更大的數組來替換當前數組
int[] oldArray = new int[10];

int[] newArray = new int[20];

for (int i = 0; i < oldArray.length; i++) {
newArray[i] = oldArray[i];
}

// 也可以使用System.arraycopy方法來實現數組間的復制
// System.arraycopy(oldArray, 0, newArray, 0, oldArray.length);

oldArray = newArray;
代碼2 在數組位置index上添加元素e
//oldArray 表示當前存儲元素的數組
//size 表示當前元素個數
public void add(int index, int e) {

if (index > size || index < 0) {
System.out.println("位置不合法...");
}

//如果數組已經滿了 就擴容
if (size >= oldArray.length) {
// 擴容函數可參考代碼1
}

for (int i = size - 1; i >= index; i--) {
oldArray[i + 1] = oldArray[i];
}

//將數組elementData從位置index的所有元素往后移一位
// System.arraycopy(oldArray, index, oldArray, index + 1,size - index);

oldArray[index] = e;

size++;
}
上面簡單寫出了數組實現線性表的兩個典型函數，具體我們可以參考Java里面的ArrayList集合類的源碼。數組實現的線性表優(yōu)點在于可以通過下標來訪問或者修改元素，比較高效，主要缺點在于插入和刪除的花費開銷較大，比如當在第一個位置前插入一個元素，那么首先要把所有的元素往后移動一個位置。為了提高在任意位置添加或者刪除元素的效率，可以采用鏈式結構來實現線性表。

鏈表

鏈表是一種物理存儲單元上非連續(xù)、非順序的存儲結構，數據元素的邏輯順序是通過鏈表中的指針鏈接次序實現的。鏈表由一系列節(jié)點組成，這些節(jié)點不必在內存中相連。每個節(jié)點由數據部分Data和鏈部分Next，Next指向下一個節(jié)點，這樣當添加或者刪除時，只需要改變相關節(jié)點的Next的指向，效率很高。



單鏈表的結構
下面主要用代碼來展示鏈表的一些基本操作，需要注意的是，這里主要是以單鏈表為例，暫時不考慮雙鏈表和循環(huán)鏈表。

代碼3 鏈表的節(jié)點
class Node<E> {

E item;
Node<E> next;

//構造函數
Node(E element) {
this.item = element;
this.next = null;
}
}
代碼4 定義好節(jié)點后，使用前一般是對頭節(jié)點和尾節(jié)點進行初始化
//頭節(jié)點和尾節(jié)點都為空 鏈表為空
Node<E> head = null;
Node<E> tail = null;
代碼5 空鏈表創(chuàng)建一個新節(jié)點
//創(chuàng)建一個新的節(jié)點 并讓head指向此節(jié)點
head = new Node("nodedata1");

//讓尾節(jié)點也指向此節(jié)點
tail = head;
代碼6 鏈表追加一個節(jié)點
//創(chuàng)建新節(jié)點 同時和最后一個節(jié)點連接起來
tail.next = new Node("node1data2");

//尾節(jié)點指向新的節(jié)點
tail = tail.next;
代碼7 順序遍歷鏈表
Node<String> current = head;
while (current != null) {
System.out.println(current.item);
current = current.next;
}
代碼8 倒序遍歷鏈表
static void printListRev(Node<String> head) {
//倒序遍歷鏈表主要用了遞歸的思想
if (head != null) {
printListRev(head.next);
System.out.println(head.item);
}
}
代碼 單鏈表反轉
//單鏈表反轉 主要是逐一改變兩個節(jié)點間的鏈接關系來完成
static Node<String> revList(Node<String> head) {

if (head == null) {
return null;
}

Node<String> nodeResult = null;

Node<String> nodePre = null;
Node<String> current = head;

while (current != null) {

Node<String> nodeNext = current.next;

if (nodeNext == null) {
nodeResult = current;
}

current.next = nodePre;
nodePre = current;
current = nodeNext;
}

return nodeResult;
}
上面的幾段代碼主要展示了鏈表的幾個基本操作，還有很多像獲取指定元素，移除元素等操作大家可以自己完成，寫這些代碼的時候一定要理清節(jié)點之間關系，這樣才不容易出錯。

鏈表的實現還有其它的方式，常見的有循環(huán)單鏈表，雙向鏈表，循環(huán)雙向鏈表。 循環(huán)單鏈表 主要是鏈表的最后一個節(jié)點指向第一個節(jié)點，整體構成一個鏈環(huán)。 雙向鏈表 主要是節(jié)點中包含兩個指針部分，一個指向前驅元，一個指向后繼元，JDK中LinkedList集合類的實現就是雙向鏈表。** 循環(huán)雙向鏈表** 是最后一個節(jié)點指向第一個節(jié)點。

二、棧與隊列

棧和隊列也是比較常見的數據結構，它們是比較特殊的線性表，因為對于棧來說，訪問、插入和刪除元素只能在棧頂進行，對于隊列來說，元素只能從隊列尾插入，從隊列頭訪問和刪除。

棧

棧是限制插入和刪除只能在一個位置上進行的表，該位置是表的末端，叫作棧頂，對棧的基本操作有push(進棧)和pop(出棧)，前者相當于插入，后者相當于刪除最后一個元素。棧有時又叫作LIFO(Last In First Out)表，即后進先出。



棧的模型
下面我們看一道經典題目，加深對棧的理解。



關于棧的一道經典題目
上圖中的答案是C，其中的原理可以好好想一想。

因為棧也是一個表，所以任何實現表的方法都能實現棧。我們打開JDK中的類Stack的源碼，可以看到它就是繼承類Vector的。當然，Stack是Java2前的容器類，現在我們可以使用LinkedList來進行棧的所有操作。

隊列

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



隊列示意圖
我們可以使用鏈表來實現隊列，下面代碼簡單展示了利用LinkedList來實現隊列類。

代碼9 簡單實現隊列類
public class MyQueue<E> {

private LinkedList<E> list = new LinkedList<>();

// 入隊
public void enqueue(E e) {
list.addLast(e);
}

// 出隊
public E dequeue() {
return list.removeFirst();
}
}
普通的隊列是一種先進先出的數據結構，而優(yōu)先隊列中，元素都被賦予優(yōu)先級。當訪問元素的時候，具有最高優(yōu)先級的元素最先被刪除。優(yōu)先隊列在生活中的應用還是比較多的，比如醫(yī)院的急癥室為病人賦予優(yōu)先級，具有最高優(yōu)先級的病人最先得到治療。在Java集合框架中，類PriorityQueue就是優(yōu)先隊列的實現類，具體大家可以去閱讀源碼。

三、樹與二叉樹

樹型結構是一類非常重要的非線性數據結構，其中以樹和二叉樹最為常用。在介紹二叉樹之前，我們先簡單了解一下樹的相關內容。

樹

** 樹 是由n（n>=1）個有限節(jié)點組成一個具有層次關系的集合。它具有以下特點：每個節(jié)點有零個或多個子節(jié)點；沒有父節(jié)點的節(jié)點稱為 根 節(jié)點；每一個非根節(jié)點有且只有一個 父節(jié)點 **；除了根節(jié)點外，每個子節(jié)點可以分為多個不相交的子樹。



樹的結構
二叉樹基本概念

定義
二叉樹是每個節(jié)點最多有兩棵子樹的樹結構。通常子樹被稱作“左子樹”和“右子樹”。二叉樹常被用于實現二叉查找樹和二叉堆。

相關性質
二叉樹的每個結點至多只有2棵子樹(不存在度大于2的結點)，二叉樹的子樹有左右之分，次序不能顛倒。

二叉樹的第i層至多有2(i-1)個結點；深度為k的二叉樹至多有2k-1個結點。

一棵深度為k，且有2^k-1個節(jié)點的二叉樹稱之為** 滿二叉樹 **；

深度為k，有n個節(jié)點的二叉樹，當且僅當其每一個節(jié)點都與深度為k的滿二叉樹中，序號為1至n的節(jié)點對應時，稱之為** 完全二叉樹 **。




三種遍歷方法
在二叉樹的一些應用中，常常要求在樹中查找具有某種特征的節(jié)點，或者對樹中全部節(jié)點進行某種處理，這就涉及到二叉樹的遍歷。二叉樹主要是由3個基本單元組成，根節(jié)點、左子樹和右子樹。如果限定先左后右，那么根據這三個部分遍歷的順序不同，可以分為先序遍歷、中序遍歷和后續(xù)遍歷三種。

(1) 先序遍歷 若二叉樹為空，則空操作，否則先訪問根節(jié)點，再先序遍歷左子樹，最后先序遍歷右子樹。 (2) 中序遍歷 若二叉樹為空，則空操作，否則先中序遍歷左子樹，再訪問根節(jié)點，最后中序遍歷右子樹。(3) 后序遍歷 若二叉樹為空，則空操作，否則先后序遍歷左子樹訪問根節(jié)點，再后序遍歷右子樹，最后訪問根節(jié)點。



給定二叉樹寫出三種遍歷結果
樹和二叉樹的區(qū)別
(1) 二叉樹每個節(jié)點最多有2個子節(jié)點，樹則無限制。 (2) 二叉樹中節(jié)點的子樹分為左子樹和右子樹，即使某節(jié)點只有一棵子樹，也要指明該子樹是左子樹還是右子樹，即二叉樹是有序的。 (3) 樹決不能為空，它至少有一個節(jié)點，而一棵二叉樹可以是空的。

上面我們主要對二叉樹的相關概念進行了介紹，下面我們將從二叉查找樹開始，介紹二叉樹的幾種常見類型，同時將之前的理論部分用代碼實現出來。

二叉查找樹

定義
二叉查找樹就是二叉排序樹，也叫二叉搜索樹。二叉查找樹或者是一棵空樹，或者是具有下列性質的二叉樹： (1) 若左子樹不空，則左子樹上所有結點的值均小于它的根結點的值；(2) 若右子樹不空，則右子樹上所有結點的值均大于它的根結點的值；(3) 左、右子樹也分別為二叉排序樹；(4) 沒有鍵值相等的結點。



典型的二叉查找樹的構建過程
性能分析
對于二叉查找樹來說，當給定值相同但順序不同時，所構建的二叉查找樹形態(tài)是不同的，下面看一個例子。



不同形態(tài)平衡二叉樹的ASL不同
可以看到，含有n個節(jié)點的二叉查找樹的平均查找長度和樹的形態(tài)有關。最壞情況下，當先后插入的關鍵字有序時，構成的二叉查找樹蛻變?yōu)閱沃?，樹的深度為n，其平均查找長度(n+1)/2(和順序查找相同），最好的情況是二叉查找樹的形態(tài)和折半查找的判定樹相同，其平均查找長度和log2(n)成正比。平均情況下，二叉查找樹的平均查找長度和logn是等數量級的，所以為了獲得更好的性能，通常在二叉查找樹的構建過程需要進行“平衡化處理”，之后我們將介紹平衡二叉樹和紅黑樹，這些均可以使查找樹的高度為O(log(n))。

代碼10 二叉樹的節(jié)點

class TreeNode<E> {

E element;
TreeNode<E> left;
TreeNode<E> right;

public TreeNode(E e) {
element = e;
}
}
二叉查找樹的三種遍歷都可以直接用遞歸的方法來實現：

代碼12 先序遍歷
protected void preorder(TreeNode<E> root) {

if (root == null)
return;

System.out.println(root.element + " ");

preorder(root.left);

preorder(root.right);
}
代碼13 中序遍歷
protected void inorder(TreeNode<E> root) {

if (root == null)
return;

inorder(root.left);

System.out.println(root.element + " ");

inorder(root.right);
}
代碼14 后序遍歷
protected void postorder(TreeNode<E> root) {

if (root == null)
return;

postorder(root.left);

postorder(root.right);

System.out.println(root.element + " ");
}
代碼15 二叉查找樹的簡單實現
/**
* @author JackalTsc
*/
public class MyBinSearchTree<E extends Comparable<E>> {

// 根
private TreeNode<E> root;

// 默認構造函數
public MyBinSearchTree() {
}

// 二叉查找樹的搜索
public boolean search(E e) {

TreeNode<E> current = root;

while (current != null) {

if (e.compareTo(current.element) < 0) {
current = current.left;
} else if (e.compareTo(current.element) > 0) {
current = current.right;
} else {
return true;
}
}

return false;
}

// 二叉查找樹的插入
public boolean insert(E e) {

// 如果之前是空二叉樹 插入的元素就作為根節(jié)點
if (root == null) {
root = createNewNode(e);
} else {
// 否則就從根節(jié)點開始遍歷 直到找到合適的父節(jié)點
TreeNode<E> parent = null;
TreeNode<E> current = root;
while (current != null) {
if (e.compareTo(current.element) < 0) {
parent = current;
current = current.left;
} else if (e.compareTo(current.element) > 0) {
parent = current;
current = current.right;
} else {
return false;
}
}
// 插入
if (e.compareTo(parent.element) < 0) {
parent.left = createNewNode(e);
} else {
parent.right = createNewNode(e);
}
}
return true;
}

// 創(chuàng)建新的節(jié)點
protected TreeNode<E> createNewNode(E e) {
return new TreeNode(e);
}

}

// 二叉樹的節(jié)點
class TreeNode<E extends Comparable<E>> {

E element;
TreeNode<E> left;
TreeNode<E> right;

public TreeNode(E e) {
element = e;
}
}

上面的代碼15主要展示了一個自己實現的簡單的二叉查找樹，其中包括了幾個常見的操作，當然更多的操作還是需要大家自己去完成。因為在二叉查找樹中刪除節(jié)點的操作比較復雜，所以下面我詳細介紹一下這里。

二叉查找樹中刪除節(jié)點分析
要在二叉查找樹中刪除一個元素，首先需要定位包含該元素的節(jié)點，以及它的父節(jié)點。假設current指向二叉查找樹中包含該元素的節(jié)點，而parent指向current節(jié)點的父節(jié)點，current節(jié)點可能是parent節(jié)點的左孩子，也可能是右孩子。這里需要考慮兩種情況：

current節(jié)點沒有左孩子，那么只需要將patent節(jié)點和current節(jié)點的右孩子相連。
current節(jié)點有一個左孩子，假設rightMost指向包含current節(jié)點的左子樹中最大元素的節(jié)點，而parentOfRightMost指向rightMost節(jié)點的父節(jié)點。那么先使用rightMost節(jié)點中的元素值替換current節(jié)點中的元素值，將parentOfRightMost節(jié)點和rightMost節(jié)點的左孩子相連，然后刪除rightMost節(jié)點。
// 二叉搜索樹刪除節(jié)點
public boolean delete(E e) {

TreeNode<E> parent = null;
TreeNode<E> current = root;

// 找到要刪除的節(jié)點的位置
while (current != null) {
if (e.compareTo(current.element) < 0) {
parent = current;
current = current.left;
} else if (e.compareTo(current.element) > 0) {
parent = current;
current = current.right;
} else {
break;
}
}

// 沒找到要刪除的節(jié)點
if (current == null) {
return false;
}

// 考慮第一種情況
if (current.left == null) {
if (parent == null) {
root = current.right;
} else {
if (e.compareTo(parent.element) < 0) {
parent.left = current.right;
} else {
parent.right = current.right;
}
}
} else { // 考慮第二種情況
TreeNode<E> parentOfRightMost = current;
TreeNode<E> rightMost = current.left;
// 找到左子樹中最大的元素節(jié)點
while (rightMost.right != null) {
parentOfRightMost = rightMost;
rightMost = rightMost.right;
}

// 替換
current.element = rightMost.element;

// parentOfRightMost和rightMost左孩子相連
if (parentOfRightMost.right == rightMost) {
parentOfRightMost.right = rightMost.left;
} else {
parentOfRightMost.left = rightMost.left;
}
}

return true;
}
平衡二叉樹

平衡二叉樹又稱AVL樹，它或者是一棵空樹，或者是具有下列性質的二叉樹：它的左子樹和右子樹都是平衡二叉樹，且左子樹和右子樹的深度之差的絕對值不超過1。



平衡二叉樹
AVL樹是最先發(fā)明的自平衡二叉查找樹算法。在AVL中任何節(jié)點的兩個兒子子樹的高度最大差別為1，所以它也被稱為高度平衡樹，n個結點的AVL樹最大深度約1.44log2n。查找、插入和刪除在平均和最壞情況下都是O（log n）。增加和刪除可能需要通過一次或多次樹旋轉來重新平衡這個樹。

紅黑樹

紅黑樹是平衡二叉樹的一種，它保證在最壞情況下基本動態(tài)集合操作的事件復雜度為O(log n)。紅黑樹和平衡二叉樹區(qū)別如下：(1) 紅黑樹放棄了追求完全平衡，追求大致平衡，在與平衡二叉樹的時間復雜度相差不大的情況下，保證每次插入最多只需要三次旋轉就能達到平衡，實現起來也更為簡單。(2) 平衡二叉樹追求絕對平衡，條件比較苛刻，實現起來比較麻煩，每次插入新節(jié)點之后需要旋轉的次數不能預知。點擊查看更多

四、圖

簡介
圖是一種較線性表和樹更為復雜的數據結構，在線性表中，數據元素之間僅有線性關系，在樹形結構中，數據元素之間有著明顯的層次關系，而在圖形結構中，節(jié)點之間的關系可以是任意的，圖中任意兩個數據元素之間都可能相關。圖的應用相當廣泛，特別是近年來的迅速發(fā)展，已經滲入到諸如語言學、邏輯學、物理、化學、電訊工程、計算機科學以及數學的其他分支中。

相關閱讀
因為圖這部分的內容還是比較多的，這里就不詳細介紹了，有需要的可以自己搜索相關資料。

(1) 《百度百科對圖的介紹》
(2) 《數據結構之圖（存儲結構、遍歷）》

五、總結

到這里，關于常見的數據結構的整理就結束了，斷斷續(xù)續(xù)大概花了兩天時間寫完，在總結的過程中，通過查閱相關資料，結合書本內容，收獲還是很大的，在下一篇博客中將會介紹常用數據結構與算法整理總結（下）之算法篇，歡迎大家關注。