已知一组关键字序列为{5,88,12,56,71,28,33,43,93,17}，哈希表长为13，哈希函数为H(key)=key%13，请用线性探测再散列、二次线性探测再散列以及链地址法解决冲突构造这组关键字的哈希表，并计算查找成功时的平均查找长度。请编写C++代码实现上述功能

线性探测再散列：

#include <iostream>
#define MAXSIZE 13
using namespace std;

int hashTable[MAXSIZE] = {0};

void insert(int key) {
    int pos = key % MAXSIZE;
    if (hashTable[pos] == 0) {
        hashTable[pos] = key;
    } else {
        int i = 1;
        while (hashTable[(pos + i) % MAXSIZE] != 0) {
            i++;
        }
        hashTable[(pos + i) % MAXSIZE] = key;
    }
}

int search(int key) {
    int pos = key % MAXSIZE;
    int i = 0;
    while (hashTable[(pos + i) % MAXSIZE] != key) {
        i++;
        if (hashTable[(pos + i) % MAXSIZE] == 0 || i == MAXSIZE) {
            return -1;
        }
    }
    return (pos + i) % MAXSIZE;
}

int main() {
    int arr[10] = {5,88,12,56,71,28,33,43,93,17};
    for (int i = 0; i < 10; i++) {
        insert(arr[i]);
    }
    for (int i = 0; i < MAXSIZE; i++) {
        cout << hashTable[i] << " ";
    }
    cout << endl;
    int pos = search(33);
    if (pos != -1) {
        cout << "Find key 33 at position " << pos << endl;
    } else {
        cout << "Key 33 not found" << endl;
    }
    return 0;
}

二次线性探测再散列：

#include <iostream>
#define MAXSIZE 13
using namespace std;

int hashTable[MAXSIZE] = {0};

void insert(int key) {
    int pos = key % MAXSIZE;
    if (hashTable[pos] == 0) {
        hashTable[pos] = key;
    } else {
        int i = 1;
        while (hashTable[(pos + i*i) % MAXSIZE] != 0) {
            i++;
        }
        hashTable[(pos + i*i) % MAXSIZE] = key;
    }
}

int search(int key) {
    int pos = key % MAXSIZE;
    int i = 0;
    while (hashTable[(pos + i*i) % MAXSIZE] != key) {
        i++;
        if (hashTable[(pos + i*i) % MAXSIZE] == 0 || i == MAXSIZE) {
            return -1;
        }
    }
    return (pos + i*i) % MAXSIZE;
}

int main() {
    int arr[10] = {5,88,12,56,71,28,33,43,93,17};
    for (int i = 0; i < 10; i++) {
        insert(arr[i]);
    }
    for (int i = 0; i < MAXSIZE; i++) {
        cout << hashTable[i] << " ";
    }
    cout << endl;
    int pos = search(33);
    if (pos != -1) {
        cout << "Find key 33 at position " << pos << endl;
    } else {
        cout << "Key 33 not found" << endl;
    }
    return 0;
}

链地址法：

#include <iostream>
#include <vector>
#define MAXSIZE 13
using namespace std;

struct Node {
    int val;
    Node* next;
    Node(int x) : val(x), next(NULL) {}
};

vector<Node*> hashTable(MAXSIZE, NULL);

void insert(int key) {
    int pos = key % MAXSIZE;
    if (hashTable[pos] == NULL) {
        hashTable[pos] = new Node(key);
    } else {
        Node* p = hashTable[pos];
        while (p->next != NULL) {
            p = p->next;
        }
        p->next = new Node(key);
    }
}

int search(int key) {
    int pos = key % MAXSIZE;
    Node* p = hashTable[pos];
    int cnt = 0;
    while (p != NULL) {
        if (p->val == key) {
            return cnt;
        }
        p = p->next;
        cnt++;
    }
    return -1;
}

int main() {
    int arr[10] = {5,88,12,56,71,28,33,43,93,17};
    for (int i = 0; i < 10; i++) {
        insert(arr[i]);
    }
    for (int i = 0; i < MAXSIZE; i++) {
        cout << i << ": ";
        Node* p = hashTable[i];
        while (p != NULL) {
            cout << p->val << " ";
            p = p->next;
        }
        cout << endl;
    }
    int cnt = search(33);
    if (cnt != -1) {
        cout << "Find key 33, search " << cnt+1 << " times" << endl;
    } else {
        cout << "Key 33 not found" << endl;
    }
    return 0;
}

其中，查找成功时的平均查找长度为指定关键字的查找长度之和与关键字总数的商。