哈希查找【数据结构】

本文介绍: 定义哈希函数为H(key) = key%11，输入表长（大于、等于11）。输入关键字集合，用线性探测再散列构建哈希表，并查找给定关键字。测试次数t哈希表长m、关键字个数nn个关键字查找次数kk个待查关键字对每组测试数据，输出以下信息：构造的哈希表信息，数组中没有关键字的位置输出NULL对k个待查关键字，分别输出：0或1（0—不成功，1—成功）、比较次数、查找成功的位置（从1开始）112 104225630171 1 10 61 6 2。

DS哈希查找—线性探测再散列

题目描述
定义哈希函数为H(key) = key%11，输入表长（大于、等于11）。输入关键字集合，用线性探测再散列构建哈希表，并查找给定关键字。

输入
测试次数t
每组测试数据为：
哈希表长m、关键字个数n
n个关键字
查找次数k
k个待查关键字

输出
对每组测试数据，输出以下信息：
构造的哈希表信息，数组中没有关键字的位置输出NULL
对k个待查关键字，分别输出：0或1（0—不成功，1—成功）、比较次数、查找成功的位置（从1开始）

输入样例1
1
12 10
22 19 21 8 9 30 33 4 15 14
4
22
56
30
17

输出样例1
22 30 33 14 4 15 NULL NULL 19 8 21 9
1 1 1
0 6
1 6 2
0 1

#include<bits/stdc++.h>
using namespace std;
//构建哈希表
void hashBuild(int x,int a[],int m)
{
    int index=x%11;
    if(!a[index]) a[index]=x;
    else
    {
        //线性探测再散列
        int d=1;
        while(a[(index+d)%m]&&d<m) d++;
        a[(index+d)%m]=x;
    }
}
int main()
{
    int t;
    cin>>t;
    for(int i=0;i<t;i++)
    {
        int m,n;
        cin>>m>>n;
        int a[m];
        memset(a,0,sizeof(a));
        for(int j=0;j<n;j++)
        {
            int x;
            cin>>x;
            //构建哈希表
            hashBuild(x,a,m);
        }
        for(int i=0;i<m;i++)
        {
            if(i==0) (a[i])?cout<<a[i]:cout<<"NULL";
            else (a[i])?cout<<" "<<a[i]:cout<<" NULL";
        }
        cout<<endl;
        int k;
        cin>>k;
        for(int j=0;j<k;j++)
        {
            int x;
            cin>>x;
            int time=0;
            int loc=-1;
            int index=x%11;
            //查找一次就成功
            if(a[index]==x)
            {
                cout<<"1 1 "<<index+1<<endl;
                continue;
            }
            int d=0;
            while(a[(index+d)%m]!=x&&a[(index+d)%m]&&d<m) d++;
            //查找失败
            if(d==m||!a[(index+d)%m])
            {
                cout<<"0 "<<d+1<<endl;
                continue;
            }
            else cout<<"1 "<<d+1<<" "<<(index+d)%m+1<<endl;
        }
    }
    return 0;
}

DS哈希查找—二次探测再散列

题目描述
定义哈希函数为H(key) = key%11。输入表长（大于、等于11），输入关键字集合，用二次探测再散列构建哈希表，并查找给定关键字。

输入
测试次数t
每组测试数据格式如下：
哈希表长m、关键字个数n
n个关键字
查找次数k
k个待查关键字

输出
对每组测试数据，输出以下信息：
构造的哈希表信息，数组中没有关键字的位置输出NULL
对k个待查关键字，分别输出：
0或1（0—不成功，1—成功）、比较次数、查找成功的位置（从1开始）

输入样例1
1
12 10
22 19 21 8 9 30 33 4 41 13
4
22
15
30
41

输出样例1
22 9 13 NULL 4 41 NULL 30 19 8 21 33
1 1 1
0 3
1 3 8
1 6 6

