设散列表的地址区间为[0,16],散列函数为h(key)=key%17。采用线性探测法处理冲突,并将关键字序列{ 26,25,72,38,8,18,59 }依次存储到散列表中。元素59存放在散列表中的地址是:
时间: 2023-06-05 17:47:20 浏览: 1062
元素59存放在散列表中的地址是3。
解释:
根据散列函数h(key)=key%17,可以得到每个关键字的散列地址:
26%17=9
25%17=8
72%17=4
38%17=4
8%17=8
18%17=1
59%17=3
由于采用线性探测法处理冲突,当发生冲突时,会依次往后查找空闲的地址,直到找到一个空闲地址为止。
因此,元素59在散列表中的地址为3。
相关问题
设散列表的地址范围为0~17散列函数为H(key)=key%16,用线性探测法处理冲突输入关键字序列(10,24,32,17,31,30,46,47,40,63,49)画出线性探测,链地址法,哈希表三个图
好的,我会根据你的要求进行处理。首先,我们来看一下线性探测法处理冲突的过程。
1. 散列函数 H(key) = key % 16
2. 输入关键字序列(10,24,32,17,31,30,46,47,40,63,49)
3. 用线性探测法进行处理,发生冲突的关键字在散列表中依次向后查找,直到找到一个空的位置为止。
下面是线性探测法处理冲突的图示:
```
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17
----------------------------------------------------------------------------
0 |10|24|32| | | | | | | | | | | | | | | |
----------------------------------------------------------------------------
1 |17| | | | | | | | | | | | | | | | | |
----------------------------------------------------------------------------
2 |31|30| | | | | | | | | | | | | | | | |
----------------------------------------------------------------------------
3 |46|47| | | | | | | | | | | | | | | | |
----------------------------------------------------------------------------
4 |40| | | | | | | | | | | | | | | | | |
----------------------------------------------------------------------------
5 | | | | | | | | | | | | | | | | | | |
----------------------------------------------------------------------------
6 | | | | | | | | | | | | | | | | | | |
----------------------------------------------------------------------------
7 | | | | | | | | | | | | | | | | | | |
----------------------------------------------------------------------------
8 | | | | | | | | | | | | | | | | | | |
----------------------------------------------------------------------------
9 | | | | | | | | | | | | | | | | | | |
----------------------------------------------------------------------------
10| | | | | | | | | | |49 | | | | | | |63 |
----------------------------------------------------------------------------
```
接下来,我们再来看一下链地址法处理冲突的过程。
1. 散列函数 H(key) = key % 16
2. 输入关键字序列(10,24,32,17,31,30,46,47,40,63,49)
3. 用链地址法进行处理,发生冲突的关键字在散列表中的位置上形成一个链表,每个链表节点存储一个关键字。
下面是链地址法处理冲突的图示:
```
0 -> 10 -> 40
1 -> 17
2 -> 32 -> 47
3 -> 63
4
5 -> 30 -> 46
6
7 -> 31
8
9 -> 24
10
11
12
13
14
15
16
17
```
最后,我们再来看一下哈希表处理冲突的过程。
1. 散列函数 H(key) = key % 16
2. 输入关键字序列(10,24,32,17,31,30,46,47,40,63,49)
3. 用哈希表进行处理,发生冲突的关键字在散列表中的位置上形成一个链表,每个链表节点存储一个关键字。
下面是哈希表处理冲突的图示:
```
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17
----------------------------------------------------------------------------
0 |10| | | | | | | | | | | | | | | | | |
----------------------------------------------------------------------------
1 | | |32| | | | | | | | | | | | | | | |
----------------------------------------------------------------------------
2 | | | | | |30 | | | | | | | | | | | | |
----------------------------------------------------------------------------
3 | | | |17 | | |46 |47 | | | | | | | | | | |
----------------------------------------------------------------------------
4 | | | | |31 | | | | | | | | | | | | | |
----------------------------------------------------------------------------
5 | |24 | | | | | | | | | | | | | | | | |
----------------------------------------------------------------------------
6 | | | | | | | | | | | | | | | | | | |
----------------------------------------------------------------------------
7 | | | | | | | | | | | | | | | | | | |
----------------------------------------------------------------------------
8 | | | | | | | | | | | | | | | | | | |
----------------------------------------------------------------------------
9 | | | | | | | | | | | | | | | | | | |
----------------------------------------------------------------------------
10| | | | | | | | | |49 | | | | | |40 | |63 |
----------------------------------------------------------------------------
```
散列表的地址区间为0~15,散列函数为H(key)=key%13。设有一组关键字{19,01,23,14,55,20,84}, 采用线性探测法解决冲突,依次存放在散列表中。问: 1)元素84存放在散列表中的地址是多少? 2)搜索元素84需要的比较次数是多少?
好的,我来帮您解决这道题目。
根据题目所给条件,我们可以得到哈希函数:H(key) = key % 13,即key对13取模。
接下来,我们可以按照以下步骤构造哈希表:
1. 初始化一个长度为16的哈希表,全部元素设为-1,表示该槽位为空。
2. 对于关键字序列中的每一个元素,计算其哈希值,即H(key)。
3. 如果哈希表中该槽位为空,将该元素插入到该槽位中,否则进行线性探测,直到找到一个空的槽位。
4. 线性探测的方式为:从当前槽位开始,一直往后遍历哈希表,直到找到一个空的槽位或者遍历了整个哈希表。如果找到了空槽位,则插入该元素;如果遍历了整个哈希表,那么从头开始重新遍历,直到找到一个空的槽位为止。
根据上述步骤,我们可以得到完整的哈希表构造过程如下:
|索引|关键字|
|---|---|
|0|55|
|1|01|
|2|14|
|3|19|
|4|20|
|5|84|
|6|23|
|7|-1|
|8|-1|
|9|-1|
|10|-1|
|11|-1|
|12|-1|
|13|-1|
|14|-1|
|15|-1|
其中,-1表示空槽位。注意,这里我们采用了线性探测的方式解决冲突,因此有些元素并不是按照哈希函数计算出来的哈希值所对应的槽位存储的。例如,关键字19的哈希值为6,但是由于槽位6已经被关键字23占用了,因此它被插入到了槽位3中。
根据上述哈希表,我们可以回答以下问题:
1. 元素84存放在散列表中的地址是多少?
根据哈希函数H(key)=key%13,我们可以得到元素84的哈希值为H(84)=84%13=11。因此,元素84应该被插入到槽位11中。查看上述哈希表,我们可以发现,确实有一个元素84存储在了槽位5中。因此,元素84存放在散列表中的地址是5。
2. 搜索元素84需要的比较次数是多少?
我们可以按照以下步骤进行搜索:
1. 计算元素84的哈希值为11。
2. 查找槽位11中的元素,发现元素84与该元素匹配。
因此,搜索元素84需要进行1次比较。
希望这个例子能够帮助您更好地理解散列表的构造过程和搜索过程。