A : DS哈希查找–链地址法

A : DS哈希查找–链地址法

Time Limit: 1 Sec     Memory Limit: 128 Mb     Submitted: 13     Solved: 9

Description

给出一个数据序列，建立哈希表，采用求余法作为哈希函数，模数为11，哈希冲突用链地址法和表头插入

如果首次查找失败，就把数据插入到相应的位置中

实现哈希查找功能

Input

第一行输入n，表示有n个数据

第二行输入n个数据，都是自然数且互不相同，数据之间用空格隔开

第三行输入t，表示要查找t个数据

从第四行起，每行输入一个要查找的数据，都是正整数

Output

每行输出对应数据的查找结果

Sample Input

6
11 23 39 48 75 62
6
39
52
52
63
63
52

Sample Output

6 1
error
8 1
error
8 1
8 2

Hint

注意，当两次输入要相同的查找数据，如果第一次查找不成功就会执行插入，那么第二次查找必然成功，且查找次数为1次（因为做表头插入）

例如示例数据中输入两次52，第一次查找失败就把52插入到位置8，第二次查找就成功了，所以第一次输出error，第二次就输出8 1

为什么第三次输入52会输出8 2

ac代码如下：

#include<iostream>
using namespace std;
struct Node //由于哈希冲突用链地址法，所以加入第二个元素Node *next
{
    int data;
    Node *next;
};  
Node *s[11]; //由于求余法作为哈希函数，所以哈希表分配mod11内存
void Hash_add(int key)  //一种常见的表头插入方法
{
    Node *p=new Node;
    p->data=key;
    p->next=s[key%11];
    s[key%11]=p;
}
int main()
{
    int n,key;
    while(cin>>n)
    {
        for(int i=0; i<11; i++)s[i]=NULL; //由于多组样例需要初始化哈希表
        while(n--)  //构建哈希表
        {
            cin>>key;
            Hash_add(key);
        }
        cin>>n;
        while(n--) //n次查询
        {
            cin>>key;
            Node *p=s[key%11]; //找到key对应的链表s
            int num=1;
            while(p) //对链表进行遍历查询
            {
                if(p->data==key)break;
                p=p->next;
                num++;//查询深度
            }
            if(p)cout<<key%11<<" "<<num<<endl;  //如果不是因为到尾NULL结束，输出哈希表链表位置和深度
            else    //否则输出error，并加入哈希表
            {
                cout<<"error"<<endl;
                Hash_add(key);
            }
        }
    }
    return 0;
}