数据结构实验报告8--哈希表的建立与查找_哈希表 数据结构实验报告

实验内容及要求：

编写控制台应用程序，提供以下菜单项：

1. 插入关键字
2. 删除关键字
3. 查找关键字
4. 结束程序

其中，“插入关键字”是指从键盘输入一个关键字，将关键字插入哈希表中，若插入的关键字已存储于哈希表中，则插入失败，显示提示信息；若插入关键字数目已超过哈希表设计容量，则插入失败，显示提示信息；其它情况则插入成功，显示提示信息。程序初始运行时，哈希表为空，通过插入多个关键字建立哈希表。

“删除关键字”是指从键盘输入一个关键字，若在哈希表中查找成功，则将关键字从哈希表中删除；若查找失败，显示提示信息。

“查找关键字”是指从键盘输入一个关键字，在哈希表中查找，显示查找成功与失败的提示信息。

已知哈希函数H(K)=K mod m，其中m为哈希表长度（程序中m应不小于10）。可选择用二次探测再散列或链地址法解决冲突。若选用二次探测再散列，装填因子设为0.8；若选用链地址法，要求哈希表允许的关键字最大数目为2m。

提示：选用二次探测再散列时，空闲元素位置应存入“哑元素”占位，以标识元素位置空闲。

参考博客:(4条消息) 西南交通大学数据结构第八次实验--哈希表的建立与查找_Jellyfish Knight的博客-CSDN博客 

#define _CRT_SECURE_NO_WARNINGS 1
#include<iostream>
 
using namespace std;
 
struct Node {
    int data = -1;
    bool flag = false;
    Node* next = nullptr;
};
 
 
class Menu {
private:
    Node* hash_map;
    int max_length;//哈希表总长度
    int cur_length;//哈希表当前长度
 
    int HashFunction(int key) const;
 
    static void ShowMenu();
 
    void Insert();
 
    void Delete();
 
    void Inquire();
 
public:
    Menu(int length);
 
    void Test();
 
    ~Menu() {
        delete hash_map;
    }
 
};
 
Menu::Menu(int length) {
    while (length < 10) {
        cout << "哈希表长度需要不小于10！请重新输入！" << endl;
        cin >> length;
    }
    max_length = length;
    hash_map = new Node[length];
    cur_length = 0;
}
//哈希函数
int Menu::HashFunction(int key) const {
    return key % max_length;
}
//菜单展示
void Menu::ShowMenu() {
    cout << "============================================" << endl;
	cout << "1.	插入关键字: " << endl;
	cout << "2.	删除关键字: " << endl;
	cout << "3.	查找关键字: " << endl;
	cout << "4.	结束程序: " << endl;
	cout << "5.	清屏: " << endl;
	cout << "============================================" << endl;
}
//插入关键字
void Menu::Insert() {
    int key;
    cout << "请输入要插入的关键字: ";
    cin >> key;
    int position = HashFunction(key);//通过哈希函数计算位置
    auto p = &hash_map[position];
    if (cur_length + 1 > 2 * max_length) {
        cout << "当前长度已超过允许长度!!!" << endl;
        cout << "插入失败!!!" << endl;
        return;
    }
    //先判断关键字是否存在
    if (p->flag) {
        if (p->data == key) {
            cout << "插入失败!!!当前关键字已存在!!!" << endl;
            return;
        }
        else {
            //解决冲突
            while (p) {
                if (p->data == key) {
                    cout << "插入失败!!!当前关键字已存在!!!" << endl;
                    return;
                }
                else {
                    if (p->next) {
                        p = p->next;
                    }
                    else {
                        auto new_node = new Node;
                        new_node->data = key;
                        new_node->flag = true;
                        p->next = new_node;
                        cur_length++;
                        break;
                    }
                }
            }
        }
    }
    //不存在则直接插入
    else {
        hash_map[position].data = key;
        hash_map[position].flag = true;
        cur_length++;
    }
    cout << "插入关键字: " << key << " 成功!!!" << endl;
}
 
void Menu::Delete() {
    int key;
    cout << "请输入需要删除的关键字: ";
    cin >> key;
    int position = HashFunction(key);
    auto p1 = &hash_map[position];
    auto p2 = &hash_map[position];
    bool flag = false;//只要找到待删除的关键字,则令flag为1
    while (p1 && p1->flag) {
        //删除不是解决冲突后的元素
        if (p1->data == key) {
            if (p1 == p2) {
                //如果p1指针指向不为空,则让当前哈希表中的值为p1指针所指向的值
                if (p1->next) {
                    hash_map[position] = *p1->next;
                    flag = true;
                    break;
                }
                //如果p1指针指向NULL,则直接删除当前的值
                else {
                    p1->flag = false;
                    p1->data = -1;
                    flag = true;
                    break;
                }
            }
            else {
                if (p1->next) {
                    p2->next = p1->next;
                    p1->next = nullptr;
                    flag = true;
                    delete p1;
                    break;
                }
                else {
                    p2->next = nullptr;
                    flag = true;
                    delete p1;
                    break;
                }
            }
        }
        //删除的是解决冲突后的元素
        else {
            p1 = p1->next;
            p2 = p1;
        }
    }
    if (!flag) {
        cout << "删除关键字 " << key << " 失败!!!因为它不存在!!!" << endl;
    }
    else {
        cur_length--;
        cout << "删除成功!!!" << endl;
    }
}
 
void Menu::Inquire() {
    int key;
    cout << "请输入要查询的关键字: " << endl;
    cin >> key;
    int position = HashFunction(key);
    auto p1 = &hash_map[position];
    int flag = false;
    while (p1 && p1->flag ) {
        if (p1->data == key) {
            flag = true;
            break;
        }
        else {
            p1 = p1->next;
        }
    }
    if (flag) {
        cout << "查询成功!!!" << endl;
        cout << "关键字" << key << " 在哈希表中!" << endl;
    }
    else {
        cout << "查询失败!" << endl;
        cout << "关键字" << key << " 不在哈希表中!" << endl;
 
    }
}
 
void Menu::Test() {
    int choice;
    ShowMenu();
    while (true) {
        
        cin >> choice;
        switch (choice) {
        case 1:
            Insert();
            break;
        case 2:
            Delete();
            break;
        case 3:
            Inquire();
            break;
        case 4:
            cout << "退出成功!!!" << endl;
            exit(0);
        case 5: {
            system("cls"); 
            ShowMenu();
            break;
            }
        default:
            break;
        }
    }
}
 
int main() {
    int m;
    cout << "请输入哈希表的长度m: " << endl;
    cin >> m;
    Menu menu(m);
    menu.Test();
    return 0;
}