// 字典树模版 // http://acm.hdu.edu.cn/showproblem.php?pid=1251 /* 自己由于能力有限,这种图,树之类的还没看,更别提做了,这个字典数的题目也是花了差不多一天才完全理解 其中主要是看别人的代码,自己再思考,再写, 这里推荐一个人的博客,从里面学到了很多,里面很多文章都是很好的 有兴趣的可以看看,我的这个代码几乎和他的一样,差不多背下来了吧,嘿嘿 url 传送 http://www.wutianqi.com/ */ // 这里我也不知道怎么回事,在参数函数里面,关于结构体的,必须使用-〉 而在main函数里面则只用. 可能是编译器的缘故,我用的是code::blocks // 在isCreatDicTree 函数里面构建树(有26个分支),其实每当到了一个节点的时候,下一步总要构建一个新的节点,再新节点又有26个null的,除了字符串已经处理完了 // 在结构体里面的next[26],其实就是这样的工能, // 在isFindDicTree函数里面主要是把现在的字符串和以建立好的字典书进行比较,最后返回v值,这里的v值,其实就是存放该节点的位置,当最后一个字母搜素完成了之后 // 就返回该字符串的v值 #include<stdio.h> #include<stdlib.h> #include<string.h> #include<iostream> using namespace std; typedef struct isDicTree { int v; isDicTree *next[26]; }isDicTree; isDicTree root; void isCreatDicTree(char *s) { isDicTree *p=&root,*q; int len,i,j,id; len=strlen(s); for(i=0;i<len;i++) { id=s[i]-'a'; if(p->next[id]==NULL) { q=(isDicTree *)malloc(sizeof(root)); q->v=1; for(j=0;j<26;j++) q->next[j]=NULL; p->next[id]=q; p=p->next[id]; } else { p->next[id]->v++; p=p->next[id]; } } } int isFindDicTree(char *s) { int len,i,id; len=strlen(s); isDicTree *p=&root; for(i=0;i<len;i++) { id=s[i]-'a'; if(p->next[id]==NULL) return 0; else p=p->next[id]; } return p->v; } int main() { int i; char str[15]; for(i=0;i<26;i++) root.next[i]=NULL; while(gets(str) && str[0]!='\0') isCreatDicTree(str); while(scanf("%s",str)!=EOF) printf("%d\n",isFindDicTree(str)); return 0; }