文档库

最新最全的文档下载
当前位置:文档库 > 哈希表实验报告

哈希表实验报告

数据结构实验报告四——哈希表查找名字(字符串)

实验题目:哈希表查找名字(字符串)

实验目标:

输入一组名字(至少50个),将其保存并利用哈希表查找。输出哈希查找冲突次数,哈希表负载因子、查找命中率。

数据结构:

哈希表和数组(二维)。二维数组用于静态顺序存储名字(字符串),哈希表采用开放定址法,用于存储名字(字符串)对应的关键字并实现对名字(字符串)的查找。

需要的操作有:

1.关键字求取(主函数中两次出现,未单独编为函数)

]+1)位ASCII码值-最后一关键字key=abs(字符串首位ASCII码值-第二位ASCII码值+第([n

2

位ASCII码值-倒数第二位ASCII码值)*字符串长度(abs为求整数绝对值的函数)。

2.处理关键字的哈希函数(Hash)

利用平方取中法求关键值key在哈希表中的位置。公式add=(key*key)%1000/LENGTH(add 为key在哈希表中的地址)。

int Hash(int key)

{

return((key*key)/1000%LENGTH);

}

3.处理哈希表中冲突的函数(Collision)

利用线性探测再散列处理冲突,利用全局变量count统计冲突次数。

int Collision(int key,int Hashtable[])

{

int i;

for(i=1;i<=LENGTH;i++)

{

if(Hashtable[(Hash(key)+i)%LENGTH]==-1)

return((Hash(key)+i)%LENGTH);

count++;

}

}

4.哈希表初始化(InitHash)

void InitHash(int Hashtable[])

{

int i;

for(i=0;i

Hashtable[i]=-1;

}

5.向哈希表中插入关键字(InsertHash)

void InsertHash(int key,int Hashtable[])

{

int add;

哈希表实验报告

(共9页)