DS哈希查找--链地址法(表头插入)

叶茂林

发布于 2023-07-30 13:33:22

34900

代码可运行

文章被收录于专栏：叶子的开发者社区叶子的开发者社区

运行总次数：0

代码可运行

题目描述

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

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

实现哈希查找功能

输入

第一行输入n，表示有n个数据第二行输入n个数据，都是自然数且互不相同，数据之间用空格隔开第三行输入t，表示要查找t个数据从第四行起，每行输入一个要查找的数据，都是正整数

输出

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

输入样例1

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

输出样例1

6 1 error 8 1 error 8 1 8 2

提示

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

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

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

AC代码

#include<iostream>
using namespace std;
struct Node{
    int data;
    Node*next=NULL;
};
class HashList{
    int n,temp,key;
    Node hash[12];
public:
    HashList(){
        cin>>n;
        while(n--){
            cin>>temp;
            Insert(temp);
        }
        cin>>n;
        while(n--){
            cin>>temp;
            Find(temp);
        }
    }
    void Insert(int&data){
        Node*newOne=new Node;
        newOne->data=data;
        newOne->next=hash[data%11].next;
        hash[data%11].next=newOne;
    }
    void Find(int&data){
        if(hash[data%11].next==NULL){
            cout<<"error"<<endl;
            Insert(data);
        }else if(hash[data%11].next->data==data){
            cout<<data%11<<' '<<'1'<<endl;
        }else{
            int count=2;
            Node*current=hash[data%11].next->next;
            while(current){
                if(current->data==data){
                    cout<<data%11<<' '<<count<<endl;
                    return;
                }
                count++;
            }
            cout<<"error"<<endl;
            Insert(data);
        }
    }
};
int main() {
    HashList test;
    return 0;
}

本文参与腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。

原始发表：2022-12-12，如有侵权请联系 cloudcommunity@tencent.com 删除

data