已知散列函数为H(key)=key%p(p为自定的常数),冲突处理方法分别为线性探测法、拉链法实现散列表的建立(利用插入算法实现),并输出某一关键字(自己给定)的查找结果及探测次数。 用C++写出代码
时间: 2024-03-18 10:41:14 浏览: 14
下面是一个简单的 C++ 实现,可以实现散列表的建立和关键字的查找:
```cpp
#include <iostream>
using namespace std;
const int MAXSIZE = 100; // 散列表的最大长度
const int EMPTY = -1; // 空单元的标记
// 散列表中的数据元素
typedef struct {
int key; // 关键字域
// 其他数据域
} ElemType;
// 散列表
typedef struct {
ElemType elem[MAXSIZE]; // 数据元素
int count; // 散列表中已存数据元素个数
} HashTable;
// 线性探测法
int LinearProbe(int p, int i) {
return i; // 直接返回下一个单元
}
// 拉链法
int Chain(int p, int i) {
return (p + i) % MAXSIZE; // 返回散列地址
}
// 插入元素到散列表中
void Insert(HashTable& H, int key, int (*f)(int, int)) {
int i = 0, addr;
do {
addr = (*f)(key, i++);
} while (H.elem[addr].key != EMPTY && i < MAXSIZE); // 寻找第一个空单元
if (i >= MAXSIZE) {
cout << "散列表已满,插入失败!" << endl;
return;
}
H.elem[addr].key = key; // 在空单元中插入关键字
H.count++; // 散列表中已存数据元素个数加 1
}
// 在散列表中查找关键字
int Search(HashTable H, int key, int (*f)(int, int)) {
int i = 0, addr;
do {
addr = (*f)(key, i++);
if (H.elem[addr].key == key) {
return addr; // 查找成功,返回关键字在散列表中的位置
}
} while (H.elem[addr].key != EMPTY && i < MAXSIZE);
return -1; // 查找失败,返回 -1
}
int main() {
HashTable H;
H.count = 0; // 初始时散列表中已存数据元素个数为 0
// 初始化散列表
for (int i = 0; i < MAXSIZE; i++) {
H.elem[i].key = EMPTY;
}
// 插入数据元素
int p, n;
cout << "请输入常数 p:";
cin >> p;
cout << "请输入数据元素个数:";
cin >> n;
cout << "请输入数据元素的关键字:" << endl;
for (int i = 0; i < n; i++) {
int key;
cin >> key;
Insert(H, key, LinearProbe); // 这里使用线性探测法
}
// 查找关键字
int key;
cout << "请输入要查找的关键字:";
cin >> key;
int pos = Search(H, key, LinearProbe); // 这里使用线性探测法
if (pos == -1) {
cout << "查找失败!" << endl;
} else {
cout << "查找成功!关键字在散列表中的位置为:" << pos << endl;
}
return 0;
}
```
在程序中,我们首先定义了一个 `HashTable` 结构体表示散列表,其中包含一个 `elem` 数组存储数据元素和一个 `count` 变量表示已存数据元素个数。然后,我们实现了两种冲突处理方法的散列函数 `LinearProbe` 和 `Chain`,以及插入元素到散列表中的 `Insert` 函数和在散列表中查找关键字的 `Search` 函数。在 `main` 函数中,我们先读入常数 `p` 和数据元素个数,然后使用 `Insert` 函数插入数据元素。最后,根据查找结果输出相应信息。需要注意的是,我们在这里只使用了线性探测法和插入算法进行散列表的建立和关键字的查找,拉链法的实现和使用类似,这里不再赘述。