這篇文章給大家分享的是有關(guān)Java數(shù)據(jù)結(jié)構(gòu)與算法的示例分析的內(nèi)容。小編覺得挺實用的，因此分享給大家做個參考，一起跟隨小編過來看看吧。

十載的庫爾勒網(wǎng)站建設(shè)經(jīng)驗，針對設(shè)計、前端、開發(fā)、售后、文案、推廣等六對一服務(wù)，響應(yīng)快，48小時及時工作處理。成都營銷網(wǎng)站建設(shè)的優(yōu)勢是能夠根據(jù)用戶設(shè)備顯示端的尺寸不同，自動調(diào)整庫爾勒建站的顯示方式，使網(wǎng)站能夠適用不同顯示終端，在瀏覽器中調(diào)整網(wǎng)站的寬度，無論在任何一種瀏覽器上瀏覽網(wǎng)站，都能展現(xiàn)優(yōu)雅布局與設(shè)計，從而大程度地提升瀏覽體驗。創(chuàng)新互聯(lián)從事“庫爾勒網(wǎng)站設(shè)計”,“庫爾勒網(wǎng)站推廣”以來，每個客戶項目都認(rèn)真落實執(zhí)行。

第1章 數(shù)據(jù)結(jié)構(gòu)與算法基礎(chǔ)概述

1.1 數(shù)據(jù)結(jié)構(gòu)和算法的重要性

• 算法是程序的靈魂，優(yōu)秀的程序可以在海量數(shù)據(jù)計算時，依然保持高速計算

• 數(shù)據(jù)結(jié)構(gòu)和算法的關(guān)系：

• 程序 = 數(shù)據(jù)結(jié)構(gòu) + 算法

• 數(shù)據(jù)結(jié)構(gòu)是算法的基礎(chǔ), 換言之，想要學(xué)好算法，需要把數(shù)據(jù)結(jié)構(gòu)學(xué)到位。

• 數(shù)據(jù)結(jié)構(gòu)和算法學(xué)習(xí)大綱
  

1.2 數(shù)據(jù)結(jié)構(gòu)概述

• 數(shù)據(jù)結(jié)構(gòu)可以簡單的理解為數(shù)據(jù)與數(shù)據(jù)之間所存在的一些關(guān)系，數(shù)據(jù)的結(jié)構(gòu)分為數(shù)據(jù)的存儲結(jié)構(gòu)和數(shù)據(jù)的邏輯結(jié)構(gòu)。

邏輯結(jié)構(gòu)

• 集合結(jié)構(gòu)：數(shù)據(jù)元素同屬于一個集合，他們之間是并列關(guān)系，無其他的關(guān)系；可以理解為中學(xué)時期學(xué)習(xí)的集合，在一個范圍之內(nèi)，有很多的元素，元素間沒有什么關(guān)系

• 線性結(jié)構(gòu)：元素之間存在著一對一的關(guān)系；可以理解為每個學(xué)生對應(yīng)著一個學(xué)號，學(xué)號與姓名就是線性結(jié)構(gòu)

• 樹形結(jié)構(gòu)：元素之間存在著一對多的關(guān)系，可以簡單理解為家庭族譜一樣，一代接一代

• 圖形結(jié)構(gòu)：元素之間存在多對多的關(guān)系，每一個元素可能對應(yīng)著多個元素，或被多個元素對應(yīng)，網(wǎng)狀圖

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

• 順序存儲結(jié)構(gòu)：就是將數(shù)據(jù)進(jìn)行連續(xù)的存儲，我們可以將它比喻成學(xué)校食堂打飯排隊一樣，一個接著一個；

• 鏈?zhǔn)酱鎯Y(jié)構(gòu)：不是按照順序存儲的，后一個進(jìn)來的數(shù)只需要將他的地址告訴前一個節(jié)點，前一個節(jié)點中就存放了它后面那個數(shù)的地址，所以最后一個數(shù)的存儲地址就是為null；可以將這種結(jié)構(gòu)比喻成商場吃飯叫號，上面的號碼比喻成是地址，你可以之后后面的地址是什么，上面的其他內(nèi)容就是該節(jié)點的內(nèi)容；

• 區(qū)別：

• 順序存儲的特點是查詢快，插入或者刪除慢

• 鏈?zhǔn)酱鎯Φ奶攸c是查詢慢，插入或者刪除快

1.3 算法概述

• 同一問題不同解決方法

• 通過時間和空間復(fù)雜度判斷算法的優(yōu)劣

• 算法沒有最好的，只有最合適的，學(xué)習(xí)算法是為了積累學(xué)習(xí)思路，掌握學(xué)習(xí)思路，并不是為了解決某問題去記住某種算法；對于時間復(fù)雜度與空間復(fù)雜度，現(xiàn)在大多數(shù)開發(fā)情況下，我們都在使用以空間換時間，耗費更多的內(nèi)存，來保證擁有更快的速度。

• 各排序算法復(fù)雜度及穩(wěn)定性：
  

如何理解“大O記法”

對于算法進(jìn)行特別具體的細(xì)致分析雖然很好，但在實踐中的實際價值有限。對于算法的時間性質(zhì)和空間性質(zhì)，最重要的是其數(shù)量級和趨勢，這些是分析算法效率的主要部分。而計量算法基本操作數(shù)量的規(guī)模函數(shù)中那些常量因子可以忽略不計。例如，可以認(rèn)為 3n^2 和 100n^2 屬于同一個量級，如果兩個算法處理同樣規(guī)模實例的代價分別為這兩個函數(shù)，就認(rèn)為它們的效率“差不多”，都為n^2級。

