【 数据结构 】字典树的构建及搜索代码实现

   声明:本站部分内容来自互联网,如若本站内容侵犯了原著者的合法权益,可联系我们进行处理。

25

#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;
}