HDU 1251 统计难题

题目链接~~>

做题感悟：这是接触字典树的第一题，记录一下。

解题思路：见代码（因为只有一组数据，so 不用释放内存）。

代码：

  

   

    

     

    
    

     

      #include<stdio.h>
     
    
   

    

     

    
    

     

      #include<iostream>
     
    
   

    

     

    
    

     

      #include<map>
     
    
   

    

     

    
    

     

      #include<string>
     
    
   

    

     

    
    

     

      #include<string.h>
     
    
   

    

     

    
    

     

      #include<stdlib.h>
     
    
   

    

     

    
    

     

      #include<queue>
     
    
   

    

     

    
    

     

      #include<algorithm>
     
    
   

    

     

    
    

     

      using namespace std ;
     
    
   

    

     

    
    

     

      #define LEN sizeof(struct node)
     
    
   

    

     

    
    

     

      struct node
     
    
   

    

     

    
    

     

      {
     
    
   

    

     

    
    

     
 int count ;
     
    
   

    

     

    
    

     
 struct node *next[26] ;
     
    
   

    

     

    
    

     

      } ;
     
    
   

    

     

    
    

     

      struct node *root ;
     
    
   

    

     

    
    

     

      struct node *build() // 建立新节点
     
    
   

    

     

    
    

     

      {
     
    
   

    

     

    
    

     
 struct node *p ;
     
    
   

    

     

    
    

     

       p=(struct node*)malloc(LEN) ;
     
    
   

    

     

    
    

     
 for(int i=0 ;i<26 ; i++)
     
    
   

    

     

    
    

     

       {
     
    
   

    

     

    
    

     

       p->next[i]=NULL ;
     
    
   

    

     

    
    

     

       }
     
    
   

    

     

    
    

     

       p->count=1 ;
     
    
   

    

     

    
    

     
 return p ;
     
    
   

    

     

    
    

     

      }
     
    
   

    

     

    
    

     

      void save(char *s) // 保存节点
     
    
   

    

     

    
    

     

      {
     
    
   

    

     

    
    

     
 struct node *p ;
     
    
   

    

     

    
    

     
 int len=strlen(s) ;
     
    
   

    

     

    
    

     
 if(!len) return ;
     
    
   

    

     

    
    

     

       p=root ;
     
    
   

    

     

    
    

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

    

     

    
    

     

       {
     
    
   

    

     

    
    

     
 int temp=s[i]-'a' ;
     
    
   

    

     

    
    

     
 if(p->next[temp]!=NULL)
     
    
   

    

     

    
    

     

       {
     
    
   

    

     

    
    

     

       p=p->next[temp] ;
     
    
   

    

     

    
    

     

       p->count=p->count+1 ; // 存入字符便记录一下
     
    
   

    

     

    
    

     

       }
     
    
   

    

     

    
    

     
 else
     
    
   

    

     

    
    

     

       {
     
    
   

    

     

    
    

     

       p->next[temp]=build() ;
     
    
   

    

     

    
    

     

       p=p->next[temp] ; // 用此地址继续存
     
    
   

    

     

    
    

     

       }
     
    
   

    

     

    
    

     

       }
     
    
   

    

     

    
    

     

      }
     
    
   

    

     

    
    

     

      int seach(char *s) // 查询
     
    
   

    

     

    
    

     

      {
     
    
   

    

     

    
    

     
 int len=strlen(s) ;
     
    
   

    

     

    
    

     
 if(!len)  return 0 ;
     
    
   

    

     

    
    

     
 struct node *p ;
     
    
   

    

     

    
    

     

       p=root ;
     
    
   

    

     

    
    

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

    

     

    
    

     

       {
     
    
   

    

     

    
    

     
 int temp=s[i]-'a' ;
     
    
   

    

     

    
    

     
 if(p->next[temp]!=NULL)
     
    
   

    

     

    
    

     

       p=p->next[temp] ;
     
    
   

    

     

    
    

     
 else  return 0 ;
     
    
   

    

     

    
    

     

       }
     
    
   

    

     

    
    

     
 return p->count ;
     
    
   

    

     

    
    

     

      }
     
    
   

    

     

    
    

     

      int main()
     
    
   

    

     

    
    

     

      {
     
    
   

    

     

    
    

     
 int ans ;
     
    
   

    

     

    
    

     
 char s[15] ;
     
    
   

    

     

    
    

     

       root=build() ;
     
    
   

    

     

    
    

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

    

     

    
    

     

       save(s) ;
     
    
   

    

     

    
    

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

    

     

    
    

     

       {
     
    
   

    

     

    
    

     

       ans=seach(s) ;
     
    
   

    

     

    
    

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

    

     

    
    

     

       }
     
    
   

    

     

    
    

     
 return 0 ;
     
    
   

    

     

    
    

     

      }
     
    
  
 

关于字典树的博客~>
 

文章来源: blog.csdn.net，作者：Linux猿，版权归原作者所有，如需转载，请联系作者。

原文链接：blog.csdn.net/nyist_zxp/article/details/19111061