Datenstrukturen - Array

Array ist eine der grundlegendsten und am häufigsten verwendeten Datenstrukturen.

Ein Array ist eine Sammlung von Elementen desselben Typs, die zusammenhängend im Speicher abgelegt sind.

Array-Definition und Speicherlayout

In C wird nach der Deklaration eines Arrays ein zusammenhängender Speicherblock zugewiesen, und auf jedes Element kann direkt über den Index zugegriffen werden.

数组内存布局示意图

Die obige Abbildung zeigt das Speicherlayout eines Arrays mit 5 int-Elementen. Angenommen, die Startadresse ist 0x1000 und jedes int belegt 4 Bytes, dann:

  • arr[0]Befindet sich an Adresse 0x1000
  • arr[1]Befindet sich an Adresse 0x1004 (0x1000 + 4)
  • arr[i]Befindet sich an Adresse 0x1000 + i × 4

Gerade wegen dieser zusammenhängenden Speichereigenschaft können ArraysStartadresse + Offsetverwenden, um in O(1)-Zeit auf jedes Element zuzugreifen.

Eindimensionales Array

Beispiel

#include <stdio.h>

int main() {
    /* Eindimensionales Array deklarieren und initialisieren */
    int arr[5] = {10, 20, 30, 40, 50};

    /* Jedes Element durchlaufen und darauf zugreifen */
    printf("Array-Elemente: ");
    for (int i = 0; i < 5; i++) {
        printf("%d ", arr[i]);
    }
    printf("\n");  /* Ausgabe: Array-Elemente: 10 20 30 40 50 */

    /* Direkter Zugriff über Index, Zeitkomplexität O(1) */
    printf("arr[2] = %d\n", arr[2]);  /* Ausgabe: 30 */

    return 0;
}

Mehrdimensionales Array

C unterstützt mehrdimensionale Arrays, am häufigsten sind zweidimensionale Arrays, die oft verwendet werden, um tabellarische Daten wie Matrizen darzustellen.

Zweidimensionale Arrays werden weiterhin zusammenhängend im Speicher zeilenweise gespeichert (Zeilenhauptreihenfolge) und durch Berechnung von Zeilen- und Spaltenindizes auf eine zweidimensionale Ansicht abgebildet.

Beispiel

#include <stdio.h>

int main() {
    /* Deklariere ein zweidimensionales Array mit 3 Zeilen und 4 Spalten */
    int matrix[3][4] = {
        {1,  2,  3,  4},
        {5,  6,  7,  8},
        {9, 10, 11, 12}
    };

    /* Durchlaufe das zweidimensionale Array: äußere Schleife iteriert über Zeilen, innere Schleife iteriert über Spalten */
    printf("Zweidimensionales Array (3×4 Matrix):\n");
    for (int i = 0; i < 3; i++) {        /* i ist der Zeilenindex */
        for (int j = 0; j < 4; j++) {    /* j ist der Spaltenindex */
            printf("%2d ", matrix[i][j]);
        }
        printf("\n");
    }

    /* Zugriff auf ein bestimmtes Element: matrix[row][column] */
    printf("matrix[1][2] = %d\n", matrix[1][2]);  /* Ausgabe: 7 */
    return 0;
}

Die Berechnungsformel für die Speicheradresse eines zweidimensionalen Arrays:元素地址 = 起始地址 + (i × 列数 + j) × sizeof(元素类型). Dabei ist i der Zeilenindex und j der Spaltenindex.

Grundlegende Operationen mit Arrays

数组插入和删除操作流程

Die obige Abbildung zeigt die Kernschritte der Einfüge- und Löschoperationen von Arrays: Beim Einfügen müssen die Elemente nach der Zielposition einzeln nach hinten verschoben werden, um Platz zu schaffen; beim Löschen müssen die Elemente nach der Zielposition einzeln nach vorne verschoben werden, um die Lücke zu füllen.

Traversierung

Beispiel

#include <stdio.h>

/* Alle Elemente des Arrays durchlaufen und ausgeben Zeitkomplexität: O(n), wobei n die Länge des Arrays ist */
"Traversierungsergebnis: "
void traverse(int arr[], int n) {
    printf(/* Berechne die Länge des Arrays */);
    for (int i = 0; i < n; i++) {
        printf("%d ", arr[i]);
    }
    printf("\n");
}

int main() {
    int arr[] = {15, 28, 43, 56, 71};
    int n = sizeof(arr) / sizeof(arr[0]);  Insertion
    traverse(arr, n);
    return 0;
}

Insertion

Beispiel

#include <stdio.h>

