Java 資料結構 - 快速指南

---

---

Java 資料結構 - 建立陣列

在 Java 中，陣列是一種資料結構/容器，它儲存相同型別元素的固定大小的順序集合。陣列用於儲存資料集合，但通常將陣列視為相同型別變數的集合更有用。

• 元素 - 儲存在陣列中的每個專案稱為元素。

• 索引 - 陣列中每個元素的位置都有一個數字索引，用於標識元素。

建立陣列

要建立陣列，需要宣告特定的陣列，指定其型別和引用它的變數。然後，使用 new 運算子為已宣告的陣列分配記憶體（在方括號“[ ]”中指定陣列的大小）。

語法

dataType[] arrayRefVar;   
arrayRefVar = new dataType[arraySize];
(or)
dataType[] arrayRefVar = new dataType[arraySize];

或者，您可以透過直接指定用逗號分隔的元素來建立陣列，這些元素位於花括號“{ }”內。

dataType[] arrayRefVar = {value0, value1, ..., valuek};

透過索引訪問陣列元素。陣列索引是從 0 開始的；也就是說，它們從 0 開始到 arrayRefVar.length-1。

示例

以下語句宣告一個整數型別的陣列變數 myArray，並分配記憶體以儲存 10 個整數型別元素並將它的引用賦值給 myArray。

int[] myList = new int[10];

填充陣列

上面的語句只是建立了一個空陣列。需要透過使用索引為每個位置賦值來填充此陣列 -

myList [0] = 1;
myList [1] = 10;
myList [2] = 20;
.
.
.
.

示例

以下是一個 Java 示例，用於建立一個整數陣列。在這個例子中，我們嘗試建立一個大小為 10 的整數陣列，填充它，並使用迴圈顯示它的內容。

public class CreatingArray {
   public static void main(String args[]) {
      int[] myArray = new int[10];
      myArray[0] = 1;
      myArray[1] = 10;
      myArray[2] = 20;
      myArray[3] = 30;
      myArray[4] = 40;
      myArray[5] = 50;
      myArray[6] = 60;
      myArray[7] = 70;
      myArray[8] = 80;
      myArray[9] = 90;      
      System.out.println("Contents of the array ::");
      
      for(int i = 0; i<myArray.length; i++) {
        System.out.println("Element at the index "+i+" ::"+myArray[i]);
      } 
   }
}

輸出

Contents of the array ::
Element at the index 0 ::1
Element at the index 1 ::10
Element at the index 2 ::20
Element at the index 3 ::30
Element at the index 4 ::40
Element at the index 5 ::50
Element at the index 6 ::60
Element at the index 7 ::70
Element at the index 8 ::80
Element at the index 9 ::90

示例

以下是另一個 Java 示例，它透過獲取使用者的輸入來建立和填充陣列。

import java.util.Scanner;
public class CreatingArray {
   public static void main(String args[]) {
      // Instantiating the Scanner class
      Scanner sc = new Scanner(System.in);
      
      // Taking the size from user
      System.out.println("Enter the size of the array ::");
      int size = sc.nextInt();
      
      // creating an array of given size
      int[] myArray = new int[size];
      
      // Populating the array
      for(int i = 0 ;i<size; i++) {
         System.out.println("Enter the element at index "+i+" :");
         myArray[i] = sc.nextInt();
      }
      
      // Displaying the contents of the array
      System.out.println("Contents of the array ::");
      for(int i = 0; i<myArray.length; i++) {
         System.out.println("Element at the index "+i+" ::"+myArray[i]);
      }
   }
}

輸出

Enter the size of the array ::
5
Enter the element at index 0 :
25
Enter the element at index 1 :
65
Enter the element at index 2 :
78
Enter the element at index 3 :
66
Enter the element at index 4 :
54
Contents of the array ::
Element at the index 0 ::25
Element at the index 1 ::65
Element at the index 2 ::78
Element at the index 3 ::66
Element at the index 4 ::54

向陣列插入元素

插入操作是將一個或多個數據元素插入陣列中。根據需要，可以在陣列的開頭、結尾或任何給定索引處新增新元素。

演算法

令LA為具有N個元素的線性陣列（無序），K為正整數，使得K<=N。以下是將ITEM插入到LA的第K個位置的演算法 -

Step 1 - Start
Step 2 - Set J = N
Step 3 - Set N = N+1
Step 4 - Repeat steps 5 and 6 while J >= K
Step 5 - Set LA[J+1] = LA[J]
Step 6 - Set J = J-1
Step 7 - Set LA[K] = ITEM
Step 8 - Stop

示例

由於 Java 中的陣列大小在插入操作後是固定的，因此不會顯示陣列的冗餘元素。因此，如果您在陣列中間插入元素，為了顯示最後一個元素，需要建立一個大小為 n+1 的新陣列（其中 n 是當前陣列的大小），並將元素插入其中，然後顯示它，或者在列印陣列內容後單獨列印最後一個元素。

public class InsertingElements {
   public static void main(String args[]) {
      int[] myArray = {10, 20, 30, 45, 96, 66};      
      int pos = 3;
      int data = 105;
      int j = myArray.length;
      int lastElement = myArray[j-1];
      
      for(int i = (j-2); i >= (pos-1); i--) {
    	  myArray[i+1] = myArray[i];
      }
      myArray[pos-1] = data;
      System.out.println("Contents of the array after insertion ::");
   
      for(int i = 0; i < myArray.length; i++) {
         System.out.print(myArray[i]+ ", ");
      }   
      System.out.print(lastElement);
   }
}

輸出

Contents of the array after insertion ::
10, 20, 105, 30, 45, 96, 66

Apache Commons 提供了一個名為org.apache.commons.lang3的庫，以下是將庫新增到專案的 Maven 依賴項。

<dependencies>
   <dependency>
      <groupId>org.apache.commons</groupId>
         <artifactId>commons-lang3</artifactId>
         <version>3.0</version>
   </dependency>
</dependencies>

此包提供了一個名為ArrayUtils的類。您可以使用此類的add()方法在陣列的特定位置新增元素。

示例

import java.util.Scanner;
import org.apache.commons.lang3.ArrayUtils;

public class InsertingElements {
   public static void main(String args[]) {
      Scanner sc = new Scanner(System.in);
      System.out.println("Enter the number of elements needed :");
      int n = sc.nextInt();
      int[] myArray = new int[n];
      System.out.println("Enter the elements ::");
      
      for(int i = 0; i < n; i++) {
         myArray[i] = sc.nextInt();
      }        
      System.out.println("Enter the position to insert the element :");
      int pos = sc.nextInt();	  
      System.out.println("Enter the element:");
      int element = sc.nextInt();      
      int [] result = ArrayUtils.add(myArray, pos, element);      
      System.out.println("Contents of the array after insertion ::");   
      
      for(int i = 0; i < result.length; i++) {
         System.out.print(result[i]+ " ");
      }   
   }
}

輸出

Enter the number of elements needed :
5
Enter the elements ::
55
45
25
66
45
Enter the position to insert the element :
3
Enter the element:
404
Contents of the array after insertion ::
55 45 25 404 66 45

從陣列中刪除元素

要從陣列中刪除現有元素，需要跳過給定位置（例如 k）處的元素，方法是用下一個元素 (k+1) 替換它，然後用 k+2 處的元素替換 k+1 處的元素，一直持續到陣列的末尾。最後忽略最後一個元素。

演算法

假設 LA 是一個具有 N 個元素的線性陣列，K 是一個正整數，使得 K<=N。以下是刪除 LA 的第 K 個位置的元素的演算法。

Step 1 - Start
Step 2 - Set J = K
Step 3 - Repeat steps 4 and 5 while J < N
Step 4 - Set LA[J] = LA[J + 1]
Step 5 - Set J = J+1
Step 6 - Set N = N-1
Step 7 - Stop

示例

public class RemovingElements {
   public static void main(String args[]) {
      int[] myArray = {10, 20, 30, 45, 96, 66};
      
      int pos = 3;
      int j = myArray.length;
      
      for(int i = pos; i < j-1; i++) {
         myArray[i] = myArray[i+1];
      }        

      System.out.println("Contents of the array after deletion ::");   
      for(int i = 0; i < myArray.length-1; i++) {
         System.out.print(myArray[i]+ ", ");
      }   
   }
}

輸出

Contents of the array after deletion ::
10, 20, 30, 96, 66,

ArrayUtils類提供remove()方法來從陣列中刪除元素。

示例

import java.util.Scanner;
import org.apache.commons.lang3.ArrayUtils;

public class RemovingElements {
   public static void main(String args[]) {
      Scanner sc = new Scanner(System.in);
      System.out.println("Enter the number of elements needed :");
      int n = sc.nextInt();
      int[] myArray = new int[n];
      System.out.println("Enter the elements ::");
      
      for(int i = 0; i < n; i++) {
         myArray[i] = sc.nextInt();
      }        
      
      System.out.println("Enter the position to delete the element :");
      int pos = sc.nextInt();
      
      int [] result = ArrayUtils.remove(myArray, pos);
      System.out.println("Contents of the array after deletion ::");
   
      for(int i = 0; i < result.length; i++) {
         System.out.print(result[i]+ " ");
      }
   }
}

輸出

Enter the number of elements needed :
5
Enter the elements ::
44
55
62
45
55
Enter the position to delete the element :
3
Contents of the array after deletion ::
44 55 62 55

Java 資料結構 - 合併兩個陣列

一種方法是建立一個長度等於兩個陣列長度之和的陣列，然後逐個將兩個陣列的元素新增到其中。

示例

import java.util.Arrays;

public class JoiningTwoArrays {
   public static void main(String args[]) {
      String[] arr1 = {"JavaFX", "OpenNLP", "OpenCV", "Java"};
      String[] arr2 = {"Hadoop", "Sqoop", "HBase", "Hive" }; 
      String[] result = new String[arr1.length+arr2.length];
      int count = 0;	  
      
      for(int i = 0; i<arr1.length; i++ ) {
         result[i] = arr1[i];
         count++;
      }

      for(int i = 0; i<arr2.length; i++ ) {
         result[count++] = arr2[i];
      }
      
      System.out.println("Contents of the resultant array ::");
      System.out.println(Arrays.toString(result));
   }
}

輸出

Contents of the resultant array ::
[JavaFX, OpenNLP, OpenCV, Java, Hadoop, Sqoop, HBase, Hive]

排序陣列元素

要對陣列進行排序，請按照以下步驟操作。

• 比較陣列的前兩個元素

• 如果第一個元素大於第二個元素，則交換它們。

• 然後，比較第二個和第三個元素，如果第二個元素大於第三個元素，則交換它們。

• 重複此操作直到陣列結束。

交換陣列

• 建立一個變數 (temp)，將其初始化為 0。

• 將第一個數字賦值給 temp。

• 將第二個數字賦值給第一個數字。

• 將 temp 賦值給第二個數字。

示例

import java.util.Arrays;
public class SortingArray {
   public static void main(String args[]) {
   
     // String[] myArray = {"JavaFX", "HBase", "OpenCV", "Java", "Hadoop", "Neo4j"};
      int[] myArray = {2014, 2545, 4236, 6521, 1254, 2455, 5756, 66406}; 

      int size = myArray.length;
      for(int i = 0; i<size-1; i++) {
         for (int j = i+1; j<size; j++) {
            if(myArray[i]>(myArray[j])) {            
               int temp = myArray[i];
               myArray[i] = myArray[j];
               myArray[j] = temp;
            } 
         }     
      }
      System.out.println("Sorted array :"+Arrays.toString(myArray));     
   }
}

輸出

Sorted array :[1254, 2014, 2455, 2545, 4236, 5756, 6521, 66406]

在陣列中搜索元素

您可以使用幾種演算法搜尋陣列的元素，在此例項中，讓我們討論線性搜尋演算法。

線性搜尋是一種非常簡單的搜尋演算法。在這種型別的搜尋中，會對所有專案逐個進行順序搜尋。檢查每個專案，如果找到匹配項，則返回該特定專案，否則搜尋將繼續到資料集合的末尾。

演算法

Step 1 - Set i to 1.
Step 2 - if i > n then go to step 7.
Step 3 - if A[i] = x then go to step 6.
Step 4 - Set i to i + 1.
Step 5 - Go to Step 2.
Step 6 - Print Element x Found at index i and go to step 8.
Step 7 - Print element not found.

程式

public class LinearSearch {
   public static void main(String args[]) {
      int array[] =  {10, 20, 25, 63, 96, 57};
      int size = array.length;
      int value = 63;
      
      for (int i = 0 ; i < size-1; i++) {		  
         if(array[i]==value) {
            System.out.println("Index of the required element is :"+ i);
         }
      }
   }
}

輸出

Index of the required element is :3

二維陣列

Java 中的二維陣列表示為相同型別的一維陣列的陣列。它主要用於表示具有行和列的值表 -

Int[][] myArray = {{10, 20, 30}, {11, 21, 31}, {12, 22, 32} }

簡而言之，二維陣列包含一維陣列作為元素。它由兩個索引表示，其中第一個索引表示陣列的位置，第二個索引表示該特定陣列中元素的位置 -

示例

public class Creating2DArray {	
   public static void main(String args[]) {
      int[][] myArray = new int[3][3];	      
      myArray[0][0] = 21;
      myArray[0][1] = 22;
      myArray[0][2] = 23;
      myArray[1][0] = 24;
      myArray[1][1] = 25;
      myArray[1][2] = 26;
      myArray[2][0] = 27;
      myArray[2][1] = 28;
      myArray[2][2] = 29;      
      
      for(int i = 0; i<myArray.length; i++ ) {    	  
         for(int j = 0;j<myArray.length; j++) {
            System.out.print(myArray[i][j]+" ");
         }
         System.out.println();
      }
   }
}

輸出

21 22 23 
24 25 26 
27 28 29

Java 資料結構 - 遍歷陣列

為了處理陣列元素，我們經常使用 for 迴圈或 for each 迴圈，因為陣列中的所有元素都是相同型別，並且陣列的大小是已知的。假設我們有一個包含 5 個元素的陣列，我們可以列印此陣列的所有元素，如下所示 -

示例

public class ProcessingArrays {		
   public static void main(String args[]) {
      int myArray[] = {22, 23, 25, 27, 30};       
      
      for(int i = 0; i<myArray.length; i++) {    	  
         System.out.println(myArray[i]);    	        
      }
   }   
}

輸出

22
23
25
27
30

Java 資料結構 - BitSet 類

BitSet 類建立一種特殊型別的陣列，用於儲存位值。它可以根據需要增加大小，這使其類似於位向量。BitSet 的索引由非負值表示，每個索引都儲存一個布林值。

Java 中的 BitSet 類

BitSet 類實現一組位或標誌，可以單獨設定和清除。當您需要跟蹤一組布林值時，此類非常有用；您只需為每個值分配一個位，並根據需要設定或清除它。BitSet 陣列可以根據需要增加大小。這使其類似於位向量。

BitSet 定義了以下兩個建構函式。

BitSet 實現 Cloneable 介面並定義下表中列出的方法

示例

以下程式演示了此資料結構支援的幾種方法

import java.util.BitSet;
public class BitSetDemo {
   public static void main(String args[]) {
      BitSet bits1 = new BitSet(16);
      BitSet bits2 = new BitSet(16);
      
      // set some bits
      for(int i = 0; i < 16; i++) {
         if((i % 2) == 0) bits1.set(i);
         if((i % 5) != 0) bits2.set(i);
      }

      System.out.println("Initial pattern in bits1: ");
      System.out.println(bits1);
      System.out.println("\n Initial pattern in bits2: ");
      System.out.println(bits2);

      // AND bits
      bits2.and(bits1);
      System.out.println("\nbits2 AND bits1: ");
      System.out.println(bits2);

      // OR bits
      bits2.or(bits1);
      System.out.println("\nbits2 OR bits1: ");
      System.out.println(bits2);

      // XOR bits
      bits2.xor(bits1);
      System.out.println("\nbits2 XOR bits1: ");
      System.out.println(bits2);
   }
}

