设散列表的地址范围为0~17散列函数为H(key)=key%16,用线性探测法处理冲突输入关键字序列(10,24,32,17,31,30,46,47,40,63,49)画出线性探测,链地址法,哈希表三个图
时间: 2023-09-10 22:15:45 浏览: 100
好的,我会根据你的要求进行处理。首先,我们来看一下线性探测法处理冲突的过程。
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 |
----------------------------------------------------------------------------
```