"Array ist voll, Einfügen nicht möglich
"Ungültige Einfügeposition
/* Von hinten nach vorne die Elemente ab pos und danach um eine Position nach hinten verschieben */
/* Daten an der neuen Position schreiben */
/* Elementanzahl um 1 erhöhen */
int insert(int arr[], int n, int pos, int value, int capacity) {
    if (n >= capacity) {
        printf(/* Kapazität ist 10, derzeit sind 4 Elemente vorhanden */\n");
        return -1;
    }
    if (pos < 0 || pos > n) {
        printf("Vor dem Einfügen: "\n");
        return -1;
    }

    /* Ausgabe: Vor dem Einfügen: 10 20 30 40 */
    for (int i = n; i > pos; i--) {
        arr[i] = arr[i - 1];
    }
    arr[pos] = value;  /* Daten an die neue Position schreiben */
    return n + 1;      /* Anzahl der Elemente um 1 erhöhen */
}

int main() {
    int arr[10] = {10, 20, 30, 40};  /* Kapazität ist 10, aktuell sind 4 Elemente vorhanden */
    int n = 4;

    printf(Vor dem Einfügen:); for (int i = 0; i < n; i++) printf("%d ", arr[i]);
    printf("\n");  /* Ausgabe: Vor dem Einfügen: 10 20 30 40 */

    n = insert(arr, n, 2, 25, 10);  /* 25 an Index 2 einfügen */

    printf("Nach dem Einfügen: "); for (int i = 0; i < n; i++) printf("%d ", arr[i]);
    printf("\n");  /* Ausgabe: Nach dem Einfügen: 10 20 25 30 40 */
    return 0;
}

Löschen

Beispiel

#include <stdio.h>

/* Lösche das Element an einer angegebenen Position im Array
Parameter: arr Array, n aktuelle Elementanzahl, pos Löschposition (0-basiert)
Zeitkomplexität: O(n), im schlimmsten Fall müssen n Elemente verschoben werden
Rückgabewert: die Anzahl der Elemente nach dem Löschen */
int delete(int arr[], int n, int pos) {
    if (n <= 0) {
        printf("Array ist leer, Löschen nicht möglich\n");
        return 0;
    }
    if (pos < 0 || pos >= n) {
        printf("Ungültige Löschposition"\n");
        return n;
    }

    /* Von vorne nach hinten, die Elemente nach pos um eine Position nach vorne verschieben */
    for (int i = pos; i < n - 1; i++) {
        arr[i] = arr[i + 1];
    }
    return n - 1;  /* Die Anzahl der Elemente um 1 verringern */
}

int main() {
    int arr[10] = {10, 20, 30, 40, 50};
    int n = 5;

    printf("Vor dem Löschen: "); for (int i = 0; i < n; i++) printf("%d ", arr[i]);
    printf("\n");  /* Ausgabe: Vor dem Löschen: 10 20 30 40 50 */

    n = delete(arr, n, 2);  /* Das Element am Index 2 (30) löschen */

    printf("Nach dem Löschen: "); for (int i = 0; i < n; i++) printf("%d ", arr[i]);
    printf("\n");  /* Ausgabe: Nach dem Löschen: 10 20 40 50 */
    return 0;
}

Suche

Um einen Zielwert in einem ungeordneten Array zu finden, ist die einfachste Methode, das gesamte Array zu durchlaufen und eins nach dem anderen zu vergleichen, was als lineare Suche bezeichnet wird.

Beispiel

#include <stdio.h>

/* Lineare Suche: Suche nach einem Zielwert in einem Array
Zeitkomplexität: O(n), im schlimmsten Fall muss das gesamte Array durchlaufen werden
Rückgabewert: der Index des Zielelements, gibt -1 zurück, wenn es nicht gefunden wurde */
int search(int arr[], int n, int target) {
    for (int i = 0; i < n; i++) {
        if (arr[i] == target) {
            return i;  /* Gefunden, den Index zurückgeben */
        }
    }
    return -1;  /* Nicht gefunden */
}

int main() {
    int arr[] = {43, 17, 89, 25, 61};
    int n = 5;

    int idx = search(arr, n, 89);
    if (idx != -1) {
        printf("Zielwert 89 gefunden, Index ist %d\n", idx);  /* Ausgabe: Zielwert 89 gefunden, Index ist 2 */
    } else {
        printf("Zielwert nicht gefunden\n");
    }
    return 0;
}

Vor- und Nachteile von Arrays

VorteileBeschreibung
O(1) wahlfreier ZugriffAuf jedes Element kann in konstanter Zeit über den Index zugegriffen werden, was der größte Vorteil von Arrays ist
Zusammenhängender SpeicherZusammenhängende Speicherung begünstigt CPU-Cache-Treffer (räumliche Lokalität) und verbessert die Zugriffseffizienz
Einfache ImplementierungIntuitive Syntax, die in den meisten Programmiersprachen nativ unterstützt wird
NachteileBeschreibung
Feste GrößeStatische Arrays in C haben eine zur Kompilierzeit festgelegte Größe und können nicht dynamisch angepasst werden
Langsames Einfügen/LöschenDas Einfügen oder Löschen von Elementen in der Mitte eines Arrays erfordert das Verschieben vieler Elemente, mit einer Zeitkomplexität von O(n)
SpeicherverschwendungWenn das deklarierte Array zu groß ist, aber die tatsächliche Nutzung gering ist, führt dies zu Speicherverschwendung

Genau diese Einschränkungen führen zu der flexibleren dynamischen Struktur, die im nächsten Kapitel behandelt wird —verkettete Liste。

Zusammenfassung der Operationskomplexität

AktionZeitkomplexitätBeschreibung
Zugriff über IndexO(1)Direkte Adressberechnung
Am Ende einfügenO(1)Elemente müssen nicht verschoben werden
Am Anfang/in der Mitte einfügenO(n)Nachfolgende Elemente müssen verschoben werden
Letztes Element löschenO(1)Elemente müssen nicht verschoben werden
Element am Anfang/in der Mitte löschenO(n)Nachfolgende Elemente müssen verschoben werden
Lineare SucheO(n)Eins nach dem anderen vergleichen
Binäre Suche (sortiertes Array)O(log n)Erfordert, dass das Array sortiert ist
Weitere Erweiterungen