建立关键字序列(16,74,60,43,54,90,46,31,29,88,77)对应的哈希表A[0..12],哈希函数为 H(k)=k%p,并采用开放地址法中的线性探测法解决冲突。
时间: 2023-09-25 14:10:22 浏览: 97
假设人名为中国人姓名的汉语拼音形式。待填入哈希表的人名共有30个,取平均查找长度的上限为2。哈希函数采用除留余数法构造,用线性探测再散列法处理冲突。
好的,根据您的要求,我会回答您的问题,同时不会透露您的要求。
根据您给出的关键字序列和哈希函数H(k)=k%p,我们可以先选取一个合适的质数p,假设我们选择p=13。
接下来,我们可以根据哈希函数将关键字映射到哈希表中的位置。具体的计算方法是:对于每个关键字k,计算H(k)的值,然后将其作为关键字在哈希表中的位置。如果该位置已经被占用,则采用线性探测法,沿着哈希表的下一个位置继续查找,直到找到一个空闲位置。
下面是具体的过程:
1. 初始化哈希表A[0..12]为空表。
2. 对于每个关键字k,计算H(k)的值,并将其作为关键字在哈希表中的位置。如果该位置已经被占用,则采用线性探测法,沿着哈希表的下一个位置继续查找,直到找到一个空闲位置。
关键字k H(k)=k%p 在哈希表中的位置
------------------------------------------------
16 3 A[3]
74 10 A[10]
60 8 A[8]
43 4 A[4]
54 2 A[2]
90 0 A[0]
46 7 A[7]
31 5 A[5]
29 3* A[4] (冲突,线性探测)
88 4* A[5] (冲突,线性探测)
77 11 A[11]
*表示该位置已经被占用,需要继续线性探测。
3. 最终的哈希表A[0..12]如下:
A[0]:90
A[1]:
A[2]:54
A[3]:16
A[4]:43
A[5]:31
A[6]:
A[7]:46
A[8]:60
A[9]:
A[10]:74
A[11]:77
A[12]:
这就是将关键字序列(16,74,60,43,54,90,46,31,29,88,77)对应的哈希表A[0..12],哈希函数为 H(k)=k%p,并采用开放地址法中的线性探测法解决冲突的具体过程。
阅读全文