Datenstrukturen: Arrays

Statisches Array

Array ist eine lineare Datenstruktur, in der alle Elemente der Reihe nach angeordnet sind. Es handelt sich um eine Sammlung von Elementen des gleichen Datentyps, die an zusammenhängenden Speicherorten gespeichert sind.

Initialisierung

public class Array<T> {
    private T[] self;
    private int size;
    @SuppressWarnings("unchecked")
    public Array(int size) {
        if (size <= 0) {
            throw new IllegalArgumentException("Invalid array size (must be positive): " + size);
        } else {
            this.size = size;
            this.self = (T[]) new Object[size];
        }
    }
}

In der Core-Array-Klasse speichern wir die Größe des Arrays und ein allgemeines Grundgerüst für die Array-Initialisierung. Im Konstruktor fragen wir nach der Größe des Arrays, erstellen ein Objekt und wandeln es in unser gewünschtes Array um.

Methode festlegen

public void set(T item, int index) {
        if (index >= this.size || index < 0) {
            throw new IndexOutOfBoundsException("Index Out of bounds: " + index);
        } else {
            this.self[index] = item;
        }
    }

Diese Methode fordert die Speicherung eines Elements im Array und den Index an, auf dem das Element gespeichert werden soll.

Get-Methode

public T get(int index) {
        if (index >= this.size || index < 0) {
            throw new IndexOutOfBoundsException("Index Out of bounds");
        } else {
            return self[index];
        }
    }

Get-Methode fragt nach einem Index und ruft ein Element aus diesem Index ab.

Druckmethode

public void print() {
        for (int i = 0; i < size; i++) {
            System.out.println(this.self[i]+" ");
        }
    }

Die Druckmethode druckt einfach alle Mitglieder eines Arrays in einer einzigen Zeile, wobei jedes Element durch ein Leerzeichen dazwischen getrennt wird.

Sortiertes Array

Arrays, aber mit einer Funktionalität zum Sortieren von Elementen selbst.

Initialisierung

public class SortedArray<T extends Comparable<T>> {
    private T[] array;
    private int size;
    private final int maxSize;
    @SuppressWarnings("unchecked")
    public SortedArray(int maxSize) {
        if (maxSize <= 0) {
            throw new IllegalArgumentException("Invalid array max size (must be positive): " + maxSize);
        }
        this.array = (T[]) new Comparable[maxSize];
        this.size = 0;
        this.maxSize = maxSize;
    }
}

In der Klasse „Sorted Array“ speichern wir die Größe des Arrays und fragen auch nach der maximalen Größe des Arrays sowie nach einem allgemeinen Grundgerüst für die Array-Initialisierung. Im Konstruktor fragen wir nach der maximalen Größe des Arrays, erstellen ein Objekt und geben es in unser gewünschtes Array um.

Getter

public int length() {
        return this.size;
    }
 public int maxLength() {
        return this.maxSize;
    }
 public T get(int index) {
        if (index < 0 || index >= this.size) {
            throw new IndexOutOfBoundsException("Index out of 
 bounds: " + index);
        }
        return this.array[index];
    }

Einfügemethode

private int findInsertionPosition(T item) {
        int left = 0;
        int right = size - 1;
        while (left <= right) {
            int mid = (left + right) / 2;
            int cmp = item.compareTo(this.array[mid]);
            if (cmp < 0) {
                right = mid - 1;
            } else {
                left = mid + 1;
            }
        }
        return left;
    }
public void insert(T item) {
        if (this.size >= this.maxSize) {
            throw new IllegalStateException("The array is already full");
        }

        int position = findInsertionPosition(item);

        for (int i = size; i > position; i--) {
            this.array[i] = this.array[i - 1];
        }
        this.array[position] = item;
        size++;
    }

Einfügemethode fügt das Element in sortierter Form an seiner Position ein.

Löschmethode

    public void delete(T item) {
        int index = binarySearch(item);
        if (index == -1) {
            throw new IllegalArgumentException("Unable to delete element " + item + ": the entry is not in the array");
        }

        for (int i = index; i < size - 1; i++) {
            this.array[i] = this.array[i + 1];
        }
        this.array[size - 1] = null;
        size--;
    }

Suchmethoden

private int binarySearch(T target) {
        int left = 0;
        int right = size - 1;
        while (left <= right) {
            int mid = (left + right) / 2;
            int cmp = target.compareTo(this.array[mid]);
            if (cmp == 0) {
                return mid;
            } else if (cmp < 0) {
                right = mid - 1;
            } else {
                left = mid + 1;
            }
        }
        return -1;
    }
public Integer find(T target) {
        int index = binarySearch(target);
        return index == -1 ? null : index;
    }

Traverse-Methode

public void traverse(Callback<T> callback) {
        for (int i = 0; i < this.size; i++) {
            callback.call(this.array[i]);
        }
    }

Rückrufschnittstelle

public interface Callback<T> {
        void call(T item);
    }

Verwendung der Callback-Schnittstelle beim Traversieren

public class UppercaseCallback implements UnsortedArray.Callback<String> {
    @Override
    public void call(String item) {
        System.out.println(item.toUpperCase());
    }
}

Unsortiertes Array

Von oben ist es fast dasselbe
Initialisierung und Getter sind gleich.

Einfügemethode

public void insert(T item) {
        if (this.size >= this.maxSize) {
            throw new IllegalStateException("The array is already full");
        } else {
            this.self[this.size] = item;
            this.size++;
        }
    }

Die Löschmethode ist ebenfalls dieselbe

Suchmethode

public Integer find(T target) {
        for (int i = 0; i < this.size; i++) {
            if (this.self[i].equals(target)) {
                return i;
            }
        }
        return null;
    }

Dynamisches Array

Dynamische Arrays sind wie Array-Listen oder Listen.

Initialisierung

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

    @SuppressWarnings("unchecked")
    public DynamicArray(int initialCapacity) {
        if (initialCapacity <= 0) {
            throw new IllegalArgumentException("Invalid initial capacity: " + initialCapacity);
        }
        this.capacity = initialCapacity;
        this.array = (T[]) new Object[initialCapacity];
        this.size = 0;
    }
}

Methode einfügen

private void resize(int newCapacity) {
        @SuppressWarnings("unchecked")
        T[] newArray = (T[]) new Object[newCapacity];
        for (int i = 0; i < size; i++) {
            newArray[i] = array[i];
        }
        array = newArray;
        capacity = newCapacity;
    }
    public void insert(T item) {
        if (size >= capacity) {
            resize(2 * capacity);
        }
        array[size++] = item;
    }

Methode löschen

public void delete(T item) {
        int index = find(item);
        if (index == -1) {
            throw new IllegalArgumentException("Item not found: " + item);
        }

        for (int i = index; i < size - 1; i++) {
            array[i] = array[i + 1];
        }
        array[--size] = null;
        if (capacity > 1 && size <= capacity / 4) {
            resize(capacity / 2);
        }
    }

Alles andere ist gleich.
Ich hoffe, das hilft bei der Arbeit mit Arrays. Viel Glück!

Das obige ist der detaillierte Inhalt vonDatenstrukturen: Arrays. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!