# POJ 2418 Hardwood Species

This problem can be solved by at least 4 methods:

• Quick Sort
• Binary Search Tree
• Trie and Depth First Search
• Map

Unfortunately, I only implemented the first two methods. Here is the source code:

Use Quick Sort:

 cpp POJ 2418 Hardwood Species (Use Quick Sort) #include #include using namespace std; int n; struct tree{ char key[31]; int times; tree* l,* r; }; tree* makeTree(char c[]){ tree* t=new tree(); t->l=0; t->r=0; t->times=1; strcpy(t->key,c); return t; } void Insert(tree* &t,char c[]){ if(t==0){ t=makeTree(c); return; } tree* tmp=t; tree* p; while(tmp!=0&&strcmp(tmp->key,c)!=0){ p=tmp; if(strcmp(tmp->key,c)<0){ tmp=tmp->r; } else{ tmp=tmp->l; } } if(tmp==0){ tmp=makeTree(c); if(strcmp(p->key,c)<0){ p->r=tmp; } else{ p->l=tmp; } } else{ tmp->times++; } } void InOrder(tree* t){ if(t!=0){ InOrder(t->l); printf("%s %.4f\n",t->key,t->times*100.0/n); InOrder(t->r); } } int main(){ freopen("in.txt","r",stdin); char c[31]; tree* root=0; n=0; while(scanf("%[^\n]",c)!=EOF&&c[0]){ n++; Insert(root,c); getchar(); c[0]=0; } InOrder(root); return 0; }


Use BST

 cpp POJ 2418 Hardwood Species (Use Binary Search Tree)
#include <iostream>
#include <algorithm>
using namespace std;
#define N 1000000
char a[N][31];
int b[N];
int c[N];
double d[N];
bool cmp(int x,int y){
int i;
for(i=0;i<31;i++){
if(a[x][i]!=a[y][i]||a[x][i]==0)
break;
}
return a[x][i]<a[y][i];
}
int main(){
//freopen("in.txt","r",stdin);
int n=0;
int i;
while(scanf("%[^\n]",a[n])!=EOF&&a[n][0]){
b[n]=n;
n++;
getchar();
}
sort(b,b+n,cmp);
for(i=0;i<n;i++)
c[i]=1;
for(i=0;i<n-1;i++){
int j1=b[i],j2=b[i+1];
if(strcmp(a[j1],a[j2])==0){
c[j2]+=c[j1];
c[j1]=0;
}
}
for(i=0;i<n;i++){
if(c[i]>0){
d[i]=100.0*c[i]/n;
}
}
for(i=0;i<n;i++){
int j=b[i];
if(c[j]){
printf("%s %.4f\n",a[j],d[j]);
}
}
return 0;
}


Problems