回复 16楼 BlueGuy
最傻的方法应该就是读的时候跟前边所有的比，如果有了就给那个计数加1。如果没有就续在末尾。
最后只要按顺序输出字串和出现的次数就行了。
这方法应该行吧~ 不过除了最傻的方法，别的我老不知道用什么。也不是没有其它思路，只是不知道怎么改进能进的多一点~

回复 31楼 pangding
最优的方法肯定就是构造二叉树，毫无疑问.

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

#define N 10010
#define M 10007
struct hashtabel
{
   
    char str[200] ;
    int num;
}a[N], b[N];

int hash(char *s)

{

    int h = 0, a = 127;
   
    for (; *s ; s++)
        
        h = (a*h + *s) % M;
   
    return h;
   
}

int getnum(char *s)
{
    int x;
   
    x = hash(s);
   
    while (strcmp(a[x].str, "") && strcmp(a[x].str, s)) // 该位置有值且值不匹配串
    {
        
        x = (x+1) % M;
        if (!(strcmp(a[x].str, "")))                    // 找一个没有值的位置
        {
            strcpy(a[x].str, s);
            return x;
        }
    }
    return x;
}

int main(void)
{
    char t[200];
    int i, j, n, total;
   
    for (i = 0; i < N; i++)
    {
        strcpy(a[i].str, "");
        a[i].num = 0;
    }
   
    scanf("%d\n", &n);
    for (i = 0, j = 0;  i < n; i++)
    {
        
        gets(t);
        total = getnum(t);
        
        if (a[total].num == 0)
        {
            strcpy(b[j].str, t);
            b[j].num = total;
            j++;
        }
        a[total].num++;
    }
   
    for (i = 0; i < j; i++)
        printf("%s %d\n", b[i].str, a[b[i].num].num);
   
    return 0;
}

霍纳算法是直接最优线性算法。 基于如下所示的小括号结合法
.....
霍纳算法的应用

引理：......  (mod (解释：取余)函数的算术性质)

在7位ASCII码中， 一个单词可以看作是128进制的数字。对于 'BlueGuy ' 这样的单词所表示的数对计算机来说太大。 无法用普通的算术函数来表达。要计算出字符串的 取模哈希函数。

可以将键分块转换。我们可以利用 mod (解释：取余)函数的算术性质并使用霍纳算法来完成。

 

int hash(char *v, int M)

{

     int h = 0, a = 127;

     for (; *v ; v++)

         h = (a*h + *v) % M;

     return h;

}

 

这个算法有意思吧  简单强大吧

有没有个大规模的数据，来测试下性能？

<b>没有  不过听说 哈希很强大  呵呵</b>

[ 本帖最后由 BlueGuy 于 2009-8-25 13:14 编辑 ]

回复 37楼 BlueGuy
我开始也想到用哈希来优化了，不过不太会弄。以前没听过你说的那个算法，正好学学~

回复 38楼 pangding
哦对，我当时想用哈希的时候，看到SW说特殊数据的问题。我当时想要是用哈希表，肯定能找到一组特殊数据，让很多字串键值相同。这样不是会引起效率骤减？还是说不用考虑这种情况？

回复 39楼 pangding
任何算法都有适用的范围吧。