4.对于关键字序列a[]={21,34,5 ,67 ,89 ,100,76 ,88 ,94 ,65,77,53 ,66,70,98}, 请为其选 择哈希函数及开放地址法处理冲突的线性探测函数,构造哈希表。
时间: 2023-08-19 12:36:33 浏览: 122
为了构造哈希表,我们需要先选择一个哈希函数和一种处理冲突的方法。对于给定的关键字序列a,我们可以选择简单的取模哈希函数,即将关键字除以一个较大的素数p,取余数作为哈希地址。
假设我们选择素数p=31,那么可以得到以下哈希函数:
```
int hashFunc(int key) {
return key % 31;
}
```
接下来选择一种处理冲突的方法,我们可以选择线性探测法,即当发生哈希地址冲突时,依次往后寻找下一个空闲位置,直到找到一个空闲位置为止。
根据以上哈希函数和处理冲突的方法,我们可以构造一个大小为15的哈希表,并将关键字序列a插入到哈希表中。插入过程中,如果发生冲突,就采用线性探测法往后寻找空闲位置。
以下是C语言的示例代码:
```
int hashFunc(int key) {
return key % 31;
}
int linearProbe(int key, int i) {
return (hashFunc(key) + i) % 15;
}
void insert(int hashTable[], int key) {
int i = 0;
int pos = linearProbe(key, i);
while(hashTable[pos] != -1) {
i++;
pos = linearProbe(key, i);
}
hashTable[pos] = key;
}
int main() {
int a[] = {21,34,5,67,89,100,76,88,94,65,77,53,66,70,98};
int hashTable[15];
memset(hashTable, -1, sizeof(hashTable));
for(int i = 0; i < 15; i++) {
insert(hashTable, a[i]);
}
return 0;
}
```
在上面的代码中,我们定义了一个大小为15的哈希表,初始值全部设置为-1,表示该位置为空。然后逐个将关键字插入到哈希表中,如果发生冲突,就采用线性探测法寻找下一个空闲位置。最终,哈希表中的元素如下:
```
hashTable[] = {21, -1, 34, 5, 67, 88, 76, 89, -1, 94, 65, 77, 53, 66, 70}
```
可以看到,哈希表中的元素已经按照哈希函数的规则插入到了各个位置,并且冲突也被处理了。
阅读全文