在程序中我们对关键字key应用散列函数H(key)来判断关键字key是否在散列表中,即计算H(key)的值,H(key)值确定所存数据在散列表中的位置。这样一个数据元素的地址是通过函数来计算的,所以数据元素并不需要按照特定的顺序来存放。但是散列函数H(key)将关键字映射为一个整数时,有可能两个关键字的地址相同,所以构造散列函数时要考虑尽量减少冲突的发生。构造散列函数有多种方法,如:平方取中法、除留余数随机数法。本程序采用除留余数法。程序的具体实现如下:本程序是用模板类myhash来实现,包括protected和public属性成员。其中protected成员有*ht(自定义散列表指针)、*empty(bool类型指针,功能是将元素值空、m(散列表容量)、p(除留余数法的除数)以及辅助函数H(key)(散列函数)和collision(处理冲突的函数);public成员包括构造函数、析构函数和复制构造函数以及=重载函数,其它成员函数主要有:traver(遍历散列表)、show()(打印出哈希表所存的元素)返回值为bool类型的函数search\insert\Delete。search函数(查询关键字为key的元素的位值)、insert函数(插入元素e到哈希表中)、Delete函数(删除关键字为key的元素)。本程序的main函数同样采用两种类型的数据来进行测试,int型和char型,主要测试元素的插入、删除和搜索。
2019-12-21 20:06:51
4KB
哈希表
c++
1