设给定的散列表存储空间为H[1-m]，每个单元可存放一个记录，H[i]的初始值为零，选取散列函数为H(R.key)，其中key为记录R的关键字，解决冲突的方法为线性控测法，编写一个函数将某记录R填入到散列表H中。

好的，以下是使用线性探测法将记录R插入散列表H中的函数实现（假设记录R的关键字是整数类型）：

void insert(int H[], int m, int key, int value) {
    int i = key % m;  // 使用散列函数计算初始位置
    while (H[i] != 0) {  // 如果该位置已经被占用
        i = (i + 1) % m;  // 利用线性探测法找到下一个可用位置
    }
    H[i] = value;  // 将记录填入散列表中
}

在上述代码中，`H[]`是存储散列表的数组，`m`是散列表的大小，`key`是记录的关键字，`value`是记录的值。首先使用散列函数计算记录的初始位置，如果该位置已经被占用，就通过线性探测法找到下一个可用位置，最后将记录填入散列表中。

请注意，线性探测法可能会导致散列表出现聚集现象（即某些位置被占用的比其他位置更频繁），从而影响散列性能。因此，在实际应用中，需要选择更为高效的解决冲突方法，如链地址法、双重散列等。

相关问题

设有一组关键字{29,01,13,15,56,20,87,27,69,9,10,74},散列函数为：H(key)=key % 17,采用线性测方法解决冲突。试在0到18的散列地址空间中对该关键字序列构造散列表，并计算成功查找的平均查找度。手写过程

### 回答1：
首先，我们需要将关键字序列通过散列函数映射到散列表中。根据题目给出的散列函数H(key)=key % 17，我们可以得到以下散列地址：

- H(29) = 12
- H(01) = 1
- H(13) = 13
- H(15) = 15
- H(56) = 5
- H(20) = 3
- H(87) = 4
- H(27) = 10
- H(69) = 4
- H(9) = 9
- H(10) = 10
- H(74) = 8

可以看到，有两个关键字（87和69）映射到了同一个散列地址4上，这就是冲突。

接下来，我们采用线性探测法解决冲突。具体来说，当关键字key映射到散列地址i上时发生冲突，我们就依次检查散列地址i+1，i+2，i+3……，直到找到一个空闲的散列地址为止。这里需要注意的是，我们在检查下一个散列地址时需要使用散列函数重新计算，即H(i+1)，H(i+2)，H(i+3)……。

下面是具体的构造过程：

- 将关键字29映射到散列地址12，放置关键字29。
- 将关键字01映射到散列地址1，放置关键字01。
- 将关键字13映射到散列地址13，放置关键字13。
- 将关键字15映射到散列地址15，放置关键字15。
- 将关键字56映射到散列地址5，放置关键字56。
- 将关键字20映射到散列地址3，放置关键字20。
- 发现关键字87映射到散列地址4时发生冲突，依次检查散列地址5、6、7、8、9、10、11、12、13、14、15、16、0、1、2，发现散列地址9是空闲的，将关键字87放置在散列地址9上。
- 将关键字27映射到散列地址10，放置关键字27。
- 发现关键字69映射到散列地址4时再次发生冲突，依次检查散列地址5、6、7、8、9、10、11、12、13、14、15、16、0、1、2，发现散列地址11是空闲的，将关键字69放置在散列地址11上。
- 将关键字9映射到散列地址9，放置关键字9。
- 发现关键字10映射到散列地址10时发生冲突，依次检查散列地址11、12、13、14、15、16、0、1、2、3、4、5、6、7、8，发现散列地址0是空闲的，将关键字10放置在散列地址0上。
- 将关键字74映射到散列地址8，放置关键字74。

现在，我们已经成功构造了散列表。下面计算平均查找度。假设查找一个关键字时，需要检查k个散列地址（包括散列地址本身），则成功查找的平均查找度为：

平均查找度 = (1/12)*(1+1+1+1+1+1+3+1+2+1+1+1) = 1.25

因此，成功查找的平均查找度为1.25。

### 回答2：
首先，“散列函数为：H(key)=key % 17”表示散列函数将关键字除以17取余数作为散列地址。

根据线性探测法，当出现冲突时，依次尝试下一个散列地址，直到找到空闲的地址为止。

