计算每个字符串出现的频率POJ2418

题目描述

给出大量的字符串，每个字符串的字符数不超过30，字符串可能有重复，请统计每个字符串出现的频率(保留到小数点后第四位），并按字典序打印结果。

分析

字符串数量太多，如果按照定义一个数组然后逐个统计的思路，查找的时间复杂度很高o(n)。根据二叉搜索树的特点，如果把所有字符串构造成一个二叉搜索树，那么按中序遍历出来的结果就是字典序，查找的时间复杂度就减为o(logn)。

这里主要涉及二叉搜索树的两个功能：

1. 插入操作（把字符串按二叉搜索树的规则插入），这里可以利用递归实现：

void insert(struct TreeNode **root, char *s)
{
    if(*root==NULL){
        //树为空
        struct TreeNode *p=(struct TreeNode *)malloc(sizeof(struct TreeNode));
        p->left=p->right=NULL;
        strcpy(p->str,s);
        p->count=1;
        *root=p;
    }
    if(strcmp(s,(*root)->str)==0)
        //两字符串如果相等，计数+1
        (*root)->count++;
        return;
    else if(strcmp(s,(*root)->str)<0)//如果字典序小于根节点,插入左子树,否则插入右子树
        insert(&((*root)->left),s);
    else
        insert(&((*root)->right),s);
}
<!--0-->

1. 查找-中序遍历

   void inorder(struct TreeNode *root)
   {
       if(root==NULL)
           return;
       else{
           inorder(root->left);
           printf("%s %.4f\n",root->str,100*(double)(root->count)/(double)(sum));
           inorder(root->right);
       }
   }        
   

代码

#include<stdio.h>
#include<stdlib.h>
#include<string.h>
struct TreeNode{
    char str[31];
    struct TreeNode *left;
    struct TreeNode *right;
    int count;
};

int sum=0;

void insert(struct TreeNode **root,char *s)
{
    if((*root)==NULL){
        struct TreeNode *p=(struct TreeNode *)malloc(sizeof(struct TreeNode));
        strcpy(p->str,s);
        p->left=p->right=NULL;
        p->count=1;
        *root=p;
    }
    if(strcmp(s,(*root)->str)==0)
        (*root)->count++;
        return;
    else if(strcmp(s,(*root)->str)<0)
        insert(&((*root)->left),s);
    else
        insert(&((*root)->right),s);
}

void inorder(struct TreeNode *root)
{
    if(*root==NULL)
        return;
    inorder(root->left);
    printf("%s %.4f\n",root->str,100*(double)(root->count)/(double)sum);
    inorder(root->right);
}

int main()
{
    char input[31];
    struct TreeNode *root;
    while(gets(input)!=NULL){
        insert(&root,input);
        sum++;
    }
    if(sum!=0)
        inorder(root);
    return 0;
}