首页 > 试题广场 >

字典树的实现

[编程题]字典树的实现

热度指数：5726 时间限制：C/C++ 2秒，其他语言4秒空间限制：C/C++ 256M，其他语言512M
算法知识视频讲解

字典树又称为前缀树或者Trie树，是处理字符串常用的数据结构。假设组成所有单词的字符仅是‘a’～‘z’，请实现字典树的结构，并包含以下四个主要的功能。void insert(String word)：添加word，可重复添加；void delete(String word)：删除word，如果word添加过多次，仅删除一次；boolean search(String word)：查询word是否在字典树中出现过(完整的出现过，前缀式不算)；int prefixNumber(String pre)：返回以字符串pre作为前缀的单词数量。现在给定一个m，表示有m次操作，每次操作都为以上四种操作之一。每次操作会给定一个整数op和一个字符串word，op代表一个操作码，如果op为1，则代表添加word，op为2则代表删除word，op为3则代表查询word是否在字典树中，op为4代表返回以word为前缀的单词数量（数据保证不会删除不存在的word）。

输入描述:

输入包含多行，第一行一个整数m，代表操作次数。接下来m行，每行包含一个整数op，和一个字符串word。

输出描述:

对于每次操作，如果op为3时，如果word在字典树中，请输出“YES”，否则输出“NO”；如果op为4时，请输出返回以word为前缀的单词数量，其它情况不输出。

示例1

输入

7
1 qwer
1 qwe
3 qwer
4 q
2 qwer
3 qwer
4 q

输出

YES
2
NO
1

备注:

要求时空复杂度均为

算法知识视频讲解

helloxuanbao

#include <stdlib.h>
#include <stdbool.h>
#include <string.h>
#include <stdio.h>

typedef struct tn {
    int pass;
    int end;
    struct tn **children;  // 存放子节点的指针
} node;

node *new_node() {
    node *new_node = malloc(sizeof(node));
    new_node->pass = 0;
    new_node->end = 0;
    new_node->children = (node **) calloc(26, sizeof(node *));
    return new_node;
}

void destroy_node(node *node) {
    free(node->children);
    free(node);
}

void destroy_whole_path(node *node) {
    for (int i = 0; i < 26; i++) {
        if (node->children[i] != NULL) {
            destroy_node(node->children[i]);
        }
    }
    destroy_node(node);
}

typedef node *trie;

trie new_trie() {
    return new_node();
}

void insert(trie trie, char *word) {
    if (word == NULL || strlen(word) == 0) {
        return;
    }
    int len = (int) strlen(word);
    node *cur = trie;
    cur->pass++;
    int path;
    for (int i = 0; i < len; i++) {
        path = word[i] - 'a';
        if (cur->children[path] == NULL) {
            cur->children[path] = new_node();
        }
        cur = cur->children[path];
        cur->pass++;
    }
    cur->end++;
}

bool search(trie trie, char *word) {
    if (word == NULL || strlen(word) == 0) {
        return false;
    }
    node *cur = trie;
    int path;
    for (int i = 0; i < strlen(word); i++) {
        path = word[i] - 'a';
        if (cur->children[path] == NULL) {
            return false;
        }
        cur = cur->children[path];
    }
    return cur->end != 0;
}

void delete(trie trie, char *word) {
    if (!search(trie, word)) {
        return;
    }
    node *cur = trie, *next;
    cur->pass--;
    int path;
    for (int i = 0; i < strlen(word); i++) {
        path = word[i] - 'a';
        if (--cur->children[path]->pass == 0) {
            next = cur->children[path];
            cur->children[path] = NULL;
            destroy_whole_path(next);
            return;
        }
        cur = cur->children[path];
    }
    cur->end--;
}

int prefixNumber(trie trie, char *word) {
    if (word == NULL || strlen(word) == 0) {
        return false;
    }
    node *cur = trie;
    int path;
    for (int i = 0; i < strlen(word); i++) {
        path = word[i] - 'a';
        if (cur->children[path] == NULL) {
            return 0;
        }
        cur = cur->children[path];
    }
    return cur->pass;
}

#define MAXLEN 21

int main(void) {
    trie trie = new_trie();
    int n, op;
    char str[MAXLEN];
    scanf("%d", &n);
    for (int i = 0; i < n; i++) {
        scanf("%d%s", &op, str);
        if (op == 1) insert(trie, str);
        else if (op == 2) delete(trie, str);
        else if (op == 3) printf("%s\n", search(trie, str) ? "YES" : "NO");
        else if (op == 4) printf("%d\n", prefixNumber(trie, str));
    }
    destroy_node(trie);
    return 0;
}

发表于 2022-02-10 16:18:43 回复(0)