散列表实现与应用：线性开型寻址与链表散列

"该实验报告来自山东大学计算机科学与技术学院的数据结构与算法课程，由学生张愈博完成。实验内容涉及散列表的实现，包括线性开型寻址和链表散列两种方法，用于处理溢出问题。实验中需要设计一个字典，其关键字为整数，容量为961，插入500个不同的随机整数，并实现字典的建立、搜索和删除功能。实验环境为DevC++5.11 on Windows10。" 在实验中，张愈博同学探讨了两种不同的散列技术： 1. 线性探查方法： - 在这个方法中，首先定义了一个`pair`类，包含关键字和相关的内容。 - 散列表类包含一个指向`pair`对象的指针数组，以及散列函数、表大小`dSize`和散列函数除数`divisor`。 - 实现的功能包括检查是否为空、计算大小、搜索、插入和删除。 - 删除操作涉及到寻找关键字为`theKey`的`pair`，找到其在表中的位置`pos`，然后从`pos`开始遍历数组，将所有键值与`theKey`相同的元素向后移动，直到回到`pos`。这种算法的时间复杂度为`O(n)`。 2. 链表散列： - 这种方法中，每个桶是一个`sortedChain`类，它内部使用链表结构存储`PairNode`，每个`PairNode`包含一个`pair`和指向下一个节点的指针。 - `sortedChain`类提供了判断空、计算大小、搜索、插入、删除和输出等操作。 - 由于`sortedChain`的链表是有序的，这有助于提高搜索效率，减少链表散列的搜索时间。 实验旨在让学生深入理解散列表的原理和应用，通过实际操作来掌握散列表的定义、实现和使用。线性探查法和链表散列是常见的冲突解决策略，前者通过顺序查找解决冲突，后者则利用链表将冲突元素链接起来。这两种方法各有优缺点，线性探查法可能会导致聚集现象，而链表散列则可能因为链表长度不一而导致性能差异。在实际应用中，需要根据数据特性和需求选择合适的散列策略。