Perbincangan mendalam tentang struktur data dan algoritma asas JAVA

Java ialah bahasa pengaturcaraan berorientasikan objek Pembangun boleh menggunakan struktur data dan algoritma yang berbeza untuk mengoptimumkan prestasi program dan menulis kod yang lebih cekap. Dalam artikel ini, kami akan menyelidiki struktur data dan algoritma asas Java dan berkongsi beberapa kod sampel untuk membantu anda memahami konsep ini dengan lebih baik.

1. Struktur data asas

Struktur data asas dalam Java termasuk tatasusunan, senarai terpaut, tindanan dan baris gilir. Struktur data ini adalah asas untuk semua struktur dan algoritma data lain.

1.1 Tatasusunan

Tatasusunan ialah himpunan nilai yang disimpan secara berterusan dalam ingatan. Di Java, tatasusunan boleh mempunyai jenis data yang berbeza, seperti int, char, String, double, float, dll.

Berikut ialah contoh kod untuk tatasusunan Java:

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

Kod ini mencipta tatasusunan jenis int bernama nums, yang mengandungi 5 integer. Seterusnya, kami memberikan nilai kepada setiap elemen tatasusunan. Untuk mengakses elemen dalam tatasusunan, anda menggunakan nilai indeks, contohnya nums[0] bermaksud elemen pertama dalam tatasusunan mempunyai nilai 1.

1.2 Senarai Terpaut

Senarai terpaut ialah struktur data linear, di Java ia terdiri daripada nod, setiap nod mengandungi nilai dan penunjuk ke nod seterusnya. Senarai terpaut boleh terdiri daripada jenis yang berbeza seperti senarai pautan tunggal, senarai pautan dua kali dan senarai pautan bulat.

Berikut ialah contoh kod untuk senarai terpaut sehala dalam 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;
        }
    }
}

Kod ini mentakrifkan kelas Nod yang mengandungi nilai dan penuding ke nod seterusnya. Selain itu, kelas LinkedList juga ditakrifkan, di mana kaedah add() digunakan untuk menambah nilai baharu pada senarai terpaut. Jika senarai terpaut kosong, kami menetapkan nod baharu sebagai nod kepala. Jika tidak, kami melintasi senarai terpaut, mencari nod terakhir dan menambah nod baharu sebagai atribut seterusnya.

1.3 Tindanan

Timbunan ialah struktur data masuk-dahulu (LIFO) Dalam Java, ia boleh dilaksanakan melalui tatasusunan atau senarai terpaut. Dalam tindanan, elemen ditambah secara berurutan, tetapi hanya elemen yang paling baru ditambah boleh diakses kerana ia berada di bahagian atas tindanan.

Berikut ialah contoh kod untuk tindanan yang dilaksanakan oleh tatasusunan 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;
    }
}

Kod ini mentakrifkan kelas ArrayStack, yang mengandungi tatasusunan, saiz tindanan dan bahagian atas indeks unsur teratas dalam tindanan. Kaedah push() menambah elemen baharu pada timbunan dan mengeluarkan mesej ralat jika timbunan penuh. Kaedah pop() digunakan untuk mengalih keluar elemen teratas daripada timbunan dan mengeluarkan mesej ralat jika timbunan kosong.

1.4 Baris Gilir

Barisan ialah struktur data masuk dahulu keluar (FIFO) Di Java, ia boleh dilaksanakan melalui tatasusunan atau senarai terpaut. Dalam baris gilir, elemen baharu sentiasa ditambah pada penghujung baris gilir, dan elemen tertua yang ditambah sentiasa berada di hadapan baris gilir.

Berikut ialah contoh kod untuk baris gilir yang dilaksanakan sebagai senarai terpaut 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;
    }
}

Kod ini mentakrifkan kelas Nod yang mengandungi nilai dan penunjuk ke nod seterusnya. Selain itu, kelas Queue juga ditakrifkan, di mana kaedah enqueue() digunakan untuk menambah nod baharu pada baris gilir. Jika baris gilir kosong, nod baharu ditetapkan sebagai kepala dan ekor. Jika tidak, kami memautkan nod baharu ke ekor dan mengemas kini nod ekor ke nod baharu. Kaedah dequeue() digunakan untuk mengalih keluar elemen daripada baris gilir dan mengembalikan nilainya. Jika baris gilir kosong, mesej ralat akan dikeluarkan.

2. Algoritma Biasa

Di Java, algoritma yang berbeza boleh digunakan untuk menyelesaikan pelbagai masalah, seperti pengisihan, carian dan grafik. Di bawah adalah beberapa algoritma biasa dan kami akan terus menyelidiki pelaksanaannya.

2.1 Isih gelembung

Isih gelembung ialah algoritma pengisihan yang ringkas dan mudah dilaksanakan yang mengisih tatasusunan dengan membandingkan unsur bersebelahan dan menukar kedudukannya. Proses ini berulang sehingga tiada lagi elemen untuk ditukar. Berikut ialah kod sampel untuk algoritma isihan gelembung yang dilaksanakan dalam 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;
                }
            }
        }
    }
}

Kod ini mentakrifkan kaedah sort() yang menerima parameter tatasusunan jenis int dan digunakan untuk mengisih tatasusunan. Dalam kaedah sort(), kami menggunakan dua gelung bersarang untuk melelaran melalui tatasusunan dan membandingkan elemen bersebelahan. Jika elemen di sebelah kiri lebih besar daripada elemen di sebelah kanan, tukar kedudukan mereka.

2.2 Carian binari

Carian binari ialah algoritma carian yang boleh digunakan untuk mencari elemen tertentu dalam tatasusunan tertib. Algoritma membandingkan elemen tengah tatasusunan dengan elemen sasaran setiap kali untuk menentukan sama ada elemen sasaran berada di sebelah kiri atau kanan. Proses ini diulang sehingga elemen sasaran ditemui atau ditentukan tidak wujud.

Berikut ialah kod sampel untuk algoritma carian binari yang dilaksanakan dalam 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;
    }
}

Kod ini mentakrifkan kaedah carian() yang menerima tatasusunan jenis int dan parameter elemen sasaran. Dalam kaedah search(), kami menggunakan dua penunjuk kiri dan kanan untuk menentukan sempadan tatasusunan. Kami kemudian menggunakan gelung sementara untuk membandingkan elemen tengah tatasusunan dengan elemen sasaran untuk menentukan kedudukan elemen sasaran. Jika elemen sasaran lebih kecil daripada elemen tengah, bahagian kiri dicari. Jika tidak, separuh kanan dicari.

2.3 Rekursi

Rekursi ialah fungsi panggilan kendiri yang boleh digunakan untuk menyelesaikan pelbagai masalah. Di Jawa, rekursi boleh dicapai melalui kes asas dan panggilan rekursif.

以下是一个使用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的实现方式和优化程序的方法。

Atas ialah kandungan terperinci Perbincangan mendalam tentang struktur data dan algoritma asas JAVA. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!