時間復(fù)雜度

一個算法花費的時間與算法中語句的執(zhí)行次數(shù)成正比例，哪個算法中語句執(zhí)行次數(shù)多,它花費時間就多。算法中的語句執(zhí)行次數(shù)稱為語句頻度或時間頻度,記為T(n)。n 稱為問題的規(guī)模，當(dāng) n 不斷變化時，時間頻度T(n)也會不斷變化。但有時我們想知道它變化時呈現(xiàn)什么規(guī)律。為此，我們引入時間復(fù)雜度概念。

一般情況下，算法中基本操作重復(fù)執(zhí)行的次數(shù)是問題規(guī)模 n 的某個函數(shù),用T(n)表示，若有某個輔助函數(shù)f(n)，使得當(dāng) n 趨近于無究大時，T(n)/f(n)的極限值為不等于零的常數(shù)，則稱f(n)是T(n)的同數(shù)量級函數(shù)。記作T(n)=O(f(n))，稱O(f(n))為算法的漸進(jìn)時間復(fù)雜度，簡稱時間復(fù)雜度。

有時候，算法中基本操作重復(fù)執(zhí)行的次數(shù)還隨問題的輸入數(shù)據(jù)集不同而不同,如在冒泡排序中，輸入數(shù)據(jù)有序而無序，結(jié)果是不一樣的。此時，我們計算平均值。

時間復(fù)雜度基本計算規(guī)則：

• 基本操作，即只有常數(shù)項，認(rèn)為其時間復(fù)雜度為O(1)

• 順序結(jié)構(gòu)，時間復(fù)雜度按加法進(jìn)行計算

• 循環(huán)結(jié)構(gòu)，時間復(fù)雜度按乘法進(jìn)行計算

• 分支結(jié)構(gòu)，時間復(fù)雜度取最大值

• 判斷一個算法的效率時，往往只需要關(guān)注操作數(shù)量的最高次項，其它次要項和常數(shù)項可以忽略

• 在沒有特殊說明時，我們所分析的算法的時間復(fù)雜度都是指最壞時間復(fù)雜度

常用時間復(fù)雜度：

• 注意：經(jīng)常將log2n（以2為底的對數(shù)）簡寫成logn

常見時間復(fù)雜度之間的關(guān)系：

• 所以時間消耗由小到大為：O(1) < O(log n) < O(n) < O(nlog n) < O(n^2) < O(2^n) < O(n!) < O(n^n)

案例1：

count = 0;				      (1)
	for(i = 0;i <= n;i++)	  (2)
		for(j = 0;j <= n;j++) (3)
			count++;          (4)

• 語句（1）執(zhí)行1次

• 語句（2）執(zhí)行n次

• 語句（3）執(zhí)行n^2次

• 語句（4）執(zhí)行n^2次

• 時間復(fù)雜度為：T(n) = 1+n+n^2+n^2 = O(n^2)

案例2：

a = 1; 						(1)
b = 2;						(2)
for(int i = 1;i <= n;i++) { (3)
	int s = a + b;			(4)
	b = a;					(5)
	a = s;					(6)
}	

• 語句（1）、（2）執(zhí)行1次

• 語句（3）執(zhí)行n次

• 語句（4）、（5）、（6）執(zhí)行n次

• 時間復(fù)雜度為：T(n) = 1+1+4n = o(n)

案例3：

i = 1;		 (1)while(i<n) {
	i = i*2; (2)}

• 語句（1）的頻度是1

• 設(shè)語句（2）的頻度是f(n)，則2f(n)<=n;f(n)<=log2n,取最大值f(n) = log2n

• 時間復(fù)雜度為：T(n) = O(log2n)

空間復(fù)雜度

• 算法的空間復(fù)雜度計算公式：S(n) = 0( f(n) )，其中 n 為輸入規(guī)模，f(n)為語句關(guān)于 n 所占存儲空間的函數(shù)

• 一個算法在計算機存儲器上所占用的存儲空間，包括三個方面

• 存儲算法本身所占用的存儲空間

• 算法的輸入輸出數(shù)據(jù)所占用的存儲空間

• 算法在運行過程中臨時占用的存儲空間

案例：指定的數(shù)組進(jìn)行反轉(zhuǎn)，并返回反轉(zhuǎn)的內(nèi)容

解法一：

public static int[] reverse1(int[] arr) {
    int n = arr.length; //申請4個字節(jié)
    int temp; //申請4個字節(jié)
    for (int start = 0, end = n - 1; start <= end; start++, end--) {
        temp = arr[start];
        arr[start] = arr[end];
        arr[end] = temp;
    }
    return arr;}

• 空間復(fù)雜度為：S(n) = 4+4 = O(8) = O(1)

解法二：

public static int[] reverse2(int[] arr) {
    int n = arr.length; //申請4個字節(jié)
    int[] temp = new int[n]; //申請n*4個字節(jié)+數(shù)組自身頭信息開銷24個字節(jié)
    for (int i = n - 1; i >= 0; i--) {
        temp[n - 1 - i] = arr[i];
    }
    return temp;}

• 空間復(fù)雜度為：S(n) = 4+4n+24 = O(n+28) = O(n)

根據(jù)大O推導(dǎo)法則，算法一的空間復(fù)雜度為0(1),算法二的空間復(fù)雜度為0(n)，所以從空間占用的角度講，算法一要優(yōu)于算法二。

由于java中有內(nèi)存垃圾回收機制，并且jvm對程序的內(nèi)存占用也有優(yōu)化(例如即時編譯) , 我們無法精確的評估一個java程序的內(nèi)存占用情況，但是了解了java的基本內(nèi)存占用，使我們可以對java程序的內(nèi)存占用情況進(jìn)行估算。

