问题 B: DS哈希查找—二次探测再散列(关键字互不相同）

今天药忘吃喽~ 2023-10-04 15:19 37阅读 0赞

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

*  直奔代码

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

问题 B: DS哈希查找—二次探测再散列(关键字互不相同）
    时间限制: 1 Sec  内存限制: 128 MB
    提交: 123  解决: 57
    [提交][状态][讨论版]
    题目描述
    定义哈希函数为H(key) = key%11。输入表长（大于、等于11），输入关键字集合，用二次探测再散列构建哈希表，并查找给定关键字。
    
    输入
    测试次数t
    每组测试数据格式如下：
    哈希表长m、关键字个数n
    n个关键字(关键字为互不相同的正整数）
    查找次数k
    k个待查关键字
    输出
    对每组测试数据，输出以下信息：
    构造的哈希表信息，数组中没有关键字的位置输出NULL
    对k个待查关键字，分别输出：
    0或1（0—不成功，1—成功）、比较次数、查找成功的位置（从1开始）
    样例输入
    1
    12 10
    22 19 21 8 9 30 33 4 41 13
    4
    22
    15
    30
    41
    样例输出
    22 9 13 NULL 4 41 NULL 30 19 8 21 33
    1 1 1
    0 3
    1 3 8
    1 6 6
    提示

## 直奔代码 ##

// 问题 B: DS哈希查找—二次探测再散列(关键字互不相同）
    #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 t1 = (h+di*di)%m;
                    int t2 = (h-di*di)%m;
                    t2 = t2<0 ? (t2+m) : t2;
    
                    /*******
                     * 重点： 这里一定要注意对t2的取值范围进行处理，小于0的时候要进行循环移位
                     * 博主再初学这个的时候，可是被他坑惨了呜呜
                     * 
                     * ******/
    
    
                    if( a[t1] == INF ){
                        a[t1] = num;
                        break;
                    } else if( a[t2] == INF ){
                        a[t2] = 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 = 0;
                int flag = 0;              // 没找到为0， 找到为1
                int tf = 0;
                int di = 1;
                 /**************
                  * 查找分三种情况：
                  * 1. 要找的关键字的hash地址为空
                  * 2. 要找的关键字的hash地址不为空且等于关键字
                  * 3. 要找的关键字的hash地址不为空，也不等于关键字，则进行二次探测（平方）
                  * 
                  * #### 注意比较次数自加的位置
                  *     1. 先和自身的hash地址比较，不匹配则+1
                  *     2. 和t1 = (h+di*di)%m; t1的地址比较，不成功则+1
                  *     3. 和t2 = (h-di*di)%m; t2 的地址比较，不成功则+1
                  * **********/
                 times ++;
                 if(a[h]==INF){             // 第一种情况     
                     cout<<0<<" "<<times<<endl;
                 }
                 else{
                     if( a[h]==f ){         // 第二种情况
                         cout<< 1 << " " << times << " " << h+1 <<endl;
                         continue;
                     }
                     while(true){           // 第三种情况
                        int t1 = (h+di*di)%m;
                        int t2 = (h-di*di)%m;
                        t2 = t2<0 ? (t2+m) : t2;
                        times++;
                        if( a[t1]==f ){
                             cout<<1<<" "<<times<<" "<<t1+1<<endl;
                             flag = 1;
                             break;
                         }
                        times++;
                        if( a[t2]==f ){
                             cout<<1<<" "<<times<<" "<<t2+1<<endl;
                             flag = 1;
                             break;
                         }
                        if(a[t1]==INF || a[t2]==INF ){
                            break;
                        }
                         di ++;
                     }
                     if( flag==0 ){
                         cout<<0<<" "<<times<<endl;
                     }
                 }
            }
        }
        return 0;
    }