字典树 --c语言
(1)trie.h
?
#ifndef TRIE_H_#define TRIE_H_typedef struct word_trie_t word_trie_t;typedef enum bool bool;enum bool{ false=0, true=1,};struct word_trie_t{ bool (*insert)(word_trie_t *this,char *str); bool (*find_word)(word_trie_t *this,char *str); int (*find_prefix)(word_trie_t *this,char *str); bool (*delete)(word_trie_t *this,char *str); void (*destroy)(word_trie_t *this);};word_trie_t *word_trie_create();#endif?
(2)trie.c
?
#include "trie.h"#include <stdio.h>#include <string.h>#include <malloc.h>///////////////////////* 字典树节点 *///////////////////////#define TRIE_NODE_MAX 26typedef struct trie_node_t trie_node_t;/*字典树节点结构*/struct trie_node_t{ int count; //用来计算前缀数 bool is_str; //用来标识到此的字符串 trie_node_t *word[TRIE_NODE_MAX]; //子节点指针};/*创建一个节点*/trie_node_t* trie_node_create(){ trie_node_t* node=(trie_node_t *)malloc(sizeof(trie_node_t)); memset(node,0,sizeof(trie_node_t)); return node;}/*回收一个节点*/void trie_node_destroy(trie_node_t* node){ free(node); }////////////////////////////////////* 字典树对外接口实现 *////////////////////////////////////typedef struct private_word_trie_t private_word_trie_t;struct private_word_trie_t{ word_trie_t public; //对外接口 trie_node_t *root; //字典树根};//插入一个字符串bool insert(private_word_trie_t *this,char *str){ trie_node_t *current=this->root; int word_pos; //不断的循环插入，直到字符串结尾 while(*str) { word_pos=*str-'a'; //如果插入的分支为空，新建节点 if(current->word[word_pos]==NULL) { current->word[word_pos]=trie_node_create(); } current=current->word[word_pos]; //节点索引值增加 current->count++; str++; } //在最后一个节点标识为一个字符串 current->is_str=true; return true;}//查找节点bool find_word(private_word_trie_t *this,char *str){ trie_node_t *current=this->root; int word_pos; while(*str) { word_pos=*str-'a'; //如果分支为空，标识没有此字符串 if((current=current->word[word_pos])==NULL) { return false; } str++; } return current->is_str;}//查找前缀数int find_prefix(private_word_trie_t *this,char *str){ trie_node_t *current=this->root; int word_pos; while(*str) { word_pos=*str-'a'; if((current=current->word[word_pos])==NULL) { return 0; } str++; } return current->count; }//删除一个字符串bool delete(private_word_trie_t *this,char *str){ trie_node_t *current=this->root; int word_pos; trie_node_t *del=NULL; //第一步查找，如果是曾经插入的字符串，可以删除 if(find_word(this,str)) { //释放前缀数，如果索引值为0，可以回收节点 while(*str) { word_pos=*str-'a'; if(((current->word[word_pos])->count--)==0) { del=current->word[word_pos]; current->word[word_pos]=NULL; str++; break; } str++; } //释放下面的节点 if(del!=NULL) { while(*str) { word_pos=*str-'a'; current=del; del=current->word[word_pos]; trie_node_destroy(current); str++; } trie_node_destroy(del); } return true; } else { return false; }}//递归回收节点void trie_destroy(trie_node_t *node){ int i; for(i=0;i<TRIE_NODE_MAX;i++) { if(node->word[i]!=NULL) { trie_destroy(node->word[i]); } } trie_node_destroy(node);}//销毁节点树void destroy(private_word_trie_t *this){ trie_destroy(this->root); free(this);}//创建字典树对象word_trie_t *word_trie_create(){ private_word_trie_t *this=(private_word_trie_t *)malloc(sizeof(private_word_trie_t)); this->public.insert=(bool (*)(word_trie_t *,char *))insert; this->public.find_word=(bool (*)(word_trie_t *,char *))find_word; this->public.find_prefix=(int (*)(word_trie_t *,char *))find_prefix; this->public.delete=(bool (*)(word_trie_t *,char *))delete; this->public.destroy=(void (*)(word_trie_t *))destroy; this->root=trie_node_create(); return &this->public;}int main(){ word_trie_t *tree=word_trie_create();char str[100];while(gets(str)&&str[0]){ tree->insert(tree,str);}while(gets(str)&&str[0]){ printf("前缀:%d\n",tree->find_prefix(tree,str)); if(tree->find_word(tree,str)) { printf("%s是插入的一个字符串\n",str); } else { printf("%s不是插入的一个字符串\n",str); }}tree->destroy(tree);return 1;}?