JAVA の基礎となるデータ構造とアルゴリズムについての詳細な説明

Java はオブジェクト指向プログラミング言語であり、開発者はさまざまなデータ構造とアルゴリズムを使用して、プログラムのパフォーマンスを最適化し、より効率的なコードを作成できます。この記事では、Java の基礎となるデータ構造とアルゴリズムを詳しく掘り下げ、これらの概念をよりよく理解するのに役立つサンプル コードをいくつか紹介します。

1. 基本データ構造

Java の基本データ構造には、配列、リンク リスト、スタック、キューが含まれます。これらのデータ構造は、他のすべてのデータ構造とアルゴリズムの基礎となります。

1.1 配列

配列は、メモリに継続的に保存される値のコレクションです。 Java では、配列には int、char、String、double、float などのさまざまなデータ型を含めることができます。

次は、Java 配列のサンプル コードです。

int[] nums = new int[5];
nums[0] = 1;
nums[1] = 2;
nums[2] = 3;
nums[3] = 4;
nums[4] = 5;

このコードは、5 つの整数を含む nums という名前の int 型配列を作成します。次に、配列の各要素に値を割り当てます。配列内の要素にアクセスするには、インデックス値を使用します。たとえば、nums[0] は、配列内の最初の要素の値が 1 であることを意味します。

1.2 リンク リスト

リンク リストは線形データ構造です。Java では、リンク リストはノードで構成されます。各ノードには値と次のノードへのポインタが含まれます。リンク リストには、単一リンク リスト、二重リンク リスト、循環リンク リストなど、さまざまなタイプがあります。

次は、Java 一方向リンク リストのサンプル コードです。

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

class LinkedList {
    Node head;
    public LinkedList() {
        head = null;
    }
    public void add(int value) {
        Node newNode = new Node(value);
        if(head == null) {
            head = newNode;
        }
        else {
            Node current = head;
            while(current.next != null) {
                current = current.next;
            }
            current.next = newNode;
        }
    }
}

このコードは、値と次のノードへのポインターを含む Node クラスを定義します。さらに、LinkedList クラスも定義されており、add() メソッドを使用してリンク リストに新しい値を追加します。リンクされたリストが空の場合、新しいノードをヘッド ノードとして設定します。それ以外の場合は、リンク リストを走査し、最後のノードを見つけて、新しいノードを次の属性として追加します。

1.3 スタック

スタックは後入れ先出し (LIFO) データ構造であり、Java では配列またはリンク リストを通じて実装できます。スタックでは、要素は順番に追加されますが、最近追加された要素はスタックの最上位にあるため、アクセスできるのは最後に追加された要素のみです。

次は、Java 配列によって実装されたスタックのサンプル コードです:

class ArrayStack {
    int[] arr;
    int top;
    int size;
    public ArrayStack(int size) {
        this.size = size;
        arr = new int[size];
        top = -1;
    }
    public void push(int value) {
        if(top == size - 1) {
            System.out.println("Stack overflow!");
            return;
        }
        arr[++top] = value;
        System.out.println("Element pushed: " + value);
    }
    public int pop() {
        if(top == -1) {
            System.out.println("Stack underflow!");
            return -1;
        }
        int value = arr[top--];
        System.out.println("Element popped: " + value);
        return value;
    }
}

このコードは、配列、スタックのサイズ、およびインデックスの先頭を含む ArrayStack クラスを定義します。スタックの最上位の要素。 Push() メソッドは、スタックに新しい要素を追加し、スタックがいっぱいの場合はエラー メッセージを出力します。 Pop() メソッドは、スタックから最上位の要素を削除し、スタックが空の場合にエラー メッセージを出力するために使用されます。

1.4 キュー

キューは先入れ先出し (FIFO) データ構造であり、Java の配列またはリンク リストを通じて実装できます。キューでは、新しい要素は常にキューの最後に追加され、追加された最も古い要素が常にキューの先頭になります。

次は、Java リンク リストによって実装されたキューのサンプル コードです。

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

class Queue {
    Node head, tail;
    public Queue() {
        head = null;
        tail = null;
    }
    public void enqueue(int value) {
        Node newNode = new Node(value);
        if(tail == null) {
            head = tail = newNode;
        }
        else {
            tail.next = newNode;
            tail = newNode;
        }
    }
    public int dequeue() {
        if(head == null) {
            System.out.println("Queue underflow!");
            return -1;
        }
        int value = head.value;
        head = head.next;
        if(head == null) {
            tail = null;
        }
        System.out.println("Element dequeued: " + value);
        return value;
    }
}

