一个简单的问题:有一个庞大的字符串数组,然后给你一个单独的字符串,让你从这个数组中查找是否有这个字符串并找到它,你会怎么做?有一个方法最简单,老老 实实从头查到尾,一个一个比较,直到找到为止,我想只要学过程序设计的人都能把这样一个程序作出来,但要是有程序员把这样的程序交给用户,我只能用无语来 评价,或许它真的能工作,但...也只能如此了。最合适的算法自然是使用HashTable(哈希表),先介绍介绍其中的基本知识,所谓Hash,一般是一个整数,通过某种算法,可以把一个字符串"压缩" 成一个整数。当然,无论如何,一个32位整数是无法对应回一个字符串的,但在程序中,两个字符串计算出的Hash值相等的可能非常小,下面看看在MPQ中的Hash算法:以下的函数生成一个长度为0x500(合10进制数:1
1、用数组#include <stdio.h>#define N 4typedef int datatype;typedef struct{ datatype key;}Hretype;int LHashsearch(Hretype HT[N], datatype k){ int addr,i=0; addr = k % N; while(i<N && HT[addr].key != -1 && HT[addr].key != k) { i++; addr = (addr+1)%N; } if(i == N) return -1; //表溢出 else return addr;}int LHinsert(Hretype HT[N], Hret