我们可以按照以下步骤进行构造散列表：

1. 创建一个长度为 19 的数组（0 到 18），用于存储关键字。
2. 将关键字序列逐个进行散列，并插入到对应的散列地址中。
- 将关键字 29 散列到 12 号地址（29%17=12）。
- 将关键字 01 散列到 1 号地址（1%17=1）。
- 将关键字 13 散列到 13 号地址（13%17=13）。
- 将关键字 15 散列到 15 号地址（15%17=15）。
- 将关键字 56 散列到 5 号地址（56%17=5）。
- 将关键字 20 散列到 3 号地址（20%17=3）。
- 将关键字 87 散列到 4 号地址（87%17=4）。
- 将关键字 27 散列到 10 号地址（27%17=10）。
- 将关键字 69 散列到 18 号地址（69%17=1）（出现冲突，尝试下一个地址，然后再次冲突，依次尝试下一个地址，直到找到空闲地址）。
- 将关键字 9 散列到 9 号地址（9%17=9）。
- 将关键字 10 散列到 10 号地址（10%17=10）（出现冲突，尝试下一个地址）。插入到 11 号地址（11%17=11）。
- 将关键字 74 散列到 7 号地址（74%17=7）（出现冲突，依次尝试下一个地址，直到找到空闲地址）。

散列表为：[ ,01 , ,15 ,87 ,20 , ,74 , , ,29 , ,13 , ,56 , , ,69 , ,10 ]。

3. 计算成功查找的平均查找度。即，对所有关键字进行查找，计算查找每个关键字时需要查找的次数，并求平均值。
- 查找关键字 29，需要查找 1 次。
- 查找关键字 01，需要查找 1 次。
- 查找关键字 13，需要查找 1 次。
- 查找关键字 15，需要查找 1 次。
- 查找关键字 56，需要查找 1 次。
- 查找关键字 20，需要查找 1 次。
- 查找关键字 87，需要查找 1 次。
- 查找关键字 27，需要查找 2 次。
- 查找关键字 69，需要查找 1 次。
- 查找关键字 9，需要查找 1 次。
- 查找关键字 10，需要查找 2 次。
- 查找关键字 74，需要查找 1 次。

总共查找次数为 13 次，平均查找次数为 13/12 ≈ 1.083 次。

注：由于散列函数本身的性质以及关键字的选取，可能会导致冲突的发生，而线性探测法可能会出现聚集的问题，即多个关键字在散列表中相邻的位置，这会影响到散列表的性能。因此，在实际应用中，需要根据具体情况选择合适的散列函数和解决冲突的方法。

### 回答3：
首先，根据给定的散列函数H(key)=key % 17，将关键字序列依次计算散列地址：

29 % 17 = 12
01 % 17 = 1
13 % 17 = 13
15 % 17 = 15
56 % 17 = 5
20 % 17 = 3
87 % 17 = 3
27 % 17 = 10
69 % 17 = 1
9 % 17 = 9
10 % 17 = 10
74 % 17 = 8

然后，根据线性探测方法处理冲突，从散列地址为12的位置开始向后探测，直到找到一个空的位置：

12：29 13：13 14： 15：15 16： 17： 18：
3：20
10：27 11： 12： 13： 14： 15： 16：
0：01
1：69
2：15
3：87
4： 5：56
6：
7： 8：74
9：9

依次将关键字插入散列表中，直到所有关键字都插入完毕。

成功查找的平均查找度计算如下：
查找度为线性探测过程中查找到的位置与实际应该存放的位置之间的距离。
对于每个关键字来说，总共有17个散列地址，我们可以将距离加起来再除以17，得到平均查找度。

29的查找度：0
01的查找度：1（69的实际位置-69的散列地址）
13的查找度：0
15的查找度：0
56的查找度：0
20的查找度：4（20的实际位置-20的散列地址）
87的查找度：0
27的查找度：3（10的实际位置-10的散列地址）
69的查找度：0
9的查找度：0
10的查找度：0
74的查找度：0

总查找度：0 + 1 + 0 + 0 + 0 + 4 + 0 + 3 + 0 + 0 + 0 + 0 = 8

平均查找度：总查找度 / 关键字个数 = 8 / 12 = 0.67

所以成功查找的平均查找度为0.67。