このコードは、値と次のノードへのポインタを含む Node クラスを定義します。さらに、Queue クラスも定義されており、このクラスでは enqueue() メソッドを使用して新しいノードをキューに追加します。キューが空の場合、新しいノードが先頭と末尾として設定されます。それ以外の場合は、新しいノードを末尾にリンクし、末尾のノードを新しいノードで更新します。 dequeue() メソッドは、キューから要素を削除し、その値を返すために使用されます。キューが空の場合はエラーメッセージが出力されます。

2. 共通アルゴリズム

Java では、並べ替え、検索、グラフィックスなどのさまざまな問題を解決するために、さまざまなアルゴリズムを使用できます。以下にいくつかの一般的なアルゴリズムを示します。これらの実装については引き続き詳しく調査していきます。

2.1 バブル ソート

バブル ソートは、隣接する要素を比較し、それらの位置を交換することによって配列を並べ替える、シンプルで実装が簡単な並べ替えアルゴリズムです。このプロセスは、交換する要素がなくなるまで繰り返されます。以下は、Java で実装されたバブル ソート アルゴリズムのサンプル コードです。

class BubbleSort {
    public static void sort(int[] arr) {
        int n = arr.length;
        for(int i = 0; i < n - 1; i++) {
            for(int j = 0; j < n - i - 1; j++) {
                if(arr[j] > arr[j + 1]) {
                    int temp = arr[j];
                    arr[j] = arr[j + 1];
                    arr[j + 1] = temp;
                }
            }
        }
    }
}

このコードは、int 型の配列パラメーターを受け入れ、配列のソートに使用される sort() メソッドを定義します。 sort() メソッドでは、2 つのネストされた for ループを使用して配列を反復処理し、隣接する要素を比較します。左側の要素が右側の要素より大きい場合は、それらの位置を交換します。

2.2 二分検索

二分検索は、順序付けされた配列内の特定の要素を見つけるために使用できる検索アルゴリズムです。このアルゴリズムは毎回、配列の中央の要素とターゲット要素を比較して、ターゲット要素が左側にあるか右側にあるかを判断します。このプロセスは、ターゲット要素が見つかるか、存在しないと判断されるまで繰り返されます。

次は、Java で実装されたバイナリ検索アルゴリズムのサンプル コードです。

class BinarySearch {
    public static int search(int[] arr, int target) {
        int left = 0, right = arr.length - 1;
        while(left <= right) {
            int mid = left + (right - left) / 2;
            if(arr[mid] == target) {
                return mid;
            }
            else if(arr[mid] < target) {
                left = mid + 1;
            }
            else {
                right = mid - 1;
            }
        }
        return -1;
    }
}

このコードは、int 型の配列とターゲット要素パラメーターを受け入れる search() メソッドを定義します。 search() メソッドでは、左右の 2 つのポインターを使用して配列の境界を決定します。次に、while ループを使用して配列の中央の要素とターゲット要素を比較し、ターゲット要素の位置を決定します。対象要素が中央の要素より小さい場合は、左半分が検索されます。それ以外の場合は、右半分が検索されます。

2.3 再帰

再帰は、さまざまな問題を解決するために使用できる自己呼び出し関数です。 Java では、基本ケースと再帰呼び出しを通じて再帰を実現できます。

以下是一个使用Java实现的递归算法的示例代码：

class Recursion {
    public static int factorial(int n) {
        if(n == 0) {
            return 1;
        }
        else {
            return n * factorial(n - 1);
        }
    }
}

这个代码定义了一个factorial()方法，使用递归来计算一个整数的阶乘。在factorial中，我们首先定义一个基本情况n=0，并返回1。然后，我们使用n×factorial(n-1)的递归公式来计算更大的数的阶乘。

三、结论

Java提供了一个强大的工具箱来处理各种数据结构和算法，可以用于设计和优化各种程序。在本文中，我们深入探讨了Java的基础数据结构和算法，包括数组、链表、栈、队列、冒泡排序、二分查找和递归，并给出了相应的示例代码。通过这些概念和代码示例的学习，您可以更好地理解Java的实现方式和优化程序的方法。

以上がJAVA の基礎となるデータ構造とアルゴリズムについての詳細な説明の詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。