Chinaunix首页 | 论坛 | 博客
  • 博客访问: 573500
  • 博文数量: 50
  • 博客积分: 571
  • 博客等级: 中士
  • 技术积分: 1162
  • 用 户 组: 普通用户
  • 注册时间: 2012-01-20 14:01
个人简介

希望成为一个有思想,有信仰的程序设计师。

文章分类

全部博文(50)

文章存档

2016年(2)

2015年(2)

2014年(13)

2013年(10)

2012年(23)

分类: C/C++

2012-05-26 19:00:26

题目描述:对输入的多个字符串进行统计,看哪个字符串出现的次数最多?
输入:第一行N,表示一共有N个字符串(0
输出:一行,出现次数最多的字符串。

分析:这个题目应该是一个入门级的题目,我一共想了三种方法来做这个题目。
1:用最常规的方法,开辟一个二维数组存放字符串,每输入一个字符串,就先对这个二维数组进行一次查找,如果没有则添加到数组中,如果有则对应个数加1。
2.利用散列表来做,我想对每个字符串的所有字符进行求和,然后对MAX求余,(MAX是不同字符串的最大数目)。根据得到的结果对相对应数组那个位置加1处理。对于散列冲突处理,如果出现冲突就向后一个一个移动位置,直到找到空位为止。最后再进行一次查找。即可以完成任务。
3.用二叉排序树,这个题目我个人感觉没有什么优势。我主要是利用字符串作为关键字进行排序。最后也是全部遍历,找到最大的值。
方法一代码我没有写,网上很多都是这种方法,所以我这边就不贴了。
方法二的代码:

点击(此处)折叠或打开

  1. #include <stdio.h>
  2. #include <string.h>

  3. #define MAX 1000

  4. char balloon[MAX][15];
  5. int Snum[MAX];


  6. int count(char *str);
  7. int Hash_insert(char *str,int sum);


  8. int main()
  9. {
  10.     int i,max,max_num;
  11.     char color[15];
  12.     int N=0;
  13.     while(scanf("%d",&N)!=EOF){
  14.         if(N==0) break;
  15.         memset(balloon,'\0',sizeof(balloon));
  16.         memset(Snum,'\0',sizeof(Snum));
  17.         for(i=0;i<N;i++){
  18.             scanf("%s",color);
  19.             count(color);
  20.         }
  21.         max=Snum[0];
  22.         for(i=0;i<MAX;i++) {
  23.             if(max<Snum[i]){
  24.                 max_num=i;
  25.                 max=Snum[i];
  26.             }
  27.         }
  28.     printf("%s\n",balloon[max_num]);
  29.     }
  30.     return 0;
  31. }

  32. int count(char *str)
  33. {
  34.     int len =0;
  35.     int i;
  36.     int sum=0;
  37.     len=strlen(str);
  38.     for(i=0;i<len;i++){
  39.         sum+=str[i];
  40.     }
  41.     sum=sum%MAX;
  42.     sum=Hash_insert(str,sum);
  43.     Snum[sum]++;
  44. }
  45. int Hash_insert(char *str,int sum)
  46. {
  47.     if(balloon[sum][0]){
  48.         if( strcmp(str,balloon[sum]) ){
  49.             sum++;
  50.             Hash_insert(str,sum);
  51.         }
  52.     }
  53.     else{
  54.         strcpy(balloon[sum],str);
  55.     }
  56.    return sum;
  57. }
方法三的代码:

点击(此处)折叠或打开

  1. #include <stdio.h>
  2. #include <string.h>
  3. #include <malloc.h>
  4. #define MAX 1000
  5. typedef struct node
  6.     {char key[15];
  7.      int num;
  8.      struct node *lchild,*rchild;
  9.     }Bitnode;

  10. Bitnode *Node[MAX];
  11. int Count;

  12. Bitnode *insert_tree(Bitnode *t,Bitnode *s)
  13. {
  14.     Bitnode *p,*f;
  15.     f=p=t;
  16.     while(p!=NULL){
  17.         if(strcmp(s->key,p->key)==0) {
  18.             free(s);
  19.             (p->num)++;
  20.             return t;
  21.         }
  22.         if(strcmp(s->key,p->key)<0) p=p->lchild;
  23.         else p=p->rchild;
  24.     }
  25.     if(t==NULL) {
  26.         Node[Count]=s;
  27.         Count++;
  28.         return s;
  29.      }
  30.     if(strcmp(s->key,f->key)>0) f->rchild=s;
  31.     else f->lchild=s;
  32.     Node[Count]=s;
  33.     Count++;
  34.     return t;
  35. }

  36. int main()
  37. {
  38.     int i,j,k;
  39.     int N;
  40.     int max,max_num;
  41.     Bitnode *color=NULL,*top=NULL;
  42.     while ( (scanf("%d",&N)!=EOF) && N){
  43.         Count=0;
  44.         top=NULL;
  45.         for(i=0;i<N;i++){
  46.             color=(Bitnode *)malloc(sizeof(Bitnode));
  47.             scanf("%s",color->key);
  48.             color->lchild=NULL;
  49.             color->rchild=NULL;
  50.             color->num=0;
  51.             top=insert_tree(top,color);
  52.         }
  53.         max=Node[0]->num;
  54.         max_num=0;
  55.         for(i=1;i<Count;i++){
  56.             if(max<Node[i]->num){
  57.                 max=Node[i]->num;
  58.                 max_num=i;
  59.             }
  60.         }
  61.         printf("%s\n",Node[max_num]->key);
  62.         for(i=0;i<Count;i++){
  63.             free(Node[i]);
  64.         }
  65.     }
  66. }
对于这两个程序都是可以AC的。但是内存使用上还是有点大的。由于本人水平有限,欢迎各位朋友提出宝贵意见。

阅读(2315) | 评论(0) | 转发(0) |
0

上一篇:没有了

下一篇:2012百度之星资格赛(A-C)

给主人留下些什么吧!~~