程式員必備：8種通用資料結構（總結）

最近複習面試題一些技術，發現許多都牽扯到這幾種資料結構。是以了解它們是必不可少的，這裡做一個學習總結的筆記分享一下。

···································································

數組

數組（Array）是一種 線性表 資料結構，它用一組 連續的記憶體空間 存儲一組具有 相同類型 的資料。

線性表

線性表就是資料排列成一條先一樣的結構，每個線性表上的資料最多隻有前和後兩個方向。

連續的記憶體空間和相同類型的資料類型

因為這兩個限制，數組才能可以随機通路。但是同時資料組的删除和插入等操作變的低效，需要保證連續性而做的大量的資料搬移工作。

數組的應用

用作建構其他資料結構的基礎，例如數組清單，堆，哈希表，向量和矩陣。

用于不同的排序算法，例如插入排序，快速排序，冒泡排序和合并排序。

詳細參考：資料結構之數組

···································································

連結清單

連結清單是一種順序結構，由互相連結的線性順序項目序列組成。還是實體存儲結構上非連續、非順序的存儲結構。

連結清單主要有：

1、無頭單向非循環連結清單

2、帶頭循環單連結清單

3、不帶頭雙向循環連結清單

連結清單的特性

1. 連結清單中的元素稱為節點。
2. 每個節點都包含一個密鑰和一個指向其後繼節點(稱為next)的指針。
3. 名為head的屬性指向連結清單的第一個元素。
4. 連結清單的最後一個元素稱為尾。

   

連結清單實作

public class Node {
        public int value;  
        public Node next;  
        
        Node(int value) {
            this.value = value;
            this.next = null;
        }
    }

    private Node head;  

    MyLinkedList() {
        this.head = null;
    }

           

連結清單的應用

用于編譯器設計中的符号表管理。

用于在使用Alt Tab(使用循環連結清單實作)的程式之間進行切換。

詳情參考：資料結構之連結清單

···································································

棧

棧是一種實體結構，它存儲了一組線性元素，這組元素在操作上有後進先出的特性。另外堆棧隻能在一端(稱為棧頂(top))對資料項進行插入和删除。

ps:新手可能可能困惑堆棧和棧有啥差別？其實沒啥差別…

堆是堆（heap），棧是棧（stack），堆棧是棧。“堆棧”這種叫法，容易讓新人掉坑裡。

棧的兩個基本操作：入棧（push） 出棧（pop）

棧的實作

public class myStack{
	private Object[] arr;
	private int top;

	//無參構造方法
	public myStack(){
		this.arr = new Object[10];
		this.top = -1;
	}
	//有參構造方法
	public myStack(int maxSize){
		this.arr = new Object[maxSize];
		this.top = -1;
	}

	//入棧
	public void push(Object v){
		arr[++top] = v;
	}
	//出棧
	public Object pop(){
		return arr[top--];
	}
	//檢視棧頂元素
	public Object peek(){
		return arr[top];
	}
	//判斷棧是否為空
	public boolean isEmpty(){
		return (top == -1);
	}
	
}
           

棧的應用

用于表達式評估(例如：用于解析和評估數學表達式的調車場算法)。

用于在遞歸程式設計中實作函數調用。

隊列

棧介紹完畢之後，肯定與之相對的 隊列。像棧一樣，隊列也是一種線性表。它允許在表的一端插入資料，在另一端删除元素。插入元素的這一端稱之為隊尾。删除元素的這一端我們稱之為隊首。

)

圖上描述了隊列入隊和出隊的方式；

隊列的實作

public class myQueue{
	private Object[] arr;//存放隊列元素的數組
    private int elements;//隊列元素數量
    private int front;//隊頭元素在數組中的索引
    private int rear;//隊尾元素在數組中的索引

