5、哈希表的设计与实现——链地址法 问题描述： 设计哈希表实现电话号码查找系统。 基本要求： (1)设每个记录有下列数据项：电话号码、用户名、地址； (2)从键盘输入各记录，分别以电话号码和用户名为关键字建立不同的哈希表； (3)采用链地址法解决冲突； (4)查找并显示给定电话号码的记录； (5)查找并显示给定用户名的记录。(c++代码）

以下是基于链地址法的哈希表实现电话号码查找系统的 C++ 代码：

#include <iostream>
#include <string>
#define MAX_SIZE 100 // 哈希表的最大长度

using namespace std;

// 记录类
class Record {
public:
    string phone;
    string name;
    string address;
};

// 链表节点类
class ListNode {
public:
    Record data;
    ListNode* next;
};

// 哈希表类
class HashTable {
private:
    int size; // 哈希表长度
    ListNode* table[MAX_SIZE]; // 哈希表数组
    int Hash(string key); // 哈希函数
public:
    HashTable(); // 构造函数
    ~HashTable(); // 析构函数
    void Insert(Record rec); // 插入记录
    Record* FindByPhone(string phone); // 根据电话号码查找记录
    Record* FindByName(string name); // 根据用户名查找记录
};

// 哈希函数
int HashTable::Hash(string key) {
    int sum = 0;
    for (int i = 0; i < key.size(); i++) {
        sum += key[i];
    }
    return sum % size;
}

// 构造函数
HashTable::HashTable() {
    size = MAX_SIZE;
    for (int i = 0; i < size; i++) {
        table[i] = nullptr;
    }
}

// 析构函数
HashTable::~HashTable() {
    for (int i = 0; i < size; i++) {
        ListNode* p = table[i];
        while (p != nullptr) {
            ListNode* q = p->next;
            delete p;
            p = q;
        }
    }
}

// 插入记录
void HashTable::Insert(Record rec) {
    int index = Hash(rec.phone);
    ListNode* p = table[index];
    ListNode* q = nullptr;
    while (p != nullptr) {
        q = p;
        p = p->next;
    }
    p = new ListNode;
    p->data = rec;
    p->next = nullptr;
    if (q == nullptr) {
        table[index] = p;
    } else {
        q->next = p;
    }
}

// 根据电话号码查找记录
Record* HashTable::FindByPhone(string phone) {
    int index = Hash(phone);
    ListNode* p = table[index];
    while (p != nullptr) {
        if (p->data.phone == phone) {
            return &p->data;
        }
        p = p->next;
    }
    return nullptr;
}

// 根据用户名查找记录
Record* HashTable::FindByName(string name) {
    for (int i = 0; i < size; i++) {
        ListNode* p = table[i];
        while (p != nullptr) {
            if (p->data.name == name) {
                return &p->data;
            }
            p = p->next;
        }
    }
    return nullptr;
}

int main() {
    HashTable phoneBook; // 创建电话簿哈希表

    // 从键盘输入记录，并插入哈希表中
    Record rec;
    cout << "请输入每个记录的电话号码、用户名和地址，以空格分隔：" << endl;
    for (int i = 0; i < MAX_SIZE; i++) {
        cin >> rec.phone >> rec.name >> rec.address;
        if (rec.phone == "0") {
            break; // 输入0结束输入
        }
        phoneBook.Insert(rec);
    }

    // 根据电话号码查找记录
    string phoneNum;
    cout << "请输入要查找的电话号码：" << endl;
    cin >> phoneNum;
    Record* pRec = phoneBook.FindByPhone(phoneNum);
    if (pRec == nullptr) {
        cout << "未找到该电话号码的记录。" << endl;
    } else {
        cout << "电话号码：" << pRec->phone << endl;
        cout << "用户名：" << pRec->name << endl;
        cout << "地址：" << pRec->address << endl;
    }

    // 根据用户名查找记录
    string userName;
    cout << "请输入要查找的用户名：" << endl;
    cin >> userName;
    pRec = phoneBook.FindByName(userName);
    if (pRec == nullptr) {
        cout << "未找到该用户名的记录。" << endl;
    } else {
        cout << "电话号码：" << pRec->phone << endl;
        cout << "用户名：" << pRec->name << endl;
        cout << "地址：" << pRec->address << endl;
    }

    return 0;
}

注意：本代码实现中使用了固定长度的哈希表，若要实现动态扩容，需要考虑重新哈希的问题。