数据结构实验报告四一一哈希表查找名字(字符串)实验题目：哈希表查找名字(字符串)实验目标：输入一组名字(至少50个)，将其保存并利用哈希表查找。

输出哈希查找冲突次数，哈希表负载因子、查找命中率。

数据结构：哈希表和数组(二维)。

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

需要的操作有：1.关键字求取(主函数中两次出现，未单独编为函数)关键字key=abs (字符串首位ASCII码值-第二位ASCII码值+第([n]+i )位ASCII码值撮后一位ASCII码值-倒数第二位ASCII码值)*字符串长度(abs为求整数绝对值的函数)。

2.处理关键字的哈希函数(Hash)利用平方取中法求关键值key在哈希表中的位置。

公式add=(key*key)%1000/LENGTH(add为key在哈希表中的地址)。

int Hash(i nt 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);coun t++;}}4.哈希表初始化(InitHash)void InitHash(int Hashtable[]){int i;for(i=0;i<LENGTH;i++)Hashtable[i]=-1;}5.向哈希表中插入关键字(InsertHash)void In sertHash(i nt key,i nt 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]!=key&&Hashtable[add]!=-1)add=Collision(key,Hashtable);return add;}7.输出哈希表(PrintHash)(帮助调试用)void PrintHash(int Hashtable[]){int i;for(i=0;i<LENGTH;i++)if(Hashtable[i]!=-1)printf("%3d:%d\n",i+1,Hashtable[i]);}8.求字符串长度(strlen)(函数库<string.h>&含)以及求整数的绝对值(abs)(函数库vmath.h> 包含)算法设计：1建立长度为LENGTH的哈希表Hash ( LENGTH M体值由宏定义决定)。

2输入要插入的字符串总数num ( num小于等于LENGTH，再输入num个字符串，将这num个字符串的关键值key 计算出来后插入哈希表中。

3 输出哈希表(帮助调试用，并非实验目的) 。

4 依次查找这num 个字符串对应的关键字在哈希表中位置，并统计冲突次数，记为count。

根据公式计算负载因子和命中率(负载因子=表中填入的记录数/哈希表的长度，命中率=元素个数/查找次数)。

输出元素个数、冲突次数、查找次数、负载因子、命中率。

源程序(将LENGTH定义为60，实际调试中定义为60和100各一次)：#include<stdio.h>#include<stdlib.h>#include<math.h>#include<string.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[]);void PrintHash(int Hashtable[]);int count=0,num=0;void main(){int i,key,collapsetime,searchtime,Hash[LENGTH];float loadelem,hitprob;char names[LENGTH][20];InitHash(Hash);printf("input the number of names(number<=%d).\n",LENGTH); scanf("%d",&num);printf("input names.\n"); for(i=0;i<num;i++){ scanf("%s",&names[i]);key=(abs((int)names[i][0]-(int)names[i][1]+(int)names[i][strlen(names[i])/2]-(int)names[i][str len(names[i])-2]-(int)names[i][strlen(names[i])-1]))*strlen(names[i]);/*上式为关键字求取，公式：关键字key=abs (字符串首位ASCII码值-第二位ASCII 码值+第([n/2]+1 )位ASCII码值-最后一位ASCII码值-倒数第二位ASCII码值)*字符串长度( abs 为求整数绝对值的函数) 。

*/InsertHash(key,Hash);}count=0;/* 将count 置零，清除插入过程中产生的冲突次数*/PrintHash(Hash);for(i=0;i<num;i++) {key=(abs((int)names[i][0]-(int)names[i][1]+(int)names[i][strlen(names[i])/2]-(int)names[i][str len(names[i])-2]-(int)names[i][strlen(names[i])-1]))*strlen(names[i]);/* 上式为关键字求取，公式同上*/SearchHash(key,Hash);}collapsetime=count; searchtime=count+num;loadelem=(float)num/LENGTH; hitprob=(float)num/searchtime;printf(" 元素个数：%d\n",num);printf(" 冲突次数：%d\n",collapsetime);printf(" 查找次数：%d\n",searchtime);printf(" 负载因子：%f\n",loadelem); printf(" 命中率=总人数/ 查找数：%f\n",hitprob);}int Hash(int key)/* 处理关键字的哈希函数*/{ return((key*key)/1000%LENGTH);}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++;/* 统计冲突次数*/}}void InitHash(int Hashtable[])/* 初始化哈希表*/{int i; for(i=0;i<LENGTH;i++)Hashtable[i]=-1;}void InsertHash(int key,int Hashtable[])/* 向哈希表中插入关键字*/{int add; add=Hash(key);if(Hashtable[add]==-1)Hashtable[add]=key;else { add=Collision(key,Hashtable);/* 处理哈希表中冲突，注意：这里count 也会计数，所以结束插入过程后应将count 清零*/Hashtable[add]=key;}}int SearchHash(int key,int Hashtable[])/* 查找关键字在哈希表中的地址*/{int add; add=Hash(key); if(Hashtable[add]==key) return add;while(Hashtable[add]!=key&&Hashtable[add]!=-1) add=Collision(key,Hashtable);/* 处理哈希表中冲突*/return add;}void PrintHash(int Hashtable[])/* 输出哈希表(帮助调试用) */{int i;for(i=0;i<LENGTH;i++)if(Hashtable[i]!=-1)prin tf("%3d:%d\n",i+1,Hashtable[i]);}截图第一组(LENGTH宏定义为60) 输入：50个名字(字符串，采用英文单词) 输出结果：输出：1.哈希表（帮助调试用）2.实验要求的各项参数 元素个数：50,冲突次数：77,查找次数：127，负载因子：0.833333，命中率:1 1根据线性探测在散列成功查找时的公式ASL=（1+ ）（其中，ASL 表示平均查找长度，a 表 示负载因子）。

ASL=3.5总平均查找次数为175，平均命中率为0.285714。

显然，本程序实现的哈希查找在本次试验中优于平均状况。