最接近神的男人（哈希表的使用） - linshijin的博客

作者在 2010-12-30 00:17:58 发布以下内容

　　女神雅典娜的转世---沙织率领一班青铜圣斗士来到希腊圣域与教皇决战，可是不幸被黄金之箭射中，一定要在十二小时内突破十二宫并找出教皇才能救回沙织一命。于是青铜圣斗士星矢、瞬、冰河、紫龙决定冒死突破十二宫。现在时间只剩下5个小时，而星矢一行人却遇到了号称最接近神的处女座沙加。
　　此时的沙加正在为过英语六级而拼命背单词，看见星矢等人，立马两眼放光。沙加让他们留下一个人帮忙统计下他笔记本里不同的单词数，否则绝不放行。星矢等人顿时傻了眼，他们中英语最好的瞬也只认得26个字母。正当他们一筹莫展的时候，凤凰座一辉出现了。一辉曾在“力羊峰矿影域”进修，有比较高的英语水平。
　　现在请你扮演一辉来帮助星矢等人解决这个问题。
Input
　　第一行为一个正整数N，0 < N <= 100,000，接下来的N行是N个由小写字母组成的单词，每个单词长度不超过10。
Output
　　输出笔记本中不同的单词数M。
Sample Input
9
the
quick
brown
fox
jumps
over
the
lazy
dog
Sample Output
8
设计的好的哈希表可以在O(1)的时间内实现查找，删除和插入等操作；
用哈希表实现不同单词的统计：当在哈希表中查找该单词，如果不在哈希表中，
则是新单词，计数加一，并把它插入哈希表；否则，单词已存在，不再进行统计；

源程序：

#include <iostream>
using namespace std;
struct Node{
       char s[11];
       struct Node *next;
};
Node node[317915];
int main()
{
    int n,i,k,sum,index,c;
    char tmp[11];
    Node *pnode;
    scanf("%d",&n);
    c=0;
    for(i=1;i<=n;i++)
    {
      scanf("%s",tmp);
      sum=k=0;
      while(tmp[k]!='\0')
      {
        sum=sum*7+tmp[k];
        k++;
      }
      index=sum%317915;
      if(strcmp(node[index].s,"")==0)
      {
        strcpy(node[index].s,tmp);
        c++;
      }
      else
      {
        if(strcmp(node[index].s,tmp)!=0)
        {
          pnode=node[index].next;
          while(pnode!=NULL)
          {
            if(strcmp(pnode->s,tmp)==0)
              break;
            pnode=pnode->next;
          }
          if(pnode==NULL)
          {
            c++;
            pnode=new Node;
            strcpy(pnode->s,tmp);
            pnode->next=node[index].next;
            node[index].next=pnode;
          }
        }
      }
    }

    printf("%d\n",c);
    return 0;
}