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

傷城~ 2022-12-28 04:06 121阅读 0赞

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

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

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

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

Sample  
Input  
2  
This is an Appletree  
this is an appletree  
Output  
this is an appletree 100.00%

#include <stdio.h>
    #include <stdlib.h>
    #include <string.h>
    struct node
    {
        
    	char data[30];
    	int sum;//记录相同树的个数
    	struct node* l, * r;
    };
    char a[30];
    int i, n;
    struct node* creat(struct node* root)//建树
    {
        
    	if (!root)
    	{
        
    		root = (struct node*)malloc(sizeof(struct node));
    		root->sum = 1;//基本数为1
    		strcpy(root->data, a);
    		root->l = root->r = NULL;
    	}
    	else
    	{
        //比较字符的先后顺序,
    		if (strcmp(root->data, a) == 0)//如果相等这种树的数目+1
    			root->sum++;
    		else if (strcmp(root->data, a) > 0)//如果前面的字符要更大一些，就把新的字符信息放在左子树
    			root->l = creat(root->l);
    		else
    			root->r = creat(root->r);//如果前面的字符要更小一些，就把新的字符信息放在右子树
    	}
    	return root;
    }
    void check(struct node* root)
    {
        
    	if (root)
    	{
        
    		check(root->l);//左子树是字符顺序小的
    		printf("%s %.2lf%%\n", root->data, root->sum * 1.0*100/n);//计算这种树所占的百分比并输出
    		check(root->r);
    	}
    }
    int main()
    {
        
    	int len,j;
    	scanf("%d", &n);
    	getchar();//吃掉回车
    	struct node* root = NULL;
    	for(i=0;i<n;i++)
    	{
        
    		gets(a);
    		len = strlen(a);
    		for (j = 0; j < len; j++)//根据输入样例可知Apple和apple是一种树，就要在比较的时候把大写转化为小写
    		{
        
    			if(a[j]>='A'&&a[j]<='Z')
    				a[j]=a[j]+32;
    		}
    		root = creat(root);
    	}
    	check(root);
    }

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ1ODg1MjE5_size_16_color_FFFFFF_t_70]

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ1ODg1MjE5_size_16_color_FFFFFF_t_70]: /images/20221120/ccc23daacc0a4c2ead16b212f4fbb5ce.png