首页 > 其他 > 详细

哈希表(开放定址法处理冲突)(1013)

时间:2015-06-16 10:36:24      阅读:250      评论:0      收藏:0      [点我收藏+]

Description

   采用除留余数法(H(key)=key %n)建立长度为n的哈希表,处理冲突用开放定址法的线性探测。

Input

   第一行为哈希表的长度n; 第二行为关键字的个数; 第三行为关键字集合; 第三行为要查找的数据。

Output

   如果查找成功,输出关键字所哈希表中的地址和比较次数;如果查找不成功,输出-1。

如果查找成功,输出关键字所哈希表中的地址和比较次数;如果查找不成功,输出-1。

Sample Input
 
1
2
3
4
5
13
11
16 74 60 43 54 90 46 31 29 88 77
16
Sample Output
1
3,1
技术分享
#include<iostream>
#include<cstdlib>
using namespace std;
typedef struct
{
    int data;
    int len, n;
}HashTable;
HashTable ha[101],Ha;
void InsertHT()
{
    int adr, k, cur = 0;
    cin >> k;
    adr = k%Ha.len;
    if (ha[adr].data == -1)
        ha[adr].data = k;
    else
    {
        while (ha[adr].data != -1 && cur < Ha.len)
        {
            adr = (adr + 1) % Ha.len;
            cur++;
        }
        ha[adr].data = k;
    }
}
void CreateHT(int len, int n)
{
    int i;
    Ha.len = len, Ha.n = n;
    for (i = 0; i < n; i++)
        ha[i].data = -1;
    for (i = 0; i < n; i++)
        InsertHT();
}
void Search(int x)
{
    int adr = x%Ha.len;
    int cnt = 1; int k = 0;
    while (ha[adr].data != -1 && ha[adr].data != x&&k<Ha.len)
    {
        cnt++;
        adr = (adr + 1) % Ha.len;
        k++;
    }
    if (ha[adr].data == x)
        cout << adr << , << cnt;
    else
        cout << -1;
}
int main()
{
    int len, n, x;
    cin >> len >> n;
    CreateHT(len, n);
    cin >> x;
    Search(x);
    return 0;
}
View Code

 

哈希表(开放定址法处理冲突)(1013)

原文:http://www.cnblogs.com/traini13/p/4579897.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!