国际大学生程序设计竞赛例题_5.1昵称

1,题意:
输入n(n<=100000)个昵称,不相同的不超过t(t<5000)个,统计每个昵称出现的次数.
每个昵称的长度L<100
2,解决:
(1)hash表,把字符串当作26进制的整数.
解决hash函数冲突,使用开放寻址法.
复杂度:O(L*n)
实现代码:

#include <iostream>
using namespace std;

const int hashCnt=6000;
const int maxN=100000;

struct node
{
    char* name;
    int count;
};

//返回hash值
int hashFun(char* str)
{
    int index=0;
    //注意这里索引值的求取
    for(char* p=str;*p&&index<hashCnt;p++)
    {
        index+=index*26+(*p)-96; //全部转化为小写
    }
    return index%hashCnt;

}

//这里配合qsort的使用
int cmp(const void* a,const void* b)
{
    node* m=(node*)a;
    node* n=(node*)b;
    return strcmp(m->name,n->name);
}


int cnt; //测试数目
int n;//昵称总数
node hashTable[hashCnt];

int main()
{
    freopen("5.1.in","r",stdin);
    char str1[200],str2[200];
    int index;
    int nickNum;//不同昵称的个数
    cin>>cnt;
    while(cnt--)
    {
        cin>>n;
        memset(hashTable,0,sizeof(hashTable));
        while(n--)
        {
            cin>>str1;
            strcpy( str2, strlwr(str1) );
            index=hashFun(str2);
            //开放寻址法
            while( hashTable[index].name!=0 && strcmp(hashTable[index].name,str2)!=0)
            {
                index++;
                if(index>=hashCnt) index=0;
            }
            if(hashTable[index].name==0)
            {
                hashTable[index].name=new char[strlen(str2)+1];
                strcpy(hashTable[index].name,str2);
                hashTable[index].count=1;
            }
            else
                hashTable[index].count++;
        }
        nickNum=0;
        //统计不同昵称的个数
        for(int i=0;i<hashCnt;i++)
            if(hashTable[i].count!=0)
                hashTable[nickNum++]=hashTable[i];
        qsort(hashTable,nickNum,sizeof(node),cmp);
        for(int i=0;i<nickNum;i++)
            cout<<hashTable[i].name<<" "<<hashTable[i].count<<endl;
        cout<<endl;
    }
    return 0;
}

(2)利用map实现,复杂度O(L*TlogT)
实现代码:

#include <iostream>
#include <map>

using namespace std;


int cnt; //测试数目
int n;//昵称总数

int main()
{
    freopen("5.1.in","r",stdin);
    freopen("main.txt","w",stdout);
    map<string,int> nickNum;
    string name;
    cin>>cnt;
    while(cnt--)
    {
        cin>>n;
        nickNum.clear();
        while(n--)
        {
            cin>>name;
            for(unsigned i=0;i<name.size();i++)
                name[i]|=32;
            nickNum[name]++;
        }
        map<string,int>::iterator ite;
        for(ite=nickNum.begin();ite!=nickNum.end();ite++)
            cout<<ite->first<<" "<<ite->second<<endl;
        cout<<endl;
    }
    return 0;
}