Java-Datenstruktur und -Algorithmus: Detaillierte Erläuterung praktischer Fälle

Datenstrukturen und Algorithmen sind Schlüsselelemente für die Programmeffizienz. Zu den in Java häufig verwendeten Datenstrukturen gehören Arrays, verknüpfte Listen, Stapel und Binärbäume. Zu den gängigen Algorithmen gehören die schnelle Sortierung und die binäre Suche. In diesem Artikel werden diese Konzepte auf einfache und leicht verständliche Weise anhand praktischer Fälle erläutert: Array: Speichert kontinuierlich Elemente desselben Typs, z. B. die Noten der Schüler. Verknüpfte Liste: Elemente sind durch Zeiger verknüpft, z. B. eine simulierte Warteschlange. Stack: folgt dem LIFO-Prinzip, z. B. der Verfolgung von Funktionsaufrufen. Binärbaum: Eine Baumdatenstruktur, beispielsweise ein Dateisystemverzeichnis. Schnelle Sortierung: Strategie zum Teilen und Erobern, Teilen Sie das Array in zwei Teile und sortieren Sie sie separat. Binäre Suche: Führen Sie eine binäre Suche in einem geordneten Array durch, um den Suchbereich einzugrenzen.

Java-Datenstrukturen und -Algorithmen: detaillierte Erläuterung praktischer Fälle

Einführung

Datenstrukturen und Algorithmen sind die Grundlage der Informatik und bestimmen die Effizienz und Robustheit des Programms. In diesem Artikel werden anhand einer Reihe praktischer Fälle die häufig verwendeten Datenstrukturen und Algorithmen in Java auf einfache und leicht verständliche Weise erläutert.

Array

Definition: Eine Sammlung von Elementen desselben Typs, die in einem kontinuierlichen Speicherplatz gespeichert sind.

Praktischer Fall: Speichern von Schülernoten

int[] scores = {90, 85, 78, 95, 82};

Verknüpfte Liste

Definition: Eine lineare Datenstruktur, deren Elemente durch Zeiger verknüpft sind.

Praktischer Fall: Simulierte Warteschlange

class Node {
    int value;
    Node next;
}

class Queue {
    Node head;
    Node tail;

    public void enqueue(int value) {
        Node newNode = new Node();
        newNode.value = value;
        if (head == null) {
            head = newNode;
            tail = newNode;
        } else {
            tail.next = newNode;
            tail = newNode;
        }
    }

    public int dequeue() {
        if (head == null) {
            throw new RuntimeException("Queue is empty");
        }

        int value = head.value;
        head = head.next;
        if (head == null) {
            tail = null;
        }
        return value;
    }
}

Stack

Definition: Eine lineare Datenstruktur, die dem Last-In-First-Out (LIFO)-Prinzip folgt.

Praktischer Fall: Funktionsaufrufe verfolgen

class Stack<T> {
    private List<T> elements = new ArrayList<>();

    public void push(T element) {
        elements.add(element);
    }

    public T pop() {
        if (elements.isEmpty()) {
            throw new RuntimeException("Stack is empty");
        }
        return elements.remove(elements.size() -1);
    }

    public T peek() {
        if (elements.isEmpty()) {
            throw new RuntimeException("Stack is empty");
        }
        return elements.get(elements.size() -1);
    }
}

Binärer Baum

Definition: Eine Baumdatenstruktur, die einen Wurzelknoten und null oder mehr untergeordnete Knoten enthält.

Praktischer Fall: Dateisystemverzeichnis

class TreeNode {
    private String name;
    private List<TreeNode> children;

    // ... 其他代码
}

class FileSystem {
    private TreeNode root;

    // ... 其他代码
}

Sortieralgorithmus

Schnelle Sortierung

Beschreibung: Teile- und Eroberungsstrategie, teile das Array in zwei Teile, sortiere sie separat und füge sie dann zusammen.

Praktischer Fall: Sortieren einer Reihe von Zahlen

public static void quickSort(int[] arr) {
    if (arr == null || arr.length <= 1) {
        return;
    }

    int pivot = arr[0];
    int leftIndex = 0;
    int rightIndex = arr.length - 1;

    while (leftIndex < rightIndex) {
        while (arr[rightIndex] >= pivot && rightIndex > leftIndex) {
            rightIndex--;
        }
        arr[leftIndex] = arr[rightIndex];

        while (arr[leftIndex] <= pivot && rightIndex > leftIndex) {
            leftIndex++;
        }
        arr[rightIndex] = arr[leftIndex];
    }
    arr[leftIndex] = pivot;

    quickSort(arr, 0, leftIndex - 1);
    quickSort(arr, leftIndex + 1, arr.length - 1);
}

Suchalgorithmus

Binäre Suche

Beschreibung: Führen Sie eine binäre Suche im geordneten Array durch und verengen Sie den Suchbereich Schritt für Schritt.

Praktischer Fall: Ein Element in einem Array finden

public static int binarySearch(int[] arr, int target) {
    int left = 0;
    int right = arr.length - 1;

    while (left <= right) {
        int mid = (left + right) / 2;

        if (arr[mid] == target) {
            return mid;
        } else if (arr[mid] < target) {
            left = mid + 1;
        } else {
            right = mid - 1;
        }
    }
    return -1;
}

Das obige ist der detaillierte Inhalt vonJava-Datenstruktur und -Algorithmus: Detaillierte Erläuterung praktischer Fälle. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!