0Pricing
C Academy · Lektion

Einfügen, Suchen, Löschen

Grundlegende Operationen

Einfügen, Suchen, Löschen ist eine kostenlose C Academy-Lektion auf CoddyKit. Dies ist Lektion 3 von 4. Du kannst die komplette Lektion unten kostenlos lesen – dann übst du sie direkt im Browser mit einem integrierten Code-Editor und einem KI-Tutor rund um die Uhr. Sie ist Teil des C Academy-Lernpfads, und dein Fortschritt wird über Web und CoddyKit-App synchronisiert. Der C Academy-Kurs umfasst insgesamt 4 Lektionen.

Die drei grundlegenden Operationen

Jede Hashtabelle unterstützt drei Operationen: Einfügen, Suchen und Löschen. Bei einer guten Hashfunktion und einem angemessenen Auslastungsfaktor haben alle drei durchschnittlich die Laufzeit O(1).

Wir erstellen Schritt für Schritt eine Tabelle mit Verkettung.

Die Tabellen- und Knotentypen

Wir definieren einen Knoten, der eine kopierte Schlüsselzeichenkette und einen ganzzahligen Wert enthält, sowie eine Tabellenstruktur mit dem Bucket-Array und seiner Kapazität.

#include <stdio.h>

typedef struct Node {
    char *key;
    int value;
    struct Node *next;
} Node;

typedef struct {
    Node **buckets;
    unsigned capacity;
    unsigned size;
} HashTable;

int main(void) {
    printf("types defined\n");
    return 0;
}

Die Tabelle erstellen

Reservieren Sie Speicher für die Tabelle und mit calloc für ein auf null gesetztes Bucket-Array, sodass jeder Bucket zunächst NULL enthält.

#include <stdio.h>
#include <stdlib.h>

typedef struct Node { char *key; int value; struct Node *next; } Node;
typedef struct { Node **buckets; unsigned capacity, size; } HashTable;

HashTable *ht_create(unsigned cap) {
    HashTable *t = malloc(sizeof *t);
    t->buckets = calloc(cap, sizeof(Node *));
    t->capacity = cap; t->size = 0;
    return t;
}

int main(void) {
    HashTable *t = ht_create(16);
    printf("capacity=%u size=%u\n", t->capacity, t->size);
    return 0;
}

Die Hash-Hilfsfunktion

Wir verwenden DJB2 erneut und reduzieren den Hashwert auf einen Bucket-Index. Diese Hilfsfunktion wird von allen drei Operationen verwendet.

#include <stdio.h>

unsigned long djb2(const char *s) {
    unsigned long h = 5381; int c;
    while ((c = (unsigned char)*s++)) h = ((h << 5) + h) + c;
    return h;
}

unsigned bucket_of(const char *key, unsigned cap) {
    return (unsigned)(djb2(key) % cap);
}

int main(void) {
    printf("%u\n", bucket_of("name", 16));
    return 0;
}

Einfügen: Aktualisieren oder Voranstellen

Beim Einfügen durchsuchen Sie zuerst den Bucket. Existiert der Schlüssel bereits, aktualisieren Sie seinen Wert. Andernfalls reservieren Sie Speicher für einen neuen Knoten, kopieren den Schlüssel mit strdup und fügen den Knoten am Anfang ein.

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

typedef struct Node { char *key; int value; struct Node *next; } Node;

Node *insert(Node *head, const char *key, int val) {
    for (Node *p = head; p; p = p->next)
        if (strcmp(p->key, key) == 0) { p->value = val; return head; }
    Node *n = malloc(sizeof *n);
    n->key = strdup(key); n->value = val; n->next = head;
    return n;
}

int main(void) {
    Node *b = NULL;
    b = insert(b, "a", 1);
    b = insert(b, "a", 99); /* update */
    printf("%s=%d\n", b->key, b->value);
    return 0;
}

Suchen

Beim Suchen wird der Schlüssel gehasht. Anschließend wird die Bucket-Liste durchlaufen und die Schlüssel mit strcmp verglichen. Zurückgegeben wird ein Zeiger auf den Wert (oder NULL, falls er nicht vorhanden ist).

#include <stdio.h>
#include <string.h>

typedef struct Node { char *key; int value; struct Node *next; } Node;

int *lookup(Node *head, const char *key) {
    for (Node *p = head; p; p = p->next)
        if (strcmp(p->key, key) == 0) return &p->value;
    return NULL;
}

int main(void) {
    Node n2 = {"y", 20, NULL};
    Node n1 = {"x", 10, &n2};
    int *v = lookup(&n1, "y");
    printf("%d\n", v ? *v : -1);
    return 0;
}

Löschen: Die Liste neu verknüpfen

Beim Löschen wird der Bucket durchlaufen, wobei ein Zeiger auf den vorherigen Knoten gespeichert wird. Anschließend wird die Liste um das Zielelement herum neu verknüpft und dieses freigegeben (sowohl der kopierte Schlüssel als auch der Knoten).

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

typedef struct Node { char *key; int value; struct Node *next; } Node;

Node *delete_key(Node *head, const char *key) {
    Node *prev = NULL, *cur = head;
    while (cur) {
        if (strcmp(cur->key, key) == 0) {
            if (prev) prev->next = cur->next; else head = cur->next;
            free(cur->key); free(cur);
            return head;
        }
        prev = cur; cur = cur->next;
    }
    return head;
}

