C语言的字典树实现

╰半夏微凉° 2022-06-02 01:19 203阅读 0赞

字典树是什么东西就不过多于解释了,反正在查找上面很好用,它的更好的一层封装就是AC自动机.  
C语言的字典树的实现就是如下:

#include <stdio.h> 
        #include <stdlib.h> 
        #include <string.h> 
    
        #define MAX 128
        #define IDXERR -1 
        #define INVALID 0 
        #define VALID 1 
    
        #define true 1 
        #define false 0 
    
        typedef struct TrieNode  
        {  
            int isStr; /*word flag*/  
            int elemcount; /*word number*/  
            int passcount; /*pass by number*/  
            struct TrieNode *next[MAX];  
        }Trie;  
    
        Trie * trie_malloc();  
        void trie_init(Trie *p);  
    
        void trie_insert(Trie *root, char *s);  
        int trie_search(Trie *root, char *s);  
        void trie_del(Trie *root);  
        void trie_node_del(Trie *root,  char *s);  
    
        static int verify_str( char *s);  
        static int get_index(char ch);  
        static void delete_subtrie(Trie **root);  
        static void delete_node(Trie **node,  char *chr);  
    
        void trie_init(Trie *p)  
        {  
            int i=0;  
            if(NULL == p)  
                return;  
            memset(p,0x0,sizeof(Trie));  
            for(i=0;i<MAX;i++)  
            {  
                p->next[i] = NULL;  
            }  
            p->isStr = false;  
            p->elemcount = 0;  
            p->passcount = 0;  
        }  
    
        Trie * trie_malloc()  
        {  
            Trie *temp=(Trie *)malloc(sizeof(Trie));  
            return temp;  
        }  
    
        void trie_insert(Trie *root, char *s)  
        {  
            if(NULL == root || NULL == s || *s == '\0')  
                return;  
            if(INVALID == verify_str(s))  
                return;  
            Trie *p = root;  
            int idx = 0;  
            while(*s!='\0')  
            {  
                idx = get_index(*s);  
                if(NULL == p->next[idx])   
                {  
                    Trie *temp = trie_malloc();  
                    trie_init(temp);  
                    p->next[idx]=temp;  
                    p=p->next[idx];     
                }     
                else  
                {  
                    p=p->next[idx];  
                }  
                s++;  
                p->passcount++;  
            }  
            p->isStr=true;    
            p->elemcount++;  
        }  
    
        int trie_search(Trie *root, char *s)   
        {  
            Trie *p=root;  
            int idx = 0;  
            if(NULL == root || NULL == s)  
                return 0;  
            while(p != NULL && *s != '\0')  
            {  
                idx = get_index(*s);  
                if(IDXERR == idx)  
                    return 0;  
                p=p->next[idx];  
                s++;  
            }  
            if(p != NULL && true == p->isStr)  
                return p->elemcount;  
            else  
                return 0;  
        }  
    
        void trie_del(Trie *root)  
        {  
                if(NULL == root)  
                        return;  
                delete_subtrie(&root);  
        }  
    
        static int verify_str(char *s)  
        {  
            if(NULL == s)  
                return INVALID;  
                while(*s!='\0')  
                {  
                        if(IDXERR == get_index(*s))  
                                return INVALID;  
                        s++;  
                }  
                return VALID;  
        }  
    
        static int get_index(char ch)  
        {  
                int idx = ch;  
                if(idx < 0 || idx >= MAX)  
                {  
                        idx = IDXERR;  
                }  
                return idx;  
        }  
    
        static void delete_subtrie(Trie **root)  
        {  
            int i = 0;  
            if(root != NULL && *root != NULL)  
            {  
                for(i = 0; i < MAX; i++)  
                {  
                    if((*root)->next[i]!=NULL)  
                    {  
                        delete_subtrie(&((*root)->next[i]));  
                    }  
                }  
            }  
            if(NULL != root)  
            {  
                free(*root);  
                *root = NULL;  
            }  
        }  
    
    
        static void delete_node(Trie **node, char *chr)  
        {  
            int idx = 0;  
            if(NULL == node || NULL == *node || NULL == chr)  
                return;  
            if(*chr != '\0'&& *(chr+1) != '\0' && *node != NULL)  
            {  
                chr++;  
                idx = get_index(*chr);  
                delete_node(&((*node)->next[idx]), chr);             
            }  
            if(*node != NULL)  
            {  
                free(*node);  
                *node = NULL;  
            }  
            return;  
        }   
    
        void trie_node_del(Trie *root,  char *s)  
        {  
            if(NULL == root || NULL == s || *s == '\0')  
                return;  
            int elemcount=0;  
            Trie *p = root;  
                Trie *q = p;  
                int remain=0;  
                int idx = 0;  
            if((elemcount=trie_search(root,s))<= 0)  
                return;  
            while(*s != '\0' && p != NULL)  
            {  
                idx = get_index(*s);  
                q = p;  
                p = p->next[idx];  
                remain = p->passcount - elemcount;  
                if(remain <= 0)  
                {  
                    delete_node(&p, s);  
                    q->next[idx] = p; // important 
                    p = NULL;// can delete "p = NULL" 
                    break;  
                }  
                else  
                {  
                    p->passcount = remain;  
                }  
                s++;  
            }  
            /*clear word flag*/  
            if(p != NULL)  
            {  
                p->isStr = false;  
            }  
        }

主文件:

#include "trie.h" 
    
        #define STR1 "hello" 
        #define STR2 "hell" 
        #define STR3 "helloworld" 
        #define STR4 "world" 
        #define STARLINE "****" 
    
        int main(int argc, char *argv[])  
        {  
            Trie *root= trie_malloc();  
            if(NULL == root)  
            {  
                printf("malloc trie failed\n");  
                exit(0);  
            }  
            trie_init(root);  
    
            /*insert*/  
            printf("\n %sinsert string%s\n",STARLINE,STARLINE);  
            trie_insert(root,STR1);  
            printf("%s\n",STR1);  
            trie_insert(root,STR2);  
            printf("%s\n",STR2);  
            trie_insert(root,STR3);  
            printf("%s\n",STR3);  
            trie_insert(root,STR4);  
            printf("%s\n",STR4);  
            trie_insert(root,STR2);  
            printf("%s\n",STR2);  
            /*search*/  
            printf("\n %ssearch string%s\n",STARLINE,STARLINE);  
            printf("%s, %d times\n",STR1, trie_search(root,STR1));  
            printf("%s, %d times\n",STR2, trie_search(root,STR2));  
            printf("%s, %d times\n",STR3, trie_search(root,STR3));  
            printf("%s, %d times\n",STR4, trie_search(root,STR4));  
            /*delete*/  
            printf("\n %sdelete string%s\n",STARLINE,STARLINE);  
            trie_node_del(root, STR1);  
            printf("%s\n", STR1);  
            printf("search %s, %d times\n",STR1, trie_search(root,STR1));  
    
            trie_node_del(root, STR2);  
            printf("%s\n", STR2);  
            printf("search %s, %d times\n",STR2, trie_search(root,STR2));  
    
            trie_node_del(root, STR3);  
            printf("%s\n", STR3);  
            printf("search %s, %d times\n",STR3, trie_search(root,STR3));  
    
            trie_node_del(root, STR4);  
            printf("%s\n", STR4);  
            printf("search %s, %d times\n",STR4, trie_search(root,STR4));  
    
            /*free trie*/  
            printf("\n %sfree trie%s\n",STARLINE,STARLINE);  
            trie_del(root);  
            root = NULL;  
    
            return 0;  
        }