哈希：线性探测再散列+除留余数法

#include <bits/stdc++.h>
using namespace std;
#define MAXSIZE 100
typedef struct//哈希表的结构体类型
{
    int data[MAXSIZE];//一个数组
    int sum;//sum存的是当前哈希表中的元素个数
}HashTable;

void Init(HashTable &H)//哈希表的初始化操作
{
    memset(H.data,0,MAXSIZE);
    H.sum=0;
}

int Hash(int n,int p)//哈希函数，返回一个哈希值，这里采用除留余数法（严书225页）
{
    return n%p;
}

int InsertHash(HashTable &H,int key,int p)//在哈希表H中插入一个关键字key，其中%p
{
    int k,d;
    d=0;//本次采用的是线性探测再散列，初始为0，如果发现冲突，就d++继续进行探测，如果发现没有元素，就插入
    k=Hash(key+d,p);//计算哈希值
    while(H.sum!=MAXSIZE)//只要哈希表没有满我就可以进行插入
    {
        if(!H.data[k])//如果这个地方空了，就插入
        {
            H.data[k]=key;
            H.sum++;
            return 1;
        }
        else//说明这个地方有别人了，那我得换一个地方，根据线性探测再散列的原则，我的d需要++然后再计算，直到找到一个空地方为止
        {
            d++;
            k=Hash(key+d,p);
        }
    }
    return 0;
}

int FindHash(HashTable H,int key,int p)//在哈希表H中找到关键字key的数组下标并返回，如果查找失败返回-1.查找失败有两种情况，一是哈希表是空的，二是表中该位置没有记录，即H.data[i]==0，也属于查找失败的情况。
{
    int k,d;
    d=0;
    k=Hash(key+d,p);
    while(H.sum)//只要表不空
    {
        if(!H.data[k])
            return -1;//这个地方不存在元素，查找失败
        else if(H.data[k]==key)
            return k;
        else
        {
            d++;
            k=Hash(key+d,p);
        }
    }
    return -1;//空表啥也查不到，查找失败
}

int main()
{
    HashTable H;
    int x,n,p,i,t;
    while(scanf("%d%d",&n,&p)!=EOF)
    {
        Init(H);
        for(i=0;i<n;i++)
        {
            scanf("%d",&x);
            InsertHash(H,x,p);
        }
        printf("输入你想查找的数，返回其数组下标，若查找失败则返回-1，如果你不想查了就输入-999\n");
        scanf("%d",&t);
        while(t!=-999)
        {
            printf("%d\n",FindHash(H,t,p));
            scanf("%d",&t);
        }
    }
}
#include <bits/stdc++.h>
using namespace std