Structure des données et algorithme Java : explication détaillée de cas pratiques

Les structures de données et les algorithmes sont des éléments clés pour l'efficacité des programmes. Les structures de données couramment utilisées en Java incluent les tableaux, les listes chaînées, les piles et les arbres binaires. Les algorithmes courants incluent le tri rapide et la recherche binaire. Cet article explique ces concepts de manière simple et facile à comprendre à travers des cas pratiques : Tableau : stocke en continu des éléments du même type, comme les scores des élèves. Liste chaînée : les éléments sont liés via des pointeurs, comme une file d'attente simulée. Stack : suivez le principe LIFO, comme le traçage des appels de fonction. Arbre binaire : structure de données arborescente, telle qu'un répertoire de système de fichiers. Tri rapide : stratégie de division pour mieux régner, divisez le tableau en deux parties et triez-les séparément. Recherche binaire : effectuez une recherche binaire sur un tableau ordonné pour affiner la portée de la recherche.

Structures de données et algorithmes Java : explication détaillée de cas pratiques

Introduction

Les structures de données et les algorithmes sont le fondement de l'informatique, et ils déterminent l'efficacité et la robustesse du programme. Cet article expliquera les structures de données et les algorithmes couramment utilisés en Java d'une manière simple et facile à comprendre à travers une série de cas pratiques.

Array

Définition : Une collection d'éléments du même type stockés dans un espace mémoire continu.

Cas pratique : Stockage des notes des élèves

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

Liste chaînée

Définition : Une structure de données linéaire dont les éléments sont liés par des pointeurs.

Cas pratique : File d'attente simulée

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

Définition : Une structure de données linéaire qui suit le principe du dernier entré, premier sorti (LIFO).

Cas pratique : Traçage des appels de fonction

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);
    }
}

Arbre binaire

Définition : Une structure de données arborescente contenant un nœud racine et zéro ou plusieurs nœuds enfants.

Cas pratique : Répertoire du système de fichiers

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

    // ... 其他代码
}

class FileSystem {
    private TreeNode root;

    // ... 其他代码
}

Algorithme de tri

Tri rapide

Description : Stratégie de division et de conquête, divisez le tableau en deux parties, triez-les séparément, puis fusionnez.

Cas pratique : Tri d'un ensemble de nombres

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);
}

Algorithme de recherche

Recherche binaire

Description : Effectuez une recherche binaire sur le tableau ordonné, en réduisant la plage de recherche étape par étape.

Cas pratique : Trouver un élément dans un tableau

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;
}

Ce qui précède est le contenu détaillé de. pour plus d'informations, suivez d'autres articles connexes sur le site Web de PHP en chinois!