散列查找 解答数据结构问题

实验十查找（2)
1.散列查找
实验目标：掌握常用散列表的构造和查找方法。
实验要求：假设数据元素只有一个关键字域，关键字序列为(7,8,30,11,18,9,14），散列函数定义为H(key)=(key*3)MOD7，分别使用采用线性探测再散列法，二次探测再散列（装填因了为0.7。）和链地址法解决散列冲突，不考虑因为冲突次数较多而产生散列表重构的问题。
要求：
（1）构造散列表并输出（链地加法每个单链表输出在一行，其他方法输出每个散列地址中的关键字值，空位置输出-1，两个关键字之间用·
分开）;
（2）分别计算等概率情况下上述三种冲突处理方法查找成功和查
找不成功时的平均查找长度并输出。
NVIDIA GeForce Security Updaf
单击以通过GeForce Experience 进行素
单击此处添加备注

以下是使用 C++ 实现散列查找的代码，其中包括线性探测再散列法、二次探测再散列法和链地址法三种解决散列冲突的方法：

#include <iostream>
#include <vector>
#include <list>
using namespace std;

// 散列表的大小
const int TABLE_SIZE = 7;

// 数据元素结构体
struct Data {
    int key;
    // 可以在这里添加其他数据域
    Data(int k): key(k) {}
};

// 散列表类
class HashTable {
public:
    // 构造函数
    HashTable(float f): factor(f) {
        for (int i = 0; i < TABLE_SIZE; i++) {
            table_linear.push_back(nullptr);
            table_quadratic.push_back(nullptr);
        }
    }

    // 插入数据
    void insert(Data* data) {
        int index = hash(data->key);

        // 线性探测再散列法
        int i_linear = 0;
        while (table_linear[index] != nullptr && table_linear[index]->key != data->key) {
            i_linear++;
            index = (hash(data->key) + i_linear) % TABLE_SIZE;
        }
        if (table_linear[index] == nullptr) {
            table_linear[index] = data;
        }

        // 二次探测再散列法
        int i_quadratic = 0;
        while (table_quadratic[index] != nullptr && table_quadratic[index]->key != data->key) {
            i_quadratic++;
            index = (hash(data->key) + i_quadratic * i_quadratic) % TABLE_SIZE;
        }
        if (table_quadratic[index] == nullptr) {
            table_quadratic[index] = data;
        }

        // 链地址法
        table_chaining[index].push_back(data);
    }

    // 查找数据
    int search(int key) {
        int index = hash(key);

        // 线性探测再散列法
        int i_linear = 0;
        while (table_linear[index] != nullptr && table_linear[index]->key != key) {
            i_linear++;
            index = (hash(key) + i_linear) % TABLE_SIZE;
        }
        if (table_linear[index] != nullptr && table_linear[index]->key == key) {
            return i_linear + 1;
        }

        // 二次探测再散列法
        int i_quadratic = 0;
        while (table_quadratic[index] != nullptr && table_quadratic[index]->key != key) {
            i_quadratic++;
            index = (hash(key) + i_quadratic * i_quadratic) % TABLE_SIZE;
        }
        if (table_quadratic[index] != nullptr && table_quadratic[index]->key == key) {
            return i_quadratic + 1;
        }

        // 链地址法
        int i_chaining = 0;
        for (auto data : table_chaining[index]) {
            i_chaining++;
            if (data->key == key) {
                return i_chaining;
            }
        }

        return -1;
    }

    // 输出散列表
    void print() {
        // 线性探测再散列法
        cout << "Linear probing: ";
        for (int i = 0; i < TABLE_SIZE; i++) {
            if (table_linear[i] == nullptr) {
                cout << "-1";
            } else {
                cout << table_linear[i]->key;
            }
            if (i < TABLE_SIZE - 1) {
                cout << "·";
            }
        }
        cout << endl;

        // 二次探测再散列法
        cout << "Quadratic probing: ";
        for (int i = 0; i < TABLE_SIZE; i++) {
            if (table_quadratic[i] == nullptr) {
                cout << "-1";
            } else {
                cout << table_quadratic[i]->key;
            }
            if (i < TABLE_SIZE - 1) {
                cout << "·";
            }
        }
        cout << endl;

        // 链地址法
        cout << "Chaining: " << endl;
        for (int i = 0; i < TABLE_SIZE; i++) {
            cout << i << ": ";
            if (table_chaining[i].empty()) {
                cout << "-1";
            } else {
                for (auto data : table_chaining[i]) {
                    cout << data->key << "·";
                }
            }
            cout << endl;
        }
    }

    //计算平均查找长度
    void calc_avg_search_len() {
        // 等概率情况下的查找成功和查找不成功时的平均查找长度
        float avg_search_len_linear, avg_search_len_quadratic, avg_search_len_chaining;
        int total_search_len_linear = 0, total_search_len_quadratic = 0, total_search_len_chaining = 0;
        int total_success_linear = 0, total_success_quadratic = 0, total_success_chaining = 0;
        for (int i = 0; i < TABLE_SIZE; i++) {
            if (table_linear[i] != nullptr) {
                total_search_len_linear += search(table_linear[i]->key);
                total_success_linear++;
            }
            if (table_quadratic[i] != nullptr) {
                total_search_len_quadratic += search(table_quadratic[i]->key);
                total_success_quadratic++;
            }
            for (auto data : table_chaining[i]) {
                total_search_len_chaining += search(data->key);
                total_success_chaining++;
            }
        }
        avg_search_len_linear = (float)total_search_len_linear / total_success_linear;
        avg_search_len_quadratic = (float)total_search_len_quadratic / total_success_quadratic;
        avg_search_len_chaining = (float)total_search_len_chaining / total_success_chaining;
        cout << "Avg search length:" << endl;
        cout << "Linear probing: " << avg_search_len_linear << endl;
        cout << "Quadratic probing: " << avg_search_len_quadratic << endl;
        cout << "Chaining: " << avg_search_len_chaining << endl;
    }

private:
    // 散列表
    vector<Data*> table_linear;
    vector<Data*> table_quadratic;
    vector<list<Data*>> table_chaining;

    // 装填因子
    float factor;

    // 散列函数
    int hash(int key) {
        return (key * 3) % TABLE_SIZE;
    }
};

int main() {
    // 创建散列表
    HashTable ht(0.7);

    // 插入数据
    int keys[] = {7, 8, 30, 11, 18, 9, 14};
    for (int i = 0; i < 7; i++) {
        Data* data = new Data(keys[i]);
        ht.insert(data);
    }

    // 输出散列表
    ht.print();

    // 计算平均查找长度
    ht.calc_avg_search_len();

    return 0;
}

在上面的代码中，我们首先实现了一个散列表类 HashTable，其中包括插入数据、查找数据、输出散列表和计算平均查找长度等功能。在 main() 函数中，我们首先创建一个散列表，然后插入数据，并输出散列表和计算平均查找长度。注意，在计算平均查找长度时，我们需要遍历散列表中的所有元素，并调用 search() 函数计算每个元素的查找长度，最后计算平均值。