由于現(xiàn)在的計算機設(shè)備內(nèi)存一般都比較大，基本上個人計算機都是4G起步，大的可以達(dá)到32G ，所以內(nèi)存占用一般情況下并不是我們算法的瓶頸，普通情況下直接說復(fù)雜度，默認(rèn)為算法的時間復(fù)雜度。

但是，如果你做的程序是嵌入式開發(fā)，尤其是一些傳感器設(shè)備上的內(nèi)置程序,由于這些設(shè)備的內(nèi)存很小, 一般為幾kb，這個時候?qū)λ惴ǖ目臻g復(fù)雜度就有要求了，但是一般做java開發(fā)的，基本上都是服務(wù)器開發(fā), 一般不存在這樣的問題。

第2章 數(shù)組

2.1 數(shù)組概念

數(shù)組是一種線性表數(shù)據(jù)結(jié)構(gòu)，它用一組連續(xù)的內(nèi)存空間，來存儲一組具有相同類型的數(shù)據(jù)。這里我們要抽取出三個跟數(shù)組相關(guān)的關(guān)鍵詞：線性表，連續(xù)內(nèi)存空間，相同數(shù)據(jù)類型；數(shù)組具有連續(xù)的內(nèi)存空間，存儲相同類型的數(shù)據(jù)，正是該特性使得數(shù)組具有一個特性：隨機訪問。但是有利有弊，這個特性雖然使得訪問數(shù)組邊得非常容易，但是也使得數(shù)組插入和刪除操作會變得很低效，插入和刪除數(shù)據(jù)后為了保證連續(xù)性,要做很多數(shù)據(jù)搬遷工作。

查找數(shù)組中的方法有兩種：

• 線性查找：線性查找就是簡單的查找數(shù)組中的元素

• 二分法查找：二分法查找要求目標(biāo)數(shù)組必須是有序的。

2.2 無序數(shù)組

• 實現(xiàn)類：

public class MyArray {
	//聲明一個數(shù)組
	private long[] arr;
	
	//有效數(shù)據(jù)的長度
	private int elements;
	
	//無參構(gòu)造函數(shù)，默認(rèn)長度為50
	public MyArray(){
		arr = new long[50];
	}
	
	public MyArray(int maxsize){
		arr = new long[maxsize];
	}
	
	
	//添加數(shù)據(jù)
	public void insert(long value){
		arr[elements] = value;
		elements++;
	}
	
	//顯示數(shù)據(jù)
	public void display(){
		System.out.print("[");
		for(int i = 0;i < elements;i++){
			System.out.print(arr[i] + " ");
		}
		System.out.println("]");
	}
	
	//根據(jù)下標(biāo)查找數(shù)據(jù)
	public long get(int index){
		if(index >= elements || index < 0){
			throw new ArrayIndexOutOfBoundsException();
		}else{
			return arr[index];
		}
	}
	
	/**
	 * 根據(jù)值查詢
	 * @param value 需要被查詢的值
	 * @return 被查詢值的下標(biāo)
	 */
	public int search(int value){
		//聲明一個變量i用來記錄該數(shù)據(jù)的下標(biāo)值
		int i ;
		for(i = 0;i < elements;i++){
			if(value == arr[i]){
				break;
			}
		}
		//如果查詢到最后一個元素依然沒有找到
		if(i == elements){
			return -1;
		}else{
			return i;
		}
	}
	
	//根據(jù)下標(biāo)刪除數(shù)據(jù)
	public void delete(int index){
		if(index >= elements || index < 0){
			throw new ArrayIndexOutOfBoundsException();
		}else{
			//刪除該元素后，后面所有元素前移一位
			for(int i = index; i < elements;i++){
				arr[i] = arr[i+1];
			}
			elements--;
		}
		
	}
	/**
	 * 替換數(shù)據(jù)
	 * @param index 被替換的下標(biāo)
	 * @param newvalue 新的數(shù)據(jù)
	 */
	public void change(int index,int newvalue){
		if(index >= elements || index < 0){
			throw new ArrayIndexOutOfBoundsException();
		}else{
			arr[index] = newvalue;
		}
	} }

• 優(yōu)點：插入快（時間復(fù)雜度為：O(1)）、如果知道下標(biāo)，可以很快存儲

• 缺點：查詢慢（時間復(fù)雜度為：O(n)）、刪除慢

2.3 有序數(shù)組

• 實現(xiàn)類：

public class MyOrderArray { 
	private long[] arr;
	
	private int elements;
	
	public MyOrderArray(){
		arr = new long[50];
	}
	
	public MyOrderArray(int maxsize){
		arr = new long[maxsize];
	}
	
	//添加數(shù)據(jù)
	public void insert(int value){
		int i;
		for(i = 0;i < elements;i++){
			if(arr[i] > value){
				break;
			}
		}
		for(int j = elements;j > i;j--){
			arr[j] = arr[j -1];
		}
		arr[i] = value;
		elements++;
	}
	
	
	//刪除數(shù)據(jù)
	public void delete(int index){
		if(index >=elements || index <0){
			throw new ArrayIndexOutOfBoundsException();
		}else{
			for(int i = index;i < elements; i++){
				arr[i] = arr[i+1];
			}
			elements--;
		}
	}
	
	//修改數(shù)據(jù)
	public void change(int index,int value){
		if(index >= elements || index < 0){
			throw new IndexOutOfBoundsException();
		}else{
			arr[index] = value;
		}
	}
	
