Sisipkan

Pelajaran 5 dari 14 dalam kursus Trie: Struktur Data Seri #8 di Coddy.

Untuk menyisipkan kata ke dalam trie, telusuri dari root satu karakter demi satu karakter. Untuk setiap karakter dalam kata: jika node saat ini tidak memiliki child untuk karakter tersebut, buat TrieNode baru dan hubungkan dengannya. Apa pun kondisinya, pindah ke child tersebut dan lanjutkan dengan karakter berikutnya.

Saat mencapai akhir kata, tandai node tempat kamu berada dengan isEndOfWord = true. Penanda itu nantinya membedakan kata sungguhan yang tersimpan dari jalur yang kebetulan ada karena merupakan awalan dari sesuatu yang lain.

Menyisipkan "cat" lalu "car" menggunakan jalur c -> a yang sama dan hanya bercabang pada karakter ketiga. Penggunaan jalur yang sama inilah yang membuat trie sangat hemat ruang untuk dictionary.

Tantangan

Mudah

Tambahkan method insert ke class Trie.

Method ini menerima string word dan menyimpannya di trie:

Mulai dari root. Untuk setiap karakter c dalam word, jika node saat ini tidak memiliki child untuk c, tambahkan TrieNode baru di sana.
Pindah ke child tersebut dan lanjutkan.
Setelah karakter terakhir, tandai isEndOfWord pada node terakhir sebagai true.

Coba sendiri

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

int main() {
    Trie t;
    Trie_init(&t);
    char line[1024];
    while (fgets(line, sizeof(line), stdin)) {
        line[strcspn(line, "\r\n")] = '\0';
        char* cmd = strtok(line, " \t");
        if (!cmd) continue;
        if (strcmp(cmd, "rootIsEmpty") == 0) { printf("%s\n", TrieNode_childrenCount(t.root) == 0 ? "true" : "false"); }
        if (strcmp(cmd, "hasChild") == 0) { char* arg = strtok(NULL, " \t"); if (arg) printf("%s\n", t.root->children[(unsigned char)arg[0]] != NULL ? "true" : "false"); }
        if (strcmp(cmd, "insert") == 0) { char* arg = strtok(NULL, " \t"); if (arg) Trie_insert(&t, arg); }
    }
    return 0;
}

Semua pelajaran di Trie: Struktur Data Seri #8

1Pengenalan

Pengenalan Apa Itu Trie?

2Proyek Trie

class TrieNode class TrieSisipkanCari Diawali Dengan Hapus Jumlah Kata

3Tantangan Latihan

Prefiks Bersama Terpanjang Hitung Kata dengan Prefiks Pelengkapan Otomatis Kata Terpanjang dalam Dictionary Pemisahan Kata

Latihan sendiri: Compiler C online