成都网站seo推广/百度快照提交入口
开放定址的哈希表的实现
关于哈希表的一些基础知识，可以参考哈希表的全新理解
哈希表的类型定义
typedef struct {RcdType *rcd; //哈希表记录的地址指针 int size; //哈希表的规模 int count; //记录个数 int *tag; //标志指针：1为有，0为空，-1为已删除 int (*hash)(KeyType key,int size) ; //起映射作用的哈希函数指针 int (*collision)(int &hashValue,int size) ; //处理冲突的函数指针
}HashTable;
哈希表的初始化
//哈希表的初始化
Status InitHash (HashTable &H,int size,int (*hash)(KeyType,int),int (*collision)(int &,int)) {//申请了size个连续的RcdType类型的存储空间H.rcd = (RcdType*)malloc(size*sizeof(RcdType));//申请了同样个数（size）的连续的整形的存储空间//方便后面一对一登记各点的记录状态//将地址赋值给指针H.tagH.tag = (int*)malloc(size*sizeof(int));//每次申请存储空间，习惯判断是否申请成功if (H.rcd==NULL||H.tag==NULL) {return OVERFLOW;}for (int i=0;i<size;i++) {H.tag[i] = 0; //数组初始化，很多时候我们都需要保持初始化的习惯//特别是刚定义变量/申请存储空间时//因为他们可能带有默认值影响结果}H.size = size;H.count = 0;H.hash = hash;H.collision = collision; //处理冲突函数return OK;
}
冲突函数
//冲突函数
void collision(int & hashValue,int hashSize) {
//冲突函数可以根据实际问题具体设计hashValue = (hashValue+1)%hashSize;
}
哈希表的查找
//哈希表的查找
Status SearchHash(HashTable H,KeyType key,int &p,int &c) {p = H.hash(key,H.size); //求得哈希地址//如果地址p存在不等记录或者记录已经删除，则进入循环 while((1==H.tag[p]&&H.rcd[p].key!=key)||-1==H.tag) {H.collision(p,H.size); //一开始存放的时候是通过冲突函数处理的，//现在查找也通过同样的方式查找，//就好像你将东西放在某个地方，你要查找的时候还是要按同样的路前去取出 c++; //c代表层次，经过n次冲突函数，则c=n }//存在相等记录 if(H.rcd[p].key==key&&1==H.tag[p]) {return OK;}else { //不存在记录 return ERROR;}
}
插入记录
//插入
int InsertHash(HashTable &H,RcdType e) {int c=0,j;//判断待插入记录是否已经存在，通过哈稀函数返回地址j，层次c(这两个参数属于引用形参，可双向传递) if(OK == SearchHash(H,e.key,j,c)) {return -1;}else { //待插入记录在哈希表中不存在，则执行插入操作 H.rcd[j] = e;H.tag[j] = 1;++H.count;return c;}
}
删除记录
//删除
Status DeleteHash (HashTable &H,KeyType key,RcdType &e) {int j,c; //用于接收SearchHash函数中引用形参的返回值 if (ERROR == SearchHash(Hey,j,c)) {return ERROR;}else {e = H.rcd[j] ;H.tag[j] = -1 ;H.count--;return OK;}
}