	//根據(jù)下標(biāo)查詢數(shù)據(jù)
	public long get(int index){
		if(index >= elements || index < 0){
			throw new IndexOutOfBoundsException();
		}else{
			return arr[index];
		}
	}
	
	//展示數(shù)據(jù)
	public void display(){
		System.out.print("[");
		for(int i = 0; i < elements;i++){
			System.out.print(arr[i] + " ");
		}
		System.out.println("]");
	}
	
	
	//二分法查找數(shù)據(jù)
	public int binarySearch(long value){
			//聲明三個指針分別指向數(shù)組的頭，尾，中間
			int low = 0;
			int pow = elements;
			int middle = 0;
			
			while(true){
				middle = (low + pow) / 2;
				//如果中指針?biāo)傅闹档扔趲Р樵償?shù)
				if(arr[middle] == value){
					return middle;
				}else if(low > pow){
					return -1;
				}else{
					if(arr[middle] > value){
						//待查詢的數(shù)在左邊,右指針重新改變指向
						pow = middle-1;
					}else{
						//帶查詢的數(shù)在右邊，左指針重新改變指向
						low = middle +1;
					}
				}
			}
	}}

• 優(yōu)點：查詢快（時間復(fù)雜度為：O(logn)）

• 缺點：增刪慢（時間復(fù)雜度為：O(n)）

第三章 棧

3.1 棧概念

棧（stack），有些地方稱為堆棧，是一種容器，可存入數(shù)據(jù)元素、訪問元素、刪除元素，它的特點在于只能允許在容器的一端（稱為棧頂端指標(biāo)，英語：top）進(jìn)行加入數(shù)據(jù)（英語：push）和輸出數(shù)據(jù)（英語：pop）的運算。沒有了位置概念，保證任何時候可以訪問、刪除的元素都是此前最后存入的那個元素，確定了一種默認(rèn)的訪問順序。

由于棧數(shù)據(jù)結(jié)構(gòu)只允許在一端進(jìn)行操作，因而按照后進(jìn)先出的原理運作。

?？梢杂庙樞虮韺崿F(xiàn)，也可以用鏈表實現(xiàn)。

3.2 棧的操作

• Stack() 創(chuàng)建一個新的空棧

• push(element) 添加一個新的元素element到棧頂

• pop() 取出棧頂元素

• peek() 返回棧頂元素

• is_empty() 判斷棧是否為空

• size() 返回棧的元素個數(shù)

實現(xiàn)類：

