Số lượng từ

Bài học 9 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.

Hiện tại có bao nhiêu từ khác nhau trong trie này? Không có bộ đếm nào đang hoạt động, nên ta phải duyệt cây và đếm các nút có isEndOfWord là true.

Tìm kiếm theo chiều sâu bắt đầu từ nút gốc sẽ thực hiện được việc này chỉ trong một lượt duyệt. Với mỗi nút, cộng thêm 1 nếu đó là nút kết thúc từ, sau đó đệ quy qua mọi nút con và tính tổng kết quả. Tổng này là số từ được lưu trữ.

Cách này cũng tự nhiên xử lý các từ trùng lặp: chèn "cat" ba lần vẫn chỉ đánh dấu một nút là kết thúc từ, nên số đếm là 1. Các tiền tố chưa từng được chèn riêng cũng không được tính, các nút của chúng vẫn tồn tại, nhưng isEndOfWord có giá trị false.

Thử thách

Dễ

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

Phương thức này không nhận đầu vào và trả về số từ khác nhau hiện được lưu trong trie. Duyệt trie từ nút gốc và đếm mọi nút có isEndOfWord là true.

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"); }
        if (strcmp(cmd, "startsWith") == 0) { char* arg = strtok(NULL, " \t"); if (arg) printf("%s\n", Trie_startsWith(&t, arg) ? "true" : "false"); }
        if (strcmp(cmd, "delete") == 0) { char* arg = strtok(NULL, " \t"); if (arg) Trie_delete(&t, arg); }
        if (strcmp(cmd, "wordCount") == 0) { printf("%d\n", Trie_wordCount(&t)); }
    }
    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èn Tìm kiếm Bắt đầu bằng XóaSố 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