首页 > 代码库 > sicily 1003. hash

sicily 1003. hash

Description

请用HASH链式法来解决冲突,且规定链表在链表头插入新元素。

规定HASH函数为:h(x) = x % 11,即哈希数组下标为0~10.

给定两种操作:

  • I 操作,插入一个新的正整数K到哈希表中
  • F 操作,查询整数K是否在哈希表中,若不在,输出-1;若存在,输出目前K在所在链表中的顺序索引(假定链表头索引为0)。

Input

 一组数据。

第一行为整数N,0 < N <= 10000。

接下来N行为随机出现的I操作或F操作。(数据保证K不会重复,K为大于0的int类型)

Output

 对于每行F操作,按顺序输出结果。

 

Sample Input

6
F 10
I 10
I 21
F 10
I 32
F 10

Sample Output

-1
1
2

 

因为要求比较低我就直接用了数组。

我的代码如下:

#include <iostream>
using namespace std;

int main() {
    int n;
    cin>>n;
    int hash[11][n+1];
    for (int i = 0; i < 11; i++) hash[i][0] = 0;    // hash[i][0] store the count
    for (int i = 0; i < n; i++) {
        char operation;
        int num;
        cin>>operation>>num;
        int mod = num % 11;
        if (operation == F) {    // find
            int pos = -1;
            for (int j = 1; j <= hash[mod][0]; j++) {
                if (hash[mod][j] != num) continue;
                pos = j;
                break;
            }
            if (pos == -1) cout<<-1<<endl;
            else cout<<hash[mod][0] - pos<<endl;
        } else {    // insert
            hash[mod][0]++;
            hash[mod][hash[mod][0]] = num;
        }
    }
    return 0;
}

 

sicily 1003. hash