輸出

Initial pattern in bits1:
{0, 2, 4, 6, 8, 10, 12, 14}

Initial pattern in bits2:
{1, 2, 3, 4, 6, 7, 8, 9, 11, 12, 13, 14}

bits2 AND bits1:
{2, 4, 6, 8, 12, 14}

bits2 OR bits1:
{0, 2, 4, 6, 8, 10, 12, 14}

bits2 XOR bits1:
{}

Java資料結構 - 建立BitSet

可以透過例項化java.util包的BitSet類來建立一個BitSet。BitSet類的一個建構函式允許您指定其初始大小，即它可以容納的位數。

因此，要建立一個位集，請透過將所需的位數傳遞給其建構函式來例項化BitSet類。

BitSet bitSet = new BitSet(5);

示例

import java.util.BitSet;
public class CreatingBitSet {
   public static void main(String args[]) {
      
      BitSet bitSet = new BitSet(5);   
      bitSet.set(0);
      bitSet.set(2);
      bitSet.set(4);
      System.out.println(bitSet);      
   }
}

輸出

{0, 2, 4}

向 BitSet 新增值

BitSet類提供set()方法，用於將指定位的true。

示例

import java.util.BitSet;
public class CreatingBitSet {
   public static void main(String args[]) {
      
      BitSet bitSet = new BitSet(5);   
      bitSet.set(0);
      bitSet.set(2);
      bitSet.set(4);
      System.out.println(bitSet);      
   }
}

輸出

{0, 2, 4}

從 BitSet 中刪除元素

可以使用BitSet類的clear()方法清除所有位，即設定所有位為false。類似地，也可以透過將索引作為引數傳遞給此方法來清除所需索引處的值。

示例

以下是一個刪除BitSet類元素的示例。這裡，我們嘗試將索引為偶數值（最多25）的元素設定為true。稍後我們將清除索引值為5的倍數的元素。

import java.util.BitSet;
public class RemovingelementsOfBitSet {
   public static void main(String args[]) {
      BitSet bitSet = new BitSet(10);  
      
      for (int i = 1; i<25; i++) {
         if(i%2==0) {
            bitSet.set(i);
         }
      }
      System.out.println(bitSet); 
      System.out.println("After clearing the contents ::");
      
      for (int i = 0; i<25; i++) {
         if(i%5==0) {
            bitSet.clear(i);
         }      
      }
      System.out.println(bitSet);
   }
}

輸出

{2, 4, 6, 8, 10, 12, 14, 16, 18, 20, 22, 24}
After clearing the contents ::
{2, 4, 6, 8, 12, 14, 16, 18, 22, 24}

驗證 BitSet 是否為空

當其中的所有值都為false時，位集被認為為空。BitSet類提供isEmpty()方法。此方法返回一個布林值，噹噹前BitSet為空時為false，不為空時為true。

可以使用isEmpty()方法驗證特定的BitSet是否為空。

示例

import java.util.BitSet;
public class isEmpty {
   public static void main(String args[]) {
      BitSet bitSet = new BitSet(10);  
      
      for (int i = 1; i<25; i++) {
         if(i%2==0) {
            bitSet.set(i);
         }      
      }
      
      if (bitSet.isEmpty()) {
         System.out.println("This BitSet is empty");    
      } else {
         System.out.println("This BitSet is not empty"); 
         System.out.println("The contents of it are : "+bitSet);
      }
      bitSet.clear();
      
      if (bitSet.isEmpty()) {
         System.out.println("This BitSet is empty");    
      } else {
         System.out.println("This BitSet is not empty"); 
         System.out.println("The contents of it are : "+bitSet);
      }    
   }
}

輸出

This BitSet is not empty
The contents of it are : {2, 4, 6, 8, 10, 12, 14, 16, 18, 20, 22, 24}
This BitSet is empty

列印 BitSet 的元素

BitSet類的get()方法返回指定索引處位的當前狀態/值。使用它可以列印BitSet的內容。

示例

import java.util.BitSet;
public class PrintingElements {
   public static void main(String args[]) {
      BitSet bitSet = new BitSet(10);  
      
      for (int i = 1; i<25; i++) {
         if(i%2==0) {
            bitSet.set(i);
         }      
      }
      System.out.println("After clearing the contents ::");
      
      for (int i = 1; i<=25; i++) {
         System.out.println(i+": "+bitSet.get(i));       
      }
   }
}

輸出

After clearing the contents ::
1: false
2: true
3: false
4: true
5: false
6: true
7: false
8: true
9: false
10: true
11: false
12: true
13: false
14: true
15: false
16: true
17: false
18: true
19: false
20: true
21: false
22: true
23: false
24: true
25: false

或者，可以直接使用println()方法列印位集的內容。

System.out.println(bitSet);

Java資料結構 - Vector類

Vector是一種類似於陣列的資料結構。像陣列一樣，它分配連續的記憶體。與棧不同，Vector的大小是靈活的。

Vector 類

java.util.Vector類實現了一個可增長的物件陣列。類似於陣列，它包含可以使用整數索引訪問的元件。以下是關於Vector的重要幾點：

• Vector的大小可以根據需要增長或縮小以適應新增和刪除專案。

• 每個向量都試圖透過維護一個容量和一個容量增量來最佳化儲存管理。

• 從Java 2平臺v1.2開始，此類經過改造以實現List介面。

• 與新的集合實現不同，Vector是同步的。

• 此類是Java集合框架的成員。

類宣告

以下是java.util.Vector類的宣告：

public class Vector<E>
   extends AbstractList<E>
   implements List<E>, RandomAccess, Cloneable, Serializable

這裡<E>表示一個元素，可以是任何類。例如，如果您正在構建一個整數的陣列列表，那麼您可以按如下方式初始化它：

ArrayList<Integer> list = new ArrayList<Integer>();  

類建構函式

類方法

Java 資料結構 - 建立向量

java.util 類中的 Vector 類實現動態陣列。它類似於 ArrayList，但有兩個區別：Vector 是同步的，並且它包含許多不屬於集合框架的遺留方法。

可以透過例項化 **java.util** 包中的 **Vector** 類來建立一個向量。

Vector vect = new Vector();

示例

import java.util.Vector;
public class CreatingVector {
   public static void main(String args[]) {
      Vector vect = new Vector();
      vect.addElement("Java");
      vect.addElement("JavaFX");
      vect.addElement("HBase");
      vect.addElement("Neo4j");
      vect.addElement("Apache Flume");
      System.out.println(vect);	   
   }
}

輸出

[Java, JavaFX, HBase, Neo4j, Apache Flume]

向 Vector 新增元素

**Vector** 類提供 **addElement()** 方法，它接受一個物件並將指定的物件/元素新增到當前向量中。

可以使用 **addElement()** 方法將元素新增到 Vector 物件中，方法是將要新增的元素/物件作為引數傳遞給此方法。

vect.addElement("Java");

示例

import java.util.Vector;
public class CreatingVector {
   public static void main(String args[]) {
      Vector vect = new Vector();
      vect.addElement("Java");
      vect.addElement("JavaFX");
      vect.addElement("HBase");
      vect.addElement("Neo4j");
      vect.addElement("Apache Flume");
      System.out.println(vect);	   
   }
}

輸出

[Java, JavaFX, HBase, Neo4j, Apache Flume]

從 Vector 中刪除元素

**Vector** 類提供 **removeElement()** 方法，它接受一個物件並將指定的物件/元素從當前向量中移除。

可以使用 removeElement() 方法移除 Vector 物件的元素，方法是將要移除的元素的索引作為引數傳遞給此方法。

示例

import java.util.Vector;

public class RemovingElements {
   public static void main(String args[]) {
      
      Vector vect = new Vector();
      vect.addElement("Java");
      vect.addElement("JavaFX");
      vect.addElement("HBase");
      vect.addElement("Neo4j");
      vect.addElement("Apache Flume");
      System.out.println("Contents of the vector :"+vect);
      vect.removeElement(3);
      System.out.println("Contents of the vector after removing elements:"+vect);
   }
}

輸出

Contents of the vector :[Java, JavaFX, HBase, Neo4j, Apache Flume]
Contents of the vector after removing elements:[Java, JavaFX, HBase, Neo4j, Apache Flume]

驗證 Vector 是否為空

**java.util** 包中的 **Vector** 類提供 **isEmpty()** 方法。此方法驗證當前向量是否為空。如果給定向量為空，則此方法返回 true，否則返回 false。

示例

import java.util.Vector;

public class Vector_IsEmpty {
   public static void main(String args[]) {
      Vector vect = new Vector();
      vect.addElement("Java");
      vect.addElement("JavaFX");
      vect.addElement("HBase");
      vect.addElement("Neo4j");
      vect.addElement("Apache Flume");
      System.out.println("Elements of the vector :"+vect);
      boolean bool1 = vect.isEmpty();
      
      if(bool1==true) {
         System.out.println("Given vector is empty");
      } else {
         System.out.println("Given vector is not empty");    	  
      }
      vect.clear();
      boolean bool2 = vect.isEmpty();
      System.out.println("cleared the contents of the vector");       
      
      if(bool2==true) {
         System.out.println("Given vector is empty");
      } else {
         System.out.println("Given vector is not empty");    	  
      }  
   }
}

輸出

Elements of the vector :[Java, JavaFX, HBase, Neo4j, Apache Flume]
Given vector is not empty
cleared the contents of the vector
Given vector is empty

清除 Vector 的元素

可以使用 **clear()** 方法移除給定向量中的所有元素。

示例

import java.util.Vector;

public class ClearingElements {
   public static void main(String args[]) {
      Vector vect = new Vector();
      vect.addElement("Java");
      vect.addElement("JavaFX");
      vect.addElement("HBase");
      vect.addElement("Neo4j");
      vect.addElement("Apache Flume");
      
      System.out.println("Elements of the vector :"+vect);
      vect.clear();
      System.out.println("Elements of the vector after clearing it :"+vect);
   }
}

輸出

Elements of the vector :[Java, JavaFX, HBase, Neo4j, Apache Flume]
Elements of the vector after clearing it :[]

列印 Vector 的元素

可以直接使用 println 語句列印向量的所有元素。

System.out.println(vect);

或者，可以使用 hasMoreElements() 和 nextElement() 方法逐個列印其元素。

示例

import java.util.*;
public class VectorPrintingElements {
   public static void main(String args[]) {
      
      // initial size is 3, increment is 2
      Vector v = new Vector();

      v.addElement(new Integer(1));
      v.addElement(new Integer(2));
      v.addElement(new Integer(3));
      v.addElement(new Integer(4));
      System.out.println("Capacity after four additions: " + v.capacity());

      // enumerate the elements in the vector.
      Enumeration vEnum = v.elements();
      System.out.println("\nElements in vector:");

      while(vEnum.hasMoreElements())
      System.out.print(vEnum.nextElement() + " ");
      System.out.println();
   }
}

輸出

Capacity after four additions: 10

Elements in vector:
1 2 3 4

Java 資料結構 - Stack 類

棧是一種抽象資料型別 (ADT)，在大多數程式語言中常用。它被稱為棧，因為它表現得像一個現實世界的棧，例如——一副牌或一堆盤子等。

現實世界的棧只允許在一端進行操作。例如，我們只能在棧的頂部放置或移除卡片或盤子。同樣，Stack ADT 只允許在一端進行所有資料操作。在任何給定時間，我們只能訪問棧的頂部元素。

此特性使其成為 LIFO 資料結構。LIFO 代表後進先出。在這裡，最後放置（插入或新增）的元素首先被訪問。在棧術語中，插入操作稱為 **PUSH** 操作，移除操作稱為 **POP** 操作。

棧表示

下圖描述了一個棧及其操作：

棧可以使用陣列、結構、指標和連結串列實現。棧可以是固定大小的，也可以具有動態調整大小的功能。在這裡，我們將使用陣列實現棧，這使其成為固定大小的棧實現。

Stack 類

Stack 是 Vector 的一個子類，它實現標準的後進先出棧。

Stack 只定義預設建構函式，它建立一個空棧。Stack 包括 Vector 定義的所有方法，並添加了一些它自己的方法。

Stack( )

除了從其父類 Vector 繼承的方法外，Stack 還定義了以下方法：

示例

下面的程式說明了此集合支援的幾種方法：

import java.util.*;
public class StackDemo {
   static void showpush(Stack st, int a) {
      st.push(new Integer(a));
      System.out.println("push(" + a + ")");
      System.out.println("stack: " + st);
   }

   static void showpop(Stack st) {
      System.out.print("pop -> ");
      Integer a = (Integer) st.pop();
      System.out.println(a);
      System.out.println("stack: " + st);
   }

   public static void main(String args[]) {
      Stack st = new Stack();
      System.out.println("stack: " + st);
      showpush(st, 42);
      showpush(st, 66);
      showpush(st, 99);
      showpop(st);
      showpop(st);
      showpop(st);
      
      try {
         showpop(st);
      } catch (EmptyStackException e) {
         System.out.println("empty stack");
      }
   }
}

輸出

stack: [ ]
push(42)
stack: [42]
push(66)
stack: [42, 66]
push(99)
stack: [42, 66, 99]
pop -> 99
stack: [42, 66]
pop -> 66
stack: [42]
pop -> 42
stack: [ ]
pop -> empty stack

Java 資料結構 - 建立棧

棧由 **java.util** 包中的 **Stack** 類表示。可以透過例項化此類來建立一個棧。

Stack stack = new Stack();

建立棧後，可以使用 addElement() 方法向其中新增元素。

stack.addElement("Java");

示例

以下是一個示例，演示如何建立棧，向其中新增元素以及顯示其內容。

import java.util.Stack;
public class CreatingStack {
   public static void main(String args[]) {
      Stack stack = new Stack();
      stack.addElement("Java");
      stack.addElement("JavaFX");
      stack.addElement("HBase");
      stack.addElement("Flume");
      stack.addElement("Java");
      System.out.println(stack);	   
   }
}

輸出

Contents of the stack :[Java, JavaFX, HBase, Flume, Java]

向 Stack 推入元素

棧中的 push 操作涉及向其中插入元素。如果將特定元素推入棧，它將新增到棧的頂部，即第一個插入棧的元素是最後一個被彈出的元素。（先進後出）

可以使用 **push()** 方法將元素推入 Java 棧。

示例

import java.util.Stack;

public class PushingElements {
   public static void main(String args[]) {
      Stack stack = new Stack();
      stack.push(455);
      stack.push(555);
      stack.push(655);
      stack.push(755);
      stack.push(855);
      stack.push(955);
      System.out.println(stack);
   }
}

輸出

[455, 555, 655, 755, 855, 955]

從 Stack 彈出元素

棧中的 pop 操作是指從棧中移除元素。對棧執行此操作時，將移除棧頂的元素，即最後插入棧的元素將首先彈出。（後進先出）

示例

import java.util.Stack;

public class PoppingElements {
   public static void main(String args[]) {
      Stack stack = new Stack();
      stack.push(455);
      stack.push(555);
      stack.push(655);
      stack.push(755);
      stack.push(855);
      stack.push(955);
      
      System.out.println("Elements of the stack are :"+stack.pop());
      System.out.println("Contents of the stack after popping the element :"+stack);
   }
}

輸出

Elements of the stack are :955
Contents of the stack after popping the element :[455, 555, 655, 755, 855]

驗證 Stack 是否為空

**java.util** 包中的 Stack 類提供了一個 isEmpty() 方法。此方法驗證當前 Stack 是否為空。如果給定向量為空，則此方法返回 true，否則返回 false。

示例

import java.util.Stack;
public class StackIsEmpty {
   public static void main(String args[]) {
      Stack stack = new Stack();
      stack.push(455);
      stack.push(555);
      stack.push(655);
      stack.push(755);
      stack.push(855);
      stack.push(955);
      System.out.println("Contents of the stack :"+stack);
      stack.clear();
      System.out.println("Contents of the stack after clearing the elements :"+stack);
      
      if(stack.isEmpty()) {
         System.out.println("Given stack is empty");    	  
      } else {
         System.out.println("Given stack is not empty");  
      }
   }
}

