【数据结构】线性探测法构造散列表及其查找

梦里梦外; 2023-08-17 15:23 103阅读 0赞

#include<iostream>
    using namespace std;
    const int LEN = 20; // Hash表长
    const int INF = 0xffff; // 表空标记
    const int a_length = 12; // 测试数组长度
    int p = 13; // 取余质数
    int HASH[LEN]; // HASH表
    
    // 构造Hash表
    void Hash(int a[], int a_length, int p) {
        for (int i = 0; i < LEN; i++) {
            HASH[i] = INF;
        }
        for (int i = 0; i < a_length; i++) {
            int key = a[i];
            int addr = key % p;
            while (HASH[addr] != INF)
                addr++;
            HASH[addr] = key;
        }
    }
    
    // 查找Hash表元素
    int SearchHash(int key, int p) {
        cout<<"Search for "<<key<<endl;
        int addr = key % p;
        cout<<"addr = "<<addr<<", HASH["<<addr<<"] = "<<HASH[addr]<<endl;
        if (HASH[addr] == key)
            return addr;
    
        int d = 0;
        while (HASH[addr] != key) {
            d++;
            int newAddr = (addr + d) % LEN;
            cout<<"addr = ("<<addr<<" + "<<d<<") % "<<LEN<<" = "<<newAddr<<", HASH["<<newAddr<<"] = "<<HASH[newAddr]<<endl;
            if (HASH[newAddr] == key)
                return addr;
            if (HASH[newAddr] == INF)
                return -1;
        }
    }
    
    
    // 打印Hash表
    void PrintHash() {
        for (int i = 0; i < LEN; i++)
            cout<<HASH[i]<<" ";
        cout<<endl;
    }
    
    int main() {
        int a[a_length] = {19, 14, 23, 1, 68, 20, 84, 27, 55, 11, 10, 79};
        Hash(a, a_length, p);
        PrintHash();
    
        for (int i = 0; i < 12; i++) {
            SearchHash(a[i], p);
            cout<<endl;
        }
        return 0;
    }

