Description

隨著衛(wèi)星成像技術的應用，自然資源研究機構可以識別每一個棵樹的種類。請編寫程序幫助研究人員統(tǒng)計每種樹的數(shù)量，計算每種樹占總數(shù)的百分比。
Input

輸入一組測試數(shù)據。數(shù)據的第1行給出一個正整數(shù)N (n <= 100000)，N表示樹的數(shù)量；隨后N行，每行給出衛(wèi)星觀測到的一棵樹的種類名稱，樹的名稱是一個不超過20個字符的字符串，字符串由英文字母和空格組成，不區(qū)分大小寫。
Output

按字典序輸出各種樹的種類名稱和它占的百分比，中間以空格間隔，小數(shù)點后保留兩位小數(shù)。
Sample
Input

2 This is an Appletree this is an appletree

Output

this is an appletree 100.00%

Hint

哈希樹
字典樹

#include<bits/stdc++.h>using namespace std;typedef struct node {char name[30];int cnt;struct node *l, *r; } tree;int n; tree *create(tree *&root, char str[]) {if(root == NULL){root = new tree;strcpy(root->name, str);root->cnt = 1;root->l = NULL;root->r = NULL;}else{int temp = strcmp(root->name, str);if(temp > 0)create(root->l, str);else if(temp < 0)create(root->r, str);else root->cnt++;}return root; }void midorder(tree *root) {if(root){midorder(root->l);printf("%s %.2lf%%\n", root->name, 100.0 * root->cnt / n);midorder(root->r);} } int main() {//ios::sync_with_stdio(0);不能加這條語句，加了不給過int t;char s[30];tree *root;root = NULL;cin >> t;n = t;getchar();while(t--){gets(s);int len = strlen(s);for(int i = 0; i < len; i++){if(s[i] >= 'A' && s[i] <= 'Z')s[i] += 'a' - 'A';}root = create(root, s);}midorder(root);return 0; }

總結

以上是生活随笔為你收集整理的C - 数据结构实验之查找三：树的种类统计(哈希树)的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。