package mystack;public class MyStack {

    //棧的底層使用數(shù)組來存儲數(shù)據(jù)
    //private int[] elements;
    int[] elements; //測試時使用

    public MyStack() {
        elements = new int[0];
    }

    //添加元素
    public void push(int element) {
        //創(chuàng)建一個新的數(shù)組
        int[] newArr = new int[elements.length + 1];
        //把原數(shù)組中的元素復(fù)制到新數(shù)組中
        for (int i = 0; i < elements.length; i++) {
            newArr[i] = elements[i];
        }
        //把添加的元素放入新數(shù)組中
        newArr[elements.length] = element;
        //使用新數(shù)組替換舊數(shù)組
        elements = newArr;
    }

    //取出棧頂元素
    public int pop() {
        //當(dāng)棧中沒有元素
        if (is_empty()) {
            throw new RuntimeException("?？?quot;);
        }
        //取出數(shù)組的最后一個元素
        int element = elements[elements.length - 1];
        //創(chuàng)建一個新數(shù)組
        int[] newArr = new int[elements.length - 1];
        //原數(shù)組中除了最后一個元素其他元素放入新數(shù)組
        for (int i = 0; i < elements.length - 1; i++) {
            newArr[i] = elements[i];
        }
        elements = newArr;
        return element;
    }

    //查看棧頂元素
    public int peek() {
        return elements[elements.length - 1];
    }

    //判斷棧是否為空
    public boolean is_empty() {
        return elements.length == 0;
    }

    //查看棧的元素個數(shù)
    public int size() {
        return elements.length;
    }}

測試類：

package mystack;public class Demo {
    public static void main(String[] args) {
        MyStack ms = new MyStack();
        //添加元素
        ms.push(9);
        ms.push(8);
        ms.push(7);

        //取出棧頂元素//        System.out.println(ms.pop()); //7//        System.out.println(ms.pop()); //8//        System.out.println(ms.pop()); //9

        //查看棧頂元素
        System.out.println(ms.peek()); //7
        System.out.println(ms.peek()); //7

        //查看棧中元素個數(shù)
        System.out.println(ms.size()); //3
    }}

第4章 隊列

4.1 隊列概念

隊列（Queue）是只允許在一端進(jìn)行插入操作，而在另一端進(jìn)行刪除操作的線性表。

隊列是一種先進(jìn)先出的（First In First Out）的線性表，簡稱FIFO。允許插入的一端為隊尾，允許刪除的一端為隊頭。隊列不允許在中間部位進(jìn)行操作！假設(shè)隊列是q=（a1，a2，……，an），那么a1就是隊頭元素，而an是隊尾元素。這樣我們就可以刪除時，總是從a1開始，而插入時，總是在隊列最后。這也比較符合我們通常生活中的習(xí)慣，排在第一個的優(yōu)先出列，最后來的當(dāng)然排在隊伍最后。

同棧一樣，隊列也可以用順序表或者鏈表實現(xiàn)。

4.2 隊列的操作

• Queue() 創(chuàng)建一個空的隊列

• enqueue(element) 往隊列中添加一個element元素

• dequeue() 從隊列頭部刪除一個元素

• is_empty() 判斷一個隊列是否為空

• size() 返回隊列的大小

實現(xiàn)類：

public class MyQueue {

    int[] elements;

    public MyQueue() {
        elements = new int[0];
    }

    //入隊
    public void enqueue(int element) {
        //創(chuàng)建一個新的數(shù)組
        int[] newArr = new int[elements.length + 1];
        //把原數(shù)組中的元素復(fù)制到新數(shù)組中
        for (int i = 0; i < elements.length; i++) {
            newArr[i] = elements[i];
        }
        //把添加的元素放入新數(shù)組中
        newArr[elements.length] = element;
        //使用新數(shù)組替換舊數(shù)組
        elements = newArr;
    }

    //出隊
    public int dequeue() {
        if (isEmpty()) {
            throw new RuntimeException("隊空，無數(shù)據(jù)");
        }
        //把數(shù)組中第1個元素取出來
        int element = elements[0];
        //創(chuàng)建一個新數(shù)組
        int[] newArr = new int[elements.length - 1];
        //把原數(shù)組除了第一個數(shù)據(jù)，其他存入新數(shù)組
        for (int i = 0; i < elements.length; i++) {
            newArr[i] = elements[i + 1];
        }
        //新數(shù)組替換舊數(shù)組
        elements = newArr;

        return element;
    }

    //判斷是否隊空
    public boolean isEmpty() {
        return elements.length==0;
    }

    //獲取隊列長度
    public int size() {
        return elements.length;
    }}

測試類：

public class Demo {
    public static void main(String[] args) {
        MyQueue mq = new MyQueue();

        //入隊
        mq.enqueue(1);
        mq.enqueue(2);
        mq.enqueue(3);

        //出隊
        System.out.println(mq.dequeue()); //1
        System.out.println(mq.dequeue()); //2
        System.out.println(mq.dequeue()); //3
    }}

第5章 鏈表

5.1 單鏈表

單鏈表概念

單鏈表也叫單向鏈表，是鏈表中最簡單的一種形式，它的每個節(jié)點包含兩個域，一個信息域（元素域）和一個鏈接域。這個鏈接指向鏈表中的下一個節(jié)點，而最后一個節(jié)點的鏈接域則指向一個空值。

• 表元素域data用來存放具體的數(shù)據(jù)。

• 鏈接域next用來存放下一個節(jié)點的位置

單鏈表操作

• is_empty() 鏈表是否為空

• length() 鏈表長度

• travel() 遍歷整個鏈表

• add(item) 鏈表頭部添加元素

• append(item) 鏈表尾部添加元素

• insert(pos, item) 指定位置添加元素

• remove(item) 刪除節(jié)點

• search(item) 查找節(jié)點是否存在

實現(xiàn)類：

//一個節(jié)點public class Node {

    //節(jié)點內(nèi)容
    int data;
    //下一個節(jié)點
    Node next;

    public Node(int data) {
        this.data = data;
    }

    //為節(jié)點追加節(jié)點
    public Node append(Node node) {
        //當(dāng)前節(jié)點
        Node currentNode = this;
        //循環(huán)向后找
        while (true) {
            //取出下一個節(jié)點
            Node nextNode = currentNode.next();
            //如果下一個節(jié)點為null，當(dāng)前節(jié)點已經(jīng)是最后一個節(jié)點
            if (nextNode == null) {
                break;
            }
            //賦給當(dāng)前節(jié)點，無線向后找
            currentNode = nextNode;
        }
        //把需要追加的節(jié)點，追加為找到的當(dāng)前節(jié)點（最后一個節(jié)點）的下一個節(jié)點
        currentNode.next = node;
        return this;
    }

    //顯示所有節(jié)點信息
    public void show() {
        Node currentNode = this;
        while (true) {
            System.out.print(currentNode.data + " ");
            //取出下一個節(jié)點
            currentNode = currentNode.next;
            //如果是最后一個節(jié)點
            if (currentNode == null) {
                break;
            }
        }
        System.out.println();
    }

    //插入一個節(jié)點作為當(dāng)前節(jié)點的下一個節(jié)點
    public void after(Node node) {
        //取出下一個節(jié)點，作為下下一個節(jié)點
        Node nextNext = next;
        //把新節(jié)點作為當(dāng)前節(jié)點的下一個節(jié)點
        this.next = node;
        //把下下一個節(jié)點設(shè)置為新節(jié)點的下一個節(jié)點
        node.next = nextNext;

    }

    //刪除下一個節(jié)點
    public void removeNode() {
        //取出下下一個節(jié)點
        Node newNext = next.next;
        //把下下一個節(jié)點設(shè)置為當(dāng)前節(jié)點的下一個節(jié)點
        this.next = newNext;
    }

    //獲取下一個節(jié)點
    public Node next() {
        return this.next;
    }

    //獲取節(jié)點中的數(shù)據(jù)
    public int getData() {
        return this.data;
    }

    //判斷節(jié)點是否為最后一個節(jié)點
    public boolean isLast() {
        return next == null;
    }}

測試類：

public class Demo {
    public static void main(String[] args) {
        //創(chuàng)建節(jié)點
        Node n1 = new Node(1);
        Node n2 = new Node(2);
        Node n3 = new Node(3);
        //追加節(jié)點
        n1.append(n2).append(n3);
        //取出下一個節(jié)點數(shù)據(jù)
        System.out.println(n1.next().next().getData()); //3
        //判斷節(jié)點是否為最后一個節(jié)點
        System.out.println(n1.isLast()); //false
        System.out.println(n1.next().next().isLast()); //true
        //顯示所有節(jié)點信息
        n1.show(); //1 2 3
        //刪除一個節(jié)點//        n1.next.removeNode();//        n1.show(); //1 2
        //插入一個新節(jié)點
        n1.next.after(new Node(0));
        n1.show(); //1 2 0 3
    }}

