大家好，又见面了，我是全栈君，今天给大家准备了Idea注册码。
1. trie基础
(1) 是什么？
Trie，又称单词查找树或键树，是一种树形结构，是一种哈希树的变种。
(2) 性质
- 根节点不包含字符，除根节点外每一个节点都只包含一个字符
- 从根节点到某一节点，路径上经过的字符连接起来，为该节点对应的字符串
- 每个节点的所有子节点包含的字符都不相同
例如，单词序列a, to, tea, ted, ten, i, in, inn，对应的trie。
(3) 应用
用于统计和排序大量的字符串，但不仅限于字符串，所以经常被搜索引擎系统用于文本词频统计。
(4) 优点
- 最大限度地减少无谓的字符串比较
- 查询效率比哈希表高
2. 一个例子
1 #include <stdio.h> 2 #include <string.h> 3 #include <stdlib.h> 4 5 #define MAX 256//ascii码有256个字符，故每棵树的子节点最多有256个 6 #define MAXLEN 256//单词最长为256 7 8 typedef struct TrieNode 9 { 10 int count; 11 struct TrieNode *next[MAX]; 12 }TrieNode; 13 14 //插入一个单词 15 void Insert(char *word,TrieNode *root) 16 17 { 18 int i; 19 TrieNode *cur; 20 if(word[0]=='\0') 21 return; 22 cur=root; 23 for(i=0;word[i]!='\0';i++) 24 { 25 if(cur->next[word[i]]==NULL) 26 { 27 TrieNode *newNode = (TrieNode *)malloc(sizeof(TrieNode)); 28 memset(newNode,0,sizeof(TrieNode)); 29 cur->next[word[i]]=newNode; 30 } 31 cur=cur->next[word[i]]; 32 } 33 34 cur->count++; 35 return; 36 } 37 38 //创建树输入每个单词，以回车结束，则单词被插入树中，碰到*停止树的创建 39 void Construct(TrieNode *&root) 40 { 41 char inStr[MAXLEN]; 42 int size=0; 43 root = (TrieNode *)malloc(sizeof(TrieNode)); 44 memset(root,0,sizeof(TrieNode)); 45 while(1) 46 { 47 scanf("%s",inStr); 48 if(strcmp(inStr,"*")==0) 49 break; 50 Insert(inStr,root); 51 } 52 return; 53 } 54 55 //遍历整棵树 56 void Traverse(TrieNode *curP) 57 { 58 static char theWord[MAXLEN]; 59 static int pos=0; 60 int i; 61 if(curP==NULL) 62 return; 63 if(curP->count) 64 { 65 theWord[pos]='\0'; 66 printf("%s:%d\n",theWord,curP->count); 67 } 68 for(i=0;i<MAX;i++) 69 { 70 theWord[pos++]=i; 71 //从这句话可以看出在递归调用子节点前，子节点的值已经加入到单词中了 72 Traverse(curP->next[i]); 73 pos--; 74 } 75 return; 76 } 77 78 //查找一个单词是不是在树中 79 bool Find(TrieNode *root,char *word) 80 { 81 int i; 82 TrieNode *cur; 83 cur=root; 84 for(i=0;word[i]!='\0';i++) 85 { 86 if(cur->next[word[i]]==NULL) 87 { 88 return false; 89 } 90 cur=cur->next[word[i]]; 91 } 92 93 if(cur->count) 94 return true; 95 else 96 return false; 97 } /* 何问起 hovertree.com */ 98 99 int main() 100 { 101 TrieNode *root; 102 char str[MAXLEN]; 103 Construct(root); 104 printf("\n"); 105 Traverse(root); 106 printf("\n"); 107 while(1) 108 { 109 scanf("%s",str); 110 if(strcmp(str,"*")==0) 111 break; 112 printf("%s:%d\n",str,Find(root,str)); 113 } 114 115 return 0; 116 }
推荐：http://www.cnblogs.com/roucheng/p/wendang.html
版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 举报，一经查实，本站将立刻删除。
发布者：全栈程序员-站长，转载请注明出处：https://javaforall.net/120417.html原文链接：https://javaforall.net
