问题 A: DS哈希查找—线性探测再散列

素颜马尾好姑娘i 2023-10-04 15:19 52阅读 0赞

#### 文章目录 ####

*  直奔代码

--------------------

问题 A: DS哈希查找—线性探测再散列
    
    题目描述
     定义哈希函数为H(key) = key%11，输入表长（大于、等于11）。输入关键字集合，用线性探测再散列构建哈希表，并查找给定关键字。
    
    --程序要求--
    若使用C++只能include一个头文件iostream；若使用C语言只能include一个头文件stdio
    程序中若include多过一个头文件，不看代码，作0分处理
    不允许使用第三方对象或函数实现本题的要求
    输入
     测试次数t
    
    每组测试数据为：
    
    哈希表长m、关键字个数n
    
    n个关键字(关键字为互不相同的正整数）
    
    查找次数k
    
    k个待查关键字
    
    输出
    对每组测试数据，输出以下信息：
    
    构造的哈希表信息，数组中没有关键字的位置输出NULL
    
    对k个待查关键字，分别输出：0或1（0—不成功，1—成功）、比较次数、查找成功的位置（从1开始）
    
    样例输入
    1
    12 10
    22 19 21 8 9 30 33 4 15 14
    4
    22
    56
    30
    17
    样例输出
    22 30 33 14 4 15 NULL NULL 19 8 21 9
    1 1 1
    0 6
    1 6 2
    0 1
    提示

## 直奔代码 ##

#include<iostream>
    using namespace std;
    
    #define INF -99
    
    
    int main()
    {
        int t;
        cin >> t;
        while( t-- ){
            int m, n;
            cin >> m >> n;
            int * a = new int[m]; 
            for( int i=0; i<m; i++) a[i] = INF;
            
            // 建表
            while( n-- ){
                int num ; 
                cin >> num;
                int di = 1;
                int h = num%11;
                if(a[h]==INF){
                    a[h] = num;
                    continue;
                }
                while( true ){
                    int temp = (h+di)%m;
                    if( a[temp] == INF ){
                        a[temp] = num;
                        break;
                    } else{
                         di++;
                    }
                }
            }
            for(int i=0; i<m; i++){
                if(a[i] == INF ) cout<<"NULL"<<" ";
                else cout<<a[i]<<" ";
            }
            cout << endl;
            int k;
            cin >> k;
            while(k--) {
                 int f;
                 cin >> f;
                 int h = f%11;
                 int times = 1;
                 int flag = 0;
                 int tf = 0;
                 int temp = h;
    
                 /**************
                  * 查找分三种情况：
                  * 1. 要找的关键字的hash地址为空
                  * 2. 要找的关键字的hash地址不为空且等于关键字
                  * 3. 要找的关键字的hash地址不为空，也不等于关键字，则进行线性探测
                  * 
                  * 
                  * **********/
                 if(a[h]==INF){             // 第一种情况     
                     cout<<0<<" "<<1<<endl;
                 }
                 else{
                     if( a[h]==f ){         // 第二种情况
                         cout<< 1 << " " << 1 << " " << h+1 <<endl;
                         continue;
                     }
                     while(true){           // 第三种情况
                         int temp = ( h+times ) %m;
                         times++;
                         if( a[temp]==f ){
                             cout<<1<<" "<<times<<" "<<temp+1<<endl;
                             flag = 1;
                             break;
                         }
                         if(a[temp]==INF){
                             break;
                         }
                     }
                     if( flag==0 ){
                         cout<<0<<" "<<times<<endl;
                     }
                 }
            }
        }
        return 0;
    }