Finding Data Structure Experiments Part Three: Tree Species Statistics

Finding Data Structure Experiments Part Three: Tree Species Statistics

Time Limit: 400MS Memory Limit: 65536KB
Submit Statistic

Problem Description

With the application of satellite imaging technology, natural resources research institutes can identify each tree species.Write a program to help researchers count the number of each tree and calculate the percentage of each tree to the total.

Input

Enter a set of test data.The first row of the data gives a positive integer N (n <= 100000), N denotes the number of trees; the next N lines give the species name of a tree observed by the satellite. The tree name is a string of no more than 20 characters, consisting of letters and spaces, and is case insensitive.

Output

Output the species names and their percentages in dictionary order, separated by spaces, with two decimal places after the decimal point.

Example Input

2
This is an Appletree
this is an appletree

Example Output

this is an appletree 100.00%
This is to record the same number of strings, but to organize them with the structure of a tree, converting all uppercase letters to lowercase letters for easy comparison.
#include<bits/stdc++.h>
using namespace std;
char a[35];
int n;
struct bittree{
    char data[35];
    int num;      //Record the number of occurrences of this string
    bittree *lchild, *rchild;
};
bittree *Creat(bittree *root){
    if(!root){
        root = new bittree;
        root->lchild = NULL;
        root->rchild = NULL;
        root->num = 1;
        strcpy(root->data, a);
    }
    else{
        if(strcmp(a, root->data) == 0)
            root->num++;
        else if(strcmp(a, root->data)<0)
            root->lchild = Creat(root->lchild);
        else
            root->rchild = Creat(root->rchild);
    }
    return root;
}
void Inorder(bittree *root){
    if(root){
        Inorder(root->lchild);
        printf("%s %.2lf%%\n", root->data,(1.0*root->num*100)/n);
                    //Note that the percent sign in printf needs to be escaped by%%
        Inorder(root->rchild);
    }
}
int main(){
    bittree *root =NULL;
    cin>>n;
    getchar();       //Swallow a line break
    for(int k=0; k<n; k++){
        gets(a);              //Get() ends input with Enter (space does not end), accepts spaces, and discards the last carriage return!
        int len = strlen(a);
        for(int i=0; i<len; i++)
            a[i] = tolower(a[i]);      //Functions that convert uppercase letters to lowercase letters
        root = Creat(root);
    }
    Inorder(root);
    return 0;
}


Posted on Sat, 09 May 2020 09:37:04 -0700 by shazly