当前位置:编程学习 > C/C++ >>

hdu 1004 trie树

这道题其实很简单,直接开数组或者用map映射也好,为了练习trie树,我就用trie来做了,而且用动态申请内存,无聊的我啊
 
[cpp]  
/***************************************************************** 
    > File Name: t.c 
    > Author: Lobo Chim 
    > Created Time: 2013年01月24日 星期四 13时09分33秒 
 ****************************************************************/  
  
#include <stdio.h>  
#include <string.h>  
  
#define CN 26  
  
typedef struct node  
{  
    struct node *child[CN];  
    int count;  
    char s[16];  
    node()  
    {  
        count=0;  
        int i;  
        for(i=0;i<CN;i++)  
            child[i]=NULL;  
    }  
}NODE;  
  
void insert(NODE *root,const char *str)  
{  
    int len=strlen(str);  
    int i;  
    NODE *cur=root;  
    for(i=0;i<len;i++)  
    {  
            if(cur->child[str[i]-'a']!=NULL)  
            {  
                cur=cur->child[str[i]-'a'];  
            }  
            else  
            {  
                cur->child[str[i]-'a']=new NODE;  
                 cur=cur->child[str[i]-'a'];  
            }  
    }  
    strcpy(cur->s,str);  
    cur->count++;  
}  
  
void dfs(const NODE * root,char * &str,int &max)  
{  
    int i,temp;  
    for(i=0;i<CN;i++)  
    {  
        if(root->count > max)  
        {  
            max=root->count;  
            str=(char *)root->s;  
        }  
        if(root->child[i])  
        dfs(root->child[i],str,max);  
    }  
}  
  
void del(NODE *root)  
{  
    int i;  
    for(i=0;i<CN;i++)  
        if(root->child[i])  
            del(root->child[i]);  
    delete root;  
    root=NULL;  
}  
  
int main()  
{  
    int Case;  
    while(scanf("%d",&Case)!=EOF && Case )  
    {  
        int i;  
        char s[16];  
        NODE *root=new NODE;  
        for(i=0;i<Case;i++)  
        {  
            scanf("%s",s);  
            insert(root,s);  
        }  
        char *p;  
        int max=0;  
        dfs(root,p,max);  
        printf("%s\n",p);  
        del(root);  
    }  
    return 0;  
}  
 
 
补充:软件开发 , C++ ,
CopyRight © 2012 站长网 编程知识问答 www.zzzyk.com All Rights Reserved
部份技术文章来自网络,