輸出

Contents of the stack :[455, 555, 655, 755, 855, 955]
Contents of the stack after clearing the elements :[]
Given stack is empty

清除 Stack 的元素

Stack 類的 **clear()** 方法用於清除當前棧的內容。

示例

import java.util.Stack;

public class ClearingElements {
   public static void main(String[] args) {
      Stack stack = new Stack();
      stack.push(455);
      stack.push(555);
      stack.push(655);
      stack.push(755);
      stack.push(855);
      stack.push(955);
      System.out.println("Contents of the stack :"+stack);
      stack.clear();
      System.out.println("Contents of the stack after clearing the elements :"+stack);
   }
}

輸出

Contents of the stack :[455, 555, 655, 755, 855, 955]
Contents of the stack after clearing the elements :[]

列印 Stack 的元素

可以直接使用 println() 方法列印棧的內容。

System.out.println(stack)

Stack 類還提供 iterator() 方法。此方法返回當前 Stack 的迭代器。使用它可以逐個列印棧的內容。

示例

import java.util.Iterator;
import java.util.Stack;

public class PrintingElements {
   public static void main(String args[]) {
      Stack stack = new Stack();
      stack.push(455);
      stack.push(555);
      stack.push(655);
      stack.push(755);
      stack.push(855);
      stack.push(955);
      System.out.println("Contents of the stack :");	
      Iterator it = stack.iterator();
      
      while(it.hasNext()) {
         System.out.println(it.next());    	  
      }
   }
}

輸出

Contents of the stack :
455
555
655
755
855
955

Java 資料結構 - 優先佇列類

佇列是一種抽象資料結構，與棧有點類似。與棧不同，佇列的兩端都是開放的。一端始終用於插入資料（入隊），另一端用於移除資料（出隊）。佇列遵循先進先出方法，即首先儲存的資料項將首先被訪問。

隊列表示

正如我們現在瞭解的那樣，在佇列中，我們出於不同的原因訪問兩端。下圖試圖解釋佇列作為資料結構的表示：

與棧一樣，佇列也可以使用陣列、連結串列、指標和結構實現。為簡單起見，我們將使用一維陣列實現佇列。

優先佇列類

**java.util.PriorityQueue** 類是一個基於優先順序堆的無界優先順序佇列。以下是關於 PriorityQueue 的重要幾點：

• 優先順序佇列的元素根據它們的自然順序或在佇列構造時提供的比較器進行排序，具體取決於使用哪個建構函式。

• 優先順序佇列不允許空元素。

• 依賴自然順序的優先順序佇列也不允許插入不可比較的物件。

類宣告

以下是 **java.util.PriorityQueue** 類的宣告：

public class PriorityQueue<E>
   extends AbstractQueue<E>
   implements Serializable

引數

以下是 **java.util.PriorityQueue** 類的引數：

**E** - 這是此集合中儲存的元素的型別。

類建構函式

類方法

Java 資料結構 - 建立佇列

Java 提供了一個名為 Queue 的介面，它表示佇列資料結構。此介面具有各種子類，例如 ArrayBlockingQueue、ArrayDeque、ConcurrentLinkedDeque、ConcurrentLinkedQueue、DelayQueue、LinkedBlockingDeque、LinkedBlockingQueue、LinkedList、LinkedTransferQueue、PriorityBlockingQueue、PriorityQueue、SynchronousQueue。

可以透過例項化這些類中的任何一個來在 Java 中建立一個佇列。在我們的示例中，我們將嘗試透過例項化 **PriorityQueue** 類來建立一個佇列。

• 它是一個基於優先順序堆的無界優先順序佇列。

• 它的元素根據它們的自然順序或在佇列構造時提供的比較器進行排序，具體取決於使用哪個建構函式。

• 它不允許空元素。

• 它依賴自然順序也不允許插入不可比較的物件。

示例

import java.util.PriorityQueue;
import java.util.Queue;

public class CreatingQueue {
   public static void main(String args[]) {
      //Create priority queue
      Queue <String>  prQueue = new PriorityQueue <String> () ;      
      
      //Adding elements
      prQueue.add("JavaFX");
      prQueue.add("Java");
      prQueue.add("HBase");
      prQueue.add("Flume");
      prQueue.add("Neo4J");
      
      System.out.println("Priority queue values are: " + prQueue) ; 
   }
}

輸出

 
Priority queue values are: [Flume, HBase, Java, JavaFX, Neo4J]

向 Queue 新增元素

佇列介面的 **add()** 方法接受一個元素作為引數，並將其新增到當前佇列中。

要向佇列新增元素，請例項化佇列介面的任何子類，並使用 add() 方法新增元素。

示例

import java.util.PriorityQueue;
import java.util.Queue;

public class CreatingQueue {
   public static void main(String args[]) {

      //Create priority queue
      Queue <String>  prQueue = new PriorityQueue <String> (); 
    
      //Adding elements
      prQueue.add("JavaFX");
      prQueue.add("Java");
      prQueue.add("HBase");
      prQueue.add("Flume");
      prQueue.add("Neo4J");      
      System.out.println("Priority queue values are: " + prQueue) ; 
   }
}

輸出

Priority queue values are: [Flume, HBase, Java, JavaFX, Neo4J]

從 Queue 中刪除元素

與 add() 方法類似，Queue 介面提供 remove() 方法。此方法接受一個元素作為引數，並將其從佇列中移除。

使用此方法可以從佇列中移除元素。

示例

import java.util.PriorityQueue;
import java.util.Queue;
import java.util.Scanner;

public class RemovingElements {
   public static void main(String args[]) {

      //Create priority queue
      Queue <String>  prQueue = new PriorityQueue <String> () ; 
      
      //Adding elements
      prQueue.add("JavaFX");
      prQueue.add("Java");
      prQueue.add("HBase");
      prQueue.add("Flume");
      prQueue.add("Neo4J");
      
      System.out.println("Enter the element to be deleted");
      Scanner sc = new Scanner(System.in);
      String element = sc.next();
 
      System.out.println("Contents of the queue : " + prQueue) ;       
      prQueue.remove(element);
      System.out.println("Contents of the queue after deleting sepcified element: " + prQueue) ; 
   }
}

清除 Queue 的元素

Queue 介面提供了一個名為 **clear()** 的方法。此方法用於從當前佇列中移除所有元素。

示例

import java.util.PriorityQueue;
import java.util.Queue;
import java.util.Scanner;

public class ClearingElements {
   public static void main(String args[]) {
         
      //Create priority queue
      Queue <String>  prQueue = new PriorityQueue <String> () ; 
      
      //Adding elements
      prQueue.add("JavaFX");
      prQueue.add("Java");
      prQueue.add("HBase");
      prQueue.add("Flume");
      prQueue.add("Neo4J");
       
      System.out.println("Contents of the queue : " + prQueue) ;       
      prQueue.clear();
      System.out.println("Contents of the queue after deleting specified element: " + prQueue) ;    
   }	
}

輸出

Contents of the queue : [Flume, HBase, Java, JavaFX, Neo4J]
Contents of the queue after deleting specified element: []

列印 Queue 的元素

可以使用 println() 方法直接列印佇列的內容。

System.out.println(queue)

除此之外，Queue 還提供 iterator() 方法，該方法返回當前佇列的迭代器。使用它可以逐個列印其內容。

示例

import java.util.Iterator;
import java.util.PriorityQueue;
import java.util.Queue;

public class PrintingElements {
   public static void main(String args[]) {
         
      // Create priority queue
      Queue <String>  prQueue = new PriorityQueue <String> () ; 
      
      // Adding elements
      prQueue.add("JavaFX");
      prQueue.add("Java");
      prQueue.add("HBase");
      prQueue.add("Flume");
      prQueue.add("Neo4J");

      Iterator iT = prQueue.iterator();
      System.out.println("Contents of the queue are :");
      
      while(iT.hasNext()) {
         System.out.println(iT.next());  
      }
   }
}

輸出

Contents of the queue are :
Flume
HBase
Java
JavaFX
Neo4J

Java 資料結構 - 連結串列類

介紹

java.util.LinkedList類的操作實現了雙向連結串列的預期功能。對列表進行索引的操作將從列表的開頭或結尾開始遍歷，選擇離指定索引較近的一端。

類宣告

以下是java.util.LinkedList類的宣告：

public class LinkedList<E>
   extends AbstractSequentialList<E>
   implements List<E>, Deque<E>, Cloneable, Serializable

引數

以下是java.util.LinkedList類的引數：

• **E** - 這是此集合中儲存的元素的型別。

欄位

繼承自java.util.AbstractList類的欄位。

類建構函式

類方法

示例

package com.tutorialspoint;

import java.util.*;

public class LinkedListDemo {
   public static void main(String[] args) {

      // create a LinkedList
      LinkedList list = new LinkedList();

      // add some elements
      list.add("Hello");
      list.add(2);
      list.add("Chocolate");
      list.add("10");

      // print the list
      System.out.println("LinkedList:" + list);

      // add a new element at the end of the list
      list.add("Element");

      // print the updated list
      System.out.println("LinkedList:" + list);
   }
}

輸出

LinkedList:[Hello, 2, Chocolate, 10]
LinkedList:[Hello, 2, Chocolate, 10, Element]

連結串列是由一系列連結組成的序列，每個連結包含一個指向另一個連結的連線。連結串列是僅次於陣列的第二常用資料結構。

連結串列表示

連結串列可以視覺化為一個節點鏈，其中每個節點都指向下一個節點。

• 每個連結串列包含一個頭節點和一個或多個節點。

• 每個節點儲存資料以及下一個元素的地址。

• 列表的最後一個元素為null，標誌著列表的結尾。

連結串列有三種類型

• 單鏈表 - 只能向前遍歷專案。

• 雙向連結串列 - 可以向前和向後遍歷專案。

• 迴圈連結串列 - 最後一個專案包含指向第一個元素的下一個連結，而第一個元素包含指向最後一個元素的上一個連結。

Java資料結構 - 建立連結串列

java.util包中的LinkedList類表示Java中的單鏈表。可以透過例項化此類來建立一個連結串列。

LinkedList linkedLlist = new LinkedList();

示例

import java.util.LinkedList;
public class CreatingLinkedList {
   public static void main(String args[]) {
      LinkedList linkedList = new LinkedList();
      linkedList.add("Mangoes");
      linkedList.add("Grapes");
      linkedList.add("Bananas");
      linkedList.add("Oranges");
      linkedList.add("Pineapples");
      
      System.out.println("Contents of the linked list :"+linkedList);	   
   }
}

輸出

Contents of the linked list :[Mangoes, Grapes, Bananas, Oranges, Pineapples]

向連結串列新增元素

LinkedList類提供了一個名為add()的方法。此方法接受一個元素作為引數，並將其新增到列表的末尾。

可以使用此方法向連結串列新增元素。

示例

import java.util.LinkedList;
public class CreatingLinkedList {
   public static void main(String args[]) {
      LinkedList linkedList = new LinkedList();
      linkedList.add("Mangoes");
      linkedList.add("Grapes");
      linkedList.add("Bananas");
      linkedList.add("Oranges");
      linkedList.add("Pineapples");

      System.out.println("Contents of the linked list :"+linkedList);
   }
}

輸出

Contents of the linked list :[Mangoes, Grapes, Bananas, Oranges, Pineapples]

從連結串列中刪除元素

LinkedList類的remove()方法接受一個元素作為引數，並將其從當前連結串列中移除。

可以使用此方法從連結串列中移除元素。

示例

import java.util.LinkedList;

public class RemovingElements {
   public static void main(String[] args) {
      LinkedList linkedList = new LinkedList();
      linkedList.add("Mangoes");
      linkedList.add("Grapes");
      linkedList.add("Bananas");
      linkedList.add("Oranges");
      linkedList.add("Pineapples");	      
      
      System.out.println("Contents of the linked list :"+linkedList);      
      linkedList.remove("Grapes");
      
      System.out.println("Contents of the linked list after removing the specified element :"+linkedList);
   }
}

輸出

Contents of the linked list :[Mangoes, Grapes, Bananas, Oranges, Pineapples]
Contents of the linked list after removing the specified element :[Mangoes, Bananas, Oranges, Pineapples]

Java資料結構 - 雙向連結串列

雙向連結串列是連結串列的一種變體，與單鏈表相比，可以輕鬆地向前和向後兩種方式遍歷。以下是理解雙向連結串列概念的一些重要術語。

連結 - 連結串列的每個連結都可以儲存稱為元素的資料。

Next - 連結串列的每個連結都包含指向下一個連結的連結，稱為Next。

Prev - 連結串列的每個連結都包含指向前一個連結的連結，稱為Prev。

LinkedList - 連結串列包含指向第一個連結（稱為First）和最後一個連結（稱為Last）的連線連結。

雙向連結串列表示

• 雙向連結串列包含一個名為first和last的連結元素。
• 每個連結都包含一個或多個數據欄位和兩個連結欄位，分別稱為next和prev。
• 每個連結都使用其next連結與其下一個連結連結。
• 每個連結都使用其prev連結與其前一個連結連結。
• 最後一個連結的連結為null，標誌著列表的結尾。

示例

class Node{
   int data;
   Node preNode, nextNode, CurrentNode;
   Node() {
      preNode = null;
      nextNode = null; 
   }
   Node(int data) {
      this.data = data;
   }
}

public class DoublyLinked {
   Node head, tail;
   int size;   
   public void printData() {
      System.out.println("         ");
      Node node = head;
      while(node !=null) {
         System.out.println(node.data);
         node = node.nextNode;
      }
      System.out.println( );  
   }
   public void insertStart(int data) {
      Node node = new Node();
      node.data = data;
      node.nextNode = head;
      node.preNode = null;
      if(head!=null) {
         head.preNode = node;
      }
      head = node;
      if(tail == null) {
         tail = node;
      }
      size++;   
   }
   public void insertEnd(int data) {
      Node node = new Node();
      node.data = data;
      node.nextNode = null;
      node.preNode = tail;
      
      if(tail!=null) {
         tail.preNode = node;
      }
      tail = node;
      if(head == null) {
         head = node;
      }
      size++;   
   }   
   public static void main(String args[]) {   
      DoublyLinked dl = new DoublyLinked();
      dl.insertStart(10);
      dl.insertStart(20);
      dl.insertStart(30);
      dl.insertStart(1);
      dl.insertStart(56);
      dl.insertStart(40);
      dl.printData();
   }
}

輸出

40
56
1
30
20
10

Java資料結構 - 迴圈連結串列

迴圈連結串列是連結串列的一種變體，其中第一個元素指向最後一個元素，最後一個元素指向第一個元素。單鏈表和雙向連結串列都可以轉換為迴圈連結串列。

單鏈表作為迴圈連結串列

在單鏈表中，最後一個節點的next指標指向第一個節點。

雙向連結串列作為迴圈連結串列

在雙向連結串列中，最後一個節點的next指標指向第一個節點，第一個節點的prev指標指向最後一個節點，從而形成雙向迴圈連結串列。

根據以上說明，需要注意以下幾點：

在單鏈表和雙向連結串列中，最後一個連結的next都指向列表的第一個連結。

在雙向連結串列中，第一個連結的previous指向列表的最後一個連結。

示例

class Node{	
   int data;
   Node preNode, nextNode, CurrentNode;
   Node() {
      preNode = null;
      nextNode = null; 
   }	   
   Node(int data) {
      this.data = data;
   }		
}
public class CircularLinked {
   Node head, tail;
   int size;
	   
