3375 data structure experiment search 3: tree species statistics

3375 data structure experiment search 3: tree species statistics

Time Limit: 400MS Memory Limit: 65536KB

Problem Description

With the application of satellite imaging technology, natural resource research institutions can identify the type of each tree. Please write a program to help researchers count the number of each tree and calculate the percentage of each tree in the total.

Input

Enter a set of test data. The first line of data gives a positive integer N (N < = 100000), N represents the number of trees; then N lines, each line gives the category name of a tree observed by the satellite. The name of the tree is a string of no more than 20 characters. The string consists of English letters and spaces, regardless of case.

Output

Output all kinds of tree names and their percentages in dictionary order, with spaces in the middle and 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%
#include <bits/stdc++.h>

using namespace std;

struct node
{
    char str[22];
    int cnt;
    struct node *l, *r;
}Tree;
int n;
struct node *Inster(struct node *Head, char *s)
{
    if(!Head)
    {
        Head = new struct node;
        Head->cnt = 1;
        strcpy(Head->str, s);
        Head->l = NULL, Head->r = NULL;
    }
    else
    {
        int cmp = strcmp(Head->str,s);
        if(cmp > 0)
            Head->l = Inster(Head->l, s);
        else if(cmp < 0)
            Head->r = Inster(Head->r, s);
        else
            Head->cnt++;
    }
    return Head;
}
void Mid(struct node *Head)
{
    if(Head)
    {
        Mid(Head->l);
        printf("%s %.2lf%c\n",Head->str,Head->cnt*100.0/n,'%');
        Mid(Head->r);
    }
}

int main()
{
    struct node *Head = NULL;
    char str[22];
    scanf("%d\n",&n);
    for(int j=0; j<n; j++)
    {
        gets(str);
        for(int i=0; str[i]; i++)
        {
            if(str[i] >= 'A' && str[i] <= 'Z')
                str[i] += 32;
        }
        Head = Inster(Head,str);
    }
    Mid(Head);
    return 0;
}



Posted on Sat, 02 May 2020 13:06:09 -0700 by aquarius