0Pricing
C Academy · Lekcja

Wstawianie, wyszukiwanie i usuwanie

Podstawowe operacje

Wstawianie, wyszukiwanie i usuwanie to bezpłatna lekcja C Academy na CoddyKit. To lekcja 3 z 4. Możesz przeczytać całą lekcję poniżej za darmo — a potem ćwiczyć ją interaktywnie w przeglądarce z wbudowanym edytorem kodu i tutorem AI dostępnym 24/7. To część ścieżki edukacyjnej C Academy, a Twój postęp synchronizuje się między webem a aplikacją CoddyKit. Kurs C Academy zawiera 4 lekcji w sumie.

Trzy podstawowe operacje

Każda tablica haszująca obsługuje trzy operacje: wstawianie, wyszukiwanie i usuwanie. Przy dobrej funkcji skrótu i rozsądnym współczynniku zapełnienia wszystkie trzy operacje mają średnią złożoność O(1).

Krok po kroku zbudujemy tablicę opartą na łańcuchowaniu.

Typy tablicy i węzła

Definiujemy węzeł przechowujący skopiowany klucz tekstowy i wartość całkowitą, a także strukturę tablicy przechowującą tablicę kubełków i jej pojemność.

#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;
}

Tworzenie tablicy

Alokujemy tablicę oraz wyzerowaną tablicę kubełków za pomocą calloc, dzięki czemu każdy kubełek ma początkowo wartość NULL.

#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;
}

Pomocnicza funkcja haszująca

Ponownie używamy DJB2 i redukujemy jej wynik do indeksu kubełka. Ta funkcja pomocnicza jest używana przez wszystkie trzy operacje.

#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;
}

Wstawianie: aktualizacja lub dodanie na początku

Podczas wstawiania najpierw przeszukujemy kubełek. Jeśli klucz już istnieje, aktualizujemy jego wartość. W przeciwnym razie alokujemy nowy węzeł (ze skopiowanym kluczem uzyskanym za pomocą strdup) i dodajemy go na początku listy.

#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;
}

Wyszukiwanie

Wyszukiwanie oblicza skrót klucza, a następnie przechodzi przez listę kubełka, porównując klucze za pomocą strcmp. Zwraca wskaźnik na wartość (lub NULL, jeśli klucz nie występuje).

#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;
}

Usuwanie: ponowne łączenie listy

Usuwanie przechodzi przez kubełek, zachowując wskaźnik na poprzedni węzeł, a następnie omija docelowy węzeł przez ponowne połączenie listy i zwalnia jego pamięć (zarówno skopiowany klucz, jak i węzeł).

#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;
}

Połączenie wszystkiego

Kompletna tablica realizuje te operacje, obliczając kubełek, a następnie delegując pracę do funkcji pomocniczych listy. Oto kompletna, niewielka tablica w działaniu.

#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;
}

Dlaczego kopiować klucz

Przechowujemy klucze za pomocą strdup, aby tablica posiadała własną kopię. Gdybyśmy przechowywali wskaźnik należący do wywołującego, klucz mógłby zostać zmieniony lub zwolniony niezależnie od tablicy, co prowadziłoby do błędów wyszukiwania.

Oznacza to również, że podczas usuwania należy wywołać free dla skopiowanego klucza.

Złożoność czasowa

Przy równomiernej funkcji skrótu i współczynniku zapełnienia utrzymywanym w pobliżu 0.75:

  • Wstawianie: średnio O(1)
  • Wyszukiwanie: średnio O(1)
  • Usuwanie: średnio O(1)

W najgorszym przypadku jest to O(n), gdy wszystkie klucze kolidują w jednym kubełku.

Zwalnianie całej tablicy

Aby uniknąć wycieków pamięci, zwolnij każdy węzeł w każdym kubełku, następnie tablicę kubełków, a na końcu strukturę tablicy.

#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;
}

Szybkie sprawdzenie

Sprawdź swoje rozumienie podstawowych operacji.

Podsumowanie

Zaimplementowałeś(-aś) trzy podstawowe operacje tablicy haszującej z łańcuchowaniem.

  • Wstawianie aktualizuje wartość lub dodaje węzeł na początku
  • Wyszukiwanie przechodzi przez listę kubełka za pomocą strcmp
  • Usuwanie ponownie łączy listę i zwalnia zarówno klucz, jak i węzeł
  • Zarządzaj własnością kluczy za pomocą strdup i zwalniaj wszystkie zasoby podczas niszczenia tablicy

Często zadawane pytania

Czy lekcja „Wstawianie, wyszukiwanie i usuwanie” jest bezpłatna?

Tak — pełny tekst „Wstawianie, wyszukiwanie i usuwanie” jest dostępny za darmo tutaj w sieci. Aby ćwiczyć ją interaktywnie (wbudowany edytor kodu i tutor AI dostępny 24/7) i odblokować resztę kursu C Academy, przejdź na CoddyKit PRO. Kurs C Academy zawiera 4 lekcji w sumie.

Co nauczysz się w „Wstawianie, wyszukiwanie i usuwanie”?

Podstawowe operacje Ćwiczysz C Academy z praktycznym kodem, który uruchamiasz bezpośrednio w przeglądarce, a tutor AI dostępny 24/7 odpowiada na Twoje pytania podczas pracy nad lekcją.

Czy potrzebuję doświadczenia, aby zacząć C Academy?

Nie wymagamy żadnego doświadczenia. C Academy w CoddyKit jest strukturyzowany dla początkujących i zaawansowanych użytkowników, więc możesz zacząć tutaj lub od początku i uczyć się w swoim tempie. To lekcja 3 z 4.

Ile czasu zajmuje lekcja „Wstawianie, wyszukiwanie i usuwanie”?

Większość lekcji CoddyKit trwa około 5–10 minut. Każda lekcja to mały, interaktywny krok, dzięki czemu robisz systematyczne postępy i zawsze wracasz dokładnie do tego samego miejsca — na webie i w aplikacji.

Czy mogę pisać i uruchamiać kod w tej lekcji C Academy?

Tak. Każda lekcja C Academy zawiera wbudowany edytor kodu, więc piszesz i uruchamiasz prawdziwy kod bezpośrednio w przeglądarce i od razu otrzymujesz sprzężenie zwrotne od AI — bez konfiguracji na komputerze.

Wszystkie lekcje w tym kursie

  1. Funkcje haszujące
  2. Obsługa kolizji
  3. Wstawianie, wyszukiwanie i usuwanie
  4. Zmiana rozmiaru i współczynnik zapełnienia
← Powrót do C Academy