不过一笑

Well life is tough,make a good laugh

  C++博客 :: 首页 :: 联系 :: 聚合  :: 管理
  8 Posts :: 0 Stories :: 1 Comments :: 0 Trackbacks

公告

This guy's no expert,he's just to build a solid foundation,that may turn out to be useful in the future

常用链接

留言簿

我参与的团队

搜索

  •  

最新评论

阅读排行榜

评论排行榜

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 }


posted on 2010-10-06 11:29 雨过有声 阅读(310) 评论(0)  编辑 收藏 引用

只有注册用户登录后才能发表评论。
【推荐】超50万行VC++源码: 大型组态工控、电力仿真CAD与GIS源码库
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理