POJ2418Hardwood Species

题意：输入若干个树木品种，里边有的是重复的，让你统计每个品种占输入的总数量的百分比，最后按字典序输出

思路：本题数量很大，所以采用直接统计的方式会超时，而采用的方法可以用二叉搜索树，或者用map函数或者是字典树都可以实现，呃，我想说，为什么用G++交WA了，得用C++交才对啊

#include<cstdio>
#include<cstring>
#include<cstdlib>
using namespace std ;
struct node
{
    char name[31] ;
    struct node *lchild,*rchild ;
    int count ;//记录该结点品种出现次数
}tree ;
struct node *root ;
int n = 0 ;
void mid(struct node *root)
{
    if(root != NULL)//按照中序遍历模式计算输出就是字典序
    {
        mid(root->lchild) ;
        printf("%s %.4lf
",root->name,((double)(root->count)/(n*1.0))*100) ;
        //输出单词和所占百分比
        mid(root->rchild);
    }
}
void insertBST(struct node **root,char *s)
{
    if(*root == NULL)
    {
        struct node *p = (struct node *)malloc(sizeof(tree));
        strcpy(p->name,s);//品种复制给新开辟的结点
        p->lchild = NULL ;
        p->rchild = NULL ;
        p->count = 1 ;
        *root = p ;
    }
    else
    {
        if(strcmp(s,(*root)->name) == 0)//出现相同品种
        {
            ((*root)->count)++ ;//该品种数加1，并不再重复插入
            return;
        }
        else if(strcmp(s,(*root)->name) < 0)//如果插入单词小于当前结点单词
        insertBST(&((*root)->lchild),s);//插入当前品种左子树
        else insertBST(&((*root)->rchild),s);//否则插入右子树
    }
}
int main()
{
    char s[31];
    while(gets(s)!=NULL)
    {
        insertBST(&root,s);
        n++ ;
    }
    mid(root) ;
    return 0 ;
}

View Code

http://www.cnblogs.com/fanminghui/p/3272141.html

会神用map写的，代码好短....