0Pricing
C Academy · Pelajaran

Sisipkan, Cari, Hapus

Operasi inti.

Sisipkan, Cari, Hapus adalah pelajaran C Academy gratis di CoddyKit. Ini adalah pelajaran 3 dari 4. Kamu bisa membaca pelajaran lengkapnya di bawah secara gratis — lalu praktikkan langsung di browser dengan editor kode bawaan dan tutor AI 24/7. Ini adalah bagian dari jalur belajar C Academy, dan progresmu tersinkronisasi di web dan aplikasi CoddyKit. Kursus C Academy mencakup 4 pelajaran total.

Tiga Operasi Inti

Setiap tabel hash mendukung tiga operasi: penyisipan, pencarian, dan penghapusan. Dengan hash yang baik dan faktor muatan yang wajar, ketiganya berjalan dalam waktu rata-rata O(1).

Kita akan membuat tabel berbasis pengaitan langkah demi langkah.

Jenis Tabel dan Simpul

Kita mendefinisikan simpul yang menyimpan string kunci hasil salinan dan nilai bilangan bulat, serta struktur tabel yang menyimpan larik ember dan kapasitasnya.

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

Membuat Tabel

Alokasikan tabel dan larik ember yang diinisialisasi nol dengan calloc, sehingga setiap ember dimulai sebagai 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;
}

Pembantu Hash

Kita menggunakan kembali DJB2 dan menguranginya menjadi indeks ember. Fungsi pembantu ini digunakan oleh ketiga operasi.

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

Sisipkan: Perbarui atau Tambahkan di Awal

Saat menyisipkan, cari ember terlebih dahulu. Jika kunci sudah ada, perbarui nilainya. Jika tidak, alokasikan simpul baru (dengan kunci hasil salinan melalui strdup) dan tambahkan di awal.

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

Pencarian

Pencarian melakukan hash pada kunci, lalu menelusuri daftar ember sambil membandingkan kunci dengan strcmp. Operasi ini mengembalikan penunjuk ke nilai (atau NULL jika tidak ditemukan).

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

Hapus: Sambungkan Ulang Daftar

Penghapusan menelusuri ember sambil menyimpan penunjuk ke simpul sebelumnya, lalu menyambungkan ulang daftar melewati target dan membebaskannya (baik kunci hasil salinan maupun simpulnya).

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

Menyatukan Semuanya

Tabel lengkap membungkus operasi-operasi ini dengan menghitung ember, lalu menyerahkan tugas kepada fungsi pembantu daftar. Berikut contoh tabel mini lengkap yang sedang dijalankan.

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

Mengapa Kunci Perlu Disalin

Kita menyimpan kunci dengan strdup agar tabel memiliki salinannya sendiri. Jika kita menyimpan penunjuk milik pemanggil, kunci tersebut dapat berubah atau dibebaskan tanpa sepengetahuan kita sehingga merusak pencarian.

Ini juga berarti penghapusan harus melakukan free pada kunci hasil salinan.

Kompleksitas Waktu

Dengan hash seragam dan faktor muatan yang dipertahankan di sekitar 0.75:

  • Sisipkan: rata-rata O(1)
  • Pencarian: rata-rata O(1)
  • Hapus: rata-rata O(1)

Kasus terburuknya adalah O(n) ketika semua kunci bertabrakan di satu ember.

Membebaskan Seluruh Tabel

Untuk mencegah kebocoran, bebaskan setiap simpul di setiap ember, kemudian larik ember, lalu struktur tabelnya.

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

Pemeriksaan Singkat

Uji pemahaman Anda tentang operasi inti.

Ringkasan

Anda telah mengimplementasikan tiga operasi inti tabel hash dengan pengaitan.

  • Sisipkan memperbarui atau menambahkan simpul di awal
  • Pencarian menelusuri daftar ember dengan strcmp
  • Hapus menyambungkan ulang dan membebaskan kunci serta simpul
  • Miliki kunci Anda sendiri dengan strdup dan bebaskan semuanya saat pembongkaran

Pertanyaan yang Sering Diajukan

Apakah pelajaran “Sisipkan, Cari, Hapus” gratis?

Ya — teks lengkap “Sisipkan, Cari, Hapus” gratis dibaca di sini di web. Untuk praktiknya secara interaktif (editor kode bawaan dan tutor AI 24/7) dan buka sisa kursus C Academy, upgrade ke CoddyKit PRO. Kursus C Academy mencakup 4 pelajaran total.

Apa yang akan aku pelajari di “Sisipkan, Cari, Hapus”?

Operasi inti. Kamu berlatih C Academy dengan kode praktik yang langsung kamu jalankan di browser, dan tutor AI 24/7 menjawab pertanyaanmu saat kamu mengerjakan pelajaran ini.

Apakah aku perlu pengalaman untuk memulai C Academy?

Tidak diperlukan pengalaman sebelumnya. C Academy di CoddyKit dirancang untuk pemula hingga pelajar tingkat lanjut, jadi kamu bisa memulai di sini atau dari awal dan belajar sesuai kecepatan kamu sendiri. Ini adalah pelajaran 3 dari 4.

Berapa lama pelajaran “Sisipkan, Cari, Hapus” memakan waktu?

Sebagian besar pelajaran CoddyKit memakan waktu sekitar 5–10 menit. Setiap pelajaran ringkas dan interaktif, jadi kamu membuat kemajuan stabil dan melanjutkan dari tempat kamu tinggalkan di web dan aplikasi.

Bisakah aku menulis dan menjalankan kode dalam pelajaran C Academy ini?

Ya. Setiap pelajaran C Academy menyertakan editor kode bawaan, jadi kamu menulis dan menjalankan kode nyata langsung di browser dan mendapatkan umpan balik AI instan — tidak diperlukan penyiapan lokal.

Semua pelajaran dalam kursus ini

  1. Fungsi Hash
  2. Penanganan Collision
  3. Sisipkan, Cari, Hapus
  4. Pengubahan Ukuran dan Faktor Muatan
← Kembali ke C Academy