// p = 13时的结果
    65535 14 1 68 27 55 19 20 84 79 23 11 10 65535 65535 65535 65535 65535 65535 65535
    Search for 19
    addr = 6, HASH[6] = 19
    
    Search for 14
    addr = 1, HASH[1] = 14
    
    Search for 23
    addr = 10, HASH[10] = 23
    
    Search for 1
    addr = 1, HASH[1] = 14
    addr = (1 + 1) % 20 = 2, HASH[2] = 1
    
    Search for 68
    addr = 3, HASH[3] = 68
    
    Search for 20
    addr = 7, HASH[7] = 20
    
    Search for 84
    addr = 6, HASH[6] = 19
    addr = (6 + 1) % 20 = 7, HASH[7] = 20
    addr = (6 + 2) % 20 = 8, HASH[8] = 84
    
    Search for 27
    addr = 1, HASH[1] = 14
    addr = (1 + 1) % 20 = 2, HASH[2] = 1
    addr = (1 + 2) % 20 = 3, HASH[3] = 68
    addr = (1 + 3) % 20 = 4, HASH[4] = 27
    
    Search for 55
    addr = 3, HASH[3] = 68
    addr = (3 + 1) % 20 = 4, HASH[4] = 27
    addr = (3 + 2) % 20 = 5, HASH[5] = 55
    
    Search for 11
    addr = 11, HASH[11] = 11
    
    Search for 10
    addr = 10, HASH[10] = 23
    addr = (10 + 1) % 20 = 11, HASH[11] = 11
    addr = (10 + 2) % 20 = 12, HASH[12] = 10
    
    Search for 79
    addr = 1, HASH[1] = 14
    addr = (1 + 1) % 20 = 2, HASH[2] = 1
    addr = (1 + 2) % 20 = 3, HASH[3] = 68
    addr = (1 + 3) % 20 = 4, HASH[4] = 27
    addr = (1 + 4) % 20 = 5, HASH[5] = 55
    addr = (1 + 5) % 20 = 6, HASH[6] = 19
    addr = (1 + 6) % 20 = 7, HASH[7] = 20
    addr = (1 + 7) % 20 = 8, HASH[8] = 84
    addr = (1 + 8) % 20 = 9, HASH[9] = 79
    
    // p = 7时的结果
    14 1 23 84 11 19 68 20 27 55 10 79 65535 65535 65535 65535 65535 65535 65535 65535
    Search for 19
    addr = 5, HASH[5] = 19
    
    Search for 14
    addr = 0, HASH[0] = 14
    
    Search for 23
    addr = 2, HASH[2] = 23
    
    Search for 1
    addr = 1, HASH[1] = 1
    
    Search for 68
    addr = 5, HASH[5] = 19
    addr = (5 + 1) % 20 = 6, HASH[6] = 68
    
    Search for 20
    addr = 6, HASH[6] = 68
    addr = (6 + 1) % 20 = 7, HASH[7] = 20
    
    Search for 84
    addr = 0, HASH[0] = 14
    addr = (0 + 1) % 20 = 1, HASH[1] = 1
    addr = (0 + 2) % 20 = 2, HASH[2] = 23
    addr = (0 + 3) % 20 = 3, HASH[3] = 84
    
    Search for 27
    addr = 6, HASH[6] = 68
    addr = (6 + 1) % 20 = 7, HASH[7] = 20
    addr = (6 + 2) % 20 = 8, HASH[8] = 27
    
    Search for 55
    addr = 6, HASH[6] = 68
    addr = (6 + 1) % 20 = 7, HASH[7] = 20
    addr = (6 + 2) % 20 = 8, HASH[8] = 27
    addr = (6 + 3) % 20 = 9, HASH[9] = 55
    
    Search for 11
    addr = 4, HASH[4] = 11
    
    Search for 10
    addr = 3, HASH[3] = 84
    addr = (3 + 1) % 20 = 4, HASH[4] = 11
    addr = (3 + 2) % 20 = 5, HASH[5] = 19
    addr = (3 + 3) % 20 = 6, HASH[6] = 68
    addr = (3 + 4) % 20 = 7, HASH[7] = 20
    addr = (3 + 5) % 20 = 8, HASH[8] = 27
    addr = (3 + 6) % 20 = 9, HASH[9] = 55
    addr = (3 + 7) % 20 = 10, HASH[10] = 10
    
    Search for 79
    addr = 2, HASH[2] = 23
    addr = (2 + 1) % 20 = 3, HASH[3] = 84
    addr = (2 + 2) % 20 = 4, HASH[4] = 11
    addr = (2 + 3) % 20 = 5, HASH[5] = 19
    addr = (2 + 4) % 20 = 6, HASH[6] = 68
    addr = (2 + 5) % 20 = 7, HASH[7] = 20
    addr = (2 + 6) % 20 = 8, HASH[8] = 27
    addr = (2 + 7) % 20 = 9, HASH[9] = 55
    addr = (2 + 8) % 20 = 10, HASH[10] = 10
    addr = (2 + 9) % 20 = 11, HASH[11] = 79
    
    // p = 11时的结果
    
    Search for 14
    addr = 3, HASH[3] = 14
    
    Search for 23
    addr = 1, HASH[1] = 23
    
    Search for 1
    addr = 1, HASH[1] = 23
    addr = (1 + 1) % 20 = 2, HASH[2] = 1
    
    Search for 68
    addr = 2, HASH[2] = 1
    addr = (2 + 1) % 20 = 3, HASH[3] = 14
    addr = (2 + 2) % 20 = 4, HASH[4] = 68
    
    Search for 20
    addr = 9, HASH[9] = 20
    
    Search for 84
    addr = 7, HASH[7] = 84
    
    Search for 27
    addr = 5, HASH[5] = 27
    
    Search for 55
    addr = 0, HASH[0] = 55
    
    Search for 11
    addr = 0, HASH[0] = 55
    addr = (0 + 1) % 20 = 1, HASH[1] = 23
    addr = (0 + 2) % 20 = 2, HASH[2] = 1
    addr = (0 + 3) % 20 = 3, HASH[3] = 14
    addr = (0 + 4) % 20 = 4, HASH[4] = 68
    addr = (0 + 5) % 20 = 5, HASH[5] = 27
    addr = (0 + 6) % 20 = 6, HASH[6] = 11
    
    Search for 10
    addr = 10, HASH[10] = 10
    
    Search for 79
    addr = 2, HASH[2] = 1
    addr = (2 + 1) % 20 = 3, HASH[3] = 14
    addr = (2 + 2) % 20 = 4, HASH[4] = 68
    addr = (2 + 3) % 20 = 5, HASH[5] = 27
    addr = (2 + 4) % 20 = 6, HASH[6] = 11
    addr = (2 + 5) % 20 = 7, HASH[7] = 84
    addr = (2 + 6) % 20 = 8, HASH[8] = 19
    addr = (2 + 7) % 20 = 9, HASH[9] = 20
    addr = (2 + 8) % 20 = 10, HASH[10] = 10
    addr = (2 + 9) % 20 = 11, HASH[11] = 79