5.2 循環(huán)鏈表

循環(huán)鏈表概念

單鏈表的一個變形是單向循環(huán)鏈表，鏈表中最后一個節(jié)點的 next 域不再為 None，而是指向鏈表的頭節(jié)點。

循環(huán)鏈表操作

實現(xiàn)類：

//表示一個節(jié)點public class LoopNode {

    //節(jié)點內(nèi)容
    int data;
    //下一個節(jié)點
    LoopNode next = this; //與單鏈表的區(qū)別，追加了一個this，當(dāng)只有一個節(jié)點時指向自己

    public LoopNode(int data) {
        this.data = data;
    }

    //插入一個節(jié)點
    public void after(LoopNode node) {
        LoopNode afterNode = this.next;
        this.next = node;
        node.next = afterNode;
    }

    //刪除一個節(jié)點
    public void removeNext() {
        LoopNode newNode = this.next.next;
        this.next = newNode;
    }

    //獲取下一個節(jié)點
    public LoopNode next() {
        return this.next;
    }

    //獲取節(jié)點中的數(shù)據(jù)
    public int getData() {
        return this.data;
    }}

測試類：

public class Demo {
    public static void main(String[] args) {
        //創(chuàng)建節(jié)點
        LoopNode n1 = new LoopNode(1);
        LoopNode n2 = new LoopNode(2);
        LoopNode n3 = new LoopNode(3);
        LoopNode n4 = new LoopNode(4);

        //增加節(jié)點
        n1.after(n2);
        n2.after(n3);
        n3.after(n4);
        System.out.println(n1.next().getData()); //2
        System.out.println(n2.next().getData()); //3
        System.out.println(n3.next().getData()); //4
        System.out.println(n4.next().getData()); //1
    }}

5.3 雙向循環(huán)鏈表

雙向循環(huán)鏈表概念

在雙向鏈表中有兩個指針域，一個是指向前驅(qū)結(jié)點的prev，一個是指向后繼結(jié)點的next指針

雙向循環(huán)鏈表操作

實現(xiàn)類：

public class DoubleNode {
    //上一個節(jié)點
    DoubleNode pre = this;
    //下一個節(jié)點
    DoubleNode next = this;
    //節(jié)點數(shù)據(jù)
    int data;

    public DoubleNode(int data) {
        this.data = data;
    }

    //增加節(jié)點
    public void after(DoubleNode node) {
        //原來的下一個節(jié)點
        DoubleNode nextNext = next;
        //新節(jié)點作為當(dāng)前節(jié)點的下一個節(jié)點
        this.next = node;
        //當(dāng)前節(jié)點作為新節(jié)點的前一個節(jié)點
        node.pre = this;
        //原來的下一個節(jié)點作為新節(jié)點的下一個節(jié)點
        node.next = nextNext;
        //原來的下一個節(jié)點的上一個節(jié)點為新節(jié)點
        nextNext.pre = node;
    }

    //獲取下一個節(jié)點
    public DoubleNode getNext() {
        return this.next;
    }

    //獲取上一個節(jié)點
    public DoubleNode getPre() {
        return this.pre;
    }

    //獲取數(shù)據(jù)
    public int getData() {
        return this.data;
    }}

測試類：

public class Demo {
    public static void main(String[] args) {
        //創(chuàng)建節(jié)點
        DoubleNode n1 = new DoubleNode(1);
        DoubleNode n2 = new DoubleNode(2);
        DoubleNode n3 = new DoubleNode(3);

        //追加節(jié)點
        n1.after(n2);
        n2.after(n3);

        //查看上一個，自己，下一個節(jié)點內(nèi)容
        System.out.println(n2.getPre().getData()); //1
        System.out.println(n2.getData()); //2
        System.out.println(n2.getNext().getData()); //3

        System.out.println(n1.getPre().getData()); //3
        System.out.println(n3.getNext().getData()); //1
    }}

第6章 樹結(jié)構(gòu)基礎(chǔ)

6.1 為什么要使用樹結(jié)構(gòu)

線性結(jié)構(gòu)中不論是數(shù)組還是鏈表，他們都存在著詬?。槐热绮檎夷硞€數(shù)必須從頭開始查，消耗較多的時間。使用樹結(jié)構(gòu)，在插入和查找的性能上相對都會比線性結(jié)構(gòu)要好

6.2 樹結(jié)構(gòu)基本概念

示意圖

1、根節(jié)點：最頂上的唯一的一個；如：A

2、雙親節(jié)點：子節(jié)點的父節(jié)點就叫做雙親節(jié)點；如A是B、C、D的雙親節(jié)點，B是E、F的雙親節(jié)點

3、子節(jié)點：雙親節(jié)點所產(chǎn)生的節(jié)點就是子節(jié)點

4、路徑：從根節(jié)點到目標(biāo)節(jié)點所走的路程叫做路徑；如A要訪問F，路徑為A-B-F

5、節(jié)點的度：有多少個子節(jié)點就有多少的度（最下面的度一定為0，所以是葉子節(jié)點）

6、節(jié)點的權(quán)：在節(jié)點中所存的數(shù)字

7、葉子節(jié)點：沒有子節(jié)點的節(jié)點，就是沒有下一代的節(jié)點；如：E、F、C、G

8、子樹：在整棵樹中將一部分看成也是一棵樹，即使只有一個節(jié)點也是一棵樹，不過這個樹是在整個大樹職中的，包含的關(guān)系