int main(void) {
    Node *b = malloc(sizeof *b);
    b->key = strdup("a"); b->value = 1; b->next = NULL;
    b = delete_key(b, "a");
    printf("%s\n", b ? "left" : "empty");
    return 0;
}

Alles zusammenführen

Eine vollständige Tabelle kapselt diese Schritte, indem sie den Bucket berechnet und anschließend die Listen-Hilfsfunktionen aufruft. Hier sehen Sie eine vollständige kleine Tabelle in Aktion.

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

typedef struct Node { char *key; int value; struct Node *next; } Node;

unsigned long djb2(const char *s){unsigned long h=5381;int c;while((c=(unsigned char)*s++))h=((h<<5)+h)+c;return h;}

#define CAP 16
Node *table[CAP];

void put(const char *k, int v) {
    unsigned i = djb2(k) % CAP;
    Node *n = malloc(sizeof *n);
    n->key = strdup(k); n->value = v; n->next = table[i];
    table[i] = n;
}
int get(const char *k) {
    for (Node *p = table[djb2(k) % CAP]; p; p = p->next)
        if (!strcmp(p->key, k)) return p->value;
    return -1;
}

int main(void) {
    put("age", 30); put("score", 95);
    printf("age=%d score=%d\n", get("age"), get("score"));
    return 0;
}

Warum der Schlüssel kopiert wird

Wir speichern Schlüssel mit strdup, damit die Tabelle eine eigene Kopie besitzt. Würden wir den Zeiger des Aufrufers speichern, könnte der Schlüssel geändert oder unter unserem Zugriff freigegeben werden, wodurch Suchvorgänge beschädigt würden.

Das bedeutet außerdem, dass beim Löschen der kopierte Schlüssel mit free freigegeben werden muss.

Zeitkomplexität

Bei einer gleichmäßigen Hashverteilung und einem Auslastungsfaktor nahe 0.75 gilt:

  • Einfügen: durchschnittlich O(1)
  • Suchen: durchschnittlich O(1)
  • Löschen: durchschnittlich O(1)

Im schlechtesten Fall beträgt die Laufzeit O(n), wenn alle Schlüssel in einem Bucket kollidieren.

Die gesamte Tabelle freigeben

Um Speicherlecks zu vermeiden, geben Sie zuerst jeden Knoten in jedem Bucket frei, danach das Bucket-Array und schließlich die Tabellenstruktur.

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

typedef struct Node { char *key; int value; struct Node *next; } Node;

void free_bucket(Node *head) {
    while (head) { Node *nx = head->next; free(head->key); free(head); head = nx; }
}

int main(void) {
    Node *b = malloc(sizeof *b);
    b->key = strdup("k"); b->value = 1; b->next = NULL;
    free_bucket(b);
    printf("freed\n");
    return 0;
}

Kurzer Test

Testen Sie Ihr Verständnis der grundlegenden Operationen.

Zusammenfassung

Sie haben die drei grundlegenden Hashtabellen-Operationen mit Verkettung implementiert.

  • Beim Einfügen wird ein Knoten aktualisiert oder am Anfang eingefügt
  • Beim Suchen wird die Bucket-Liste mit strcmp durchlaufen
  • Beim Löschen wird die Liste neu verknüpft und sowohl Schlüssel als auch Knoten werden freigegeben
  • Verwalten Sie Ihre Schlüssel mit strdup selbst und geben Sie beim Aufräumen alles frei

Häufig gestellte Fragen

Ist die Lektion „Einfügen, Suchen, Löschen“ kostenlos?

Ja — der vollständige Text von „Einfügen, Suchen, Löschen“ ist hier im Web kostenlos zu lesen. Um sie interaktiv zu üben (integrierter Code-Editor und 24/7 KI-Tutor) und den Rest des C Academy-Kurses freizuschalten, upgrade auf CoddyKit PRO. Der C Academy-Kurs umfasst insgesamt 4 Lektionen.

Was lerne ich in „Einfügen, Suchen, Löschen“?

Grundlegende Operationen Du übst C Academy mit praktischem Code, den du direkt im Browser ausführst, und ein 24/7 KI-Tutor beantwortet deine Fragen während du die Lektion bearbeitest.

Brauche ich Erfahrung, um C Academy zu starten?

Keine Vorkenntnisse erforderlich. C Academy auf CoddyKit ist für Anfänger bis fortgeschrittene Lernende strukturiert, sodass du hier starten oder von Anfang an beginnen und in deinem eigenen Tempo voranschreiten kannst. Dies ist Lektion 3 von 4.

Wie lange dauert die Lektion „Einfügen, Suchen, Löschen“?

Die meisten CoddyKit-Lektionen dauern etwa 5–10 Minuten. Jede ist kompakt und interaktiv, sodass du stetig Fortschritte machst und genau dort weitermachst, wo du aufgehört hast – im Web und in der App.

Kann ich in dieser C Academy-Lektion Code schreiben und ausführen?

Ja. Jede C Academy-Lektion enthält einen integrierten Code-Editor, sodass du echten Code direkt in deinem Browser schreibst und ausführst und sofort KI-Feedback erhältst — ohne lokale Einrichtung erforderlich.

Alle Lektionen in diesem Kurs

  1. Hash-Funktionen
  2. Kollisionsbehandlung
  3. Einfügen, Suchen, Löschen
  4. Größenanpassung und Load Factor
← Zurück zu C Academy