.
数据构造实验报告四——哈希表查找名字〔字符串〕
实验题目:哈希表查找名字〔字符串〕 实验目标:
输入一组名字〔至少50个〕,将其保存并利用哈希表查找。输出哈希查找冲突次数,哈希表负载因子、查找命中率。 数据构造: 哈希表和数组〔二维〕。二维数组用于静态顺序存储名字〔字符串〕,哈希表采用开放定址法,用于存储名字〔字符串〕对应的关键字并实现对名字〔字符串〕的查找。 需要的操作有:
1.关键字求取〔主函数中两次出现,未单独编为函数〕
关键字key=abs〔字符串首位ASCII码值-第二位ASCII码值+第〔[]+1〕位ASCII码值-最后一位ASCII码值-倒数第二位ASCII码值〕*字符串长度〔abs为求整数绝对值的函数〕。 2.处理关键字的哈希函数〔Hash〕
利用平方取中法求关键值key在哈希表中的位置。公式add=〔key*key〕00/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 5.向哈希表中插入关键字〔InsertHash〕 void InsertHash(int key,int Hashtable[]) { int add; word版 . } 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 8.求字符串长度〔strlen〕〔函数库 1建立长度为LENGTH的哈希表Hash〔LENGTH具体值由宏定义决定〕。 2输入要插入的字符串总数num〔num小于等于LENGTH〕,再输入num个字符串,将这num个字符串的关键值key计算出来后插入哈希表中。 3输出哈希表〔帮助调试用,并非实验目的〕。 4依次查找这num个字符串对应的关键字在哈希表中位置,并统计冲突次数,记为count。根据公式计算负载因子和命中率〔负载因子=表中填入的记录数/哈希表的长度,命中率=元素个数/查找次数〕。输出元素个数、冲突次数、查找次数、负载因子、命中率。 源程序〔将LENGTH定义为60,实际调试中定义为60和100各一次〕: #include #define LENGTH 60 /*实际调试中定义为60和100各一次*/ word版 . 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(\ scanf(\ printf(\ for(i=0;i /*上式为关键字求取,公式:关键字key=abs〔字符串首位ASCII码值-第二位ASCII码值+第〔[n/2]+1〕位ASCII码值-最后一位ASCII码值-倒数第二位ASCII码值〕*字符串长度〔abs为求整数绝对值的函数〕。*/ InsertHash(key,Hash); } count=0;/*将count置零,去除插入过程中产生的冲突次数*/ PrintHash(Hash); for(i=0;i