数据结构之树的统计

刺骨的言语ヽ痛彻心扉 2022-06-10 08:37 168阅读 0赞

### 数据结构实验之查找三：树的种类统计 ###

Time Limit: 400MS Memory Limit: 65536KB

[Submit][] [Statistic][]

#### Problem Description ####

随着卫星成像技术的应用，自然资源研究机构可以识别每一个棵树的种类。请编写程序帮助研究人员统计每种树的数量，计算每种树占总数的百分比。

#### Input ####

输入一组测试数据。数据的第1行给出一个正整数N (n <= 100000)，N表示树的数量；随后N行，每行给出卫星观测到的一棵树的种类名称，树的名称是一个不超过20个字符的字符串，字符串由英文字母和空格组成，不区分大小写。

#### Output ####

按字典序输出各种树的种类名称和它占的百分比，中间以空格间隔，小数点后保留两位小数。

#### Example Input ####

2
    This is an Appletree
    this is an appletree

#### Example Output ####

this is an appletree 100.00%

//代码;
    //注意的问题1：数字后面如果要输入字符，记得加getchar();
    //          2:把一个字符串赋给另一个字符串，最好用strcmp函数，如果挨个字符赋值的话。记得要把最后的‘\0’也赋进去
    //          3：如果要输出%，可以这样写%%；
    //再来说说这个题的思路，反正我是没想到这么做。没想到用二叉树解决问题这么简单。应该多方面想想问题，脑洞大一点。
    #include <stdio.h>
    #include <stdlib.h>
    #include <string.h>
    typedef struct BiTNode
    {
        char s[40];
        int data;
        struct BiTNode *lchild,*rchild;
    }BiTNode,*BiTree;
    BiTree Creat(BiTree root,char tree[],int n)
    {
         int i;
    
        if(!root)
        {
            root = (BiTree)malloc(sizeof(BiTNode));
            for(i = 0;i<=n;i++)//赋值，用n把'\0'赋值进去。或者用strcpy函数、
            root->s[i] = tree[i];
            root->lchild=NULL;//记得让左孩子和右孩子为空。否则会运行错误。
            root->rchild=NULL;
            root->data = 1;
        }
        else
        {
            if(strcmp(tree,root->s)==0)
            {
                root->data++;
            }
            else if(strcmp(tree,root->s)>0)
            {
                root->rchild = Creat(root->rchild,tree,n);
            }
            else
                root->lchild = Creat(root->lchild,tree,n);
        }
        return root;
    
    }
    void midprint(BiTree root,int n)
    {
        if(root)
        {
            midprint(root->lchild,n);
            printf("%s %.2lf%%\n",root->s,root->data*1.0/n*100);//注意%输出
            midprint(root->rchild,n);
        }
    }
    int main()
    {
        int n;
        scanf("%d",&n);
        int m = n;
        getchar();
        BiTree root = NULL;
        while(n--)
        {
            int i;
            char tree[40];
          gets(tree);
            int b = strlen(tree);
            for(i = 0;i<=b-1;i++)
            {
                if(tree[i]>='A'&&tree[i]<='Z')
                    tree[i] = tree[i]+ ('a'-'A');
            }
    
    
            root = Creat(root,tree,b);
        }
        midprint(root,m);
        printf("\n");
        return 0;
    }

[Submit]: http://acm.sdut.edu.cn/onlinejudge2/index.php/Home/Contest/contestsubmit/cid/2217/pid/3375.html
[Statistic]: http://acm.sdut.edu.cn/onlinejudge2/index.php/Home/Contest/conteststatus/cid/2217/pid/3375.html