数据结构实验之查找三:树的种类统计 (排序树)
程序员文章站
2022-03-24 16:07:14
...
C - 数据结构实验之查找三:树的种类统计
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 <bits/stdc++.h>
using namespace std;
int n, flag;
struct node {
node *l, *r;
string name;
int data;
};
string s;
void toLower() {
int len = s.size();
for (int i = 0; i < len; i++) {
if (s[i] <= 'Z' && s[i] >= 'A') s[i] += 32;
}
}
node *creat(node *root) {
if (!root) {
root = new node;
root->data = 1;
root->name = s;
root->l = NULL;
root->r = NULL;
return root;
}
if (root->name > s)
root->l = creat(root->l);
else if (root->name == s)
root->data++;
else
root->r = creat(root->r);
return root;
}
void solve(node *root) {
if (root) {
solve(root->l);
double ans = root->data;
ans /= n;
ans *= 100;
cout << root->name;
printf(" %.2f%\n", ans);
solve(root->r);
}
}
int main() {
int m, i, k;
cin >> n;
getchar();
node *root;
root = new node;
root = NULL;
for (i = 0; i < n; i++) {
getline(cin, s);
toLower();
root = creat(root);
}
solve(root);
return 0;
}
上一篇: php编写时怎么预览