   public void printData() {
      Node node = head;
      if(size<=0) {
         System.out.print("List is empty");
      } else {
         do {
            System.out.print(" " + node.data);
            node = node.nextNode;
         }
         while(node!=head);
      }
   }
   public void insertStart(int data) {
      Node node = new Node();
      node.data = data;
      node.nextNode = head;
      node.preNode = null;
      
      if(size==0) {
         head = node;
         tail = node;
         node.nextNode = head;
      } else {
         Node tempNode = head;
         node.nextNode = tempNode;
         head = node;
         tail.nextNode = node;
      }
      size++;   
   }
   public void insertEnd(int data) {
      if(size==0) {
         insertStart(data);
      } else {
         Node node = new Node();
         tail.nextNode =node;
         tail = node; 
         tail.nextNode = head;
         size++;   
      }
   }
	public static void main(String args[]) {
      CircularLinked dl = new CircularLinked();
      dl.insertStart(10);
      dl.insertStart(20);
      dl.insertStart(30);
      dl.insertStart(1);
      dl.insertStart(56);
      dl.insertStart(40);
      dl.printData();
   }			
}

輸出

40 56 1 30 20 10

Java資料結構 - Set介面

Set是一個無序的集合，不允許重複元素。它模擬了數學集合的抽象概念。當我們向其中新增元素時，它會動態增長。Set類似於陣列。

Set介面

Set是一個不能包含重複元素的集合。它模擬了數學集合的抽象概念。

Set介面僅包含從Collection繼承的方法，並增加了禁止重複元素的限制。

Set還在equals和hashCode操作的行為上增加了更嚴格的約定，允許即使Set例項的實現型別不同，也可以有意義地進行比較。

Set宣告的方法總結在下表中：

示例

Set在HashSet、TreeSet、LinkedHashSet等多個類中都有實現。以下是一個解釋Set功能的示例：

import java.util.*;
public class SetDemo {
   
   public static void main(String args[]) {
      int count[] = {34, 22,10,60,30,22};
      Set<Integer> set = new HashSet<Integer>();
      try {
         for(int i = 0; i < 5; i++) {
            set.add(count[i]);
         }
         System.out.println(set);

         TreeSet sortedSet = new TreeSet<Integer>(set);
         System.out.println("The sorted list is:");
         System.out.println(sortedSet);

         System.out.println("The First element of the set is: "+ (Integer)sortedSet.first());
         System.out.println("The last element of the set is: "+ (Integer)sortedSet.last());
      }
      catch(Exception e) {}
   }
} 

輸出

[34, 22, 10, 60, 30]
The sorted list is:
[10, 22, 30, 34, 60]
The First element of the set is: 10
The last element of the set is: 60

Java資料結構 - 建立Set

java.util包中的Set介面表示Java中的集合。HashSet和LinkedHashSet類實現了此介面。

要建立一個集合（物件），需要例項化這兩個類中的一個。

Set set = new HashSet();

示例

import java.util.HashSet;
import java.util.Set;

public class CreatingSet {
   public static void main(String args[]) {      
      Set set = new HashSet();      
      set.add(100);
      set.add(501);
      set.add(302);
      set.add(420);
      System.out.println("Contents of the set are: "+set);	   
   }
}

輸出

Contents of the set are: [100, 420, 501, 302]

向 Set 新增元素

可以使用Set介面的add()方法向集合中新增元素。此方法接受一個元素作為引數，並將給定的元素/物件新增到集合中。

示例

import java.util.HashSet;
import java.util.Set;

public class CreatingSet {
   public static void main(String args[]) {      
      Set set = new HashSet();      
      set.add(100);
      set.add(501);
      set.add(302);
      set.add(420);
      System.out.println("Contents of the set are: "+set);	   
   }
}

輸出

Contents of the set are: [100, 420, 501, 302]

從 Set 中刪除元素

Set介面的remove()方法接受一個元素作為引數，並將其從當前集合中刪除。

可以使用此方法從集合中移除元素。

示例

import java.util.HashSet;
import java.util.Set;

public class RemovingElements {
   public static void main(String args[]) {
      Set set = new HashSet();      
      set.add(100);
      set.add(501);
      set.add(302);
      set.add(420);
      System.out.println("Contents of the set are: "+set);

      set.remove(100);
      System.out.println("Contents of the set after removing one element : "+set);
   }
}

輸出

Contents of the set are: [100, 420, 501, 302]
Contents of the set after removing one element : [420, 501, 302]

Java資料結構 - 遍歷Set

Set介面繼承了Iterator介面，因此它提供了iterator()方法。此方法返回當前集合的迭代器物件。

迭代器物件允許呼叫兩個方法：

• hasNext() - 此方法驗證當前物件是否包含更多元素，如果包含則返回true。

• next() - 此方法返回當前物件的下一個元素。

使用這兩個方法，可以在Java中遍歷Set。

示例

import java.util.HashSet;
import java.util.Iterator;
import java.util.Set;

public class LoopThroughSet {
   public static void main(String args[]) {      
      Set set = new HashSet();      
      set.add(100);
      set.add(501);
      set.add(302);
      set.add(420);
      System.out.println("Contents of the set are: ");
      Iterator iT = set.iterator();
      
      while( iT.hasNext()) {
         System.out.println(iT.next());     	  
      }   
   }
}

輸出

Contents of the set are: 
100
420
501
302

Java資料結構 - 合併兩個Set

Set介面提供了一個名為addAll()的方法（從Collection介面繼承），可以使用此方法將一個集合的內容新增到另一個集合中。

示例

import java.util.HashSet;
import java.util.Iterator;
import java.util.Set;

public class AddingTwoSets {
   public static void main(String args[]) {
      Set set1 = new HashSet();      
      set1.add(100);
      set1.add(501);
      set1.add(302);
      set1.add(420);
      System.out.println("Contents of set1 are: ");
      System.out.println(set1); 

      Set set2 = new HashSet();      
      set2.add(200);
      set2.add(630);
      set2.add(987);
      set2.add(665);
      System.out.println("Contents of set2 are: ");
      System.out.println(set2); 
      
      set1.addAll(set2);
      System.out.println("Contents of set1 after addition: ");
      System.out.println(set1);
   }
}

輸出

Contents of set1 are: 
[100, 420, 501, 302]
Contents of set2 are: 
[630, 200, 665, 987]
Contents of set1 after addition: 
[100, 420, 501, 630, 200, 665, 987, 302]

Java資料結構 - 兩個Set的差集

假設我們透過新增兩個（或更多）集合的內容來建立一個集合物件，當需要從該集合中完全移除特定集合的內容時，可以使用removeAll()方法。

此方法屬於Set介面，它繼承自Collection介面。它接受一個集合物件，並一次性將它的內容從當前Set（物件）中完全移除。

示例

import java.util.HashSet;
import java.util.Set;

public class SubtractingTwoSets {
   public static void main(String args[]) {      
      Set set1 = new HashSet();      
      set1.add(100);
      set1.add(501);
      set1.add(302);
      set1.add(420);
      System.out.println("Contents of set1 are: ");
      System.out.println(set1); 

      Set set2 = new HashSet();      
      set2.add(200);
      set2.add(630);
      set2.add(987);
      set2.add(665);
      System.out.println("Contents of set2 are: ");
      System.out.println(set2); 
      
      set1.addAll(set2);
      System.out.println("Contents of set1 after addition: ");
      System.out.println(set1);
      
      set1.removeAll(set2);
      System.out.println("Contents of set1 after removal");
      System.out.println(set1);
   }
}

輸出

Contents of set1 are: 
[100, 420, 501, 302]
Contents of set2 are: 
[630, 200, 665, 987]
Contents of set1 after addition: 
[100, 420, 501, 630, 200, 665, 987, 302]
Contents of set1 after removal
[100, 420, 501, 302]

Java資料結構 - Dictionary類

Dictionary類是一個抽象類，它表示儲存鍵值對的資料結構。其中的每個鍵都與一個值相關聯，可以使用其各自的鍵檢索這些值。

因此，像對映一樣，字典也可以理解（認為）為鍵值對的列表。

Java中的Dictionary類

Dictionary是一個抽象類，表示鍵值儲存庫，其操作方式與Map非常相似。

給定鍵和值，可以在Dictionary物件中儲存該值。儲存值後，可以使用其鍵檢索它。因此，像對映一樣，字典可以被認為是鍵值對的列表。

Dictionary定義的抽象方法如下：

Dictionary 類已過時。應實現 Map 介面以獲得鍵值儲存功能。

示例

package com.tutorialspoint;

import java.util.*;

public class DictionaryDemo {
   public static void main(String[] args) {

      // create a new hasthtable
      Dictionary d = new Hashtable();

      // put some elements
      d.put("1", "Chocolate");
      d.put("2", "Cocoa");
      d.put("5", "Coffee");

      // print how many times put was called
     System.out.println("Number of times put was called:" + d.size());
   }
}

輸出

Number of times put was called:3

Java 資料結構 - 建立字典

由於 Dictionary 是一個抽象類，因此不能直接例項化它。HashTable 類是 Dictionary 類的子類。因此，您可以透過例項化此類來建立字典物件。

Dictionary dic = new Hashtable();

示例

import java.util.Hashtable;
import java.util.Dictionary;

public class CreatingDictionary {
   public static void main(String args[]) {
      Dictionary dic = new Hashtable();
      dic.put("Ram", 94.6);
      dic.put("Rahim", 92);
      dic.put("Robert", 85);
      dic.put("Roja", 93);
      dic.put("Raja", 75);
      System.out.println(dic);    		  
   }
}

輸出

{Rahim = 92, Roja = 93, Raja = 75, Ram = 94.6, Robert = 85}

向字典新增元素

Dictionary 類提供了一個名為 put() 的方法，此方法接受鍵值對（物件）作為引數並將其新增到字典中。

您可以使用此方法向字典中新增元素。

示例

import java.util.Hashtable;
import java.util.Dictionary;

public class CreatingDictionary {
   public static void main(String args[]) {
      Dictionary dic = new Hashtable();
      dic.put("Ram", 94.6);
      dic.put("Rahim", 92);
      dic.put("Robert", 85);
      dic.put("Roja", 93);
      dic.put("Raja", 75);
      System.out.println(dic);    		  
   }
}

輸出

{Rahim = 92, Roja = 93, Raja = 75, Ram = 94.6, Robert = 85}

從字典中刪除元素

您可以使用字典類的 remove() 方法刪除字典中的元素。此方法接受鍵或鍵值對並刪除相應的元素。

dic.remove("Ram");
or
dic.remove("Ram", 94.6);

示例

import java.util.Hashtable;
import java.util.Dictionary;

public class RemovingElements {
   public static void main(String args[]) {
      Dictionary dic = new Hashtable();
      dic.put("Ram", 94.6);
      dic.put("Rahim", 92);
      dic.put("Robert", 85);
      dic.put("Roja", 93);
      dic.put("Raja", 75);

      System.out.println("Contents of the hash table :"+dic); 
      dic.remove("Ram");
      System.out.println("Contents of the hash table after deleting specified elements :"+dic); 
   }
}

輸出

Contents of the hash table :{Rahim = 92, Roja = 93, Raja = 75, Ram = 94.6, Robert = 85}
Contents of the hash table after deleting specified elements :{Rahim = 92, Roja = 93, Raja = 75, Robert = 85}

檢索字典中的值

您可以使用 Dictionary 類的 get() 方法檢索特定鍵的值。如果將特定元素的鍵作為此方法的引數傳遞，則它將返回指定鍵的值（作為物件）。如果字典在指定的鍵下不包含任何元素，則返回 null。

您可以使用此方法檢索字典中的值。

示例

import java.util.Hashtable;
import java.util.Dictionary;

public class RetrievingElements {
   public static void main(String args[]) {
      Dictionary dic = new Hashtable();
      dic.put("Ram", 94.6);
      dic.put("Rahim", 92);
      dic.put("Robert", 85);
      dic.put("Roja", 93);
      dic.put("Raja", 75);      
      Object ob = dic.get("Ram");
      System.out.println("Value of the specified key :"+ ob);            
   }
}

輸出

Value of the specified key :94.6

遍歷字典

Dictionary 類提供了一個名為 keys() 的方法，該方法返回一個列舉物件，其中包含雜湊表中的所有鍵。

使用此方法獲取鍵，並使用 get() 方法檢索每個鍵的值。

Enumeration（介面）的 hasMoreElements() 方法如果列舉物件還有更多元素則返回 true。您可以使用此方法執行迴圈。

示例

import java.util.Enumeration;
import java.util.Hashtable;
import java.util.Dictionary;

public class Loopthrough {
   public static void main(String args[]) {
      String str;
      Dictionary dic = new Hashtable();
      dic.put("Ram", 94.6);
      dic.put("Rahim", 92);
      dic.put("Robert", 85);
      dic.put("Roja", 93);
      dic.put("Raja", 75);
      
      Enumeration keys = dic.keys();
      System.out.println("Contents of the hash table are :");
      
      while(keys.hasMoreElements()) {
         str = (String) keys.nextElement();
         System.out.println(str + ": " + dic.get(str));
      }       
   }
}

輸出

Contents of the hash table are :
Rahim: 92
Roja: 93
Raja: 75
Ram: 94.6
Robert: 85

Java 資料結構 - HashTable 類

雜湊表是一種以關聯方式儲存資料的資料結構。在雜湊表中，資料以陣列格式儲存，其中每個資料值都有其自己的唯一索引值。如果我們知道所需資料的索引，則資料訪問速度非常快。

因此，它成為一個數據結構，其中插入和搜尋操作非常快，而不管資料的大小如何。雜湊表使用陣列作為儲存介質，並使用雜湊技術生成要插入元素或從中定位元素的索引。

Java 的 HashTable 類

Hashtable 是最初的 java.util 的一部分，它是 Dictionary 的具體實現。

但是，Java 2 重新設計了 Hashtable，使其也實現了 Map 介面。因此，Hashtable 現在已整合到集合框架中。它類似於 HashMap，但它是同步的。

與 HashMap 一樣，Hashtable 在雜湊表中儲存鍵值對。使用 Hashtable 時，您指定用作鍵的物件以及要連結到該鍵的值。然後對鍵進行雜湊處理，生成的雜湊程式碼用作在表中儲存值的索引。

以下是 HashTable 類提供的建構函式列表。

除了 Map 介面定義的方法外，Hashtable 還定義了以下方法

示例

以下程式演示了此資料結構支援的幾種方法

import java.util.*;
public class HashTableDemo {
   public static void main(String args[]) {
      
      // Create a hash map
      Hashtable balance = new Hashtable();
      Enumeration names;
      String str;
      double bal;
      
      balance.put("Zara", new Double(3434.34));
      balance.put("Mahnaz", new Double(123.22));
      balance.put("Ayan", new Double(1378.00));
      balance.put("Daisy", new Double(99.22));
      balance.put("Qadir", new Double(-19.08));

      // Show all balances in hash table.
      names = balance.keys();
      
      while(names.hasMoreElements()) {
         str = (String) names.nextElement();
         System.out.println(str + ": " + balance.get(str));
      }        
      System.out.println();
      
      // Deposit 1,000 into Zara's account
      bal = ((Double)balance.get("Zara")).doubleValue();
      balance.put("Zara", new Double(bal + 1000));
      System.out.println("Zara's new balance: " + balance.get("Zara"));
   }
}

輸出

Qadir: -19.08
Zara: 3434.34
Mahnaz: 123.22
Daisy: 99.22
Ayan: 1378.0

Zara's new balance: 4434.34

Java 資料結構 - 建立雜湊表

Java 包 java.util 提供了一個名為 HashTable 的類，它表示雜湊表。這儲存鍵值對，使用 Hashtable 時，您指定用作鍵的物件以及要連結到該鍵的值。然後對鍵進行雜湊處理，生成的雜湊程式碼用作在表中儲存值的索引。

您可以透過例項化 HashTable 類來建立雜湊表。

HashTable hashTable = new HashTable();

示例

import java.util.Hashtable;

public class CreatingHashTable {
   public static void main(String args[]) {
      Hashtable hashTable = new Hashtable();
      hashTable.put("Ram", 94.6);
      hashTable.put("Rahim", 92);
      hashTable.put("Robert", 85);
      hashTable.put("Roja", 93);
      hashTable.put("Raja", 75);
      System.out.println(hashTable);    		  
   }
}

輸出

{Rahim = 92, Roja = 93, Raja = 75, Ram = 94.6, Robert = 85}