9、層：就是族譜中有多少代的人；如：A是1，B、C、D是2，E、F、G是3

10、樹的高度：樹的最大的層數(shù)：就是層數(shù)中的最大值

11、森林：多個樹組成的集合

6.3 樹的種類

無序樹：樹中任意節(jié)點的子節(jié)點之間沒有順序關(guān)系，這種樹稱為無序樹，也稱為自由樹；

有序樹：樹中任意節(jié)點的子節(jié)點之間有順序關(guān)系，這種樹稱為有序樹；

• 二叉樹：每個節(jié)點最多含有兩個子樹的樹稱為二叉樹；

• 完全二叉樹：對于一顆二叉樹，假設(shè)其深度為d(d>1)。除了第d層外，其它各層的節(jié)點數(shù)目均已達(dá)最大值，且第d層所有節(jié)點從左向右連續(xù)地緊密排列，這樣的二叉樹被稱為完全二叉樹，其中滿二叉樹的定義是所有葉節(jié)點都在最底層的完全二叉樹;

• 平衡二叉樹（AVL樹）：當(dāng)且僅當(dāng)任何節(jié)點的兩棵子樹的高度差不大于1的二叉樹；

• 排序二叉樹（二叉查找樹（英語：Binary Search Tree），也稱二叉搜索樹、有序二叉樹）；

• 霍夫曼樹（用于信息編碼）：帶權(quán)路徑最短的二叉樹稱為哈夫曼樹或最優(yōu)二叉樹；

• B樹：一種對讀寫操作進(jìn)行優(yōu)化的自平衡的二叉查找樹，能夠保持?jǐn)?shù)據(jù)有序，擁有多余兩個子樹。

6.4 樹的存儲與表示

順序存儲：將數(shù)據(jù)結(jié)構(gòu)存儲在固定的數(shù)組中，然在遍歷速度上有一定的優(yōu)勢，但因所占空間比較大，是非主流二叉樹。二叉樹通常以鏈?zhǔn)酱鎯Α?br/>
鏈?zhǔn)酱鎯?/strong>：

由于對節(jié)點的個數(shù)無法掌握，常見樹的存儲表示都轉(zhuǎn)換成二叉樹進(jìn)行處理，子節(jié)點個數(shù)最多為2

6.5 常見的一些樹的應(yīng)用場景

1、xml，html等，那么編寫這些東西的解析器的時候，不可避免用到樹

2、路由協(xié)議就是使用了樹的算法

3、MySQL數(shù)據(jù)庫索引

4、文件系統(tǒng)的目錄結(jié)構(gòu)

5、所以很多經(jīng)典的AI算法其實都是樹搜索，此外機器學(xué)習(xí)中的decision tree也是樹結(jié)構(gòu)

第7章 二叉樹大全

7.1 二叉樹的定義

任何一個節(jié)點的子節(jié)點數(shù)量不超過 2，那就是二叉樹；二叉樹的子節(jié)點分為左節(jié)點和右節(jié)點，不能顛倒位置

7.2 二叉樹的性質(zhì)(特性)

性質(zhì)1：在二叉樹的第i層上至多有2^(i-1)個結(jié)點（i>0）

性質(zhì)2：深度為k的二叉樹至多有2^k - 1個結(jié)點（k>0）

性質(zhì)3：對于任意一棵二叉樹，如果其葉結(jié)點數(shù)為N0，而度數(shù)為2的結(jié)點總數(shù)為N2，則N0=N2+1;

性質(zhì)4：具有n個結(jié)點的完全二叉樹的深度必為 log2(n+1)

性質(zhì)5：對完全二叉樹，若從上至下、從左至右編號，則編號為i 的結(jié)點，其左孩子編號必為2i，其右孩子編號必為2i＋1；其雙親的編號必為i/2（i＝1 時為根,除外）

7.3 滿二叉樹與完全二叉樹

滿二叉樹： 所有葉子結(jié)點都集中在二叉樹的最下面一層上，而且結(jié)點總數(shù)為：2^n-1 (n為層數(shù) / 高度）

完全二叉樹： 所有的葉子節(jié)點都在最后一層或者倒數(shù)第二層，且最后一層葉子節(jié)點在左邊連續(xù)，倒數(shù)第二層在右邊連續(xù)（滿二叉樹也是屬于完全二叉樹）（從上往下，從左往右能挨著數(shù)滿）

7.4 鏈?zhǔn)酱鎯Φ亩鏄?/h3>

創(chuàng)建二叉樹：首先需要一個樹的類，還需要另一個類用來存放節(jié)點，設(shè)置節(jié)點；將節(jié)點放入樹中，就形成了二叉樹；（節(jié)點中需要權(quán)值，左子樹，右子樹，并且都能對他們的值進(jìn)行設(shè)置）。

樹的遍歷：

• 先序遍歷：根節(jié)點，左節(jié)點，右節(jié)點（如果節(jié)點有子樹，先從左往右遍歷子樹，再遍歷兄弟節(jié)點）
  先序遍歷結(jié)果為：A B D H I E J C F K G

• 中序遍歷：左節(jié)點，根節(jié)點，右節(jié)點（中序遍歷可以看成，二叉樹每個節(jié)點，垂直方向投影下來（可以理解為每個節(jié)點從最左邊開始垂直掉到地上），然后從左往右數(shù)）
  中遍歷結(jié)果為：H D I B E J A F K C G

• 后序遍歷：左節(jié)點，右節(jié)點，根節(jié)點
  后序遍歷結(jié)果：H I D J E B K F G C A

• 層次遍歷：從上往下，從左往右
  層次遍歷結(jié)果：A B C D E F G H I J K
  

