Tìm kiếm

Bài học 6 trên 14 trong khóa học Cây tiền tố, chuỗi cấu trúc dữ liệu số 8 của Coddy.

Tìm một từ là thao tác ngược lại với chèn: đi từ nút gốc xuống từng ký tự một, theo các nút con khớp với từng ký tự. Nếu tại bất kỳ thời điểm nào, nút hiện tại không có nút con ứng với ký tự tiếp theo, từ đó không có trong trie và ta có thể trả về false ngay.

Nếu đi qua được mọi ký tự, ta sẽ đến một nút. Câu trả lời phụ thuộc vào giá trị cờ isEndOfWord của nút đó. Đây là điểm khác biệt quan trọng: sau khi chèn "car", đường đi cho "ca" đã có trong trie, nhưng search("ca") vẫn phải trả về false vì chưa có ai đánh dấu nút đó là điểm kết thúc một từ.

Thử thách

Dễ

Thêm một phương thức search vào lớp Trie.

Phương thức này nhận một chuỗi word và trả về:

true nếu word đã được thêm vào trie trước đó.
false trong các trường hợp còn lại, bao gồm khi chỉ có tiền tố của word tồn tại hoặc chỉ lưu một từ dài hơn bắt đầu bằng word.

Tự làm thử

#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); }
        if (strcmp(cmd, "search") == 0) { char* arg = strtok(NULL, " \t"); if (arg) printf("%s\n", Trie_search(&t, arg) ? "true" : "false"); }
    }
    return 0;
}

Tất cả bài học trong Cây tiền tố, chuỗi cấu trúc dữ liệu số 8

1Giới thiệu

Giới thiệu Trie là gì?

2Dự án Trie

Lớp TrieNode Lớp Trie ChènTìm kiếmBắt đầu bằng Xóa Số lượng từ

3Thử thách luyện tập

Tiền tố chung dài nhất Đếm từ có tiền tố Tự động hoàn thành Từ dài nhất trong từ điển Tách từ

Tự luyện tập: Trình biên dịch C online