向雜湊表新增元素

HashTable 類提供了一個名為 put() 的方法，此方法接受鍵值對（物件）作為引數並將其新增到當前雜湊表中。

您可以使用此方法將鍵值對新增到當前雜湊表中。

示例

import java.util.Hashtable;

public class CreatingHashTable {
   public static void main(String args[]) {
      Hashtable hashTable = new Hashtable();
      hashTable.put("Ram", 94.6);
      hashTable.put("Rahim", 92);
      hashTable.put("Robert", 85);
      hashTable.put("Roja", 93);
      hashTable.put("Raja", 75);
      System.out.println(hashTable);    		  
   }
}

輸出

{Rahim = 92, Roja = 93, Raja = 75, Ram = 94.6, Robert = 85}

從雜湊表中刪除元素

您可以刪除雜湊表中的元素，您可以使用 HashTable 類的 remove() 方法。

對於此方法，您需要傳遞鍵或鍵值對以刪除所需的元素。

hashTable.remove("Ram");
or
hashTable.remove("Ram", 94.6);

示例

import java.util.Hashtable;

public class RemovingElements {
   public static void main(String args[]) {
      Hashtable hashTable = new Hashtable();
      hashTable.put("Ram", 94.6);
      hashTable.put("Rahim", 92);
      hashTable.put("Robert", 85);
      hashTable.put("Roja", 93);
      hashTable.put("Raja", 75);

      System.out.println("Contents of the hash table :"+hashTable); 
      hashTable.remove("Ram");
      System.out.println("Contents of the hash table after deleting the specified elements :"+hashTable); 
   }
}

輸出

Contents of the hash table :{Rahim = 92, Roja = 93, Raja = 75, Ram = 94.6, Robert = 85}
Contents of the hash table after deleting the specified elements :{Rahim = 92, Roja = 93, Raja = 75, Robert = 85}

檢索雜湊表中的值

您可以使用 get() 方法檢索特定鍵的值。如果將特定元素的鍵作為此方法的引數傳遞，則它將返回指定鍵的值（作為物件）。如果雜湊表在指定的鍵下不包含任何元素，則返回 null。

您可以使用此方法檢索雜湊表中的值。

示例

import java.util.Hashtable;
public class RetrievingElements {
   public static void main(String args[]) {
      Hashtable hashTable = new Hashtable();
      hashTable.put("Ram", 94.6);
      hashTable.put("Rahim", 92);
      hashTable.put("Robert", 85);
      hashTable.put("Roja", 93);
      hashTable.put("Raja", 75);      
      
      Object ob = hashTable.get("Ram");
      System.out.println("Value of the specified key :"+ ob);            
   }
}

輸出

Value of the specified key :94.6

遍歷雜湊表

HashTable 類提供了一個名為 keys() 的方法，該方法返回一個列舉物件，其中包含雜湊表中的所有鍵。

使用此方法獲取鍵，並使用 get() 方法檢索每個鍵的值。

Enumeration（介面）的 hasMoreElements() 方法如果列舉物件還有更多元素則返回 true。您可以使用此方法執行迴圈。

示例

import java.util.Enumeration;
import java.util.Hashtable;

public class Loopthrough {
   public static void main(String args[]) {
      String str;
      Hashtable hashTable = new Hashtable();
      hashTable.put("Ram", 94.6);
      hashTable.put("Rahim", 92);
      hashTable.put("Robert", 85);
      hashTable.put("Roja", 93);
      hashTable.put("Raja", 75);
      
      Enumeration keys = hashTable.keys();
      System.out.println("Contents of the hash table are :");
      
      while(keys.hasMoreElements()) {
         str = (String) keys.nextElement();
         System.out.println(str + ": " + hashTable.get(str));
      }       
   }
}

輸出

Contents of the hash table are :
Rahim: 92
Roja: 93
Raja: 75
Ram: 94.6
Robert: 85

合併兩個雜湊表

HashTable 類的 putAll() 方法接受一個 map 物件作為引數，將其所有內容新增到當前雜湊表中並返回結果。

使用此方法，您可以合併兩個雜湊表的內容。

示例

import java.util.Hashtable;

public class JoiningTwoHashTables {
   public static void main(String args[]) {
      String str;
      Hashtable hashTable1 = new Hashtable();
      hashTable1.put("Ram", 94.6);
      hashTable1.put("Rahim", 92);
      hashTable1.put("Robert", 85);
      hashTable1.put("Roja", 93);
      hashTable1.put("Raja", 75);
      
      System.out.println("Contents of the 1st hash table :"+hashTable1);
      
      Hashtable hashTable2 = new Hashtable();
      hashTable2.put("Sita", 84.6);
      hashTable2.put("Gita", 89);
      hashTable2.put("Ramya", 86);
      hashTable2.put("Soumaya", 96);
      hashTable2.put("Sarmista", 92);      
      System.out.println("Contents of the 2nd hash table :"+hashTable2);
      hashTable1.putAll(hashTable2);      
      System.out.println("Contents after joining the two hash tables: "+hashTable1);
   }
}

輸出

Contents of the 1st hash table :{Rahim = 92, Roja = 93, Raja = 75, Ram = 94.6, Robert = 85}
Contents of the 2nd hash table :{Sarmista = 92, Soumaya = 96, Sita = 84.6, Gita = 89, Ramya = 86}
Contents after joining the two hash tables: {Soumaya = 96, Robert = 85, Ram = 94.6, Sarmista = 92, 
   Raja = 75, Sita = 84.6, Roja = 93, Gita = 89, Rahim = 92, Ramya = 86}

建立二叉樹

樹是一種資料結構，其元素/節點彼此連線，類似於連結串列。但是，與連結串列不同的是，樹是一種非線性資料結構，其中樹中的每個元素/節點都連線到多個節點（以分層方式）。

• 在樹中，沒有任何前置元素的節點，即樹頂部的節點，稱為根節點。每棵樹只包含一個根節點。

• 除根節點外的任何節點都向上有一條邊連線到稱為父節點的節點。

• 由其向下邊連線的給定節點下方的節點稱為其子節點。

• 沒有子節點的節點稱為葉節點。

每個節點最多隻有 0 個、1 個或 2 個子節點的樹稱為二叉樹。二叉樹兼具有序陣列和連結串列的優點，因為搜尋速度與排序陣列一樣快，插入或刪除操作速度與連結串列一樣快。

在 Java 中建立二叉樹

要建立/實現二叉樹，請建立一個 Node 類，該類將儲存int值並保留對每個子節點的引用，建立三個變數。

兩個 Node 型別的變數用於儲存左節點和右節點，一個整數型別的變數用於儲存資料。然後從另一個類嘗試建立節點，這樣在分層方式中，任何節點都不應該超過 2 個子節點。

示例

以下是建立二叉樹的示例，這裡我們建立了一個 Node 類，其中包含資料、左節點和右節點的變數，包括 setter 和 getter 方法來設定和檢索它們的值。

import java.util.LinkedList;
import java.util.Queue;

class Node{
   int data;
   Node leftNode, rightNode;
   
   Node() {
      leftNode = null;
      rightNode = null;     
      this.data = data;
   }
   Node(int data) {
      leftNode = null;
      rightNode = null;     
      this.data = data;
   }   
   int getData() {
      return this.data;	   
   }
   Node getleftNode() {
      return this.leftNode;	   
   }	   
   Node getRightNode() {
      return this.leftNode;	   
   }
   void setData(int data) {
      this.data = data; 
   }		   
   void setleftNode(Node leftNode) {
      this.leftNode = leftNode;	   
   }
   void setRightNode(Node rightNode) {
      this.leftNode = rightNode;	      
   }
}
public class CreatingBinaryTree {
   public static void main(String[] args){
      Node node = new Node(50);
      node.leftNode = new Node(60);
      node.leftNode.leftNode = new Node(45);
      node.leftNode.rightNode = new Node(64);

      node.rightNode = new Node(60);
      node.rightNode.leftNode = new Node(45);
      node.rightNode.rightNode = new Node(64);
      System.out.println("Binary Tree Created Pre-order of its elements is: ");
      preOrder(node);	   
   }
   public static void preOrder(Node root){
      if(root !=null){
         System.out.println(root.data);
         preOrder(root.leftNode);
         preOrder(root.rightNode);    	  
      }
   }
}

輸出

Binary Tree Created Pre-order of its elements is: 
50
60
45
64
60
45
64

向樹中插入鍵

沒有特定的規則將元素插入二叉樹，您可以根據需要插入節點。

插入節點時應記住的唯一一點是，在二叉樹中，每個節點最多隻能有兩個子節點。

因此，要將節點插入樹中，

• 逐層遍歷每個節點，檢查它是否有左節點和右節點。

• 如果任何節點同時具有左節點和右節點，則不能插入另一個節點，因為二叉樹中的節點最多隻能有兩個子節點，將這些值新增到佇列中並繼續。

• 如果任何節點沒有左節點或右節點，則建立一個新節點並將其新增到那裡。

簡而言之，將節點插入沒有左子樹或右子樹或兩者都沒有的父節點。

示例

import java.util.LinkedList;
import java.util.Queue;

class Node{
   int data;
   Node leftNode, rightNode;
   
   Node() {
      leftNode = null;
      rightNode = null;     
      this.data = data;
   }
   Node(int data) {
      leftNode = null;
      rightNode = null;     
      this.data = data;
   }   
   int getData() {
      return this.data;	   
   }
   Node getleftNode() {
      return this.leftNode;	   
   }	   
   Node getRightNode() {
      return this.leftNode;	   
   }
   void setData(int data) {
      this.data = data; 
   }		   
   void setleftNode(Node leftNode) {
      this.leftNode = leftNode;	   
   }
   void setRightNode(Node rightNode) {
      this.leftNode = rightNode;	      
   }
}
public class InsertingElements {
   public static int[] insertElement(int[] myArray, int pos, int data) {
      int j = myArray.length;      
      int lastElement = myArray[j-1];      
	      
      for(int i = (j-2); i >= (pos-1); i--) {
         myArray[i+1] = myArray[i];
      }     
      myArray[pos-1] = data;
      
      int[] resultArray = new int[j+1];      
      for(int i = 0; i < myArray.length; i++) {
         resultArray[i] = myArray[i]; 
      }   
      resultArray[resultArray.length-1] = lastElement;
      return resultArray;
	}
	public static void main(String args[]){
      int[] myArray = {10, 20, 30, 45, 96, 66};      
      int pos = 3;
      int data = 10005;
      int[] result = insertElement(myArray, pos, data);   
      
      for(int i = 0; i < result.length; i++){
         System.out.println(result[i]);
      }   
   }
}

輸出

10
20
10005
30
45
96
66

樹的中序遍歷

在此遍歷方法中，首先訪問左子樹，然後訪問根，最後訪問右子樹。我們應該始終記住，每個節點本身都可以表示一個子樹。

如果以中序遍歷二叉樹，則輸出將以升序產生排序的鍵值。

我們從A開始，按照中序遍歷，我們移動到它的左子樹B。B也以中序遍歷。這個過程一直持續到訪問所有節點。這棵樹的中序遍歷輸出將是：

D → B → E → A → F → C → G

演算法

直到所有節點都被遍歷：

Step 1: Recursively traverse left subtree.
Step 2: Visit root node.
Step 3: Recursively traverse right subtree.

示例

class Node{
   int data;
   Node leftNode, rightNode;
   
   Node() {
      leftNode = null;
      rightNode = null;     
      this.data = data;
   }
   Node(int data) {
      leftNode = null;
      rightNode = null;     
      this.data = data;
   }
   int getData() {
      return this.data;	   
   }
   Node getleftNode() {
      return this.leftNode;      
   }
   Node getRightNode() {
      return this.leftNode;      
   }
   void setData(int data) {
      this.data = data; 
   }
   void setleftNode(Node leftNode) {
      this.leftNode = leftNode;      
   }
   void setRightNode(Node rightNode) {
      this.leftNode = rightNode;         
   }
}
public class InOrderBinaryTree {
   public static void main(String[] args) {
      Node node = new Node(50);
      node.leftNode = new Node(60);
      node.leftNode.leftNode = new Node(45);
      node.leftNode.rightNode = new Node(64);

      node.rightNode = new Node(60);
      node.rightNode.leftNode = new Node(45);
      node.rightNode.rightNode = new Node(64);
      System.out.println("inorder arrangement of given elements: ");
      inOrder(node);
   }
   public static void inOrder(Node root) {
      if(root !=null) {
         inOrder(root.leftNode);
         System.out.println(root.data);
         inOrder(root.rightNode);         
      }
   }
}

輸出

inorder arrangement of given elements: 
45
60
64
50
45
60
64

樹的前序遍歷

在此遍歷方法中，首先訪問根節點，然後訪問左子樹，最後訪問右子樹。

我們從A開始，按照前序遍歷，我們首先訪問A本身，然後移動到它的左子樹B。B也以前序遍歷。這個過程一直持續到訪問所有節點。這棵樹的前序遍歷輸出將是：

A → B → D → E → C → F → G

演算法

直到所有節點都被遍歷：

Step 1: Visit root node.
Step 2: Recursively traverse left subtree.
Step 3: Recursively traverse right subtree.

示例

class Node{
   int data;
   Node leftNode, rightNode;
   
   Node() {
      leftNode = null;
      rightNode = null;     
      this.data = data;
   }
   Node(int data) {
      leftNode = null;
      rightNode = null;     
      this.data = data;
   }
   int getData() {
      return this.data;	   
   }
   Node getleftNode() {
      return this.leftNode;      
   }
   Node getRightNode() {
      return this.leftNode;      
   }
   void setData(int data) {
      this.data = data; 
   }
   void setleftNode(Node leftNode) {
      this.leftNode = leftNode;      
   }
   void setRightNode(Node rightNode) {
      this.leftNode = rightNode;         
   }
}
public class PreOrderBinaryTree {
   public static void main(String[] args) {
      Node node = new Node(50);
      node.leftNode = new Node(60);
      node.leftNode.leftNode = new Node(45);
      node.leftNode.rightNode = new Node(64);

      node.rightNode = new Node(60);
      node.rightNode.leftNode = new Node(45);
      node.rightNode.rightNode = new Node(64);
      System.out.println("pre-order arrangement of given elements: ");
      preOrder(node);
   }   
   public static void preOrder(Node root) {
      if(root !=null) {
         System.out.println(root.data);
         preOrder(root.leftNode);
         preOrder(root.rightNode);         
      }
   }
}

輸出

pre-order arrangement of given elements: 
50
60
45
64
60
45
64

樹的後序遍歷

在此遍歷方法中，根節點最後訪問，因此得名。我們首先遍歷左子樹，然後遍歷右子樹，最後遍歷根節點。

我們從A開始，按照後序遍歷，首先訪問左子樹B。B也進行後序遍歷。這個過程持續到所有節點都被訪問為止。這個樹的後序遍歷輸出結果是：

D → E → B → F → G → C → A

演算法

直到所有節點都被遍歷：

Step 1 − Recursively traverse left subtree.
Step 2 − Recursively traverse right subtree.
Step 3 − Visit root node.

示例

class Node{
   int data;
   Node leftNode, rightNode;
   Node() {
      leftNode = null;
      rightNode = null;     
      this.data = data;
   }
   Node(int data) {
      leftNode = null;
      rightNode = null;     
      this.data = data;
   }
   int getData() {
      return this.data;	   
   }
   Node getleftNode() {
      return this.leftNode;      
   }
   Node getRightNode() {
      return this.leftNode;      
   }
   void setData(int data) {
      this.data = data; 
   }
   void setleftNode(Node leftNode) {
      this.leftNode = leftNode;      
   }
   void setRightNode(Node rightNode) {
      this.leftNode = rightNode;         
   }
}
public class PostOrderBinaryTree {
   public static void main(String[] args) {
      Node node = new Node(50);
      node.leftNode = new Node(60);
      node.leftNode.leftNode = new Node(45);
      node.leftNode.rightNode = new Node(64);

      node.rightNode = new Node(60);
      node.rightNode.leftNode = new Node(45);
      node.rightNode.rightNode = new Node(64);
   
      System.out.println("post-order arrangement of given elements: ");
      postOrder(node);
   }   
   public static void postOrder(Node root) {
      if(root !=null) {
         postOrder(root.leftNode);
         postOrder(root.rightNode);    
         System.out.println(root.data);
      }
   }  
}