	//無參構造方法
	public myQueue(){
		arr = new Object[10];
		elements = 0;
		front = 0;
		rear = -1;
		
	}
	//有參構造方法
	public myQueue(int maxSize){
		arr = new Object[maxSize];
		elements = 0;
		front = 0;
		rear = -1;
	}
	//判斷隊列是否滿了
	public boolean isFull(){
		return (elements == arr.length);
	}
	//判斷隊列是否為空
	public boolean isEmpty(){
		return (elements==0);
	}
	//檢視隊首元素
	public Object peek() {
    	return arr[front];
	}
	
}
           

隊列的插入我們需要考慮一下幾種情況。

1.隊列已經填充滿了

2.因為隊列在數組中是連續的，如果隊列的元素在數組中最後，需要将元素從隊首到隊尾移到數組中第一位，也就是将後面的位置空出來(參考下圖)。

//插入資料到隊尾
	public void enQueue(Object v){
		//判斷隊列是否滿了
		if(isFull()) {
			System.out.printf("隊列已滿無法插入")
		}
		//判斷隊列是否元素在最後位置
		if(elements > 1&& rear == arr.length -1){
			for(int i =0;i < elements;i++,front++){
				arr[i]=arr[front];
			}
			front=0;
			rear = elements-1;
		}
		//其他情況正常插入
		arr[rear++]=v;
		elements++;
	}
           

隊列的移除我們需要考慮一下幾種情況。

1.隊列是空隊列

2.隊列僅剩一個元素

public Object deQueue(){
	if(isEmpty()){
		return null;
	}
	Obeject value = arr[front++];
	if(elements == 1){
		front=0;
		rear=-1;
		elements=0;
	}else{
		elements --;
	}
	return value;
}
           

隊列的特性

在隊尾插入元素，在隊首删除元素。

FIFO（先進先出），就向排隊取票一樣。

參考部落格：資料結構：隊列的原理和實作

哈希表

哈希表就是根據一個函數H，根據這個函數和查找關鍵字key，可以直接确定查找值所在位置。

函數H就是哈希函數，它根據key計算出應該存儲位址的位置，而哈希表是基于哈希函數建立的一種查找表。

一張圖讓你更加直覺的了解哈希表

哈希表的應用

用于實作資料庫索引。

用于實作關聯數組。

用于實作"設定"資料結構。

要想建立一個哈希表，還需要考慮哈希函數的選取，以及遇到哈希沖突的解決方式。關于哈希函數構造以及哈希沖突的解決大家可以參考下方連結的部落格。

資料結構 Hash表（哈希表）

樹

樹是一種層次結構，其中資料按層次進行組織并連結在一起。此結構與連結清單不同，而在連結清單中，項目以線性順序連結。

在過去的幾十年中，已經開發出各種類型的樹木，以适合某些應用并滿足某些限制。一些示例是二叉搜尋樹，B樹，紅黑樹，展開樹，AVL樹和n元樹。

這裡我就隻大概介紹二叉樹

每個節點最多含有兩個子樹的樹稱為二叉樹。（我們一般在書中試題中見到的樹是二叉樹，但并不意味着所有的樹都是二叉樹。）

在二叉樹的概念下又衍生出滿二叉樹和完全二叉樹的概念

滿二叉樹：除最後一層無任何子節點外，每一層上的所有結點都有兩個子結點。也可以這樣了解，除葉子結點外的所有結點均有兩個子結點。節點數達到最大值，所有葉子結點必須在同一層上

完全二叉樹：若設二叉樹的深度為h，除第 h 層外，其它各層 (1～(h-1)層) 的結點數都達到最大個數，第h層所有的結點都連續集中在最左邊，這就是完全二叉樹。

二叉樹的實作（簡易版）

private static class TreeNode{
	int val;
	TreeNode left;
	TreeNode right;
	
	TreeNode(int x){
		val = x;
	}
} 
           

二叉樹的周遊

先序周遊：先根節點->周遊左子樹->周遊右子樹

中序周遊：周遊左子樹->根節點->周遊右子樹

