Strukturen und verkettete Datenstrukturen in C

Eine Struktur fasst zusammengehörige Werte zu einem Datensatz zusammen. Ihre Komponenten haben Namen und können unterschiedliche Typen haben. Ein Sensormesswert benötigt zum Beispiel sowohl einen Bezeichner als auch eine Temperatur.

Einen Datensatz definieren und initialisieren

struct reading {
    int id;
    double temp_c;
};
struct reading r = {.temp_c = 21.5, .id = 7};
r.temp_c += 0.5;

Die Definition führt den Typ struct reading ein; reading ist sein Struktur-Tag. Das abschließende Semikolon steht nach der schließenden geschweiften Klammer. Die Definition des Typs legt kein Objekt an. Die Deklaration von r erzeugt ein Objekt und . wählt dessen Komponenten aus. Hier wird die Temperatur zu 22,0 °C. Wenn nur ein Struktur-Tag deklariert ist, enthält der Typname struct: reading r; benötigt ein separates typedef.

Ein Initialisierer wie {7, 21.5} folgt der Reihenfolge der Deklaration. Komponentenbezeichnungen wie .id = 7 erlauben es dir, Komponenten in einer anderen Reihenfolge zu benennen. In einem Initialisierer ausgelassene Komponenten erhalten Nullwerte, sodass {0} den ganzen Datensatz initialisiert. Eine lokale Deklaration struct reading r; ohne Initialisierer lässt ihre Komponenten unbestimmt, bis ihnen Werte zugewiesen werden.

Eine Komponente hat ihren eigenen Typ und ihre eigene Adresse. Um eine Temperatur mit scanf einzulesen, verwende scanf("%lf", &r.temp_c) und prüfe, ob der Rückgabewert 1 ist. Der Punkt bindet vor &, sodass die Adresse der double-Komponente übergeben wird.

Werte kopieren und vergleichen

struct reading s = r;
s.temp_c = -4.0;
int same = r.id == s.id && r.temp_c == s.temp_c;

Die Zuweisung kopiert alle Komponenten. Eine Änderung von s.temp_c lässt r.temp_c bei 22,0. Feste Arrays innerhalb von Strukturen werden ebenfalls kopiert: Eine Komponente char name[32] gehört zum Datensatz. Das funktioniert, obwohl eigenständige C-Arrays nicht mit = zugewiesen werden können. Zeigerkomponenten erfordern besondere Sorgfalt, weil der kopierte Zeiger weiterhin auf dasselbe Objekt zeigt.

C definiert == nicht für ganze Strukturen. Vergleiche die Komponenten, die für deine Aufgabe Gleichheit bestimmen. memcmp vergleicht rohe Bytes einschließlich Füllbytes und kann einen Unterschied zwischen Datensätzen melden, deren Komponentenwerte gleich sind.

Die Speicheranordnung nachvollziehen

Komponenten stehen in der Reihenfolge ihrer Deklaration, ohne Füllbytes vor der ersten Komponente. Der Compiler kann ungenutzte Bytes zwischen Komponenten und am Ende hinzufügen, um die Anforderungen an die Speicherausrichtung zu erfüllen. Auf einer gängigen 64-Bit-Plattform mit einem int von 4 Byte und einer Ausrichtung von 4 Byte belegt struct { char c; int i; char d; } 12 Byte. Seine Komponenten beginnen bei den Offsets 0, 4 und 8. Eine Umordnung zu int i; char c; char d; verringert die Größe üblicherweise auf 8 Byte. Verwende sizeof für die tatsächliche Größe und offsetof aus <stddef.h> für einen Offset.

Strukturen können verschachtelt sein. Bei struct point { double x_m, y_m; }; und struct rect { struct point corner; double width_m, height_m; }; greift box.corner.x_m auf die x-Koordinate der Ecke in Metern zu. Eine Struktur kann keine vollständige Komponente ihres eigenen Typs enthalten: Das würde ein unendlich großes Objekt erfordern. Ein Zeiger auf ihren eigenen Typ hat eine feste Größe und ermöglicht verkettete Knoten.

Ein typedef gibt einem bestehenden Typ einen weiteren Namen. Es ändert, wie du den Typ schreibst, nicht aber, wie sich seine Objekte verhalten. typedef double meters; macht meters zu einem weiteren Namen für double.

Eine Struktur benennen und als Wert übergeben

typedef struct {
    int id;
    double temp_c;
} reading;

reading make_reading(int id, double t) {
    reading r = {id, t};
    return r;
}
void warm_copy(reading r) {
    r.temp_c += 1.0;
}

Du kannst nun reading r = make_reading(7, 21.5); deklarieren. Die Rückgabe einer Struktur gibt ihren Wert zurück. Der Aufruf von warm_copy(r) gibt der Funktion eine Kopie, sodass die Temperatur des Aufrufers bei 21,5 °C bleibt. Eine Kopie eines kleinen Datensatzes ist oft die klarste Schnittstelle, wenn das Objekt des Aufrufers unverändert bleiben soll.

Ein selbstreferenzieller Typ benötigt sein Struktur-Tag innerhalb der Definition:

typedef struct node {
    int number;
    struct node *next;
} node;

Der Aliasname node ist nach der Deklaration verfügbar. Innerhalb dieser geschweiften Klammern bezeichnet struct node bereits den unvollständigen Typ und kann für einen Zeiger verwendet werden. Das Struktur-Tag und der Aliasname können gleich geschrieben werden, weil Tags einen eigenen Namensraum verwenden.

Über einen Zeiger auf das Objekt des Aufrufers zugreifen

void warm(reading *p) {
    p->temp_c += 1.0;
}
reading r = {7, 21.5};
reading *p = &r;
p->temp_c -= 1.5;
warm(&r);

Die Subtraktion ändert r.temp_c auf 20,0; warm ändert den Wert anschließend auf 21,0. Die Funktion erhält eine Kopie der Adresse und beide Zeiger greifen weiterhin auf denselben Datensatz zu. Verwende -> mit einem Zeiger und . mit einem Strukturobjekt. p->temp_c bedeutet (*p).temp_c. Die Klammern sind nötig, weil der Komponentenzugriff stärker bindet als die Dereferenzierung: *p.temp_c versucht, eine Komponente von p auszuwählen, bevor * angewendet wird.

Für lesenden Zugriff ohne Strukturkopie nimm const reading *p entgegen. Eine Zuweisung an p->temp_c über diesen Zeiger wird zurückgewiesen. Die Zeigervariable kann sich weiterhin ändern, zum Beispiel wenn sie durch ein Array läuft. Dagegen macht reading *const p den Zeiger selbst unveränderlich. Bei Strukturen mit Zeigerkomponenten macht ein Zeiger auf konstante Daten separat allokierte Daten, auf die eine Komponente zeigt, nicht schreibgeschützt.

Einem Datensatz auf dem Heap einen Besitzer zuweisen

Binde <stdlib.h> für die Speicherallokation und <stdbool.h> für dieses Erfolgsergebnis ein:

bool make_heap_reading(reading **out, int id, double t) {
    reading *p = malloc(sizeof *p);
    if (p == NULL) return false;
    *p = (reading){.id = id, .temp_c = t};
    *out = p;
    return true;
}

Die Funktion schreibt *out erst nach erfolgreicher Speicherallokation. Der Aufrufer kann reading *item = NULL; deklarieren, make_heap_reading(&item, 8, -2.0) aufrufen, ein falsches Ergebnis behandeln und später free(item) aufrufen. sizeof *p bestimmt die Größe des Typs, auf den gezeigt wird, noch bevor p auf einen initialisierten Datensatz zeigt; dieser Ausdruck liest den Datensatz nicht.

