Hdoj1004解题报告

题目描述：对输入的多个字符串进行统计，看哪个字符串出现的次数最多？

输入：第一行N，表示一共有N个字符串（0

输出：一行，出现次数最多的字符串。

分析：这个题目应该是一个入门级的题目，我一共想了三种方法来做这个题目。

1：用最常规的方法，开辟一个二维数组存放字符串，每输入一个字符串，就先对这个二维数组进行一次查找，如果没有则添加到数组中，如果有则对应个数加1。

2.利用散列表来做，我想对每个字符串的所有字符进行求和，然后对MAX求余，（MAX是不同字符串的最大数目）。根据得到的结果对相对应数组那个位置加1处理。对于散列冲突处理，如果出现冲突就向后一个一个移动位置，直到找到空位为止。最后再进行一次查找。即可以完成任务。

3.用二叉排序树，这个题目我个人感觉没有什么优势。我主要是利用字符串作为关键字进行排序。最后也是全部遍历，找到最大的值。

方法一代码我没有写，网上很多都是这种方法，所以我这边就不贴了。

方法二的代码：

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

#define MAX 1000

char balloon[MAX][15];
int Snum[MAX];


int count(char *str);
int Hash_insert(char *str,int sum);


int main()
{
    int i,max,max_num;
    char color[15];
    int N=0;
    while(scanf("%d",&N)!=EOF){
        if(N==0) break;
        memset(balloon,'\0',sizeof(balloon));
        memset(Snum,'\0',sizeof(Snum));
        for(i=0;i<N;i++){
            scanf("%s",color);
            count(color);
        }
        max=Snum[0];
        for(i=0;i<MAX;i++) {
            if(max<Snum[i]){
                max_num=i;
                max=Snum[i];
            }
        }
    printf("%s\n",balloon[max_num]);
    }
    return 0;
}

int count(char *str)
{
    int len =0;
    int i;
    int sum=0;
    len=strlen(str);
    for(i=0;i<len;i++){
        sum+=str[i];
    }
    sum=sum%MAX;
    sum=Hash_insert(str,sum);
    Snum[sum]++;
}
int Hash_insert(char *str,int sum)
{
    if(balloon[sum][0]){
        if( strcmp(str,balloon[sum]) ){
            sum++;
            Hash_insert(str,sum);
        }
    }
    else{
        strcpy(balloon[sum],str);
    }
   return sum;
}

方法三的代码：

#include <stdio.h>
#include <string.h>
#include <malloc.h>
#define MAX 1000
typedef struct node
    {char key[15];
     int num;
     struct node *lchild,*rchild;
    }Bitnode;

Bitnode *Node[MAX];
int Count;

Bitnode *insert_tree(Bitnode *t,Bitnode *s)
{
    Bitnode *p,*f;
    f=p=t;
    while(p!=NULL){
        if(strcmp(s->key,p->key)==0) {
            free(s);
            (p->num)++;
            return t;
        }
        if(strcmp(s->key,p->key)<0) p=p->lchild;
        else p=p->rchild;
    }
    if(t==NULL) {
        Node[Count]=s;
        Count++;
        return s;
     }
    if(strcmp(s->key,f->key)>0) f->rchild=s;
    else f->lchild=s;
    Node[Count]=s;
    Count++;
    return t;
}

int main()
{
    int i,j,k;
    int N;
    int max,max_num;
    Bitnode *color=NULL,*top=NULL;
    while ( (scanf("%d",&N)!=EOF) && N){
        Count=0;
        top=NULL;
        for(i=0;i<N;i++){
            color=(Bitnode *)malloc(sizeof(Bitnode));
            scanf("%s",color->key);
            color->lchild=NULL;
            color->rchild=NULL;
            color->num=0;
            top=insert_tree(top,color);
        }
        max=Node[0]->num;
        max_num=0;
        for(i=1;i<Count;i++){
            if(max<Node[i]->num){
                max=Node[i]->num;
                max_num=i;
            }
        }
        printf("%s\n",Node[max_num]->key);
        for(i=0;i<Count;i++){
            free(Node[i]);
        }
    }
}

对于这两个程序都是可以AC的。但是内存使用上还是有点大的。由于本人水平有限，欢迎各位朋友提出宝贵意见。

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

0

上一篇：没有了

下一篇：２０１２百度之星资格赛（Ａ－Ｃ）