数据结构实验报告四——哈希表查找名字（字符串）.doc
文本预览下载声明
数据结构实验报告四——哈希表查找名字（字符串）
实验题目：哈希表查找名字（字符串）
实验目标：
输入一组名字（至少50个），将其保存并利用哈希表查找。输出哈希查找冲突次数，哈希表负载因子、查找命中率。
数据结构：
哈希表和数组（二维）。二维数组用于静态顺序存储名字（字符串），哈希表采用开放定址法，用于存储名字（字符串）对应的关键字并实现对名字（字符串）的查找。
需要的操作有：
1.关键字求取（主函数中两次出现，未单独编为函数）
关键字key=abs（字符串首位ASCII码值-第二位ASCII码值+第（[n2]+1）位ASCII码值-最后一位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;iLENGTH;i++)
Hashtable[i]=-1;
}
5.向哈希表中插入关键字（InsertHash）
void InsertHash(int key,int Hashtable[])
{
int add;
add=Hash(key);
if(Hashtable[add]==-1)
Hashtable[add]=key;
else
{
add=Collision(key,Hashtable);
Hashtable[add]=key;
}
}
6.查找关键字在哈希表中的存储位置（SearchHash）
int SearchHash(int key,int Hashtable[])
{
int add;
add=Hash(key);
if(Hashtable[add]==key)
return add;
while(Hashtable[add]!=keyHashtable[add]!=-1)
add=Collision(key,Hashtable);
return add;
}
7.输出哈希表（PrintHash）（帮助调试用）
void PrintHash(int Hashtable[])
{
int i;
for(i=0;iLENGTH;i++)
if(Hashtable[i]!=-1)
printf(%3d:%d\n,i+1,Hashtable[i]);
}
8.求字符串长度（strlen）（函数库string.h包含）以及求整数的绝对值（abs）（函数库math.h包含）
算法设计：
1建立长度为LENGTH的哈希表Hash（LENGTH具体值由宏定义决定）。
2输入要插入的字符串总数num（num小于等于LENGTH），再输入num个字符串，将这num个字符串的关键值key计算出来后插入哈希表中。
3输出哈希表（帮助调试用，并非实验目的）。
4依次查找这num个字符串对应的关键字在哈希表中位置，并统计冲突次数，记为count。根据公式计算负载因子和命中率（负载因子=表中填入的记录数/哈希表的长度，命中率=元素个数/查找次数）。输出元素个数、冲突次数、查找次数、负载因子、命中率。
源程序（将LENGTH定义为60，实际调试中定义为60和100各一次）：
#includestdio.h
#includestdlib.h
#includemath.h
#includestring.h
#define LENGTH 60 /*实际调试中定义为60和100各一次*/
int Hash(int key);
int Collision(int key,int Hashtable[]);
void InitHash(int Hashtable[]);
void InsertHash(int key,int Hashtable[]);
int SearchHash(int key,int Hashtable[]);
显示全部