本数据结构实验旨在通过实现和分析哈希表，探讨其在处理大规模数据集中的效率与性能，涵盖冲突解决策略等核心概念。
### 一. 设计课题：哈希表设计
#### 需求分析：
**目的与任务**
根据数据元素的关键字及所给定的哈希函数建立并初始化哈希表，并利用开放地址法解决冲突问题，通过屏幕输出的功能菜单选择所需功能来实现对数据元素在哈希表中的插入、显示、查找和删除操作。初始化时将`elem[MAXSIZE]`, `elemflag[MAXSIZE]`以及计数器`count`置为0。
**程序需求**
输入一组个数不超过哈希表最大长度的数据，根据其关键字及给定的哈希函数将其存入哈希表中，并在发生冲突的情况下使用开放地址法解决。提供插入、显示、查找和删除数据元素的功能。
#### 实验概要设计：
定义ADT HashTable如下：
- **数据对象**：D1={ai| ai∈elem[MAXSIZE], i=0, 1, ..., n}，其中`MAXSIZE`为哈希表长度。
- D2={ai | ai ∈ elemflag[MAXSIZE]}是记录哈希表中每个位置是否已存放关键字的标志集合。
#### 基本操作：
1. **Hash(key)**：根据给定的关键字计算并返回其对应的哈希地址。
2. **Search(H, key)**：在哈希表H中查找指定键值key，如果找到则返回true，否则返回false。
3. **Insert(H, key)**：将数据元素插入到哈希表中。若已存在相同关键字，则输出已有此数!并失败退出；成功时计数器加一，并更新状态标志位。
4. **Delete(H, key)**：从哈希表H中删除指定键值key的数据项，返回是否删除成功的信息。
5. **Display(H)**：显示整个哈希表的内容。
#### 主要函数实现：
- 初始化哈希表
- 创建并填充哈希表（插入数据）
- 显示当前状态的哈希表内容
- 查找特定关键字是否存在
- 删除指定的关键字
### 二．程序代码：
```cpp
#include
using namespace std;
const int MAXSIZE = 10; // 假设的最大长度为10，实际使用时可根据需要调整大小。
typedef struct {
int key;
bool flag; // 标记位：未使用、已占用或已被删除的状态。
} HashNode, *HashTable[MAXSIZE];
// 初始化哈希表
void Initialize(HashTable &H) {
for (int i = 0; i < MAXSIZE; ++i)
H[i] = nullptr;
}
// 插入操作，如果关键字已经存在则输出提示信息并返回失败。
bool Insert(HashTable &H, int key) {
if (!Search(H, key)) { // 若未找到该键值
HashNode *p = new HashNode{key, true}; // 创建新节点，并设置状态为true表示已占用；
H[key % MAXSIZE] = p; // 根据哈希函数计算地址并插入。
} else {
cout << 已有此数! << endl;
return false;
}
}
// 查找操作
bool Search(HashTable &H, int key) {
HashNode *p = H[key % MAXSIZE];
while (p != nullptr && p->flag == true)
if(p->key == key) break; // 如果找到，结束循环。
else p = H[++key % MAXSIZE]; // 若未找到，则继续查找下一个地址（线性探测）。
return p != nullptr && p->flag;
}
// 显示哈希表内容
void Display(HashTable &H) {
cout << Hash table address: ;
for (int i = 0; i < MAXSIZE; ++i)
if(H[i] == nullptr || !H[i]->flag) // 如果位置为空或状态为未使用，则显示空。
cout << NULL ;
else
cout << H[i]->key << (<< i <<); // 显示关键字及地址。
cout << endl;
}
// 删除操作，成功则返回true；否则提示并返回false。
bool Delete(HashTable &H, int key) {
HashNode *p = nullptr; // 搜索目标元素
Search(H, key); // 先查找该键值的位置
if (p != nullptr && p->flag == true) { // 如果找到了且状态为已使用，则更新其标志位。
p->flag = false;
return true;
} else {
cout << 无此数! << endl; // 若未找到或已被删除，提示并返回失败信息。
return false;
}
}
int main() {
Hash
5星
