POJ 2418 二叉排序树

这一题题意就是给出很多字符串 要求出每个字符串出现的频率
STL写起来很简单 但是比较慢 这里看到一个比较好的思路就是根据字符串的排序建树 最后中序遍历计数 Node* createNode(Node *root,char cc[])
{
    if(root==NULL)
    {
        root=(Node *)malloc(sizeof(Node));
        root->lchild=NULL;
        root->rchild=NULL;
        root->times=1;
        strcpy(root->date,cc);
        return root;
    }
    if(strcmp(root->date,cc)==0)
    {
        root->times++;
    }
    else if(strcmp(root->date,cc)<0)
    {
        root->rchild=createNode(root->rchild,cc);
    }
    else if(strcmp(root->date,cc)>0)
    {
        root->lchild=createNode(root->lchild,cc);
    }

    return root;
}
再贴一个STL版本的 慢了一倍左右

#include<iostream>
#include<map>
#include<string>
using namespace std; string str;
map<string,int> mp;
map<string,int>::iterator iter,ed;
int main()
{
    int n=0;
    while(getline(cin,str))
    {
        mp[str]++;
        ++n;
    }
    iter = mp.begin();
    ed = mp.end();
   
    while(iter!=ed)
    {   
        cout<<iter->first;
        printf(" %.4lf\n",100.000000*(iter->second)/(double)n);
        ++iter;
    }
   
    return 0;
}

是卢亮写的 呵呵



posted on 2008-08-16 20:45 Victordu 阅读(859) 评论(2)  编辑 收藏 引用

评论

# re: POJ 2418 二叉排序树 2008-08-16 22:51 foxtail

求字符频率为什么要排序啊,这个主要是能快速查找,然后统计即可。
哈希表 还有红黑树符合要求的吧  回复  更多评论   

# re: POJ 2418 二叉排序树[未登录] 2008-08-18 10:20 Victordu

@foxtail
多谢指教
我说的有点问题 也不是排序 就是根据字符串相对大小关系来建一棵树 这样可以吧^ ^  回复  更多评论   


只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理


导航

<2008年8月>
272829303112
3456789
10111213141516
17181920212223
24252627282930
31123456

统计

常用链接

留言簿(5)

随笔档案(46)

搜索

积分与排名

最新评论

阅读排行榜

评论排行榜