字典树实现

╰+哭是因爲堅強的太久メ 2022-08-27 00:29 133阅读 0赞

字典树，插入时检测单词是否存在。

#include <stdio.h>
    #include <stdlib.h>
    #include <string.h>
    #include <stdbool.h>
    
    /*默认只处理26个小写字母
     *将小写字母转换为数字
     */
    #define MAX 26
    typedef struct word_node
    {
        bool is_word_end;
        int num;  //字母-'a'后的数字
        struct word_node* next[MAX];
    }word_node_t;
    
    #define INSERT_FAIL -1
    #define INSERT_SUCCESS 0
    #define INSERT_EXIST 1
    
    word_node_t *create_word(const int num)
    {
        word_node_t *p = (word_node_t*)malloc(sizeof(word_node_t));
        if (p == NULL)
        {
            printf("malloc error\n");
            exit(1);
        }
        memset(p->next, 0, MAX);
        p->is_word_end = false;
        p->num = num;
    
        return p;
    }
    
    //调用时，root必须存在且不为NULL
    int insert_word(const char *str, word_node_t *pos)
    {
        const int str_length = strlen(str);
        int i;
        for (i = 0; i < str_length; ++i)
        {
            int num = str[i] - 'a';
            if (pos->next[num] == NULL)
            {
                pos->next[num] = create_word(num);
            }
            pos = pos->next[num];
        }
    
        if (pos->is_word_end)  //已存在单词或字串与插入单词相同
          return INSERT_EXIST;
        else
        {
            pos->is_word_end = true;
            return INSERT_SUCCESS;
        }
    }
    
    void free_tree(word_node_t *root)
    {
        int i;
        for (i = 0; i < MAX; ++i)
        {
            if (root->next[i] != NULL)
            {
                free_tree(root->next[i]);
                root->next[i] = NULL;
            }
        }
        free(root);
    }
    
    int main(int argc, char **argv)
    {
        word_node_t *root = create_word(-1);
        char *a[] = {"abc", "abcd", "abcde", "abc", "bcd", "bbde", "bbde", "abcd", "xyz", "xy", "xyz"};
        int i;
        int result;
        for (i = 0; i < sizeof(a)/sizeof(char*); ++i)
        {
    
            if ((result = insert_word(a[i], root)) == INSERT_EXIST)
            {
                printf("exit:%s\n", a[i]);
            }
            else if (result == INSERT_SUCCESS)
              printf("success:%s\n", a[i]);
        }
        free_tree(root);
    }