数据结构—查找.pdf
2.虚拟产品一经售出概不退款(资源遇到问题,请及时私信上传者)
![preview](https://dl-preview.csdnimg.cn/27252006/0001-e9f7c9821f0c9021b59d8324767b69a7_thumbnail.jpeg)
![preview-icon](https://csdnimg.cn/release/downloadcmsfe/public/img/scale.ab9e0183.png)
数据结构中的查找技术是计算机科学中的重要概念,它涉及到如何高效地在数据集合中找到特定的信息。本章主要讨论了顺序查找、折半查找、二叉排序树和散列查找等几种常见查找方法。 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,对应于完全二叉树。 - **最小值节点**在二叉排序树中总是左子树为空的节点。 - **散列冲突**是指不同的关键码映射到了相同的存储地址。 - **线性探测法**处理冲突可能导致堆积,查找成功的探测位置的键值不一定都是同义词。 通过理解和掌握这些查找技术,我们可以根据具体场景选择合适的方法,优化数据的检索效率,从而提高程序性能。
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![rar](https://img-home.csdnimg.cn/images/20210720083606.png)
![zip](https://img-home.csdnimg.cn/images/20210720083736.png)
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![](https://csdnimg.cn/release/download_crawler_static/27252006/bg1.jpg)
![](https://csdnimg.cn/release/download_crawler_static/27252006/bg2.jpg)
![](https://csdnimg.cn/release/download_crawler_static/27252006/bg3.jpg)
剩余16页未读,继续阅读
![avatar-default](https://csdnimg.cn/release/downloadcmsfe/public/img/lazyLogo2.1882d7f4.png)
![avatar](https://profile-avatar.csdnimg.cn/default.jpg!1)
- 粉丝: 14
- 资源: 26万+
我的内容管理 展开
我的资源 快来上传第一个资源
我的收益
登录查看自己的收益我的积分 登录查看自己的积分
我的C币 登录后查看C币余额
我的收藏
我的下载
下载帮助
![voice](https://csdnimg.cn/release/downloadcmsfe/public/img/voice.245cc511.png)
![center-task](https://csdnimg.cn/release/downloadcmsfe/public/img/center-task.c2eda91a.png)
![dialog-icon](https://csdnimg.cn/release/downloadcmsfe/public/img/green-success.6a4acb44.png)