#include
#include
#define Alphabet_SIZE 26// 数据结构
typedef struct tnode
{int flag; // 是否为 word 节点 / word 的数量struct tnode *next[Alphabet_SIZE]; // 子节点
}tnode;tnode createDictTree(char* strs[], int len); // 为字符串数组建立字典树
void addNodeInTree(tnode *root, char *str); // 为字典树添加 word
int searchInTree(tnode *root, char *str); // 在字典树中查找 wordint main(){char *str[] = {"hello", "hell", "world", "hbchen", "hbchen"};tnode root = createDictTree(str, 5); // 建立字典树int i;for(i = 0; i < 5; i++){int cnt = searchInTree(&root, str[i]); // 查找验证printf("%s:%d
", str[i], cnt);}return 0;
}tnode createDictTree(char* strs[], int len){tnode root = {0};int i;for(i = 0; i < len; i++){addNodeInTree(&root, strs[i]);}return root;
}void addNodeInTree(tnode *root, char *str){tnode *pt = root, *next;char *ps = str;while((*ps) != ' '){int idx = *ps - 'a';next = pt->next[idx];if(next == NULL){// 子节点不存在,创建子节点并初始化pt->next[idx] = (tnode*)malloc(sizeof(tnode));next = pt->next[idx];pt->flag = 0;int i;for(i = 0; i < Alphabet_SIZE; i++){next->next[i] = NULL;}}pt = next; ps++;}pt->flag++; // str遍历完成,当前节点次数+1
}int searchInTree(tnode *root, char *str){// 返回词的频数 或 是否存在tnode *pt = root, *next;char *ps = str;while((*ps) != ' '){// 按照 word 顺序依次从 root 遍历字典树int idx = *ps - 'a';if(pt->next[idx] == NULL){return -1;}pt = pt->next[idx];ps++;}return pt->flag;
}