Ein Zeiger auf eine automatische lokale Struktur wird beim Zurückkehren der Funktion zu einem hängenden Zeiger. Gib den Strukturwert oder einen allokierten Speicherblock auf dem Heap mit einem klaren Besitzer zurück. Die Rückgabe von &r aus einer Funktion mit der lokalen Variablen r kann deren Lebensdauer nicht verlängern.

Ein Array von Strukturen hält Datensätze nebeneinander. Verwende einen Index, um einen Datensatz auszuwählen, und anschließend einen Punkt, um eine Komponente auszuwählen. So funktionieren Durchlaufen, Suchen und Sortieren ähnlich wie bei einem Array von Zahlen.

Datensätze mit einer ausdrücklichen Anzahl durchlaufen

reading readings[4] = {
    {1, 21.5}, {2, -3.0}, {3, 18.25}, {4, 30.0}
};
size_t n = sizeof readings / sizeof readings[0];
size_t best = 0;
for (size_t i = 1; i < n; ++i) {
    if (readings[i].temp_c > readings[best].temp_c)
        best = i;
}

Hier ist reading der Aliasname für die Struktur mit Bezeichner und Temperatur. Der Index des besten Werts wandert von 0 zu 3, sodass der wärmste Datensatz die ID 4 und die Temperatur 30,0 °C hat. Mit einem vorhandenen Element zu beginnen funktioniert auch, wenn jede Temperatur negativ ist; ein vermeintliches Maximum von null als Ausgangswert kann fehlschlagen. Dieser Durchlauf benötigt mindestens ein Element. Eine wiederverwendbare Suche muss ein leeres Array melden, bevor sie Element 0 liest.

Die Berechnung der Anzahl mit sizeof funktioniert dort, wo readings ein Array ist. Bei einem Funktionsparameter wird eine Arraydeklaration zu einem Zeiger, übergib daher n separat. (items + i)->temp_c und items[i].temp_c greifen auf dieselbe Komponente zu.

Eine Vergleichsfunktion für qsort bereitstellen

Binde <stdlib.h> ein. Für endliche Temperaturwerte gibt diese Vergleichsfunktion ein Vorzeichen zurück, ohne eine kleine Temperaturdifferenz in eine Ganzzahl umzuwandeln:

int cmp_temp(const void *a, const void *b) {
    const reading *x = a;
    const reading *y = b;
    return (x->temp_c > y->temp_c)
         - (x->temp_c < y->temp_c);
}
/* With the array above: */
qsort(readings, n, sizeof readings[0], cmp_temp);

Die Vergleichsfunktion erhält Adressen von Elementen. Negativ bedeutet, dass das erste vorher kommt, null bedeutet Gleichstand und positiv bedeutet danach. Die sortierte ID-Reihenfolge ist 2, 3, 1, 4. Die Rückgabe der double-Differenz schneidet eine Differenz wie −0,25 zu null ab. Das Subtrahieren von Ganzzahlschlüsseln kann überlaufen. Zuerst zu vergleichen vermeidet diese Fehler. qsort erhält die ursprüngliche Reihenfolge gleich eingestufter Elemente nicht.

Ein Array vergrößern, ohne seinen Speicher zu verlieren

Halte die Anzahl belegter Elemente und die Kapazität getrennt fest. Verwende für ein allokiertes Array mit positivem cap beim Verdoppeln der Kapazität einen temporären Zeiger. Binde <stdint.h> für SIZE_MAX ein:

if (cap > SIZE_MAX / 2 / sizeof *items) return false;
size_t new_cap = 2 * cap;
reading *tmp = realloc(items, new_cap * sizeof *items);
if (tmp == NULL) return false;
items = tmp;
cap = new_cap;

Diese Anweisungen gehören in eine Funktion, die bool zurückgibt; items ist ihr Arrayzeiger und cap ihre positive Kapazität. Bei einem Fehlschlag bleibt der alte Speicherblock verfügbar. Bei Erfolg kann der Speicherblock verschoben werden, sodass alte Zeiger auf seine Elemente ersetzt werden müssen. Eine Anfangskapazität von null benötigt eine eigene erste Speicherallokation.

Entscheiden, was eine Kopie besitzt

Bei typedef struct { char *name; int age; } person; kopiert person b = a; die Adresse in name. Beide Datensätze greifen auf dieselbe Zeichenkette zu. Würden beide als Besitzer die Zeichenkette freigeben, würde derselbe Speicherblock zweimal freigegeben. Für eine unabhängige Kopie reserviere strlen(a.name) + 1 Byte, prüfe den Erfolg und verwende strcpy aus <string.h>. Eine feste Komponente char name[32] wird mit der Struktur kopiert. strdup übernimmt Speicherallokation und Kopieren, gehört aber zu POSIX und C23, nicht zur C17-Standardbibliothek.

Ein Aufzählungstyp gibt ganzzahligen Auswahlmöglichkeiten lesbare Namen. Namen wie HIGH machen den Zweck einer Bedingung sichtbar, ohne dass sich Lesende merken müssen, wofür die Zahl 10 steht.

Die Nummerierung nachvollziehen

enum weekday { MON, TUE, WED, THU, FRI, SAT, SUN };
enum level { LOW = 1, MEDIUM, HIGH = 10, CRITICAL };
enum level alert = HIGH;

Ein ausgelassener erster Wert ist null. Spätere ausgelassene Werte sind jeweils um eins größer als der vorherige Wert. Somit ist MON gleich 0 und SUN gleich 6; die Stufen sind 1, 2, 10 und 11. Ein ausdrücklicher Wert setzt die Zählung an dieser Stelle neu an. Verschiedene Konstanten können denselben Wert haben, aber gleiche Werte können nicht als separate case-Marken im selben switch auftreten.

Ein Aliasname kann eine Deklaration verkürzen: typedef enum { RED, YELLOW, GREEN } light; erlaubt light signal = RED;. Aufzählungskonstanten teilen sich in ihrem Gültigkeitsbereich den gewöhnlichen Namensraum der Bezeichner. Zwei verschiedene Aufzählungstypen können nicht beide RED im selben Gültigkeitsbereich deklarieren. Präfixe wie LIGHT_RED und PAINT_RED halten die Namen unterscheidbar.

Jede Auswahlmöglichkeit behandeln

const char *level_name(enum level value) {
    switch (value) {
        case LOW: return "low";
        case MEDIUM: return "medium";
        case HIGH: return "high";
        case CRITICAL: return "critical";
    }
    return "unknown";
}

Jedes return beendet seinen Fall. Wenn ein Fall stattdessen eine Aktion ausführt und dann enden soll, gib ihm ein break; wird die nächste Marke erreicht, setzt sich die Ausführung dort fort. Bei GCC aktiviert -Wall Warnungen für fehlende Fälle eines Aufzählungstyps, wenn kein default vorhanden ist; Clang meldet solche Auslassungen ebenfalls standardmäßig. Eine Warnung kann einen fehlenden Fall aufdecken, wenn du später eine Konstante hinzufügst.

Eingaben als Auswahlmenge prüfen

