首页 > 代码库 > Trie字典树 静态内存
Trie字典树 静态内存
静态字典树
看了好久的字典树,挺简单的一个结构,愣是看了这么久才写出来。。。
专心一点就不会这样了。。。。
接下来就去刷刷字典树的题吧。。。。。。。
下面是字典树。。。。
定义节点
typedef struct Trie{
char val; //其实这东西没啥软用。。。注释掉也一样。。。没有变化
bool isword;
struct Trie *next[26];
}*Trie_pointer;
然后建树
这几天抽风了。。。
把memset写在函数外面去了。。。。
编译老半天过不去。。。。
日了。。。。。。。
代码:
1 #include "stdio.h" 2 #include "iostream" 3 #include "malloc.h" 4 #include "string.h" 5 6 using namespace std; 7 8 #define MAX_SIZE 26 9 10 typedef struct Trie{11 char val;12 bool isword;13 struct Trie* child[MAX_SIZE];14 }Node,*Trie_pointer;15 16 Trie_pointer CreateNode()17 {18 Trie_pointer node;19 node = (Trie_pointer)malloc(sizeof(Node));20 memset(node,0,sizeof(0));21 return node;22 }23 24 void Insert(Trie_pointer root, char *s)25 {26 Trie_pointer tmp,t = root;27 char *p = s;28 if(*s == ‘\0‘)29 return;30 while(*p != ‘\0‘)31 {32 if(t->child[*p - ‘a‘] == NULL)33 {34 tmp = CreateNode();35 tmp->val = *p;36 t->child[*p - ‘a‘] = tmp;37 }38 t = t->child[*p - ‘a‘];39 p++;40 }41 t->isword = 1;42 }43 44 bool Search(Node root, char *s)45 {46 Trie_pointer t = &root;47 char *p = s;48 if(*s == ‘\0‘)49 return false;50 while(*p != ‘\0‘)51 {52 if(t->child[*p - ‘a‘] == NULL)53 return false;54 t = t->child[*p - ‘a‘];55 p++;56 }57 if(t->isword == 0)58 return false;59 return true;60 }61 62 int main()63 {64 Node root;65 char s[20];66 int i,n;67 memset(&root,0,sizeof(Node));68 cin>>n;69 for(i=1; i<=n; i++)70 {71 cin>>s;72 Insert(&root,s);73 }74 while(cin>>s)75 {76 int flag = Search(root,s);77 if(flag)78 printf("YES\n");79 else80 printf("NO\n");81 }82 return 0;83 }
Trie字典树 静态内存
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。