哈希表构建与查找算法实现

"哈希表及其查找实验设计与实现" 哈希表是一种高效的数据结构，用于存储和查找数据。在本实验中，我们被要求设计一个哈希表来存储30个人名，确保平均查找长度小于2。哈希表通过哈希函数将键（key，这里为人名）映射到数组的索引上，从而快速访问数据。 实验的具体要求如下： 1. **哈希表存储**：使用二维字符数组`char hashlist[50][10]`来存储人名，由于人名长度小于10个字符，每个条目有足够空间存储。 2. **哈希函数**：选择除留余数法作为哈希函数，其中分子为人名的字符代码之和。这意味着我们需要计算每个名字所有字符的ASCII码总和，然后用这个总和除以一个合适的质数P（本例中P取47），得到的余数作为数组的索引。 3. **冲突解决**：采用补偿性线性探测再散列方法处理哈希冲突。当两个不同的人名映射到同一个位置时，我们会向后加Q（本例中Q取17）直到找到一个空位置。 4. **哈希表大小**：根据平均查找长度公式`平均查找长度 = (1 + 1 / (1 - α)) / 2 < 2`，可以计算出装载因子α为0.6时，哈希表的大小为m = n / α = 30 / 0.6 = 50。 5. **程序结构**： - `createhash()`函数：负责构建哈希表，将30个人名插入哈希表。 - `hashsearch()`函数：负责查找特定人名，如果找到则返回其在哈希表中的序号，否则返回"nofound！"。 - `printhash()`函数：用于打印哈希表的内容，格式化输出，每行显示10项，共5行。 - `Inithashlist()`函数：初始化哈希表，将所有位置设置为空字符串。 6. **测试数据**：用于构建哈希表的30个人名包括月份、星期和数字，例如"January", "February", "Sunday", "One"等。 在主函数中，首先调用`Inithashlist()`初始化哈希表，然后调用`createhash()`建立哈希表。接着，`printhash()`函数用于展示构建好的哈希表。用户可以输入待查找的人名，调用`hashsearch()`进行查找，结果会显示是否找到以及找到的人名在数组中的序号。 通过这个实验，我们可以学习到哈希表的基本原理、哈希函数的设计、冲突解决策略以及如何在实际问题中应用这些知识。这有助于提高我们的编程技能和理解数据结构的能力。