Der Aufzählungstyp erzwingt nicht die Zugehörigkeit zur benannten Menge. C17 erlaubt die Zuweisung einer Ganzzahl, sodass enum level x = 42; kompiliert werden kann. Eine Prüfung, ob die Zahl zwischen 1 und 11 einschließlich liegt, lässt weiterhin unbenannte Werte wie 6 zu. Prüfe die tatsächlich erlaubten Werte:

#include <stdbool.h>
bool valid_level(int value) {
    return value == LOW || value == MEDIUM
        || value == HIGH || value == CRITICAL;
}

Erst nach dieser Prüfung sollte eine Eingabe zu einer Stufe werden. Für die aufeinanderfolgenden Wochentage genügt eine Wertebereichsprüfung von MON bis SUN. In einem gewöhnlichen C17-Aufzählungstyp haben die Aufzählungskonstanten den Typ int. C23 unterstützt zusätzlich einen festgelegten zugrunde liegenden Typ wie enum color : unsigned char; diese Syntax gehört nicht zu C17.

Namen ausgeben und Anzahlen verwenden

printf("%d\n", SUN) gibt „6“ aus, nicht „SUN“. Für aufeinanderfolgende Werte, die bei null beginnen, liefert ein Namensarray den Text: const char *day_names[] = {"Mon", "Tue", "Wed", "Thu", "Fri", "Sat", "Sun"};. Nach der Prüfung eines Index ist day_names[SUN] gleich „Sun“. Für den Zugriff auf ein solches Array mit einem Stufenwert wie HIGH wäre eine andere Zuordnung nötig, weil die Stufenwerte Lücken haben.

Wird DAY_COUNT unmittelbar nach SUN hinzugefügt, erhält es den Wert 7, der als Schleifenschranke oder Arraygröße nützlich ist. Es zählt die Tage, ist aber selbst kein gültiger Tag. Namen von Aufzählungskonstanten folgen den Gültigkeitsregeln von C und können von Debuggern angezeigt werden; #define führt dagegen eine Textersetzung durch den Präprozessor aus.

Eine Union gibt mehreren Komponenten denselben Speicherbereich. Sie eignet sich für einen Wert, der eine von mehreren Arten haben kann. Eine Struktur gibt jeder Komponente einen eigenen Speicherbereich und eignet sich für einen Datensatz, der alle diese Werte zusammen benötigt.

Eine Alternative speichern

union value {
    int i;
    double d;
    char c;
};
union value v = {.d = 2.5};

Alle Komponenten beginnen an derselben Adresse. Die Union muss ihre größte Komponente aufnehmen und die Anforderungen an die Speicherausrichtung erfüllen; mit einem double von 8 Byte belegt diese Union auf gängigen Plattformen 8 Byte. Ein einfacher Initialisierer {42} initialisiert ihre erste Komponente, i; .d = 2.5 wählt d ausdrücklich aus.

Das Schreiben von v.i = 42 nach dem Initialisierer ersetzt die gespeicherte Alternative. Das anschließende Lesen von v.d wandelt 42 nicht in einen double um: Es interpretiert die gespeicherten Bytes anhand einer anderen Darstellung. Diese Darstellung kann ungültig sein. Lies die Komponente, die zu dem gespeicherten Wert gehört.

Festhalten, welche Komponente gültig ist

Kombiniere die Union mit einem Aufzählungstyp. Der Aufzählungswert ist die Kennzeichnung und die Union enthält die Nutzdaten:

enum kind { K_INT, K_DOUBLE, K_CHAR };
struct tagged {
    enum kind kind;
    union value as;
};
struct tagged make_double(double d) {
    return (struct tagged){.kind = K_DOUBLE, .as = {.d = d}};
}

Eine Hilfsfunktion setzt beide Teile gemeinsam. Schreibender Code hält die beiden Felder aufeinander abgestimmt. Wenn Code t.as.i schreibt, aber t.kind auf K_DOUBLE belässt, wählt später lesender Code die falsche Darstellung.

#include <stdio.h>
void print_cell(struct tagged t) {
    switch (t.kind) {
        case K_INT: printf("%d", t.as.i); break;
        case K_DOUBLE: printf("%.1f", t.as.d); break;
        case K_CHAR: printf("%c", t.as.c); break;
    }
}

Wird diese Funktion für Zellen mit 42, 2,5 und 'x' aufgerufen und werden zwischen den Aufrufen Leerzeichen ausgegeben, entsteht „42 2.5 x“. Jeder Fall wählt sowohl die passende Komponente als auch das passende Format. Ein Token in einem Taschenrechner kann ebenso entweder eine Zahl oder einen Operator enthalten.

Auf gängigen 64-Bit-Plattformen belegt struct tagged mit einem Aufzählungswert von 4 Byte, Füllbytes und dieser Union von 8 Byte insgesamt 16 Byte. Eine Struktur, die den Aufzählungswert und alle drei Alternativen getrennt speichert, benötigt üblicherweise 24 Byte. Dies sind Beispiele für die Speicheranordnung; frage die tatsächlichen Typgrößen mit sizeof ab.

Kleine Flags in Bitfeldern zusammenfassen

struct flags {
    unsigned int ready : 1;
    unsigned int mode : 3;
};

Die Breite steht nach dem Doppelpunkt. Ein vorzeichenloses Feld mit 1 Bit enthält 0 oder 1; ein Feld mit 3 Bit enthält 0 bis 7. Wenn du 9 in mode speicherst, bleiben die drei niederwertigen Bits erhalten und 1 wird gespeichert. Dabei gehen Informationen verloren. Prüfe daher einen Modus vor dem Speichern, wenn größere Werte einen Fehler anzeigen.

Ein Bitfeld hat keine separat adressierbare Stelle, daher ist &flags.mode für eine Variable namens flags ungültig. Seine Allokationsreihenfolge und Anordnung hängen von der Implementierung ab. Verwende eine Bitfelddeklaration nicht als portabel gültige Zusage für eine exakte Datei- oder Geräteanordnung. Eine angegebene Breite legt den Wertebereich des Feldes fest, nicht die Anordnung jedes umgebenden Bytes.

Eine einfach verkettete Liste speichert jedes Element in einem separat allokierten Knoten. Jeder Knoten enthält seinen Wert und die Adresse des nächsten Knotens. Der Kopfzeiger zeigt auf den ersten Knoten; NULL kennzeichnet sowohl eine leere Liste als auch das Ende einer Kette.

Den Verweis definieren und am Anfang einfügen

#include <stdbool.h>
#include <stdlib.h>
typedef struct node {
    int number;
    struct node *next;
} node;

bool prepend(node **head, int value) {
    node *n = malloc(sizeof *n);
    if (n == NULL) return false;
    n->number = value;
    n->next = *head;
    *head = n;
    return true;
}

Beginne mit node *list = NULL;. Rufe prepend(&list, value) auf und behandle ein falsches Ergebnis. Die Funktion nimmt die Adresse des Kopfzeigers des Aufrufers entgegen. *head bezeichnet daher den Zeiger, der geändert werden muss. Würde die Funktion nur node *head entgegennehmen und diesem lokalen Zeiger etwas zuweisen, bliebe der Kopfzeiger des Aufrufers unverändert.

Die Reihenfolge der letzten Zuweisungen erhält die alte Liste. Verbinde zuerst den neuen Knoten mit dem alten ersten Knoten und ersetze dann den Kopfzeiger. Wenn du diese Anweisungen umkehrst, wird n->next auf n selbst gesetzt und die alte Kette geht verloren. Für die eintreffenden Werte 1, 2 und 3 ergibt das wiederholte Einfügen am Anfang erst 1, dann 2 → 1 und dann 3 → 2 → 1 → NULL. Das Einfügen am Anfang kehrt die Reihenfolge des Eintreffens um.

