poj 2418 Hardwood Species-白红宇

poj 2418 Hardwood Species

阅读量：6969 次

发布时间：2019-06-27

本文共 2183 字，大约阅读时间需要 7 分钟。

题意：给定一些树，按字典序输出数名和树出现的频率；

思路：这个题用二叉搜索树可以做，同时在网上看到了一个简单的方法，用map来做，这里map真是太好用了；

map做法：

View Code

#include 
      
        #include 
        #include 
        
          #include 
         
           using namespace std; int main() {
    string a;     map
          
           tree; double n = 0; char ss[35] = {NULL}; while(gets(ss))     {
            a = ss;         ++tree[a];         ++n;     }     map
           
            ::iterator temp; for(temp = tree.begin(); temp != tree.end(); ++temp) { cout<
            
             first<<" "; printf("%.4f\n",(temp->second)*100.0/n); } return 0; }

二叉搜索树：

刚开始用stirng存名字，G++就是tle而c++就是CE ,无语了；

代码：

View Code

#include 
      
        #include 
       
         #include 
        
          #include 
         
           using namespace std; struct node {
    char s[40]; int n;     node *left,*right; }; int n = 0; node *get() {
        node *tt = NULL;     tt = new node;     tt->n = 1;     tt->left = NULL;     tt->right = NULL; return tt; } node *head = NULL; node *temp = NULL; char str[40] = {NULL}; void insert(char *str,node *t) {
    if(strcmp(str,t->s) == 0)     ++t->n; else if(strcmp(str,t->s) < 0)     {
    if(t->left == NULL)         {
                t->left = get();             t->left->n = 1;             strcpy(t->left->s,str); return ;         } else         insert(str,t->left);     } else     {
    if(t->right == NULL)         {
                t->right = get();             t->right->n = 1;           strcpy(t->right->s,str); return ;         } else         insert(str,t->right);     } } void output(node *tt) {
    if(tt->left == NULL && tt->right == NULL)    {
           printf("%s %.4f\n",tt->s,tt->n*100.00/n); return ;    } if(tt->left)     output(tt->left);        printf("%s %.4f\n",tt->s,tt->n*100.00/n); if(tt->right)     output(tt->right); } int main() {
    //freopen("input.txt","r",stdin);     gets(str);     head = get();     strcpy(head->s,str);     head->n = 1; //puts(head->s);     n = 1; while(gets(str) != NULL)    {
           ++n;        insert(str,head);    } //printf("%d\n",n);    output(head); return 0; }