輸出

post-order arrangement of given elements: 
45
64
60
45
64
60
50

搜尋樹中的最小值

要查詢一棵樹的最小值（無子節點），比較左節點和右節點，取較大值（儲存在max中），然後將其與根節點的值進行比較。

如果結果（min）較小，則它是最小值；否則，根節點是樹的最小值。

要獲取整個二叉樹的最小值，獲取左子樹的最小值、右子樹的最小值和根節點的值。現在比較這三個值，其中較小的值就是樹的最小值。

示例

class Node{
   int data;
   Node leftNode, rightNode;
   
   Node() {
      leftNode = null;
      rightNode = null;     
      this.data = data;
   }
   Node(int data) {
      leftNode = null;
      rightNode = null;     
      this.data = data;
   }
   int getData() {
      return this.data;	   
   }
   Node getleftNode() {
      return this.leftNode;      
   }
   Node getRightNode() {
      return this.leftNode;      
   }
   void setData(int data) {
      this.data = data; 
   }
   void setleftNode(Node leftNode) {
      this.leftNode = leftNode;      
   }
   void setRightNode(Node rightNode) {
      this.leftNode = rightNode;         
   }
}
public class MinValueInBinaryTree {
   public static void main(String[] args) {
      Node node = new Node(50);
      node.leftNode = new Node(60);
      node.leftNode.leftNode = new Node(45);
      node.leftNode.rightNode = new Node(64);

      node.rightNode = new Node(60);
      node.rightNode.leftNode = new Node(45);
      node.rightNode.rightNode = new Node(64);
      
      System.out.println("Minimum value is "+minimumValue(node));
   }   
   public static int minimumValue(Node root) {
      int min = 10000;      
      
      if(root!=null) {
         int lMin = minimumValue(root.leftNode);
         int rMin = minimumValue(root.rightNode);;
   
         if(lMin>rMin) {
            min = lMin;
         } else {
            min = rMin;           
         }

         if(root.data<min) {
            min = root.data;
         }
      }
      return min;
   }
}

輸出

Minimum value is 50

搜尋樹中的最大值

要查詢一棵樹的最大值（無子節點），比較左節點和右節點，取較大值（儲存在max中），然後將其與根節點的值進行比較。

如果結果（max）較大，則它是樹的最大值；否則，根節點是樹的最大值。

要獲取整個二叉樹的最大值，獲取左子樹的最大值、右子樹的最大值和根節點的值。現在比較這三個值，其中較大的值就是樹的最大值。

示例

class Node{
   int data;
   Node leftNode, rightNode;
   
   Node() {
      leftNode = null;
      rightNode = null;     
      this.data = data;
   }
   Node(int data) {
      leftNode = null;
      rightNode = null;     
      this.data = data;
   }
   int getData() {
      return this.data;	   
   }
   Node getleftNode() {
      return this.leftNode;      
   }
   Node getRightNode() {
      return this.leftNode;      
   }
   void setData(int data) {
      this.data = data; 
   }
   void setleftNode(Node leftNode) {
      this.leftNode = leftNode;      
   }
   void setRightNode(Node rightNode) {
      this.leftNode = rightNode;         
   }
}
public class MaxValueInBinaryTree {
   public static void main(String[] args){
      Node node = new Node(50);
      node.leftNode = new Node(60);
      node.leftNode.leftNode = new Node(45);
      node.leftNode.rightNode = new Node(64);

      node.rightNode = new Node(60);
      node.rightNode.leftNode = new Node(45);
      node.rightNode.rightNode = new Node(64);
     
      System.out.println("Maximum value is "+maximumValue(node));
   }
   public static int maximumValue(Node root) {
      int max = 0;      
      
      if(root!=null) {
         int lMax = maximumValue(root.leftNode);
         int rMax = maximumValue(root.rightNode);;

         if(lMax>rMax){
            max = lMax;
         } else {
            max = rMax;           
         }

         if(root.data>max) {
            max = root.data;
         }
      }
      return max;
   }
}

輸出

Maximum value is 64

在樹中搜索值

要搜尋給定樹是否包含特定元素。將其與樹中的每個元素進行比較，如果找到，則顯示一條訊息，說明找到了元素。

示例

class Node{
   int data;
   Node leftNode, rightNode;
   
   Node() {
      leftNode = null;
      rightNode = null;     
      this.data = data;
   }
   Node(int data) {
      leftNode = null;
      rightNode = null;     
      this.data = data;
   }   
   int getData() {
      return this.data;	   
   }
   Node getleftNode() {
      return this.leftNode;	   
   }	   
   Node getRightNode() {
      return this.leftNode;	   
   }
   void setData(int data) {
      this.data = data; 
   }		   
   void setleftNode(Node leftNode) {
      this.leftNode = leftNode;	   
   }
   void setRightNode(Node rightNode) {
      this.leftNode = rightNode;	      
   }
}
public class SeachingValue {
   public static void main(String[] args) {
      Node node = new Node(50);
      node.leftNode = new Node(60);
      node.leftNode.leftNode = new Node(45);
      node.leftNode.rightNode = new Node(64);

      node.rightNode = new Node(60);
      node.rightNode.leftNode = new Node(45);
      node.rightNode.rightNode = new Node(64);
      
      System.out.println("Pre order of the above created tree :");
      preOrder(node);
      System.out.println();
      int data = 60;
      boolean b = find(node, data);
      
      if(b) {
         System.out.println("Element found");    	  
      } else {
         System.out.println("Element not found");
      }
   }
   public static void preOrder(Node root) {
      if(root !=null) {
         System.out.print(root.data+" ");
         preOrder(root.leftNode);
         preOrder(root.rightNode);    	  
      }
   }
   public static boolean find(Node root, int data) {
      if(root == null) {
         return false;    	  
      }
      if(root.getData() == data) {
         return true;    	  
      }
      return find(root.getleftNode(), data)||find(root.getRightNode(), data);
   }		
}

輸出

Pre order of the above created tree :
50 60 45 64 60 45 64 
Element found

刪除樹中的葉子節點

遍歷樹中的每個節點，驗證它是否有左子節點、右子節點或兩者都有。如果它沒有任何子節點，則刪除該特定節點。

示例

class Node{
   int data;
   Node leftNode, rightNode;
   
   Node() {
      leftNode = null;
      rightNode = null;     
      this.data = data;
   }
   Node(int data) {
      leftNode = null;
      rightNode = null;     
      this.data = data;
   }   
   int getData() {
      return this.data;	   
   }
   Node getleftNode() {
      return this.leftNode;	   
   }	   
   Node getRightNode() {
      return this.leftNode;	   
   }
   void setData(int data) {
      this.data = data; 
   }		   
   void setleftNode(Node leftNode) {
      this.leftNode = leftNode;	   
   }
   void setRightNode(Node rightNode) {
      this.leftNode = rightNode;	      
   }
}
public class RemovingLeaf {
   public static void main(String[] args) {
      Node node = new Node(50);
      node.leftNode = new Node(60);
      node.leftNode.leftNode = new Node(45);
      node.leftNode.rightNode = new Node(64);

      node.rightNode = new Node(60);
      node.rightNode.leftNode = new Node(45);
      node.rightNode.rightNode = new Node(64);
      
      node.leftNode.leftNode.leftNode = new Node(96);
      System.out.println("Contents of the tree:");
      preOrder(node);	   
      removeLeaves(node);
      System.out.println();
      System.out.println("Contents of the tree after removing leafs:");
      preOrder(node);
   }
   public static void removeLeaves(Node node) {
      if (node.leftNode != null) { // tests left root
         if (node.leftNode.leftNode == null && node.leftNode.rightNode == null) { 
            node.leftNode = null; // delete
         } else {
            removeLeaves(node.leftNode);
         }
      }
   }
   public static void preOrder(Node root) {
      if(root !=null) {
         System.out.print(root.data+" ");
         preOrder(root.leftNode);
         preOrder(root.rightNode);    	  
      }      	   
   }
}

輸出

Contents of the tree:
50 60 45 96 64 60 45 64 
Contents of the tree after removing leafs:
50 60 45 64 60 45 64

Java資料結構 - AVL樹

如果二叉搜尋樹的輸入以排序（升序或降序）的方式出現會怎樣？它將如下所示：

可以觀察到，BST的最壞情況效能最接近線性搜尋演算法，即Ο(n)。在即時資料中，我們無法預測資料模式及其頻率。因此，需要平衡現有的BST。

以其發明者Adelson、Velski和Landis的名字命名，AVL樹是高度平衡的二叉搜尋樹。AVL樹檢查左右子樹的高度，並確保其差值不超過1。這個差值稱為平衡因子。

在這裡，我們看到第一棵樹是平衡的，接下來的兩棵樹是不平衡的：

在第二棵樹中，C的左子樹高度為2，右子樹高度為0，因此差值為2。在第三棵樹中，A的右子樹高度為2，而左子樹缺失，因此為0，差值再次為2。AVL樹只允許差值（平衡因子）為1。

BalanceFactor = height(left-sutree) − height(right-sutree)

如果左右子樹的高度差大於1，則使用一些旋轉技術來平衡樹。

AVL旋轉Java

為了平衡自身，AVL樹可以執行以下四種旋轉：

• 左旋轉
• 右旋轉
• 左-右旋轉
• 右-左旋轉

前兩種旋轉是單旋轉，後兩種旋轉是雙旋轉。要使樹不平衡，至少需要高度為2的樹。透過這棵簡單的樹，讓我們逐一瞭解它們。

左旋轉

如果在右子樹的右子樹中插入節點時樹變得不平衡，則執行單左旋轉：

在我們的示例中，節點A變得不平衡，因為在A的右子樹中插入了一個節點。我們透過使A成為B的左子樹來執行左旋轉。

右旋轉

如果在左子樹的左子樹中插入節點，則AVL樹可能變得不平衡。然後樹需要右旋轉。

如圖所示，透過執行右旋轉，不平衡的節點成為其左子節點的右子節點。

左-右旋轉

雙旋轉是已經解釋過的旋轉版本的稍微複雜一些的版本。為了更好地理解它們，我們應該注意旋轉時執行的每個動作。讓我們首先檢查如何執行左-右旋轉。左-右旋轉是左旋轉後跟右旋轉的組合。

右-左旋轉

第二種雙旋轉是右-左旋轉。它是右旋轉後跟左旋轉的組合。

廣度優先搜尋 (BFS)

圖是物件集合的圖形表示，其中一些物件對透過連結連線。相互連線的物件由稱為頂點的點表示，連線頂點的連結稱為邊。

形式上，圖是一對集合(V, E)，其中V是頂點集合，E是連線頂點對的邊集合。看看下面的圖：

在上圖中，

V = {a, b, c, d, e}

E = {ab, ac, bd, cd, de}

廣度優先搜尋 (BFS)

廣度優先搜尋 (BFS) 演算法以廣度優先的方式遍歷圖，並使用佇列來記住在任何迭代中遇到死衚衕時要開始搜尋的下一個頂點。

如上例所示，BFS演算法首先從A到B到E到F遍歷，然後到C和G，最後到D。它採用以下規則。

• 規則1 - 訪問相鄰的未訪問頂點。將其標記為已訪問。顯示它。將其插入佇列。

• 規則2 - 如果找不到相鄰頂點，則從佇列中刪除第一個頂點。

• 規則3 - 重複規則1和規則2，直到佇列為空。

在這個階段，我們沒有未標記（未訪問）的節點了。但是根據演算法，我們繼續出隊以獲得所有未訪問的節點。當佇列為空時，程式結束。

深度優先搜尋 (DFS)

深度優先搜尋 (DFS) 演算法以深度優先的方式遍歷圖，並使用堆疊來記住在任何迭代中遇到死衚衕時要開始搜尋的下一個頂點。

如上例所示，DFS演算法首先從S到A到D到G到E到B遍歷，然後到F，最後到C。它採用以下規則。

• 規則1 - 訪問相鄰的未訪問頂點。將其標記為已訪問。顯示它。將其壓入堆疊。

• 規則2 - 如果找不到相鄰頂點，則從堆疊中彈出頂點。（它將彈出堆疊中的所有沒有相鄰頂點的頂點。）

• 規則3 - 重複規則1和規則2，直到堆疊為空。

最短路徑演算法

最短路徑演算法是從源節點(S)到目標節點(D)尋找最小成本路徑的方法。在這裡，我們將討論Moore演算法，也稱為廣度優先搜尋演算法。

Moore演算法

• 標記源頂點S，並將其標記為i，並設定i = 0。

• 查詢與標記為i的頂點相鄰的所有未標記頂點。如果沒有頂點連線到頂點S，則頂點D未連線到S。如果有頂點連線到S，則將其標記為i+1。

• 如果D已標記，則轉到步驟4，否則轉到步驟2以增加i = i+1。

• 找到最短路徑的長度後停止。

迪克斯特拉演算法

迪克斯特拉演算法解決有向加權圖G = (V, E)上的單源最短路徑問題，其中所有邊均為非負權值（即，對於每條邊(u, v) Є E，都有w(u, v) ≥ 0）。

在下面的演算法中，我們將使用一個函式Extract-Min()，它提取具有最小鍵值的節點。

演算法：Dijkstra演算法 (G, w, s)

for each vertex v Є G.V  
   v.d := ∞ 
   v.∏ := NIL 
s.d := 0 
S := Ф 
Q := G.V 
while Q ≠ Ф 
   u := Extract-Min (Q) 
   S := S U {u} 
   
   for each vertex v Є G.adj[u] 
      if v.d > u.d + w(u, v) 
         v.d := u.d + w(u, v) 
         v.∏ := u

分析

該演算法的複雜度完全取決於Extract-Min函式的實現。如果使用線性搜尋實現Extract-Min函式，則該演算法的複雜度為O(V² + E)。

在此演算法中，如果我們使用最小堆，Extract-Min()函式作用於最小堆，從Q返回具有最小鍵值的節點，則可以進一步降低該演算法的複雜度。

示例

讓我們考慮頂點1和9分別作為起點和終點頂點。最初，除起點頂點外，所有頂點均標記為∞，起點頂點標記為0。

因此，頂點9到頂點1的最小距離為20。路徑為：

1 → 3 → 7 → 8 → 6 → 9

此路徑是根據前驅資訊確定的。

Bellman-Ford演算法

該演算法求解有向圖G = (V, E)的單源最短路徑問題，其中邊權重可能為負值。此外，如果不存在任何負權環，則可以使用此演算法查詢最短路徑。

演算法：Bellman-Ford演算法 (G, w, s)

for each vertex v Є G.V  
   v.d := ∞ 
   v.∏ := NIL 
s.d := 0 

for i = 1 to |G.V| - 1 
   for each edge (u, v) Є G.E 
      if v.d > u.d + w(u, v) 
         v.d := u.d +w(u, v) 
         v.∏ := u 
for each edge (u, v) Є G.E 
   if v.d > u.d + w(u, v) 
      return FALSE 
return TRUE

分析

第一個for迴圈用於初始化，執行O(V)次。下一個for迴圈對邊進行|V - 1|次遍歷，耗時O(E)。

因此，Bellman-Ford演算法的執行時間為O(V, E)。

示例

以下示例逐步展示了Bellman-Ford演算法的工作原理。此圖具有負邊，但不包含任何負環，因此可以使用此技術解決問題。

在初始化時，除源節點外，所有頂點均標記為∞，源節點標記為0。

第一步，所有從源節點可達的頂點都將更新為最小成本。因此，頂點a和h被更新。

下一步，頂點a, b, f和e被更新。

按照相同的邏輯，在此步驟中，頂點b, f, c和g被更新。

此處，頂點c和d被更新。

