数据结构—查找.pdf

数据结构中的查找技术是计算机科学中的重要概念，它涉及到如何高效地在数据集合中找到特定的信息。本章主要讨论了顺序查找、折半查找、二叉排序树和散列查找等几种常见查找方法。 1. **顺序查找**：顺序查找适用于任何存储结构的线性表，不论是顺序存储（如数组）还是链接存储（如链表）。它从表的一端开始逐个比较，直到找到目标元素或遍历完整个表。在最坏的情况下，顺序查找的时间复杂度为O(n)。 2. **折半查找**：又称二分查找，它适用于存储结构为顺序存储且元素有序的线性表。折半查找通过不断将查找区间减半来提高效率，平均时间复杂度为O(log n)。在成功查找时，查找次数最少为1次，最多不超过log2(n)+1次。 3. **二叉排序树**：对于给定的数列，可以构建二叉排序树，其中每个节点的左子树所有节点值小于该节点，右子树所有节点值大于该节点。查找平均比较次数等于树中所有节点的比较次数之和除以元素个数。平衡的二叉排序树查找效率高，最坏情况（退化成链表）下的时间复杂度为O(n)。 4. **散列查找**：散列查找利用散列函数将关键码映射到存储地址，查找速度快，平均查找长度与元素个数无关，而取决于装填因子。处理冲突的方法有开放定址法和拉链法。在理想情况下，散列查找可达到常数时间复杂度O(1)。 5. **其他知识点**： - **动态查找**与**静态查找**的区别在于是否涉及插入和删除操作。 - **查找成功**和**查找失败**的比较次数取决于具体查找算法的性能，例如折半查找通常比顺序查找更快，但不总是绝对的。 - **长度为n的有序表**，折半查找成功时的平均查找长度为log2(n)+1，失败时为log2(n)+1+1/n。 - **二叉排序树**的最低高度是log2(n)+1，对应于完全二叉树。 - **最小值节点**在二叉排序树中总是左子树为空的节点。 - **散列冲突**是指不同的关键码映射到了相同的存储地址。 - **线性探测法**处理冲突可能导致堆积，查找成功的探测位置的键值不一定都是同义词。 通过理解和掌握这些查找技术，我们可以根据具体场景选择合适的方法，优化数据的检索效率，从而提高程序性能。