解题思路:(注意此题我没有特意处理大小写字符问题都能AC,应该是测试用例没有特意测试大小写)
解法一、将输入数据存成二叉排序树,再中序遍历输出即可
#include <stdio.h> #include <malloc.h> #include <string.h> typedef char ElementType[35]; typedef struct TNode { ElementType name; int cnt; struct TNode *Left,*Right; }*Tree; int n; Tree BuildBiSTree(Tree T,ElementType name) { if(!T) { T=(Tree)malloc(sizeof(struct TNode)); strcpy(T->name,name); T->cnt=1; T->Left=NULL; T->Right=NULL; } else if(strcmp(name,T->name)<0) { T->Left=BuildBiSTree(T->Left,name); } else if(strcmp(name,T->name)>0) { T->Right=BuildBiSTree(T->Right,name); } else { T->cnt++; } return T; } void Trav(Tree T) { if(T) { Trav(T->Left); printf("%s %.4lf%%\n",T->name,T->cnt*1.0*100/n); Trav(T->Right); } } int main() { scanf("%d",&n); int i; Tree T=NULL; getchar(); for(i=0;i<n;i++) { ElementType name; gets(name); T=BuildBiSTree(T,name); } Trav(T); return 0; }
解法二、使用快速排序(qsort函数)
//按字母顺序排序后再统计重复个数 #include <stdio.h> #include <string.h> typedef struct { char s[31]; int cnt; } T; int cmp(char *s,char *c) { return strcmp(s,c); } int main() { int n,cnt=0; scanf("%d",&n); getchar(); T f[n],f1[n]; int i,j,k=0; for(i=0; i<n; i++) { gets(f[i].s); } qsort(f,n,sizeof(T),cmp); for(i=1; i<n; i++) { if(!cmp(f[i].s,f[i-1].s)) cnt++; else { strcpy(f1[k].s,f[i-1].s); f1[k].cnt=cnt+1; k++; cnt=0; } } strcpy(f1[k].s,f[i-1].s); f1[k].cnt=cnt+1; k++; for(i=0; i<k; i++) { printf("%s %.4lf%%\n",f1[i].s,f1[i].cnt*1.0*100/n); } return 0; }