因此，頂點s和頂點d之間的最小距離為20。

根據前驅資訊，路徑為s → h → e → g → c → d

最小生成樹 (MST)

在加權圖中，最小生成樹是指權重小於同圖所有其他生成樹的生成樹。在現實情況下，此權重可以衡量為距離、擁塞、交通負荷或分配給邊的任何任意值。

Java中的Prim演算法

Prim演算法（與克魯斯卡爾演算法一樣）用於查詢最小成本生成樹，它使用貪心演算法。Prim演算法與最短路徑優先演算法類似。

與克魯斯卡爾演算法相反，Prim演算法將節點視為單個樹，並不斷從給定圖中向生成樹新增新節點。

為了與克魯斯卡爾演算法進行對比並更好地理解Prim演算法，我們將使用相同的示例：

步驟1 - 刪除所有環和並行邊

從給定圖中刪除所有環和並行邊。對於並行邊，保留關聯成本最低的那一條，刪除所有其他邊。

步驟2 - 選擇任意節點作為根節點

在本例中，我們選擇S節點作為Prim生成樹的根節點。此節點是任意選擇的，因此任何節點都可以作為根節點。有人可能會問為什麼任何影片都可以是根節點。答案是，在生成樹中包含圖的所有節點，並且由於它是連通的，因此必須至少有一條邊將它連線到樹的其餘部分。

步驟3 - 檢查外出邊並選擇成本較低的那條邊

選擇根節點S後，我們看到S,A和S,C是兩條權重分別為7和8的邊。我們選擇邊S,A，因為它小於另一條邊。

現在，樹S-7-A被視為一個節點，我們檢查從中引出的所有邊。我們選擇成本最低的那條邊並將其包含在樹中。

此步驟之後，形成S-7-A-3-C樹。現在，我們將再次將其視為一個節點，並將再次檢查所有邊。但是，我們只選擇成本最低的邊。在本例中，C-3-D是新的邊，它小於其他邊的成本8、6、4等。

將節點D新增到生成樹後，我們現在有兩條從其引出的邊具有相同的成本，即D-2-T和D-2-B。因此，我們可以新增其中任何一條。但是下一步將再次產生邊2作為最低成本。因此，我們顯示包含兩條邊的生成樹。

我們可能會發現，使用兩種不同演算法得到的同一圖的輸出生成樹是相同的。

Java資料結構 - 克魯斯卡爾演算法

克魯斯卡爾演算法使用貪心演算法來查詢最小成本生成樹。此演算法將圖視為森林，並將每個節點都視為單個樹。只有當一條樹的成本在所有可用選項中最低且不違反MST屬性時，它才會連線到另一條樹。

為了理解克魯斯卡爾演算法，讓我們考慮以下示例：

步驟1 - 刪除所有環和並行邊

從給定圖中刪除所有環和並行邊。

對於並行邊，保留關聯成本最低的那一條，刪除所有其他邊。

步驟2 - 按權重遞增順序排列所有邊

下一步是建立一個邊和權重的集合，並按權重（成本）遞增順序排列它們。

步驟3 - 新增權重最低的邊

現在我們開始從權重最低的邊開始向圖中新增邊。在整個過程中，我們將不斷檢查生成樹屬性是否保持不變。如果透過新增一條邊，生成樹屬性不成立，那麼我們將考慮不將該邊包含在圖中。

最低成本為2，相關的邊為B,D和D,T。我們新增它們。新增它們不會違反生成樹屬性，因此我們繼續選擇下一條邊。

下一個成本為3，相關的邊為A,C和C,D。我們再次新增它們：

表中的下一個成本為4，我們觀察到新增它會在圖中建立一個環。

我們忽略它。在此過程中，我們將忽略/避免所有建立環的邊。

我們觀察到成本為5和6的邊也會建立環。我們忽略它們並繼續。

現在只剩下一個節點需要新增。在兩個可用的最低成本邊7和8之間，我們將新增成本為7的邊。

透過新增邊S,A，我們包含了圖的所有節點，現在我們有了最小成本生成樹。

Java資料結構 - 氣泡排序

排序是指以特定格式排列資料。排序演算法指定以特定順序排列資料的方式。最常見的順序是數值順序或字典順序。

排序的重要性在於，如果資料以排序方式儲存，則可以將資料搜尋最佳化到非常高的水平。排序還用於以更易讀的格式表示資料。以下是現實生活中排序的一些示例。

• 電話簿 - 電話簿按姓名排序儲存人們的電話號碼，以便可以輕鬆搜尋姓名。

• 字典 - 字典按字母順序儲存單詞，以便可以輕鬆搜尋任何單詞。

就地排序和非就地排序

排序演算法可能需要一些額外的空間來比較和臨時儲存一些資料元素。這些演算法不需要任何額外空間，排序據說發生在原地，或者例如，在陣列本身內。這稱為就地排序。氣泡排序就是一個就地排序的例子。

但是，在某些排序演算法中，程式需要的空間大於或等於被排序的元素。使用等於或更多空間的排序稱為非就地排序。歸併排序就是一個非就地排序的例子。

Java中的氣泡排序

氣泡排序是一種簡單的排序演算法。這種排序演算法是一種基於比較的演算法，其中比較每對相鄰元素，如果元素沒有按順序排列，則交換元素。這種演算法不適用於大型資料集，因為它的平均和最壞情況複雜度為Ο(n2)，其中n是專案數。

演算法

我們假設list是一個包含n個元素的陣列。我們進一步假設swap()函式交換給定陣列元素的值。

Step 1: Assume i is the first element of the list then, compare the elements i and i+1. (first two elements of the array)
Step 2: If the i (first element) is greater than the second (i+1) swap them.
Step 3: Now, increment the i value and repeat the same.(for 2nd and 3rd elements) 
Step 4: Repeat this till the end of the array.

示例

import java.util.Arrays;
public class BubbleSort {
   public static void main(String args[]) {
      int[] myArray = {10, 20, 65, 96, 56};      
      System.out.println("Contents of the array before sorting : ");
      System.out.println(Arrays.toString(myArray));
      
      int n = myArray.length;
      int temp = 0;
      
      for(int i = 0; i<n-1; i++) {
         for(int j = 0; j<n-1; j++) {
            if (myArray[j] > myArray[j+1]) {
               temp = myArray[i];
               myArray[j] = myArray[j+1];
               myArray[j+1] = temp;
            }
         }         
      }           
      System.out.println("Contents of the array after sorting : ");
      System.out.println(Arrays.toString(myArray));       
   }
}

輸出

Contents of the array before sorting : 
[10, 20, 65, 96, 56]
Contents of the array after sorting : 
[10, 10, 20, 10, 20]

Java資料結構 - 選擇排序

選擇排序是一種簡單的排序演算法。這種排序演算法是一種原地比較排序演算法，它將列表分成兩個部分：左端的有序部分和右端的無序部分。最初，有序部分為空，無序部分是整個列表。

從無序陣列中選擇最小的元素，並將其與最左邊的元素交換，該元素成為有序陣列的一部分。這個過程繼續進行，無序陣列邊界向右移動一個元素。

該演算法不適用於大型資料集，因為它的平均和最壞情況複雜度為Ο(n2)，其中n是專案的數量。

演算法

Step 1: Set MIN to location 0 in the array.
Step 2: Search the minimum element in the list.
Step 3: Swap with value at location MIN.
Step 4: Increment MIN to point to next element.
Step 5: Repeat until list is sorted.

示例

import java.util.Arrays;

public class SelectionSort {
   public static void main(String args[]) {
      int myArray[] =  {10, 20, 25, 63, 96, 57};
      int n = myArray.length;     
      
      System.out.println("Contents of the array before sorting : ");
      System.out.println(Arrays.toString(myArray));

      for (int i=0 ;i< n-1; i++) {
         int min = i;    
         for (int j = i+1; j<n; j++) {
            if (myArray[j] < myArray[min]) { 
               min = j;
            }	     
         }
         int temp = myArray[min];
         myArray[min] = myArray[i];
         myArray[i] = temp; 	   
      }
      System.out.println("Contents of the array after sorting : ");
      System.out.println(Arrays.toString(myArray));      
   }
}

輸出

Contents of the array before sorting : 
[10, 20, 25, 63, 96, 57]
Contents of the array after sorting : 
[10, 20, 25, 57, 63, 96]

Java資料結構 - 插入排序

這是一種原地比較排序演算法。這裡，維護一個子列表，該子列表始終是有序的。例如，陣列的下半部分保持有序。要插入到此有序子列表中的元素必須找到其適當的位置，然後將其插入到該位置。因此得名插入排序。

對陣列進行順序搜尋，並將無序項移動並插入到有序子列表（在同一陣列中）。該演算法不適用於大型資料集，因為它的平均和最壞情況複雜度為Ο(n2)，其中n是專案的數量。

演算法

Step 1: If it is the first element, it is already sorted. return 1;
Step 2: Pick next element.
Step 3: Compare with all elements in the sorted sub-list.
Step 4: Shift all the elements in the sorted sub-list that is greater than the value to be sorted.
Step 5: Insert the value.
Step 6: Repeat until list is sorted.

示例

import java.util.Arrays;

public class InsertionSort {
   public static void main(String args[]) {
      int myArray[] =  {10, 20, 25, 63, 96, 57};
      int size = myArray.length;
      System.out.println("Contents of the array before sorting : ");
      System.out.println(Arrays.toString(myArray));
      
      for (int i = 1 ;i< size; i++) {
         int val = myArray[i];  
         int pos = i;
         
         while(myArray[pos-1]>val && pos>0) {
            myArray[pos] = myArray[pos-1];
            pos = pos-1;
         }
         myArray[pos] = val;
      }
      System.out.println("Contents of the array after sorting : ");
      System.out.println(Arrays.toString(myArray));	  
   }
}

輸出

Contents of the array before sorting : 
[10, 20, 25, 63, 96, 57]
Contents of the array after sorting : 
[10, 20, 25, 57, 63, 96]

Java資料結構 - 歸併排序

歸併排序是一種基於分治技術的排序技術。其最壞情況時間複雜度為Ο(n log n)，是廣受推崇的演算法之一。

歸併排序首先將陣列分成相等的兩半，然後以有序的方式將它們合併。

演算法

歸併排序不斷將列表分成相等的兩半，直到無法再分割為止。根據定義，如果列表中只有一個元素，則它已排序。然後，歸併排序合併較小的已排序列表，同時保持新列表也已排序。

Step 1: if it is only one element in the list it is already sorted, return.
Step 2: divide the list recursively into two halves until it can no more be divided.
Step 3: merge the smaller lists into new list in sorted order.

示例

import java.util.Arrays;

public class MergeSort {
   int[] array = { 10, 14, 19, 26, 27, 31, 33, 35, 42, 44, 0 };   

   public void merge(int low, int mid, int high) {
      int l1, l2, i, b[] = new int[array.length];
      
      for(l1 = low, l2 = mid + 1, i = low; l1 <= mid && l2 <= high; i++) {
         if(array[l1] <= array[l2]) {
         b[i] = array[l1++];
      } else
         b[i] = array[l2++];
      }
       
      while(l1 <= mid) {
         b[i++] = array[l1++];
      }
      while(l2 <= high) { 
         b[i++] = array[l2++];
      }
         for(i = low; i <= high; i++) {
         array[i] = b[i];
      }
   }
   public void sort(int low, int high) {
      int mid;

      if(low < high) {
         mid = (low + high) / 2;
         sort(low, mid);
         sort(mid+1, high);
         merge(low, mid, high);
      } else { 
         return;
      }   
   }
   public static void main(String args[]) {
      MergeSort obj = new MergeSort();
      int max = obj.array.length-1;
      System.out.println("Contents of the array before sorting : ");
      System.out.println(Arrays.toString(obj.array));
      obj.sort(0, max);

      System.out.println("Contents of the array after sorting : ");
      System.out.println(Arrays.toString(obj.array));
   }
}

輸出

[10, 14, 19, 26, 27, 31, 33, 35, 42, 44, 0]
Contents of the array after sorting : 
[0, 10, 14, 19, 26, 27, 31, 33, 35, 42, 44]

Java資料結構 - 快速排序

快速排序是一種高效的排序演算法，它基於將資料陣列劃分成較小的陣列。一個大的陣列被劃分為兩個陣列，一個數組包含小於指定值（例如，樞軸）的值，基於該值進行劃分，另一個數組包含大於樞軸值的值。

快速排序劃分一個數組，然後遞迴呼叫自身兩次以對兩個生成的子陣列進行排序。該演算法對於大型資料集非常高效，因為它的平均和最壞情況複雜度為Ο(n2)，其中n是專案的數量。

演算法

基於我們對快速排序中劃分的理解，我們現在將嘗試為其編寫一個演算法，如下所示：

Step 1: Choose the highest index value has pivot.
Step 2: Take two variables to point left and right of the list excluding pivot.
Step 3: left points to the low index.
Step 4: right points to the high.
Step 5: while value at left is less than pivot move right.
Step 6: while value at right is greater than pivot move left.
Step 7: if both step 5 and step 6 does not match swap left and right.
Step 8: if left ≥ right, the point where they met is new pivot.

快速排序演算法

使用樞軸演算法遞迴地，我們最終得到儘可能小的分割槽。然後對每個分割槽進行快速排序處理。我們對快速排序的遞迴演算法定義如下：

Step 1: Make the right-most index value pivot.
Step 2: partition the array using pivot value.
Step 3: quicksort left partition recursively.
Step 4: quicksort right partition recursively.

示例

import java.util.Arrays;

public class QuickSortExample {
   int[] intArray = {4,6,3,2,1,9,7};
   
   void swap(int num1, int num2) {
      int temp = intArray[num1];
      intArray[num1] = intArray[num2];
      intArray[num2] = temp;
   }
   int partition(int left, int right, int pivot) {
      int leftPointer = left -1;
      int rightPointer = right;

      while(true) {
         while(intArray[++leftPointer] < pivot) {
            // do nothing
         }
         while(rightPointer > 0 && intArray[--rightPointer] > pivot) {
            // do nothing
         }
         
         if(leftPointer >= rightPointer) {
            break;
         } else {
            swap(leftPointer,rightPointer);
         }
      }
      swap(leftPointer,right);
      
      // System.out.println("Updated Array: "); 
      return leftPointer;
   }
   void quickSort(int left, int right) {
      if(right-left <= 0) {
         return;   
      } else {
         int pivot = intArray[right];
         int partitionPoint = partition(left, right, pivot);
         quickSort(left,partitionPoint-1);
         quickSort(partitionPoint+1,right);
      }        
   }
   public static void main(String[] args) { 
      QuickSortExample sort = new QuickSortExample();
      int max = sort.intArray.length;
      System.out.println("Contents of the array :");
      System.out.println(Arrays.toString(sort.intArray));
      
      sort.quickSort(0, max-1);
      System.out.println("Contents of the array after sorting :");
      System.out.println(Arrays.toString(sort.intArray));
   }
}

輸出

Contents of the array :
[4, 6, 3, 2, 1, 9, 7]
Contents of the array after sorting :
[1, 2, 3, 4, 6, 7, 9]

Java資料結構 - 堆排序

堆是一種樹，具有特定條件，即節點的值大於（或小於）其子節點的值。堆排序是一種排序，我們使用二叉堆對陣列的元素進行排序。

演算法

Step 1: Create a new node at the end of heap.
Step 2: Assign new value to the node.
Step 3: Compare the value of this child node with its parent.
Step 4: If value of parent is less than child, then swap them.
Step 5: Repeat step 3 & 4 until Heap property holds.

示例

import java.util.Arrays;
import java.util.Scanner;

