哈希表

将数组中每个元素对离数组长度len最近的素数取余获得哈希表的下标值，并使用头插法分配到哈希链表中，所以时间复杂度最坏为O(n)，即数组中所有数的哈希下标都相等。

#include<iostream>
#include<cstdlib>
#include<cassert>
using namespace std;
 
#define N 12//元素数量为12
#define P (N+1)//离元素个数最近的素数为13
 
typedef struct HashNode{
    int data;//数据域
    HashNode* link;//指针域
}HashNode;
 
typedef HashNode* HashTable[P];//创建哈希数组，元素大小为P,类型为指针
 
void InitHt(HashTable &ht){
    for(int i=0;i<P;i++)
        ht[i]=NULL;
}//初始化哈希数组
 
int Hash(int x){
    return x%P;
}//计算元素的哈希值
 
void InsHt(HashTable &ht,int x){
    int index=Hash(x);//求出元素哈希下标
    HashNode* n=(HashNode*)malloc(sizeof(HashNode));//分配节点空间
    assert(n);
    n->data=x;//初始化节点值
    n->link=ht[index];
    ht[index]=n;//头插法插入新节点
}//哈希链表插入元素
 
void ShowHt(HashTable &ht){
    for(int i=0;i<P;i++){
        cout<<i<<": ";
        HashNode* n=ht[i];
        while(n){//判断节点是否为空
            cout<<n->data<<"-->";
            n=n->link;
            //如果有冲突，则使当前节点n指向冲突的元素，否则指向空
        }
        cout<<"NULL"<<endl;
    }
}
 
HashNode* SearchHt(HashTable &ht,int x){
    int index=x%P;//通过哈希函数求关键字下标
    HashNode *n=ht[index];//n为当前哈希表中index位置链表指针
    while(n!=NULL&&n->data!=x){//相等则直接返回节点
        n=n->link;//不相等则指针右移查找下一节点
    }
    return n;//返回节点
}
 
bool RemoveHt(HashTable &ht,int x){
    HashNode* n=SearchHt(ht,x);
    if(!n)
        return false;//如果节点为空则返回false
    HashNode* pre;//要删除节点所在链表的首节点
    int index=Hash(x);
    pre=ht[index];//初始化首节点
    if(pre==n){//如果首节点即为要删除的节点
        ht[index]=pre->link;
        free(pre);
        return true;
    }
    while(pre->link!=n)//查找节点
        pre=pre->link;
    pre->link=n->link;//删除节点n
    free(n);
    return true;
}
 
int main(){
//    printf("%d",N);
//    printf("%d",P);
//  测试define常量
    HashTable ht;//哈希数组
    InitHt(ht);
    int arr[]={19,14,1,23,68,20,84,27,55,11,10,79};
    for(int i=0;i<N;i++)
        InsHt(ht,arr[i]);
    cout<<"哈希表如下:"<<endl;
    ShowHt(ht);
    cout<<endl;
    int x=19;
    HashNode* p=SearchHt(ht,x);
    if(p!=NULL){
        cout<<"查到该元素"<<endl;
    }
    else
        cout<<"不存在该元素"<<endl;
    x=27;
    if(RemoveHt(ht,x))
        cout<<"已删除节点"<<endl;
    else
        cout<<"删除失败"<<endl;
    cout<<"删除后哈希表如下"<<endl;
    ShowHt(ht);//验证删除操作是否成功
}

图1

图2