Durchlaufen, ohne den besitzenden Zeiger zu bewegen

#include <stdio.h>
void print_list(const node *head) {
    for (const node *p = head; p != NULL; p = p->next)
        printf("%d ", p->number);
}

Der Zeiger p für den Durchlauf bewegt sich, während head verfügbar bleibt. Das Beispiel gibt „3 2 1 “ mit einem abschließenden Leerzeichen aus. Bei einer leeren Liste wird der Schleifenrumpf nullmal ausgeführt. Es gibt keinen Arrayindex: Jeder Schritt liest einen Verweis, um den nächsten Knoten zu finden. Die allokierten Speicherblöcke können über den Speicher verstreut sein und das Einfügen eines Knotens bewegt vorhandene Knoten nicht.

Am Ende hinzufügen

bool append(node **head, int value) {
    node *n = malloc(sizeof *n);
    if (n == NULL) return false;
    *n = (node){.number = value, .next = NULL};
    node **link = head;
    while (*link != NULL) link = &(*link)->next;
    *link = n;
    return true;
}

link beginnt bei der Adresse des Kopfzeigers des Aufrufers. Danach wird der Zeiger zur Adresse jeder next-Komponente weiterbewegt, bis der abschließende Nullverweis erreicht ist. Eine Zuweisung an dieser Stelle funktioniert auch für eine leere Liste. Ohne gespeicherten Tail-Zeiger muss bei jedem Anhängen zunächst der vorhandenen Kette bis zum Ende gefolgt werden. Eine Funktion kann auch einen neuen Kopfzeiger zurückgeben, sofern der Aufrufer ihn speichert und eine fehlgeschlagene Speicherallokation behandelt, ohne die alte Liste zu verlieren.

Knoten in sicherer Reihenfolge freigeben

void clear_list(node **head) {
    while (*head != NULL) {
        node *old = *head;
        *head = old->next;
        free(old);
    }
}

Lies den Nachfolger, solange old noch existiert, verschiebe den Kopfzeiger und gib dann den alten Knoten frei. Nach der Schleife ist der Kopfzeiger des Aufrufers NULL. Das Lesen von old->next nach der Freigabe von old ist ein Zugriff nach der Speicherfreigabe, selbst wenn der Speicher unverändert erscheint. Ein Speicherprüfprogramm kann helfen, ungültige Lesezugriffe und vergessene Speicherblöcke aufzudecken; das Aufräumen muss auch nach dem Fehlschlag einer späteren Operation erfolgen.

Die Suche in einer Liste folgt jeweils einem Verweis. Zum Einfügen und Löschen wird mehr benötigt: die Adresse des Verweises, der geändert werden muss. Dieser Verweis kann der Kopfzeiger oder eine next-Komponente in einem vorherigen Knoten sein.

Nach einem Wert suchen

Mit dem Typ node mit den Komponenten number und next:

node *find(node *head, int value) {
    for (node *p = head; p != NULL; p = p->next)
        if (p->number == value) return p;
    return NULL;
}

Bei einer Übereinstimmung wird die Adresse des tatsächlichen Knotens zurückgegeben. Bei einem fehlenden Wert wird NULL zurückgegeben. Um den 1.000. Knoten zu erreichen, musst du vom Kopfzeiger aus 999 Verweisen folgen, selbst wenn du seine Position im Voraus kennst.

Einen Zeiger auf den zu ändernden Verweis halten

Ein node ** kann entweder auf den Kopfzeiger oder auf das next-Feld eines Knotens zeigen. Nenne ihn link: *link ist der Knoten, der aktuell über diesen Verweis erreicht wird. Das Weitergehen mit link = &(*link)->next ändert, welchen Verweis du untersuchst; die Liste selbst wird dadurch nicht geändert.

bool insert_sorted(node **head, int value) {
    node **link = head;
    while (*link != NULL && (*link)->number < value)
        link = &(*link)->next;
    node *n = malloc(sizeof *n);
    if (n == NULL) return false;
    n->number = value;
    n->next = *link;
    *link = n;
    return true;
}

Binde <stdbool.h> und <stdlib.h> ein. Die Eingabeliste muss bereits aufsteigend sortiert sein. Halte vor dem ersten Wert an, der nicht kleiner als der neue Wert ist, sodass Duplikate vor gleichen Werten eingefügt werden. Die linke Seite von && prüft auf NULL, bevor die rechte Seite den Knoten dereferenziert. Würdest du die Tests vertauschen, würde am Ende ein Nullzeiger dereferenziert.

Nach dem Einfügen von 5, 2, 8 und 4 lautet die Liste 2 → 4 → 5 → 8. Beim Einfügen von 4 in 2 → 5 → 8 bewegt sich link vom Kopfzeiger zu 2.next. Der neue Knoten zeigt auf 5 und 2.next wird auf den neuen Knoten umgelenkt. Ist das neue Element das kleinste, bezeichnet link noch den Kopfzeiger. Am Ende bezeichnet der Zeiger den abschließenden Nullverweis.

Vor der Freigabe ausketten

bool remove_first(node **head, int value) {
    node **link = head;
    while (*link != NULL && (*link)->number != value)
        link = &(*link)->next;
    if (*link == NULL) return false;
    node *old = *link;
    *link = old->next;
    free(old);
    return true;
}

Die Schleife findet den eingehenden Verweis. Indem sein Ziel als old gespeichert wird, bleibt der Knoten verfügbar, während *link auf seinen Nachfolger geändert wird. Erst danach wird der entfernte Knoten freigegeben. Das Entfernen von 5 aus 2 → 4 → 5 → 8 ergibt 2 → 4 → 8. Wird anschließend 2 entfernt, ändert sich der Kopfzeiger und es bleibt 4 → 8. Fehlt der Wert, gibt die Funktion false zurück, ohne die Liste zu ändern.

Eine Version mit zwei Zeigern verwaltet prev und cur. Ist prev null, ist der gefundene Knoten der erste und der Kopfzeiger muss geändert werden; andernfalls aktualisiere prev->next. Wird der Fall des ersten Knotens vergessen, bleibt ein Zeiger auf freigegebenen Speicher zurück. Die Version mit der Adresse des Verweises behandelt beide Fälle durch dieselbe Zuweisung.

Prüfe eine leere Eingabe, eine Liste mit einem Knoten, Übereinstimmungen am Anfang und Ende sowie einen fehlenden Wert. Bestimme bei jeder Änderung den eingehenden Verweis, den betroffenen Knoten und seinen Nachfolger, bevor du eine Zuweisung schreibst. Kein verbleibender Knoten darf unerreichbar werden und kein Verweis darf auf einen freigegebenen Knoten zeigen.

Entscheidend ist, welche Operationen dein Programm ausführt. Arrays und Listen können dieselben Werte enthalten, greifen aber unterschiedlich darauf zu und verschieben sie unterschiedlich.

Die Operationen vergleichen

Bei einer Liste ist das Finden einer Position nicht kostenlos. Das Einfügen nach einem bereits bekannten Knoten erfolgt direkt, aber das Löschen benötigt außerdem den Vorgänger oder den Verweis auf den Knoten. Wenn nur die Adresse des Knotens vorliegt, muss eine einfach verkettete Liste normalerweise vom Kopfzeiger aus durchlaufen werden, um diesen eingehenden Verweis zu finden.

