hdu 1251(字典树)

题目链接：http://acm.hdu.edu.cn/status.php?user=NYNU_WMH&pid=1251&status=5

Trie树的基本实现

字母树的插入（Insert）、删除（ Delete）和查找（Find）都非常简单，用一个一重循环即可，即第i 次循环找到前i 个字母所对应的子树，然后进行相应的操作。实现这棵字母树，我们用最常见的数组保存（静态开辟内存）即可，当然也可以开动态的指针类型（动态开辟内存）。至于结点对儿子的指向，一般有三种方法：

1、对每个结点开一个字母集大小的数组，对应的下标是儿子所表示的字母，内容则是这个儿子对应在大数组上的位置，即标号；

2、对每个结点挂一个链表，按一定顺序记录每个儿子是谁；

3、使用左儿子右兄弟表示法记录这棵树。

三种方法，各有特点。第一种易实现，但实际的空间要求较大；第二种，较易实现，空间要求相对较小，但比较费时；第三种，空间要求最小，但相对费时且不易写。

表示用G++提交一直内存超限.....Orz 而C++直接秒过.......srO

malloc 较为费时 124MS

 #include <stdio.h>

 #include <string.h>

 #include <math.h>

 #include <algorithm>

 #include <iostream>

 #include <ctype.h>

 #include <iomanip>

 #include <queue>

 #include <stdlib.h>

 using namespace std;

 struct node

 {

     int count;

     struct node *next[];

 };

 struct node *root;

 struct node *newset()   //

 {

     struct node *current;

     current=(struct node *)malloc(sizeof(struct node));

     for(int i= ;i < ; i++){

         current->next[i]=NULL;

     }

     current->count=;

     return current;

 }

 void insert(char *s)  //

 {

     struct node *current;

     int len=strlen(s);

     if(len==)

         return ;

     current= root;

     for(int i= ;i < len; i++){

         if(current->next[s[i]-'a']!=NULL){

             current = current->next[s[i]-'a'];

             current->count = current->count+;

         }

         else{

             current->next[s[i]-'a'] = newset();

             current = current->next[s[i]-'a'];

         }

     }

 }

 int find(char *s)

 {

     struct node *current;

     int len=strlen(s);

     if(len==)

         return ;

     current=root;

     for(int i= ;i < len; i++){

         if(current->next[s[i]-'a']!=NULL){

             current = current->next[s[i]-'a'];

         }

         else{

             return ;

         }

     }

     return current->count;

 }

 int main()

 {

     char str[];

     int i,ans;

     root=newset();

     while(gets(str)&&str[]!='\0'){

         insert(str);

     }

     while(~scanf("%s",str)){

         ans=find(str);

         printf("%d\n",ans);

     }

     return ;

 }

先分配好内存 109MS

 #include <stdio.h>

 #include <string.h>

 #include <math.h>

 #include <algorithm>

 #include <iostream>

 #include <ctype.h>

 #include <iomanip>

 #include <queue>

 #include <stdlib.h>

 using namespace std;

 typedef struct node

 {

     int count;

     struct node *next[];

 }Trienode;

 Trienode *root;

 Trienode memory[];

 int p=;

 struct node *newset()   //

 {

     Trienode *current = &memory[p++];

     for(int i= ;i < ; i++){

         current->next[i]=NULL;

     }

     current->count=;

     return current;

 }

 void insert(char *s)  //

 {

     struct node *current;

     int len=strlen(s);

     if(len==)

         return ;

     current= root;

     for(int i= ;i < len; i++){

         if(current->next[s[i]-'a']!=NULL){

             current = current->next[s[i]-'a'];

             current->count = current->count+;

         }

         else{

             current->next[s[i]-'a'] = newset();

             current = current->next[s[i]-'a'];

         }

     }

 }

 int find(char *s)

 {

     struct node *current;

     int len=strlen(s);

     if(len==)

         return ;

     current=root;

     for(int i= ;i < len; i++){

         if(current->next[s[i]-'a']!=NULL){

             current = current->next[s[i]-'a'];

         }

         else{

             return ;

         }

     }

     return current->count;

 }

 int main()

 {

     char str[];

     int i,ans;

     root=newset();

     while(gets(str)&&str[]!='\0'){

         insert(str);

     }

     while(~scanf("%s",str)){

         ans=find(str);

         printf("%d\n",ans);

     }

     return ;

 }

巴特西

hdu 1251(字典树)

最新文章

热门文章