HDU 1671 Phone List && POJ 3630 Phone List

题目链接~~>

做题感悟： 简单的字典树题

解题思路：判断是否存在一个号码是另一个号码的前缀（这题号码不重复），但是POJ 上须静态字典树，就是先申请再将它们连接起来（思路一样），静态用时间很少。

代码（动态内存+释放）：

  

   

    

     

    
    

     

      #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)
     
    
   

    

     

    
    

     

      int n ;
     
    
   

    

     

    
    

     

      bool flag ;
     
    
   

    

     

    
    

     

      struct node
     
    
   

    

     

    
    

     

      {
     
    
   

    

     

    
    

     
 bool count ;
     
    
   

    

     

    
    

     
 struct node *next[10] ;
     
    
   

    

     

    
    

     

      } ;
     
    
   

    

     

    
    

     

      struct node *root ; //根节点
     
    
   

    

     

    
    

     

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

    

     

    
    

     

      {
     
    
   

    

     

    
    

     
 struct node *p ;
     
    
   

    

     

    
    

     

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

    

     

    
    

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

    

     

    
    

     

       {
     
    
   

    

     

    
    

     

       p->next[i]=NULL ;
     
    
   

    

     

    
    

     

       }
     
    
   

    

     

    
    

     

       p->count=false ;
     
    
   

    

     

    
    

     
 return  p ;
     
    
   

    

     

    
    

     

      }
     
    
   

    

     

    
    

     

      void save(char *s) // 存单词同时判断
     
    
   

    

     

    
    

     

      {
     
    
   

    

     

    
    

     
 int len=strlen(s) ;
     
    
   

    

     

    
    

     
 if(!len)  return ;
     
    
   

    

     

    
    

     
 struct node *p ;
     
    
   

    

     

    
    

     

       p=root ;
     
    
   

    

     

    
    

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

    

     

    
    

     

       {
     
    
   

    

     

    
    

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

    

     

    
    

     
 if(p->next[temp]&&(p->next[temp]->count||len-1==i)) // 判断是否存在前缀
     
    
   

    

     

    
    

     

       {
     
    
   

    

     

    
    

     

       flag=true ;
     
    
   

    

     

    
    

     
 break ;
     
    
   

    

     

    
    

     

       }
     
    
   

    

     

    
    

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

    

     

    
    

     

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

    

     

    
    

     

       p=p->next[temp] ;
     
    
   

    

     

    
    

     

       }
     
    
   

    

     

    
    

     

       p->count=true ;
     
    
   

    

     

    
    

     

      }
     
    
   

    

     

    
    

     

      void del(struct node *p)// 释放内存
     
    
   

    

     

    
    

     

      {
     
    
   

    

     

    
    

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

    

     

    
    

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

    

     

    
    

     

       del(p->next[i]) ;
     
    
   

    

     

    
    

     
 free(p) ;
     
    
   

    

     

    
    

     

      }
     
    
   

    

     

    
    

     

      int main()
     
    
   

    

     

    
    

     

      {
     
    
   

    

     

    
    

     
 int T ;
     
    
   

    

     

    
    

     
 char s[15] ;
     
    
   

    

     

    
    

     
 scanf("%d",&T) ;
     
    
   

    

     

    
    

     
 while(T--)
     
    
   

    

     

    
    

     

       {
     
    
   

    

     

    
    

     

       root=build() ;
     
    
   

    

     

    
    

     

       flag=false ;
     
    
   

    

     

    
    

     
 scanf("%d",&n) ;
     
    
   

    

     

    
    

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

    

     

    
    

     

       {
     
    
   

    

     

    
    

     
 scanf("%s",s) ;
     
    
   

    

     

    
    

     
 if(!flag)
     
    
   

    

     

    
    

     

       save(s) ;
     
    
   

    

     

    
    

     

       }
     
    
   

    

     

    
    

     
 printf("%s\n",flag ? "NO" : "YES") ;
     
    
   

    

     

    
    

     

       del(root) ;  // 释放内存
     
    
   

    

     

    
    

     

       }
     
    
   

    

     

    
    

     
 return 0 ;
     
    
   

    

     

    
    

     

      }
     
    
  
 

