学步园

题意：输入N（0<=N<=1,000,000 ）个长度为M（M<=30 ）的字符串，字典序输出每种字符串出现个数。

分析：这里采用两种方法，一种是qsort，还有一种BST。

C++源码：

qsort:

#include <stdio.h><br /> #include <string.h><br /> #include <stdlib.h></p> <p>const int M = 1000000;<br /> const int N = 36;<br /> char s[M+1][N];<br /> int comp(const void *a, const void *b){<br /> return strcmp((char*)a,(char*)b);<br /> }<br /> int main()<br /> {<br /> int i,j;<br /> char c;<br /> i=j=0;<br /> while((c=getchar())!=EOF){<br /> if(c!='/n')<br /> s[i][j++]=c;<br /> else{<br /> s[i][j]='/0';<br /> i++;<br /> j=0;<br /> }</p> <p> }<br /> qsort(s,i,sizeof(s[0]),comp);<br /> if(i>1){<br /> int count=1;<br /> char tmp[N];<br /> strcpy(tmp,s[0]);<br /> for(j=1;j<i;j++){<br /> if(!strcmp(s[j],tmp)){<br /> count++;<br /> }else{<br /> printf("%s %.4f/n",tmp,count*100.0/i);<br /> strcpy(tmp,s[j]);<br /> count=1;<br /> }<br /> }<br /> printf("%s %.4f/n", tmp,count*100.0/i);<br /> }<br /> return 0;<br /> }<br />

BST:

#include <cstdio><br /> #include <cstring></p> <p>const int M = 32;<br /> struct node{<br /> node(char *s):t(1),left(NULL),right(NULL){<br /> strcpy(str,s);<br /> }<br /> char str[M];<br /> int t;<br /> node *left, *right;<br /> };<br /> node* insert(node* r, char *s){<br /> if(r==NULL){<br /> r = new node(s);<br /> }else{<br /> int ans = strcmp(r->str,s);<br /> if(ans == 0)<br /> r->t++;<br /> else if(ans==1)<br /> r->left = insert(r->left,s);<br /> else<br /> r->right = insert(r->right,s);<br /> }<br /> return r;<br /> }<br /> void inorder(node* r,int n){<br /> if(r!=NULL){<br /> inorder(r->left,n);<br /> printf("%s %.4f/n", r->str, r->t*100.0/n);<br /> inorder(r->right,n);<br /> }<br /> }<br /> int main()<br /> {<br /> int num=0;<br /> char s[M];<br /> node* root=NULL;<br /> while(gets(s)!=NULL){<br /> root=insert(root,s);<br /> num++;<br /> }<br /> inorder(root,num);<br /> return 0;<br /> }<br />