查找節(jié)點：先對樹進(jìn)行一次遍歷，然后找出要找的那個數(shù)；因為有三種排序方法，所以查找節(jié)點也分為先序查找，中序查找，后序查找；

刪除節(jié)點：由于鏈?zhǔn)酱鎯?，不能找到要刪的數(shù)直接刪除，需要找到他的父節(jié)點，然后將指向該數(shù)設(shè)置為null；所以需要一個變量來指向父節(jié)點，找到數(shù)后，再斷開連接。

代碼實現(xiàn)：

• 樹類

public class BinaryTree {

    TreeNode root;

    //設(shè)置根節(jié)點
    public void setRoot(TreeNode root) {
        this.root = root;
    }

    //獲取根節(jié)點
    public TreeNode getRoot() {
        return root;
    }

    //先序遍歷
    public void frontShow() {
        if (root != null) {
            root.frontShow();
        }
    }

    //中序遍歷
    public void middleShow() {
        if (root != null) {
            root.middleShow();
        }
    }

    //后序遍歷
    public void afterShow() {
        if (root != null) {
            root.afterShow();
        }
    }

    //先序查找
    public TreeNode frontSearch(int i) {
        return root.frontSearch(i);
    }

    //刪除一個子樹
    public void delete(int i) {
        if (root.value == i) {
            root = null;
        } else {
            root.delete(i);
        }
    }}

• 節(jié)點類

public class TreeNode {
    //節(jié)點的權(quán)
    int value;
    //左兒子
    TreeNode leftNode;
    //右兒子
    TreeNode rightNode;

    public TreeNode(int value) {
        this.value = value;
    }

    //設(shè)置左兒子
    public void setLeftNode(TreeNode leftNode) {
        this.leftNode = leftNode;
    }

    //設(shè)置右兒子
    public void setRightNode(TreeNode rightNode) {
        this.rightNode = rightNode;
    }

    //先序遍歷
    public void frontShow() {
        //先遍歷當(dāng)前節(jié)點的值
        System.out.print(value + " ");
        //左節(jié)點
        if (leftNode != null) {
            leftNode.frontShow(); //遞歸思想
        }
        //右節(jié)點
        if (rightNode != null) {
            rightNode.frontShow();
        }
    }

    //中序遍歷
    public void middleShow() {
        //左節(jié)點
        if (leftNode != null) {
            leftNode.middleShow(); //遞歸思想
        }
        //先遍歷當(dāng)前節(jié)點的值
        System.out.print(value + " ");
        //右節(jié)點
        if (rightNode != null) {
            rightNode.middleShow();
        }
    }

    //后續(xù)遍歷
    public void afterShow() {
        //左節(jié)點
        if (leftNode != null) {
            leftNode.afterShow(); //遞歸思想
        }
        //右節(jié)點
        if (rightNode != null) {
            rightNode.afterShow();
        }
        //先遍歷當(dāng)前節(jié)點的值
        System.out.print(value + " ");
    }

    //先序查找
    public TreeNode frontSearch(int i) {
        TreeNode target = null;
        //對比當(dāng)前節(jié)點的值
        if (this.value == i) {
            return this;
            //當(dāng)前節(jié)點不是要查找的節(jié)點
        } else {
            //查找左兒子
            if (leftNode != null) {
                //查找的話t賦值給target，查不到target還是null
                target = leftNode.frontSearch(i);
            }
            //如果target不為空，說明在左兒子中已經(jīng)找到
            if (target != null) {
                return target;
            }
            //如果左兒子沒有查到，再查找右兒子
            if (rightNode != null) {
                target = rightNode.frontSearch(i);
            }
        }
        return target;
    }

    //刪除一個子樹
    public void delete(int i) {
        TreeNode parent = this;
        //判斷左兒子
        if (parent.leftNode != null && parent.leftNode.value == i) {
            parent.leftNode = null;
            return;
        }
        //判斷右兒子
        if (parent.rightNode != null && parent.rightNode.value == i) {
            parent.rightNode = null;
            return;
        }
        //如果都不是，遞歸檢查并刪除左兒子
        parent = leftNode;
        if (parent != null) {
            parent.delete(i);
        }
        //遞歸檢查并刪除右兒子
        parent = rightNode;
        if (parent != null) {
            parent.delete(i);
        }

    }}

• 測試類

public class Demo {
    public static void main(String[] args) {
        //創(chuàng)建一棵樹
        BinaryTree binaryTree = new BinaryTree();
        //            

                網(wǎng)頁題目：Java數(shù)據(jù)結(jié)構(gòu)與算法的示例分析
                

                網(wǎng)頁URL：http://jinyejixie.com/article22/gpecjc.html
            
            

                成都網(wǎng)站建設(shè)公司_創(chuàng)新互聯(lián)，為您提供ChatGPT、手機網(wǎng)站建設(shè)、App開發(fā)、網(wǎng)站導(dǎo)航、云服務(wù)器、營銷型網(wǎng)站建設(shè)            
            

                廣告
                
            
            

                聲明：本網(wǎng)站發(fā)布的內(nèi)容（圖片、視頻和文字）以用戶投稿、用戶轉(zhuǎn)載內(nèi)容為主，如果涉及侵權(quán)請盡快告知，我們將會在第一時間刪除。文章觀點不代表本網(wǎng)站立場，如需處理請聯(lián)系客服。電話：028-86922220；郵箱：631063699@qq.com。內(nèi)容未經(jīng)允許不得轉(zhuǎn)載，或轉(zhuǎn)載時需注明來源：
                創(chuàng)新互聯(lián)