#include<bits/stdc++.h>
using namespace std;
//构建哈希表
void hashBuild(int x,int a[],int m)
{
    int index=x%11;
    if(!a[index]) a[index]=x;
    else
    {
        //二次探测再散列
        int d=1;
        while((((index+d)%m)>=0&&a[(index+d)%m])||((index+d)%m<0&&a[((index+d+m)%m)])&&d<m)
        {
            if(d>0) d=-d;
            else d=pow(sqrt(-d)+1,2);
        }
        ((index+d)%m>=0)?a[((index+d)%m)]=x:a[(index+d+m)%m]=x;
    }
}
int main()
{
    int t;
    cin>>t;
    for(int i=0;i<t;i++)
    {
        int m,n;
        cin>>m>>n;
        int a[m];
        memset(a,0,sizeof(a));
        for(int j=0;j<n;j++)
        {
            int x;
            cin>>x;
            hashBuild(x,a,m);
        }
        for(int i=0;i<m;i++)
        {
            if(i==0) (a[i])?cout<<a[i]:cout<<"NULL";
            else (a[i])?cout<<" "<<a[i]:cout<<" NULL";
        }
        cout<<endl;
        int k;
        cin>>k;
        for(int j=0;j<k;j++)
        {
            int x;
            cin>>x;
            int index=x%11;
            //一次就找到
            if(a[index]==x)
            {
                cout<<"1 1 "<<index+1<<endl;
                continue;
            }
            int d=0;
            while((((index+d)%m)>=0&&a[(index+d)%m]&&a[(index+d)%m]!=x)||((index+d)%m<0&&a[((index+d+m)%m)]&&a[((index+d+m)%m)]!=x)&&d<m)
            {
                if(d>0) d=-d;
                else d=pow(sqrt(-d)+1,2);
            }
            int time;
            if(d>=0) time=sqrt(d)*2;
            else time=sqrt(-d)*2+1;
            //找不到
            if(d==m||!a[(index+d)%m])
            {
                cout<<"0 "<<time<<endl;
                continue;
            }
            else cout<<"1 "<<time<<" "<<(index+d)%m+1<<endl;
        }
    }
    return 0;
}

DS哈希查找–链地址法(表头插入)

题目描述
给出一个数据序列，建立哈希表，采用求余法作为哈希函数，模数为11，哈希冲突用链地址法和表头插入
如果首次查找失败，就把数据插入到相应的位置中
实现哈希查找功能

输入
第一行输入n，表示有n个数据
第二行输入n个数据，都是自然数且互不相同，数据之间用空格隔开
第三行输入t，表示要查找t个数据
从第四行起，每行输入一个要查找的数据，都是正整数

输出
每行输出对应数据的查找结果

输入样例1
6
11 23 39 48 75 62
6
39
52
52
63
63
52

输出样例1
6 1
error
8 1
error
8 1
8 2

提示
注意，当两次输入要相同的查找数据，如果第一次查找不成功就会执行插入，那么第二次查找必然成功，且查找次数为1次（因为做表头插入）
例如示例数据中输入两次52，第一次查找失败就把52插入到位置8，第二次查找就成功了，所以第一次输出error，第二次就输出8 1
为什么第三次输入52会输出8 2

#include<bits/stdc++.h>
using namespace std;
struct node
{
    int value;
    node* next=NULL;
};
//构建哈希数组+链表
//数组的头节点是空的
void buildNode(node* a[],int x)
{
    int index=x%11;
    if(!a[index])
    {
        a[index]=new node;
    }
    node* newNode=new node;
    newNode->value=x;
    newNode->next=a[index]->next;
    a[index]->next=newNode;
}
//查找
int find(node* a[],int x)
{
    int index=x%11;
    if(!a[index]) return -1;
    node* now=a[index];
    int time=-1;
    while(now)
    {
        time++;
        if(now->value==x) return time;
        now=now->next;
    }
    return -1;
}
int main()
{
    int n;
    cin>>n;
    node* a[11];
    memset(a,NULL,sizeof(a));
    for(int i=0;i<n;i++)
    {
        int x;
        cin>>x;
        //这里注意不能写a[x%11]=new node;!!!
        //因为这样如果插入的两个数%11是相同的就会覆盖掉导致错误！！！！
        buildNode(a,x);
    }
    int t;
    cin>>t;
    for(int i=0;i<t;i++)
    {
        int x;
        cin>>x;
        if(find(a,x)==-1)
        {
            cout<<"error"<<endl;
            buildNode(a,x);
            continue;
        }
        cout<<x%11<<" "<<find(a,x)<<endl;
    }
    return 0;
}