利用散列表(哈希表)实现查找

方法:除留余数法

建立函数为:H(key) = (key*3) MOD 7, 装填因子为0.7,采用线性探测法处理冲突,生成散列表,然后进行查找操作:

#include<iostream>
using namespace std;

#define SUCCESS 1
#define UNSUCCESS 0
#define DUPLICATE -1

typedef struct{
    int key;
}TypeElement;

typedef struct{
    TypeElement *elem;
}HashTable;

int EQ(int m,int n)
{
    if(m == n)
        return 1;
    else 
        return 0;
}

void CreatHashTable(HashTable &T)
{
    int a[7];
    int m,n;
    cout << 请输入7个数: << endl;
    for(m = 0 ;m < 7; m++)
    {
        cin >> a[m];
    }

    T.elem = (TypeElement *)malloc(10*sizeof(TypeElement));

    for(m = 0;m < 7;m++)
    {
        int n = ( a[m] * 3) % 7;//求元素的地址
        while(T.elem[n].key!=NULL)//若该地址已有元素则下调;
                n++;
        T.elem[n].key= a[m];
    }
}

int  SearchHashTable(HashTable T,int k,int &p)
{
    p = (k * 3) % 7;

    while(T.elem[p].key!= NULL && !EQ(k,T.elem[p].key))
    {
            p++;
    }

    if(k == T.elem[p].key)
        return 1;
    else 
        return 0;
}

int main()
{
    int i,j,k,m,n;
    HashTable T;
    cout << 创建哈希表 << endl;
    CreatHashTable(T);

    cout << 请输入要查找的数:;
    cin >> i;

    m = SearchHashTable(T,i,j);
/*
    for(int o=0;o<7;o++)
    {
        cout << T.elem[o] <<  ;
    }

    cout << endl;
*/
    if (m == 1)
    {
        cout << 你查找数据位置是: << j;
    }
    else if(m  == 0)
    {
        cout << 查找失败! << endl;
    }

    cout << endl;

    return 0;
}
除非特别说明,本博客所有作品均采用知识共享署名-非商业性使用-禁止演绎 4.0 国际许可协议进行许可。转载请注明转自-https://www.emperinter.info/2018/12/16/%e5%88%a9%e7%94%a8%e6%95%a3%e5%88%97%e8%a1%a8%e5%93%88%e5%b8%8c%e8%a1%a8%e5%ae%9e%e7%8e%b0%e6%9f%a5%e6%89%be/

Leave a Comment