Structure de données de base JAVA et implémentation d'algorithmes

En raison de l'espace limité de l'article, je fournirai quelques exemples de mise en œuvre de structures de données et d'algorithmes clés. Tout d’abord, plusieurs structures de données et algorithmes de base sont présentés, puis des exemples de code Java correspondants sont donnés.

1. array

   • implémenter un tableau étendu dynamiquement
   • implémenter les opérations d'ajout, de suppression, de modification et de vérification du tableau

public class DynamicArray<T> {
    private Object[] array;
    private int size;
    private int capacity;

    public DynamicArray() {
        capacity = 10;
        array = new Object[capacity];
        size = 0;
    }

    public void add(T element) {
        if (size == capacity) {
            capacity *= 2;
            Object[] newArray = new Object[capacity];
            System.arraycopy(array, 0, newArray, 0, size);
            array = newArray;
        }
        array[size++] = element;
    }

    public T get(int index) {
        if (index < 0 || index >= size) throw new IndexOutOfBoundsException();
        return (T) array[index];
    }

    public void remove(int index) {
        if (index < 0 || index >= size) throw new IndexOutOfBoundsException();
        for (int i = index; i < size - 1; i++) {
            array[i] = array[i + 1];
        }
        size--;
    }
}

2. liste chaînée

   • implémenter une liste chaînée unique
   • mettre en œuvre le ajouter, supprimer, modifier et vérifier les opérations de la liste chaînée Opération

public class ListNode {
    int val;
    ListNode next;

    ListNode(int val) {
        this.val = val;
    }
}

public class LinkedList {
    private ListNode head;

    public void addAtHead(int val) {
        ListNode newHead = new ListNode(val);
        newHead.next = head;
        head = newHead;
    }

    public void addAtTail(int val) {
        if (head == null) {
            head = new ListNode(val);
        } else {
            ListNode current = head;
            while (current.next != null) {
                current = current.next;
            }
            current.next = new ListNode(val);
        }
    }

    public void deleteAtIndex(int index) {
        if (index == 0) {
            head = head.next;
            return;
        }
        int count = 0;
        ListNode current = head;
        ListNode prev = null;
        while (current != null && count < index) {
            prev = current;
            current = current.next;
            count++;
        }
        if (current != null) {
            prev.next = current.next;
        }
    }

    public ListNode get(int index) {
        ListNode current = head;
        int count = 0;
        while (current != null && count < index) {
            current = current.next;
            count++;
        }
        return current;
    }
}

3. stack

   • implémenter une pile basée sur un tableau
   • implémenter des opérations push, pop et autres de pile

public class ArrayStack {
    private int[] array;
    private int top;
    private int capacity;

    public ArrayStack(int capacity) {
        this.capacity = capacity;
        array = new int[capacity];
        top = -1;
    }

    public void push(int value) {
        if (top == capacity - 1) throw new IllegalStateException("Stack is full");
        array[++top] = value;
    }

    public int pop() {
        if (top == -1) throw new IllegalStateException("Stack is empty");
        return array[top--];
    }

    public int peek() {
        if (top == -1) throw new IllegalStateException("Stack is empty");
        return array[top];
    }

    public boolean isEmpty() {
        return top == -1;
    }
}

4. queue

   • implémenter une file d'attente basée sur un tableau
   • implémenter des opérations de file d'attente telles que la mise en file d'attente et le retrait de la file d'attente

public class ArrayQueue {
    private int[] array;
    private int front;
    private int rear;
    private int capacity;

    public ArrayQueue(int capacity) {
        this.capacity = capacity;
        array = new int[capacity];
        front = 0;
        rear = -1;
    }

    public void enqueue(int value) {
        if (rear == capacity - 1) throw new IllegalStateException("Queue is full");
        array[++rear] = value;
    }

    public int dequeue() {
        if (isEmpty()) throw new IllegalStateException("Queue is empty");
        int value = array[front];
        front++;
        return value;
    }

    public int peek() {
        if (isEmpty()) throw new IllegalStateException("Queue is empty");
        return array[front];
    }

    public boolean isEmpty() {
        return front > rear;
    }
}

5. algorithmes de tri

   • implémenter le tri à bulles, le tri par insertion, le tri par sélection, le tri rapide et d'autres algorithmes

public class Sort {
    public static void bubbleSort(int[] array) {
        int length = array.length;
        for (int i = 0; i < length - 1; i++) {
            for (int j = 0; j < length - 1 - i; j++) {
                if (array[j] > array[j + 1]) {
                    int temp = array[j];
                    array[j] = array[j + 1];
                    array[j + 1] = temp;
                }
            }
        }
    }

    public static void insertionSort(int[] array) {
        for (int i = 1; i < array.length; i++) {
            int current = array[i];
            int j = i - 1;
            while (j >= 0 && array[j] > current) {
                array[j + 1] = array[j];
                j--;
            }
            array[j + 1] = current;
        }
    }

    public static void selectionSort(int[] array) {
        for (int i = 0; i < array.length - 1; i++) {
            int minIndex = i;
            for (int j = i + 1; j < array.length; j++) {
                if (array[j] < array[minIndex]) {
                    minIndex = j;
                }
            }
            int temp = array[i];
            array[i] = array[minIndex];
            array[minIndex] = temp;
        }
    }

    public static void quickSort(int[] array, int low, int high) {
        if (low < high) {
            int mid = partition(array, low, high);
            quickSort(array, low, mid - 1);
            quickSort(array, mid + 1, high);
        }
    }

    private static int partition(int[] array, int low, int high) {
        int pivot = array[high];
        int i = low - 1;
        for (int j = low; j < high; j++) {
            if (array[j] < pivot) {
                i++;
                int temp = array[i];
                array[i] = array[j];
                array[j] = temp;
            }
        }
        int temp = array[i + 1];
        array[i + 1] = array[high];
        array[high] = temp;
        return i + 1;
    }
}

Ce qui précède présente quelques structures de données de base et un exemple d'implémentation Java d'algorithme, j'espère que cela vous sera utile.

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!