public class Heapsort {
   public static void heapSort(int[] myArray, int length) {
      int temp;
      int size = length-1;
      
      for (int i = (length / 2); i >= 0; i--) {
         heapify(myArray, i, size);
      }
      for(int i = size; i>=0; i--) {
         temp = myArray[0];
         myArray[0] = myArray[size];
         myArray[size] = temp;
         size--;
         heapify(myArray, 0, size);
      }
	   System.out.println(Arrays.toString(myArray));		   
   }
   public static void heapify (int [] myArray, int i, int heapSize) {
      int a = 2*i;
      int b = 2*i+1;
      int largestElement;
      
      if (a<= heapSize && myArray[a] > myArray[i]) {
         largestElement = a;
      } else {
         largestElement = i;
      }
      if (b <= heapSize && myArray[b] > myArray[largestElement]) {
         largestElement = b;
      }
      if (largestElement != i) {
         int temp = myArray[i];
         myArray[i] = myArray[largestElement];
         myArray[largestElement] = temp;
         heapify(myArray, largestElement, heapSize);
      }
   }	
   public static void main(String args[]) {
      Scanner scanner = new Scanner(System.in);
      System.out.println("Enter the size of the array :: ");
      int size = scanner.nextInt();      
      System.out.println("Enter the elements of the array :: ");
      int[] myArray = new int[size];
      
      for(int i = 0; i<size; i++) {    	  
         myArray[i] = scanner.nextInt();    	  
      }      
      heapSort(myArray, size);	   
   }		
}

輸出

Enter the size of the array :: 
5
Enter the elements of the array :: 
45
125
44
78
1
[1, 44, 45, 78, 125]

Java資料結構 - 線性查詢

線性查詢是一種非常簡單的搜尋演算法。在這種型別的搜尋中，對所有專案逐個進行順序搜尋。檢查每個專案，如果找到匹配項，則返回該特定專案，否則搜尋將繼續到資料集合的末尾。

演算法

線性查詢。（陣列A，值x）

Step 1: Get the array and the element to search.
Step 2: Compare value of the each element  in the array to the required value.
Step 3: In case of match print element found.

示例

public class LinearSearch {
   public static void main(String args[]) {
      int array[] =  {10, 20, 25, 63, 96, 57};
      int size = array.length;
      int value = 63;

      for (int i=0 ;i< size-1; i++) {		  
         if(array[i]==value) {
            System.out.println("Index of the required element is :"+ i);
         }
      }	 
   }
}

輸出

Index of the required element is :3

Java資料結構 - 二分查詢

二分查詢是一種快速的搜尋演算法，執行時間複雜度為Ο(log n)。該搜尋演算法基於分治的原理。為了使該演算法正常工作，資料集合應按排序形式排列。

二分查詢透過比較集合中最中間的專案來查詢特定專案。如果發生匹配，則返回專案的索引。如果中間項大於該項，則在中間項左側的子陣列中搜索該項。否則，在中間項右側的子陣列中搜索該項。此過程也繼續在子陣列上進行，直到子陣列的大小減小到零。

示例

public class BinarySearch {
   public static void main(String args[]) {
      int array[] =  {10, 20, 25, 57, 63, 96};
      int size = array.length;
      int low = 0;
      int high = size-1;
      int value = 25;
      int mid = 0;
      mid = low +(high-low)/2;

      while(low<=high) {
         if(array[mid] == value) {
            System.out.println(mid);
            break;
         } else if(array[mid]<value)
            low = mid+1;
            else high = mid - 1;
      }
      mid = (low+high)/2;      
   }
}

輸出

2

Java資料結構 - 遞迴

一些計算機程式語言允許模組或函式呼叫自身。這種技術稱為遞迴。在遞迴中，函式α要麼直接呼叫自身，要麼呼叫一個函式β，而β又呼叫原始函式α。函式α稱為遞迴函式。

int sampleMethod(int value) {
   if(value < 1) {
      return;
   }
   sampleMethod(value - 1);
   System.out.println(value);   
}

屬性

遞迴函式可能會像迴圈一樣無限執行。為了避免遞迴函式無限執行，遞迴函式必須具有兩個屬性：

• 基本條件 - 必須至少有一個基本條件，當滿足此條件時，函式停止遞迴呼叫自身。

• 遞進方法 - 遞迴呼叫應該以這樣的方式進行，每次遞迴呼叫都更接近基本條件。

實現

許多程式語言透過堆疊來實現遞迴。通常，每當一個函式（呼叫者）呼叫另一個函式（被呼叫者）或自身作為被呼叫者時，呼叫者函式將執行控制權轉移給被呼叫者。此轉移過程可能還涉及將一些資料從呼叫者傳遞給被呼叫者。

這意味著，呼叫者函式必須暫時掛起其執行，並在執行控制權從被呼叫者函式返回時恢復。在這裡，呼叫者函式需要從其暫停執行的點開始精確執行。它還需要它正在處理的完全相同的資料值。為此，將為呼叫者函式建立一個啟用記錄（或堆疊幀）。

此啟用記錄保留有關區域性變數、形式引數、返回地址以及傳遞給呼叫者函式的所有資訊。

遞迴分析

有人可能會質疑為什麼要使用遞迴，因為可以使用迭代來完成相同的任務。第一個原因是，遞迴使程式更易於閱讀，並且由於最新的增強型 CPU 系統，遞迴比迭代更有效。

時間複雜度

對於迭代，我們採用迭代次數來計算時間複雜度。同樣，對於遞迴，假設一切都是常數，我們試圖找出遞迴呼叫的次數。對函式的呼叫為Ο(1)，因此遞迴呼叫 (n) 次使遞迴函式為Ο(n)。

空間複雜度

空間複雜度計算為模組執行需要多少額外空間。對於迭代，編譯器幾乎不需要任何額外空間。編譯器不斷更新迭代中使用的變數的值。但是對於遞迴，系統需要在每次遞迴呼叫時儲存啟用記錄。因此，認為遞迴函式的空間複雜度可能高於迭代函式的空間複雜度。

Java資料結構 - 斐波那契數列

動態規劃方法類似於分治法，它將問題分解成越來越小的子問題。但與分治法不同的是，這些子問題不是獨立解決的。相反，這些較小子問題的結果會被記住並用於類似或重疊的子問題。

動態規劃用於我們可以將問題分解成類似子問題的情況，以便可以重用其結果。這些演算法主要用於最佳化。在解決當前子問題之前，動態演算法將嘗試檢查先前解決的子問題的結果。子問題的解決方案被組合起來以實現最佳解決方案。

所以我們可以說：

• 問題應該能夠分解成較小的重疊子問題。

• 可以使用較小子問題的最佳解決方案來實現最佳解決方案。

• 動態演算法使用記憶化。

比較

與解決區域性最佳化的貪婪演算法相比，動態演算法的目標是對問題進行整體最佳化。

與分治演算法（其中解決方案被組合以實現整體解決方案）相比，動態演算法使用較小子問題的輸出，然後嘗試最佳化較大的子問題。動態演算法使用記憶化來記住已解決子問題的輸出。

動態規劃可以自頂向下和自底向上兩種方式使用。當然，在大多數情況下，參考以前的解決方案輸出比重新計算更便宜（就 CPU 週期而言）。

Java中的斐波那契數列

以下是使用動態規劃技術在Java中解決斐波那契數列的方案。

示例

import java.util.Scanner;

public class Fibonacci {
   public static int fibonacci(int num) {
      int fib[] = new int[num + 1];
      fib[0] = 0;
      fib[1] = 1;
      
      for (int i = 2; i < num + 1; i++) {
         fib[i] = fib[i - 1] + fib[i - 2];
      }
      return fib[num];
   }
   public static void main(String[] args) {
	   Scanner sc = new Scanner(System.in);
      System.out.println("Enter a number :");
      int num = sc.nextInt();
      
      for (int i = 1; i <= num; i++) {
         System.out.print(" "+fibonacci(i));
      }
   }
}

輸出

1 1 2 3 5 8 13 21 34 55 89 144

Java資料結構 - 揹包問題

以下是使用動態規劃技術在Java中解決揹包問題的方案。

示例

public class KnapsackExample {
   static int max(int a, int b) { 
      return (a > b)? a : b; 
   }
   public static int knapSack(int capacity, int[] items, int[] values, int numOfItems ) {
      int i, w;
      int [][]K = new int[numOfItems+1][capacity+1];

      // Build table K[][] in bottom up manner
      for (i = 0; i <= numOfItems; i++) {
         for (w = 0; w <= capacity; w++) {
            if (i==0 || w==0) {
               K[i][w] = 0;
            } else if (items[i-1] <= w) {
               K[i][w] = max(values[i-1] + K[i-1][w-items[i-1]],  K[i-1][w]);
            } else {
               K[i][w] = K[i-1][w];
            }
         }
      }
      return K[numOfItems][capacity];
   }
   public static void main(String args[]) {
      int[] items = {12, 45, 67, 90, 45};
      int numOfItems = items.length;
      int capacity = 100;
      int[] values = {1200, 4500, 6700, 9000, 4500}; 
      
      int x = knapSack(capacity, items, values, numOfItems );
      System.out.println(x);	   
   }
}

輸出

9000

貪心演算法的組成部分

演算法旨在為給定問題實現最佳解決方案。在貪婪演算法方法中，決策是從給定的解決方案域中做出的。作為貪婪演算法，選擇似乎提供最佳解決方案的最接近的解決方案。

貪婪演算法試圖找到區域性最優解，這最終可能導致全域性最優解。但是，通常貪婪演算法不會提供全域性最優解。

貪心演算法的組成部分

貪婪演算法具有以下五個組成部分：

• 候選集 - 從該集合中建立解決方案。

• 選擇函式 - 用於選擇最佳候選者新增到解決方案中。

• 可行性函式 - 用於確定候選者是否可以用於貢獻解決方案。

• 目標函式 - 用於為解決方案或部分解決方案賦值。

• 解決方案函式 - 用於指示是否已找到完整解決方案。

應用領域

貪婪方法用於解決許多問題，例如

• 使用 Dijkstra 演算法查詢兩個頂點之間的最短路徑。

• 使用 Prim/Kruskal 演算法查詢圖中的最小生成樹等。

貪婪方法失效之處

在許多問題中，貪婪演算法都無法找到最優解，而且它可能會產生最差的解。旅行商問題和揹包問題等問題無法使用這種方法解決。

硬幣計數

這個問題是要透過選擇儘可能少的硬幣來計算到期望值，而貪婪方法迫使演算法選擇儘可能大的硬幣。如果我們提供的是1、2、5和10盧比的硬幣，並且我們被要求計算18盧比，那麼貪婪程式將是：

• 選擇一枚10盧比的硬幣，剩餘計數為8。

• 然後選擇一枚5盧比的硬幣，剩餘計數為3。

• 然後選擇一枚2盧比的硬幣，剩餘計數為1。

• 最後，選擇一枚1盧比的硬幣解決了這個問題。

儘管看起來工作正常，但對於此計數，我們只需要選擇4枚硬幣。但是，如果我們稍微改變一下問題，同樣的方法可能無法產生相同的最佳結果。

對於我們擁有面值為1、7、10的硬幣的貨幣系統，計算面值為18的硬幣將是絕對最優的，但對於像15這樣的計數，它可能使用的硬幣比必要的要多。例如，貪婪方法將使用10 + 1 + 1 + 1 + 1 + 1，總共6枚硬幣。而同樣的問題可以用只有3枚硬幣 (7 + 7 + 1) 來解決。

因此，我們可以得出結論，貪婪方法選擇立即最佳化的解決方案，並且在全域性最佳化是一個主要問題的地方可能會失敗。

Java 資料結構 - 演算法分析

演算法是一個逐步的過程，它定義了一組指令，這些指令以一定的順序執行以獲得預期的輸出。演算法通常獨立於底層語言建立，即一個演算法可以在多種程式語言中實現。

演算法分析

演算法的效率可以在兩個不同的階段進行分析，即實現之前和實現之後。它們如下所示：

事前分析 − 這是對演算法的理論分析。透過假設所有其他因素（例如處理器速度）都是恆定的並且對實現沒有影響來衡量演算法的效率。

事後分析 − 這是對演算法的經驗分析。所選演算法使用程式語言實現。然後在目標計算機上執行。在此分析中，收集實際統計資料，例如執行時間和所需空間。

我們將學習事前演算法分析。演算法分析處理各種操作的執行或執行時間。操作的執行時間可以定義為每個操作執行的計算機指令數。

演算法複雜度

假設X是一個演算法，n是輸入資料的大小，演算法X使用的時空是決定X效率的兩個主要因素。

時間因素 − 透過計算關鍵操作的數量（例如排序演算法中的比較次數）來衡量時間。

空間因素 − 透過計算演算法所需的最大記憶體空間來衡量空間。

演算法的複雜度f(n)給出了演算法的執行時間和/或儲存空間，其中n表示輸入資料的大小。

空間複雜度

演算法的空間複雜度表示演算法在其生命週期中所需的記憶體空間量。演算法所需的空間等於以下兩個部分的總和：

一個固定部分，這是儲存某些資料和變數所需的空間，這些資料和變數與問題的規模無關。例如，使用的簡單變數和常量、程式大小等。

一個可變部分，這是變數所需的空間，其大小取決於問題的規模。例如，動態記憶體分配、遞迴堆疊空間等。

任何演算法P的空間複雜度S(P)為S(P) = C + SP(I)，其中C是固定部分，S(I)是演算法的可變部分，它取決於例項特徵I。下面是一個簡單的例子，試圖解釋這個概念：

演算法：SUM(A, B)

Step 1: START
Step 2: C <- A + B + 10
Step 3: Stop

這裡我們有三個變數A、B和C以及一個常量。因此S(P) = 1 + 3。現在，空間取決於給定變數和常量型別的資料型別，並將相應地乘以。

時間複雜度

演算法的時間複雜度表示演算法執行到完成所需的時間量。時間需求可以定義為數值函式T(n)，其中T(n)可以測量為步驟數，前提是每個步驟消耗恆定時間。

例如，兩個n位整數的加法需要n個步驟。因此，總計算時間為T(n) = c * n，其中c是兩個位相加所需的時間。在這裡，我們觀察到T(n)隨著輸入大小的增加而線性增長。

Java 資料結構 - 漸近符號

演算法的漸近分析是指定義其執行時間效能的數學邊界/框架。使用漸近分析，我們可以很好地得出演算法的最壞情況、平均情況和最佳情況。

漸近分析是輸入約束的，即如果演算法沒有輸入，則認為它在恆定時間內工作。除“輸入”外，所有其他因素都被認為是恆定的。

漸近分析是指用數學計算單元計算任何操作的執行時間。例如，一個操作的執行時間計算為f(n)，另一個操作的執行時間計算為g(n²)。這意味著第一個操作的執行時間將隨著n的增加而線性增加，而第二個操作的執行時間將隨著n的增加而呈指數增長。同樣，如果n非常小，則兩個操作的執行時間幾乎相同。

通常，演算法所需的時間分為三種類型：

• 最佳情況 − 程式執行所需的最短時間。

• 平均情況 − 程式執行所需的平均時間。

• 最壞情況 − 程式執行所需的最長時間。

漸近符號

以下是常用的漸近符號，用於計算演算法的執行時間複雜度。

• Ο 符號

• Ω 符號

• θ 符號

大O符號，Ο

Ο(n)符號是表達演算法執行時間上限的形式化方法。它衡量最壞情況下的時間複雜度，即演算法可能完成所需的最長時間。

例如，對於函式f(n)

Ο(f(n)) = { g(n) : 存在c > 0和n0使得對於所有n > n0，f(n) ≤ c.g(n) 。}

歐米茄符號，Ω

Ω(n)符號是表達演算法執行時間下限的形式化方法。它衡量最佳情況下的時間複雜度，即演算法可能完成所需的最短時間。

例如，對於函式f(n)

Ω(f(n)) ≥ { g(n) : 存在c > 0和n0使得對於所有n > n0，g(n) ≤ c.f(n) 。}

西塔符號，θ

θ(n)符號是表達演算法執行時間下限和上限的形式化方法。它表示如下：

θ(f(n)) = { g(n) 當且僅當 g(n) = Ο(f(n)) 且 g(n) = Ω(f(n)) 對於所有 n > n0 。}

常見的漸近符號

以下是一些常見的漸近符號的列表：