Auch der Speicherbedarf ist wichtig. Auf einer typischen 64-Bit-Plattform belegt ein Knoten mit einem int von 4 Byte und einem Zeiger von 8 Byte nach dem Einfügen von Füllbytes 16 Byte. Für 1.000 Ganzzahlen benötigen Knoten 16.000 Byte zuzüglich Verwaltungsdaten der Speicherallokation; ein zusammenhängendes Ganzzahlarray benötigt 4.000 Byte. Das Durchlaufen des Arrays ist normalerweise schneller, weil benachbarte Werte zusammen gespeichert sind.

Metadaten der Liste zusammenhalten

typedef struct {
    node *head;
    node *tail;
    size_t count;
} list_t;

Initialisiere eine umschließende Struktur mit list_t list = {0};. Für den leeren Zustand gelten head == NULL, tail == NULL und count == 0. Jedes erfolgreiche Einfügen oder Löschen muss neben den Verweisen auch die Anzahl aktualisieren. Eine fehlgeschlagene Speicherallokation ändert keinen dieser Werte.

Mit einem Tail-Zeiger sind nach einer geprüften Speicherallokation zum Anhängen diese Zuweisungen nötig:

n->next = NULL;
if (list.tail == NULL) list.head = n;
else list.tail->next = n;
list.tail = n;
++list.count;

Hier ist n ein initialisierter Knoten. Beim ersten Knoten werden Kopf- und Tail-Zeiger gleich. Beim Entfernen des letzten Knotens muss der Tail-Zeiger zurückgesetzt werden; bei einer einfach verketteten Liste wird dafür der Vorgänger benötigt. Das Entfernen des einzigen Knotens setzt beide Enden auf NULL und die Anzahl auf null.

In beide Richtungen verknüpfen

typedef struct dnode {
    int value;
    struct dnode *prev, *next;
} dnode;
typedef struct {
    dnode *head, *tail;
} dlist;

void unlink_node(dlist *list, dnode *d) {
    if (d->prev != NULL) d->prev->next = d->next;
    else list->head = d->next;
    if (d->next != NULL) d->next->prev = d->prev;
    else list->tail = d->prev;
    free(d);
}

Diese Funktion erhält einen noch existierenden Knoten, der zur Liste gehört. Beide Nachbarn werden angepasst, bevor er freigegeben wird. An den Enden wird statt eines fehlenden Nachbarn der Kopf- oder Tail-Zeiger geändert. Eine doppelt verkettete Liste kann rückwärts durchlaufen werden und einen bekannten Knoten löschen, ohne nach seinem Vorgänger zu suchen. Dafür sind ein weiterer Zeiger pro Knoten und mehr zu verwaltende Verweise nötig.

Daten im Besitz vor ihrem Knoten freigeben

Ein word_node kann sowohl einen Speicherblock für den Knoten als auch über word einen Speicherblock für eine Zeichenkette besitzen. Sichere next, rufe free(n->word) und dann free(n) auf und gehe zum gesicherten Nachfolger. Wird nur der Knoten freigegeben, entsteht für die Zeichenkette ein Speicherleck. Das Lesen von n->word nach der Freigabe des Knotens ist ungültig. Der Besitz beschreibt, welcher Code jeden Speicherblock freigeben muss, selbst wenn mehrere Zeiger darauf zugreifen können.

Ein Stapel entfernt das zuletzt hinzugefügte Element zuerst: zuletzt hinein, zuerst heraus (LIFO). Seine Operationen definieren einen abstrakten Datentyp, unabhängig davon, ob ein Array oder verkettete Knoten die Werte enthalten. push fügt oben hinzu, pop entfernt das oberste Element und peek liest das oberste Element, ohne es zu entfernen.

Ein Array und eine Anzahl verwenden

#include <stdbool.h>
#define STACK_CAP 100
typedef struct {
    int items[STACK_CAP];
    int top;
} stack;

bool push(stack *s, int value) {
    if (s->top == STACK_CAP) return false;
    s->items[s->top++] = value;
    return true;
}
bool pop(stack *s, int *out) {
    if (s->top == 0) return false;
    *out = s->items[--s->top];
    return true;
}

Initialisiere mit stack s = {0};. Hier ist top die Anzahl der gespeicherten Elemente, sodass der oberste belegte Index top - 1 ist. Ein erfolgreiches Ablegen schreibt auf den nächsten freien Platz und erhöht die Anzahl. Ein erfolgreiches Entnehmen verringert zuerst die Anzahl und liest dann diesen Index. Der Aufrufer stellt einen gültigen out-Zeiger bereit und prüft das Ergebnis, bevor er dessen Wert verwendet.

Wenn du 4, 7 und 1 ablegst und dann zweimal entnimmst, erhältst du 1 und 7; 4 bleibt übrig. Ohne Kapazitätsprüfung schreibt das Ablegen auf einem vollen Stapel nach items[STACK_CAP] hinter das Ende. Ohne Prüfung auf einen leeren Stapel fällt das vorzeichenbehaftete top von 0 auf −1 und das Entnehmen liest items[-1]. Beide Zugriffe führen zu undefiniertem Verhalten.

Den ersten Listenknoten als oberstes Element verwenden

Ein verketteter Stapel legt ab, indem er nach geprüfter Speicherallokation am Anfang einfügt. Das Entnehmen entfernt den ersten Knoten:

bool pop_linked(node **top, int *out) {
    if (*top == NULL) return false;
    node *old = *top;
    *out = old->number;
    *top = old->next;
    free(old);
    return true;
}

node hat eine Ganzzahl number und einen next-Zeiger. Ein verketteter Stapel hat keine feste Arraykapazität, aber das Ablegen kann bei fehlgeschlagener Speicherallokation fehlschlagen. Er benötigt weiterhin Prüfungen auf einen leeren Zustand und die Freigabe der am Ende verbleibenden Knoten.

Verschachtelte Klammern zuordnen

Durchlaufe die Eingabe von links nach rechts. Lege jede öffnende runde, eckige oder geschweifte Klammer auf den Stapel. Entnimm bei jeder schließenden Klammer eine Klammer und prüfe, ob die Typen übereinstimmen. Eine schließende Klammer ohne öffnende Klammer führt sofort zum Fehlschlag. Prüfe am Ende, ob der Stapel leer ist: Übrig gebliebene öffnende Klammern bedeuten ebenfalls eine fehlende Übereinstimmung.

