Analysis:Given a list of species of trees,we are required to print out a list containing the names of species together with the percentage of each,within the whole.
The idea of this is quite simple.Input all the species and put them in a set,while counting how many times each element appears.However,to reach this goal within certain time is not that easy a task.And this is when the data structure
Binary Search Tree functions well.We can simply maintain a
Binary Search Tree here,and output the result when the insert process is finished.See the code below for details.
Code:
1 #include<cstdio>
2 #include<string>
3 #include<iostream>
4 #include<cstring>
5 using namespace std;
6 double sum;
7 struct tree
8 {
9 char name[51];
10 double num;
11 tree* lchild;
12 tree* rchild;
13 }tmp,*Root,pool[10000],*pp;
14 tree* Insert_AVL(tree* Root,char *str)
15 {
16 if(Root==NULL)
17 {
18 strcpy(pp->name,str);pp->num=1;
19 pp->lchild=NULL;pp->rchild=NULL;
20 Root=pp;pp++;
21 }
22 else
23 {
24 int judge=strcmp(str,Root->name);
25 if(judge==0) Root->num++;
26 else if(judge<0)
27 Root->lchild=Insert_AVL(Root->lchild,str);
28 else
29 Root->rchild=Insert_AVL(Root->rchild,str);
30 }
31 return Root;
32 }
33 void Inorder(tree* Root)
34 {
35 if(Root==NULL) return;
36 if(Root->lchild) Inorder(Root->lchild);
37 if(Root)
38 printf("%s %.4lf\n",Root->name,((Root->num)/sum)*100.0);
39 if(Root->rchild) Inorder(Root->rchild);
40 }
41 int main()
42 {
43 Root=NULL;pp=pool;sum=0;
44 char str[51];
45 while(gets(str)!=NULL)
46 {
47 if(str[0]!='\0')
48 {
49 Root=Insert_AVL(Root,str);sum++;
50 }
51 else
52 {
53 Inorder(Root);putchar('\n');
54 sum=0;pp=pool;Root=NULL;
55 }
56 }
57 Inorder(Root);
58 return 0;
59 }