给我以下问题的源代码:1、设计一个哈希表ha[0……m-1],其中m=18,存放(19,1,23,14,55,20,84,27,68,11,10,77)n个元素,其中:哈希函数采用除留余数法H(key)=key%p(p=13),解决冲突的方法采用开放地址法的线性探测法。设计哈希表的类型,并编程实现哈希表的创建;设计并编程实现在哈希表中查找指定关键字的算法;在查找等概率的情况下,分析算法的平均查找长;
时间: 2024-03-09 21:46:03 浏览: 15
完整代码如下:
```c++
#include <iostream>
using namespace std;
#define m 18 //哈希表长度
#define p 13 //除留余数法的除数
//哈希表结构体
typedef struct {
int key; //关键字
int value; //值
} HashNode;
//哈希表类型
typedef struct {
HashNode data[m]; //哈希表数组
int count; //哈希表中元素个数
} HashTable;
//初始化哈希表
void initHashTable(HashTable& ht) {
ht.count = 0;
for (int i = 0; i < m; i++) {
ht.data[i].key = -1; //初始化关键字为-1
}
}
//哈希函数
int hashFunction(int key) {
return key % p;
}
//插入元素到哈希表中
void insertHashTable(HashTable& ht, int key, int value) {
int index = hashFunction(key); //计算哈希值
while (ht.data[index].key != -1) { //处理冲突
index = (index + 1) % m; //线性探测法
}
ht.data[index].key = key;
ht.data[index].value = value;
ht.count++;
}
//创建哈希表
void createHashTable(HashTable& ht, int arr[], int n) {
initHashTable(ht);
for (int i = 0; i < n; i++) {
insertHashTable(ht, arr[i], arr[i]);
}
}
//在哈希表中查找指定关键字,返回对应的值
int findHashTable(HashTable& ht, int key) {
int index = hashFunction(key); //计算哈希值
while (ht.data[index].key != -1) { //处理冲突
if (ht.data[index].key == key) {
return ht.data[index].value;
}
index = (index + 1) % m; //线性探测法
}
return -1; //未找到返回-1
}
int main() {
int arr[] = {19,1,23,14,55,20,84,27,68,11,10,77};
int n = sizeof(arr) / sizeof(arr[0]);
HashTable ht;
createHashTable(ht, arr, n);
int key = 84;
int value = findHashTable(ht, key);
if (value != -1) {
cout << "在哈希表中找到了 " << key << " 对应的值为 " << value << endl;
} else {
cout << "在哈希表中未找到 " << key << endl;
}
//计算平均查找长度
double ASL = 0.0;
for (int i = 1; i <= n; i++) {
ASL += 0.5 * (1 + 1.0 / (1 - i));
}
ASL /= n;
cout << "平均查找长度为 " << ASL << endl;
return 0;
}
```