Der Text „( [ ] { } )“ ist ausgeglichen. Bei „( ]“ passt die schließende Klammer nicht zur entnommenen öffnenden Klammer. Bei „( ( )“ bleibt nach dem Durchlauf eine öffnende Klammer übrig. Ein einfaches Zählen öffnender und schließender Klammern würde eine falsche Verschachtelung wie „( [ ) ]“ übersehen.

Postfixausdrücke auswerten

Lege Zahlen beim Eintreffen auf den Stapel. Entnimm bei einem binären Operator zuerst den rechten, dann den linken Operanden, berechne left operator right und lege das Ergebnis ab. Bei „3 4 + 2 *“ verbindet + die 3 und 4 zu 7, dann verbindet * die 7 und 2 zu 14. Bei „9 4 -“ entnimm 4 als rechten und 9 als linken Operanden; das ergibt 5. Ihre Umkehrung ergibt −5. Weise zu wenige Operanden zurück und verlange genau ein Endergebnis; die Division benötigt außerdem einen rechten Operanden ungleich null.

Funktionsaufrufe haben stapelförmige Lebensdauern: Eine aufgerufene Funktion kehrt zurück, bevor ihr Aufrufer fortfährt. Jeder aktive Aufruf benötigt einen Stackframe, sodass sehr tiefe Rekursion den Aufrufstapel erschöpfen kann, selbst wenn Speicherallokationen auf dem Heap gelingen.

Eine Warteschlange entfernt das älteste Element zuerst: zuerst hinein, zuerst heraus (FIFO). Einreihen fügt hinten hinzu; Entnehmen entfernt vorn. Nachdem A, B und C eingereiht wurden, geben die nächsten beiden Entnahmen A und B zurück. Das eignet sich für Aufgaben, die in der Reihenfolge ihres Eintreffens bearbeitet werden müssen.

Beide Enden einer verketteten Warteschlange verwalten

Mit Knoten mit den Komponenten number und next und nach dem Einbinden von <stdbool.h> und <stdlib.h>:

typedef struct { node *head, *tail; } queue;

bool enqueue(queue *q, int value) {
    node *n = malloc(sizeof *n);
    if (n == NULL) return false;
    *n = (node){.number = value, .next = NULL};
    if (q->tail == NULL) q->head = n;
    else q->tail->next = n;
    q->tail = n;
    return true;
}
bool dequeue(queue *q, int *out) {
    if (q->head == NULL) return false;
    node *old = q->head;
    *out = old->number;
    q->head = old->next;
    if (q->head == NULL) q->tail = NULL;
    free(old);
    return true;
}

Initialisiere mit queue q = {0};. Das Einreihen setzt den Verweis des bisherigen letzten Knotens, bevor der Tail-Zeiger verschoben wird. Beim ersten Knoten setzt es auch den Kopfzeiger. Das Entnehmen verschiebt den Kopfzeiger nach vorn. Wird dabei der einzige Knoten entfernt, muss auch der Tail-Zeiger NULL werden. Andernfalls schreibt das nächste Einreihen über einen hängenden Tail-Zeiger. Keine der beiden Operationen muss die Liste durchlaufen.

Ein festes Array als Ring wiederverwenden

Eine Warteschlange in einem einfachen Array, die immer Index 0 entnimmt, muss ihre verbleibenden Werte verschieben. Ein Ringpuffer verwaltet stattdessen einen Index für das vorderste Element und eine Anzahl der Elemente:

#define CAP 4
typedef struct {
    char items[CAP];
    unsigned head, count;
} ring;

bool ring_put(ring *q, char value) {
    if (q->count == CAP) return false;
    q->items[(q->head + q->count) % CAP] = value;
    ++q->count;
    return true;
}
bool ring_get(ring *q, char *out) {
    if (q->count == 0) return false;
    *out = q->items[q->head];
    q->head = (q->head + 1) % CAP;
    --q->count;
    return true;
}

Initialisiere einen Ring mit {0}. head bezeichnet immer das vorderste Element, wenn die Warteschlange nicht leer ist. Der nächste Einfügeindex ist der vordere Index zuzüglich der Anzahl der Elemente, wobei % CAP ihn zurücksetzt. Lies das vorderste Element, bevor du head verschiebst. Die Anzahl unterscheidet leer von voll, ohne einen Platz aufzugeben.

Das Zurücksetzen nachvollziehen

Reihe A, B und C auf den Plätzen 0, 1 und 2 ein. Entnimm A: head wird 1 und count wird 2. D kommt auf Platz 3; E kommt auf Platz 0. Das physische Array enthält nun E, B, C, D, aber die logische Entnahmereihenfolge ist B, C, D, E. Der Ring ist voll, weil count 4 ist, obwohl das vorderste Element bei Index 1 liegt.

Ein anderer Entwurf verwaltet head und den nächsten freien Index tail ohne eine Anzahl. Dabei könnten gleiche Indizes leer oder voll bedeuten, sodass häufig ein Platz ungenutzt bleibt. Leer ist head == tail; voll ist (tail + 1) % CAP == head. Vermische diese Regel nicht mit den Kapazitätsregeln der Version mit Anzahl. Warteschlangen unterstützen auch den Besuch von Bäumen Ebene für Ebene, indem sie Knoten aufnehmen, die auf ihren Besuch warten.

Ein Binärbaum gibt jedem Knoten höchstens zwei Kinder, links und rechts genannt. Die Wurzel ist der oberste Knoten. Ein Blatt hat keine Kinder und ein Knoten bildet zusammen mit allen seinen Nachkommen einen Teilbaum. Ein fehlendes Kind und ein leerer Baum werden durch NULL dargestellt.

Die Verzweigungen darstellen

typedef struct tnode {
    int key;
    struct tnode *left;
    struct tnode *right;
} tnode;

Jeder Zeiger auf ein Kind führt zur Wurzel eines anderen Baums. Dieselbe Definition beschreibt daher ein Blatt, einen großen verzweigten Baum oder eine lange Kette. Die Höhe zählt die Kanten auf dem längsten Weg von der Wurzel zu einem Blatt: Eine Wurzel allein hat die Höhe 0. Verwende −1 für einen leeren Baum, sodass die beiden leeren Teilbäume eines Blattes unmittelbar zur Höhe 0 führen. Das Zählen von Ebenen ergäbe stattdessen eins mehr.

Die Regel auf ganze Teilbäume anwenden

Ein binärer Suchbaum ordnet die Schlüssel. Für jeden Knoten sind alle Schlüssel in seinem linken Teilbaum kleiner und alle Schlüssel in seinem rechten Teilbaum größer als der Schlüssel des Knotens. Speichere jeden Schlüssel einmal. Diese Bedingung schließt entfernte Nachkommen ein. Eine Wurzel 50 mit dem linken Kind 30 und einem rechten Kind 60 unter dieser 30 ist ungültig: 60 liegt weiterhin im linken Teilbaum von 50.

Füge 50, 30, 70, 20, 40, 60 und 80 in einen leeren binären Suchbaum ein. Die Wurzel ist 50; 30 und 70 sind ihre Kinder. Die Kinder von 30 sind 20 und 40, die von 70 sind 60 und 80. Jede Wahl einer Verzweigung erhält die von den Vorfahren übernommenen Schranken.

In jedem Schritt eine Verzweigung wählen

#include <stddef.h>
tnode *search(tnode *t, int key) {
    while (t != NULL) {
        if (key == t->key) return t;
        if (key < t->key) t = t->left;
        else t = t->right;
    }
    return NULL;
}

Die Suche nach 60 besucht im Beispiel 50, geht nach rechts zu 70 und dann nach links zu 60: drei Knoten. Die Suche nach 65 nimmt denselben Weg und versucht dann das rechte Kind von 60. Dieses Kind ist NULL, sodass 65 fehlt. Du musst den linken Teilbaum von 50 nicht untersuchen, weil dort jeder Schlüssel kleiner als 50 ist.

Die rekursive Form behandelt zuerst t == NULL und einen passenden Schlüssel und durchsucht dann das ausgewählte Kind. Die Prüfung auf einen leeren Teilbaum ist der Basisfall. Ohne sie dereferenziert eine erfolglose Suche irgendwann einen Nullzeiger. Die Schleifenversion hält an derselben Stelle an, ohne rekursive Aufrufe hinzuzufügen.

Den Aufwand durch die Form erklären

Ein perfekt balancierter Baum mit 20 Ebenen enthält 1.048.575 Schlüssel und eine Suche besucht höchstens 20 Knoten. Wenn du stattdessen bereits sortierte Schlüssel 10, 20, 30, 40, 50 einfügst, entsteht eine Kette nach rechts. Ihre Höhe ist 4 und die Suche nach 50 besucht alle fünf Knoten. Die Ordnungsregel eines binären Suchbaums allein hält den Baum nicht niedrig. Selbstbalancierende Bäume wie AVL-Bäume ordnen Verzweigungen um, um die Höhe zu begrenzen.

Um ein Minimum zu finden, folge linken Kindern, bis der nächste linke Verweis NULL ist. Für ein Maximum folge rechten Kindern. Im Beispiel mit sieben Knoten sind diese Schlüssel 20 und 80. Dieselbe Richtungswahl funktioniert bei jeder Teilbaumwurzel, weil die Ordnungsregel auch dort gilt.

Baumfunktionen arbeiten auf einem Teilbaum und verbinden ihr Ergebnis mit dessen Elternknoten. Behandle den Fall des leeren Teilbaums ausdrücklich und unterscheide Operationen, die Verweise ändern, von solchen, die Knoten nur besuchen.

Über den Teilbaumverweis einfügen

Für tnode mit key, left und right binde <stdbool.h> und <stdlib.h> ein:

bool insert(tnode **link, int key) {
    if (*link == NULL) {
        tnode *n = malloc(sizeof *n);
        if (n == NULL) return false;
        *n = (tnode){.key = key, .left = NULL, .right = NULL};
        *link = n;
        return true;
    }
    if (key < (*link)->key) return insert(&(*link)->left, key);
    if (key > (*link)->key) return insert(&(*link)->right, key);
    return true;
}

Rufe die Funktion mit insert(&root, key) auf und prüfe ihr Ergebnis. Ein vorhandener Schlüssel lässt den Baum unverändert und gilt als Erfolg. Die Adresse des Verweises ermöglicht es dem Einfügen, entweder die Wurzel des Aufrufers oder einen Zeiger auf ein Kind zu aktualisieren. Bei einer Schnittstelle, die die Wurzel zurückgibt, speichere jedes Ergebnis: t->left = insert(t->left, key) und root = insert(root, key). Wird ein zurückgegebener allokierter Knoten ignoriert, wenn der ursprüngliche Teilbaum leer war, bleibt dieser Knoten unverknüpft und es entsteht ein Speicherleck.

Wählen, wann die Wurzel besucht wird

Beim Einfügen von 50, 30, 70, 20, 40, 60, 80 lautet die Inorder-Ausgabe „20 30 40 50 60 70 80“. Preorder ergibt „50 30 20 40 70 60 80“; Postorder ergibt „20 40 30 60 80 70 50“.

void free_tree(tnode *t) {
    if (t == NULL) return;
    free_tree(t->left);
    free_tree(t->right);
    free(t);
}

Setze nach free_tree(root) beim Besitzer root = NULL. Die Funktion gibt zuerst die Kinder frei, damit sie deren Adressen aus dem noch existierenden Elternknoten lesen kann. Die Größe ist bei einem leeren Teilbaum null, sonst eins plus die Größen beider Kinder. Die Höhe ist bei einem leeren Teilbaum −1, sonst eins plus die größere der beiden Kinderhöhen. Das Beispiel hat die Größe 7 und die Höhe 2.

Löschen, ohne die Ordnung zu verletzen

Ein Blatt wird zu NULL. Ein Knoten mit einem Kind wird durch dieses Kind ersetzt. Kopiere bei zwei Kindern den kleinsten Schlüssel aus dem rechten Teilbaum in den Knoten und lösche dann diesen Nachfolger von seiner ursprünglichen Position:

tnode *erase(tnode *t, int key) {
    if (t == NULL) return NULL;
    if (key < t->key) t->left = erase(t->left, key);
    else if (key > t->key) t->right = erase(t->right, key);
    else {
        if (t->left == NULL || t->right == NULL) {
            tnode *child = t->left != NULL ? t->left : t->right;
            free(t);
            return child;
        }
        tnode *s = t->right;
        while (s->left != NULL) s = s->left;
        t->key = s->key;
        t->right = erase(t->right, s->key);
    }
    return t;
}

Rufe die Funktion als root = erase(root, key) auf. Das Löschen von 50 aus dem Beispiel setzt 60 in die Wurzel und entfernt den alten Knoten mit 60. Die Inorder-Ausgabe wird zu „20 30 40 60 70 80“; Preorder wird zu „60 30 20 40 70 80“. Ein Nachfolger kann ein rechtes Kind haben, daher muss seine Entfernung dieses Kind wieder verknüpfen.

Verwende für Wortschlüssel das Vorzeichen von strcmp, nicht Zeigergleichheit, und gib jedem Wort im Besitz einen eigenen Speicherblock. Gib das Wort vor seinem Knoten frei. Das Löschen von Datensätzen mit zwei Kindern benötigt auch einen Plan für den Besitz des verschobenen Wortes und eines zugehörigen Werts; würde ein besitzender Zeiger kopiert und dann das Wort seines ursprünglichen Knotens freigegeben, bliebe ein hängender Schlüssel zurück.

Eine Hashtabelle wählt anhand eines Schlüssels eine Ausgangsposition. Eine Hashfunktion erzeugt eine Zahl; ihr Rest modulo einer positiven Bucket-Anzahl ergibt einen Index. Separate Verkettung hält an jedem Bucket eine verkettete Liste, sodass die Suche die ausgewählte Kette durchsucht.

Hashberechnung und Gleichheit unterscheiden

Eine brauchbare Hashfunktion ist deterministisch, schnell zu berechnen und verteilt die erwarteten Schlüssel über die Buckets. Gleiche Schlüssel müssen gleiche Hashwerte ergeben. Verschiedene Schlüssel können dennoch denselben Index haben: Das ist eine Kollision, und jede Tabelle muss sie behandeln. Gibt es mehr mögliche Schlüssel als Buckets, sind einige Kollisionen unvermeidbar.

Für mit Buchstaben beginnende Wörter auf einem ASCII-kompatiblen System weist toupper((unsigned char)word[0]) - 'A' 26 Buchstaben-Buckets zu; „Luigi“ beginnt in Bucket 11. Viele englische Wörter beginnen mit „s“ und wenige mit „x“, sodass diese Regel sehr ungleichmäßige Ketten hinterlassen kann. Die explizite Typumwandlung ist nötig, weil Funktionen aus <ctype.h> einen Wert eines vorzeichenlosen Zeichentyps oder EOF benötigen. Prüfe den Anfangsbuchstaben und die Annahme über den Zeichensatz, bevor du diese Indexregel verwendest.

Auch eine Hashfunktion mit Zeichensummen hat Schwächen. Mit ASCII-Codes und zehn Buckets ergibt „cat“ die Summe 99 + 97 + 116 = 312 und erreicht Bucket 2; „dog“ ergibt die Summe 314 und erreicht Bucket 4. „act“ ergibt ebenfalls die Summe 312. Die Addition verliert die Buchstabenreihenfolge, sodass jede Umstellung kollidiert.

Die Zeichenreihenfolge in den Hashwert einbeziehen

unsigned long hash_word(const char *word) {
    unsigned long h = 5381;
    const unsigned char *p = (const unsigned char *)word;
    while (*p != '\0') {
        h = h * 33 + *p;
        ++p;
    }
    return h;
}

Dieses djb2-Muster verwendet vorzeichenlose Arithmetik, deren Überlauf auf definierte Weise zu einem Wraparound führt. Ein Überlauf bei vorzeichenbehafteten Ganzzahlen wäre undefiniertes Verhalten. Für die ASCII-Zeichenketten „cat“ und „act“ sind die Werte 193.488.125 und 193.486.013. Reduziere mit hash_word(word) % N, wobei N die positive Bucket-Anzahl ist. Die Buchstabenreihenfolge verändert diese Hashwerte, obwohl ihre Reduktion weiterhin eine Kollision ergeben kann.

Wenn eine Tabelle „Cat“ und „cat“ als gleich behandelt, müssen sowohl die Hashberechnung als auch der Vergleich dieselbe Regel für Groß- und Kleinschreibung verwenden. Wird die Groß- und Kleinschreibung nur beim Vergleich ignoriert, können gleiche Schlüssel in verschiedene Buckets gelangen, wo die Suche sie nicht miteinander vergleicht. Ein negativer Divisionsrest eines vorzeichenbehafteten Hashwerts eignet sich ebenfalls nicht als Arrayindex.

Eine Kollisionsstrategie wählen

Separate Verkettung speichert jede Kollision in der verketteten Liste eines Buckets. Die Suche vergleicht Schlüssel, bis sie eine Übereinstimmung findet oder das Ende erreicht. Offene Adressierung speichert Einträge im Array selbst. Beim linearen Sondieren wird bei einer Kollision der nächste Platz versucht und am Ende wieder von vorn begonnen. Die Suche folgt derselben Sondierungsfolge und kann daher mehrere Arrayplätze untersuchen.

Indizes beim Vergrößern der Tabelle neu berechnen

Der Belegungsfaktor ist die Anzahl der gespeicherten Schlüssel geteilt durch die Bucket-Anzahl. Zwölf Schlüssel in acht Buckets ergeben durchschnittlich 1,5 Einträge pro Bucket. Sechzehn Buckets verringern diesen Durchschnitt auf 0,75. Dieser Durchschnitt garantiert nicht, dass jede Kette kurz ist; eine schlechte Hashfunktion kann alle Schlüssel zusammen ablegen.

Ein Bucket-Index hängt von der Bucket-Anzahl ab. Berechne nach dem Reservieren und Initialisieren eines größeren Bucket-Arrays den Index jedes gespeicherten Schlüssels für die neue Anzahl neu und verknüpfe ihn dort. Würdest du die alten Kopfzeiger in die gleich nummerierten neuen Buckets kopieren, blieben Schlüssel an Stellen, an denen die neue Suche nicht nachschlägt. Eine Tabelle mit separater Verkettung kann mehr Einträge als Buckets enthalten; offene Adressierung benötigt ungenutzte Plätze für neue Einträge und zuverlässiges Sondieren.

Eine Tabelle mit separater Verkettung verbindet ein Array, Listenverweise, Zeichenkettenvergleich und Besitz. Jeder Eintrag besitzt seinen kopierten Schlüssel. Das Bucket-Array besitzt die Ketten und jede Kette endet bei NULL.

Buckets initialisieren und Text nachschlagen

#include <stdbool.h>
#include <limits.h>
#include <stdlib.h>
#include <string.h>
#define N 26
typedef struct entry {
    char *key;
    int count;
    struct entry *next;
} entry;
static entry *table[N];

Bei statischer Speicherdauer enthält anfangs jeder Bucket einen Nullzeiger. Ein lokales Array benötigt dagegen einen Initialisierer wie entry *table[N] = {NULL};. Verwende die vorzeichenlose Funktion hash_word, die bei 5381 beginnt und jedes Byte mit dem Multiplikator 33 einbezieht.

entry *find_word(const char *key) {
    size_t i = hash_word(key) % N;
    for (entry *e = table[i]; e != NULL; e = e->next)
        if (strcmp(e->key, key) == 0) return e;
    return NULL;
}

strcmp prüft Text. e->key == key würde prüfen, ob die Zeiger dieselbe Stelle bezeichnen. Zwei getrennte Puffer können gleiche Wörter enthalten, daher ist Zeigergleichheit keine Wortsuche.

Einen vorhandenen Schlüssel zählen oder einen neuen einsetzen

bool add_word(const char *key) {
    entry *e = find_word(key);
    if (e != NULL) {
        if (e->count == INT_MAX) return false;
        ++e->count;
        return true;
    }
    e = malloc(sizeof *e);
    if (e == NULL) return false;
    e->key = malloc(strlen(key) + 1);
    if (e->key == NULL) {
        free(e);
        return false;
    }
    strcpy(e->key, key);
    e->count = 1;
    size_t i = hash_word(key) % N;
    e->next = table[i];
    table[i] = e;
    return true;
}

Der Aufrufer stellt eine nullterminierte Zeichenkette bereit. Die Prüfung auf INT_MAX meldet einen Fehlschlag, bevor die Anzahl ihren int-Speicherbereich überlaufen würde. Das zusätzliche Byte im Speicherblock der Zeichenkette enthält '\0'. Wenn die zweite Speicherallokation fehlschlägt, gib den noch nicht verknüpften Eintrag frei. Der Kopfzeiger des Buckets ändert sich erst, nachdem beide Speicherallokationen und die Initialisierung gelungen sind.

Würde stattdessen e->key = key gespeichert, bliebe der Speicher des Aufrufers eingebunden. Wenn die Eingabe einen Puffer wiederholt verwendet, könnte jeder gespeicherte Zeiger das neueste Wort anzeigen. Das Kopieren des Textes gibt jedem Eintrag eine von diesem Puffer unabhängige Lebensdauer. strdup stellt diese Operation in POSIX und C23 bereit; ausdrückliche Speicherallokation und strcpy funktionieren in C17.

In einem Beispiel mit zehn Buckets und Zeichensummen ergibt das Einfügen von „cat“, „dog“, „act“ die Kette „act“ → „cat“ in Bucket 2 und „dog“ in Bucket 4. Die Suche nach „tac“ durchsucht Bucket 2, vergleicht beide Wörter und erreicht NULL. Ein passender Bucket ist nur eine mögliche Fundstelle, kein Beleg für einen gleichen Schlüssel.

Nutzdaten, Knoten und Bucket-Kopfzeiger freigeben

void clear_table(void) {
    for (size_t i = 0; i < N; ++i) {
        entry *e = table[i];
        while (e != NULL) {
            entry *next = e->next;
            free(e->key);
            free(e);
            e = next;
        }
        table[i] = NULL;
    }
}

Das Sichern von next und die Freigabe des Schlüssels erfolgen, während der Eintrag noch existiert. Das Zurücksetzen jedes Buckets ermöglicht die Wiederverwendung. Speicherprüfprogramme helfen, durchlaufene Pfade zu prüfen; auch bei fehlgeschlagener Speicherallokation muss aufgeräumt werden. Die Hashreihenfolge ist keine sortierte Reihenfolge. Für eine alphabetische Ausgabe sammle Schlüssel zum Sortieren oder speichere sie in einem binären Suchbaum.

Bei offener Adressierung benötigt das Löschen eine Löschmarkierung, damit die Suche über einen entfernten Platz hinweg zu späteren kollidierenden Schlüsseln fortgesetzt wird. Ein tatsächlich ungenutzter Platz kann eine erfolglose Suche beenden. Sondierungsfolgen müssen begrenzt sein und die Tabelle muss vergrößert werden, bevor jeder Platz belegt ist.