#include <iostream.h>
#include <iomanip.h>
#include <math.h>
#define M 11     //哈希表长度
#define N 8      //关键字个数
struct hterm
{
    int key;       //关键字值
    int si;         //散列次数
};
struct hterm hlist[M];
int i,adr,sum,d;
int x[N]={22,41,53,46,30,13,1,67};  //关键字赋值
float average;
void createhash()   //创建哈希表
{
    for(i=0;i<M;i++)
    {
        hlist[i].key=0;
        hlist[i].si=0;
    }
    for(i=0;i<N;i++)
    {
        sum=0;
        adr=(3*x[i]) % M;                  //adr=(3*x[i]) MOD M;   
        d=adr;
        if(hlist[adr].key==0)
        {
            hlist[adr].key=x[i];
            hlist[adr].si=1;
        }
        else
        {
            do    //处理冲突
            {
                d=(d+x[i]*7 % 10+1) % M;    //d=(d+x[i]*7 MOD 10+1) % M; 
                sum=sum+1;
            }while (hlist[d].key!=0);
            hlist[d].key=x[i];
            hlist[d].si=sum+1;
        }
    }
}
void outhash()//输出希表
{
    cout<<"哈希表地址  ";
    for(i=0;i<M;i++)
        cout<<setw(4)<<i;
    cout<<endl;
    cout<<"哈希表关键字:";
    for(i=0;i<M;i++)
        cout<<setw(4)<<hlist[i].key;
    cout<<endl;
    cout<<"搜索长度:   ";
    for(i=0;i<M;i++)
        cout<<setw(4)<<hlist[i].si;
    cout<<endl;
    average=0;
    for(i=0;i<M;i++)
        average=average+hlist[i].si;
    average=average/N;
        cout<<"平均搜索长度 :ASL("<<N<<")="<<average<<endl;
}
int find()  //哈希表的查找
{
    int s,h,find=1;
    cout<<"输入元素值:  ";
    cin>>s;
    h=(3*s) % M;  //h=(3*s) MOD M;
    while (hlist[h].key!=s)
    {
        h=(h+(s*7) % 10 +1) % 11;  //h=(h+(s*7) MOD 10 +1) % 11;
        if(hlist[h].key==0)
        {
            find=0;break;
        }
    }
    if(find==1)
    {
        cout<<" 位置="<<h<<endl;
        return 1;
    }
    else
    {
        cout<<"元素不存在"<<endl;
        return 0;
    }
}
void main()
{
    cout<<"使用的哈希函数为:H(k)=3*k MOD 11"<<endl;
    cout<<"采用开放地址法处理冲突:"<<endl;
    cout<<"D1=H(k),Di=(Di-1+((7*k MOD 10)+1) % 11 ),其中i=2,3,4...."<<endl;
    createhash();
    outhash();
    find();   //在哈希表中查找
}