後序周遊：周遊左子樹->周遊右子樹->根節點

樹的應用

二叉樹：用于實作表達式解析器和表達式求解器。

二進制搜尋樹：用于許多不斷輸入和輸出資料的搜尋應用程式中。

堆：由JVM(Java虛拟機)用來存儲Java對象。

Trap：用于無線網絡

詳細參考部落格：資料結構之樹

堆

堆是二叉樹的一種特殊情況，其中将父節點與其子節點的值進行比較，并對其進行相應排列。

堆分為兩種：最大堆和最小堆，兩者的差别在于節點的排序方式。

堆的實作（最大堆）

//因為堆中元素需要比較，是以泛型E實作Comparable接口
public class maxHeap <E extends  Comparable<E>>{
	private Array<E> value;
	
	public maxHeap(){
		value = new Array<E>();
	}
    //size是數組的初始化大小
	public maxHeap(int size){
		value = new Array<E>(size);
	}
	//獲得堆中的元素個數
    public int getSize() {
        return data.getSize();
    }
    //判斷堆中是否為空
    public boolean isEmpty() {
        return data.isEmpty();
    }
}

           

一個數組實作堆，不使用指針的情況下怎麼判斷父節點和子節點呢？

其實節點在數組中的位置index 和它的父節點以及子節點的索引之間有一個映射關系。

如果i是節點的索引，那麼下列公式就能計算出該節點的父節點以及左右子節點。

public int parent（int i）{
	if(i == 0){
		throw new IllegalArgumentException("該節點為根節點");
	}
	return (i-1)/2;
}
public int leftChild（int i）{
	return 2*i+1;
}
public int rightChild（int i）{
	return 2*i+2;
}
           

還有堆得上浮下沉删除，插入等操作就不一一總結了。

堆的應用

可以實作優先級隊列，以為能通過堆屬性進行優先級排序

可以在o(log n)時間實作隊列功能。

用于查找定數組中k個最小（或最大）的值

用于堆排序算法

詳細參考部落格：資料結構：堆（Heap）

圖

圖是由頂點以及連接配接各個頂點之間的邊組成的一種資料結構。

圖分為有向圖和無向圖

圖的存儲結構：鄰接矩陣，鄰接表，十字連結清單

圖的實作（鄰接矩陣）

public class Graph{
	private ArrayList<String> vertexList;//儲存頂點集合
	private int[][] edges;//儲存鄰接矩陣
	private int numOfEdges;//邊的數量

	//顯示矩陣
	public void show(){
		for(int[] link:edges){
			Syste.out.println(Arrays.toString(link));
		}
	}
	
	//得到邊數
	public int getNumOfEdges(){
		return this.numOfEdges;
	}
	
	//傳回節點對應的資料 0 ->"A" 1->"B" 2->"C"
    public String getValueByIndex(int i){
        return vertexList.get(i);
    }
	//初始化
	public Graph(int n){
		edges = new int[n][n];
		vertexList = new ArrayList<String>(n);
		numOfEdges = 0;
	}
	//插入頂點
	public void insertVertex(String vertex){
		vertexList.add(vertex);
	}
	//添加邊
	public void insertEdge(int v1.int v2 ,int weight){
			edges[v1][v2]  = weight;
			edges[v2][v1]  = weight;
			numOfEdges++;
	}
}
           

圖的周遊

圖的周遊分為深度優先周遊和廣度優先周遊。

圖的應用

用于表示社交媒體網絡。每個使用者都是一個頂點，并且在使用者連接配接時會建立一條邊。

用于表示搜尋引擎的網頁和連結。網際網路上的網頁通過超連結互相連結。每頁是一個頂點，兩頁之間的超連結是一條邊。用于Google中的頁面排名。

用于表示GPS中的位置和路線。位置是頂點，連接配接位置的路線是邊。用于計算兩個位置之間的最短路徑。

詳細參考：資料結構之圖