代码（静态字典树）：

  

   

    

     

    
    

     

      #include<stdio.h>
     
    
   

    

     

    
    

     

      #include<iostream>
     
    
   

    

     

    
    

     

      #include<map>
     
    
   

    

     

    
    

     

      #include<string>
     
    
   

    

     

    
    

     

      #include<string.h>
     
    
   

    

     

    
    

     

      #include<stdlib.h>
     
    
   

    

     

    
    

     

      #include<queue>
     
    
   

    

     

    
    

     

      #include<algorithm>
     
    
   

    

     

    
    

     

      using namespace std ;
     
    
   

    

     

    
    

     

      #define MX 1000000
     
    
   

    

     

    
    

     

      struct node
     
    
   

    

     

    
    

     

      {
     
    
   

    

     

    
    

     
 bool count ;
     
    
   

    

     

    
    

     
 struct node *next[10] ;
     
    
   

    

     

    
    

     

      }T[MX] ;
     
    
   

    

     

    
    

     

      struct node *root ;
     
    
   

    

     

    
    

     

      int top=0 ;
     
    
   

    

     

    
    

     

      bool flag ;
     
    
   

    

     

    
    

     

      struct node *build()
     
    
   

    

     

    
    

     

      {
     
    
   

    

     

    
    

     
 struct node *p ;
     
    
   

    

     

    
    

     

       p=&T[top++] ;
     
    
   

    

     

    
    

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

    

     

    
    

     

       {
     
    
   

    

     

    
    

     

       p->next[i]=NULL ;
     
    
   

    

     

    
    

     

       }
     
    
   

    

     

    
    

     

       p->count=false ;
     
    
   

    

     

    
    

     
 return p ;
     
    
   

    

     

    
    

     

      }
     
    
   

    

     

    
    

     

      void save(char *s)
     
    
   

    

     

    
    

     

      {
     
    
   

    

     

    
    

     
 int len=strlen(s) ;
     
    
   

    

     

    
    

     
 if(!len)  return ;
     
    
   

    

     

    
    

     
 struct node *p ;
     
    
   

    

     

    
    

     

       p=root ;
     
    
   

    

     

    
    

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

    

     

    
    

     

       {
     
    
   

    

     

    
    

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

    

     

    
    

     
 if(p->next[temp]&&(p->next[temp]->count||len-1==i))
     
    
   

    

     

    
    

     

       {
     
    
   

    

     

    
    

     

       flag=true ;
     
    
   

    

     

    
    

     
 return ;
     
    
   

    

     

    
    

     

       }
     
    
   

    

     

    
    

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

    

     

    
    

     

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

    

     

    
    

     

       p=p->next[temp] ;
     
    
   

    

     

    
    

     

       }
     
    
   

    

     

    
    

     

       p->count=true ;
     
    
   

    

     

    
    

     

      }
     
    
   

    

     

    
    

     

      int main()
     
    
   

    

     

    
    

     

      {
     
    
   

    

     

    
    

     
 int T,n ;
     
    
   

    

     

    
    

     
 char s[15] ;
     
    
   

    

     

    
    

     
 scanf("%d",&T) ;
     
    
   

    

     

    
    

     
 while(T--)
     
    
   

    

     

    
    

     

       {
     
    
   

    

     

    
    

     

       root=build() ;
     
    
   

    

     

    
    

     

       flag=false ;
     
    
   

    

     

    
    

     
 scanf("%d",&n) ;
     
    
   

    

     

    
    

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

    

     

    
    

     

       {
     
    
   

    

     

    
    

     
 scanf("%s",s) ;
     
    
   

    

     

    
    

     
 if(!flag)
     
    
   

    

     

    
    

     

       save(s) ;
     
    
   

    

     

    
    

     

       }
     
    
   

    

     

    
    

     
 printf("%s\n",flag ? "NO" : "YES") ;
     
    
   

    

     

    
    

     

       top=0 ;
     
    
   

    

     

    
    

     

       }
     
    
   

    

     

    
    

     
 return 0 ;
     
    
   

    

     

    
    

     

      }
     
    
  
 

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

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