p2418.cpp

大概POJ上50道比较难的题的代码

#include <iostream>
#include <cstring>
using namespace std;
struct tree{
    char name[50];
    int s;
    tree* lc;
    tree* rc;
};
tree* T = NULL;
tree* ins(tree* p,char s[]){
    int res;
    while(1){
        res = strcmp(p->name,s);
        if(res == 0){ ++(p->s); return p; }
        if(res > 0){ 
            if(p->lc == NULL){
                p->lc = new tree();
                p = p->lc;
                break;
            }
            p = p->lc;
        }
        if(res < 0){ 
            if(p->rc == NULL){
                p->rc = new tree();
                p = p->rc;
                break;
            }
            p = p->rc;
        }
    }
    strcpy(p->name,s);
    p->s = 1;
    p->lc = p->rc = NULL;
    return p;
}
void show(tree* p,int n){
    if(p->lc) show(p->lc,n);
    printf("%s %.4lf\n",p->name,100.0 * (p->s) / n);
    if(p->rc) show(p->rc,n);
}
int main(){
    char s[50];
    int n(1);
    T = new tree();
    gets(T->name);
    T->s = 1;
    T->lc = T->rc = NULL;
    while(gets(s)){
        ins(T,s);
        ++n;
    }
    show(T,n);
}