制作企业网站平台,中国观鸟记录的网站架构,开微商城需要多少钱,05网电子书一、基本概念
1-1、查找表#xff1a;
同一类型的数据元素构成的集合。
对查找表常用的操作#xff1a;
从查找表中查询某个特定的元素#xff1b;检索某个特定的元素的各种属性。 通常只进行这两种操作的查找表#xff1a;静态查找表 1-1-2、静态查找表#xff1a; 顺…一、基本概念
1-1、查找表
同一类型的数据元素构成的集合。
对查找表常用的操作
从查找表中查询某个特定的元素检索某个特定的元素的各种属性。 通常只进行这两种操作的查找表静态查找表 1-1-2、静态查找表 顺序查找——考的少折半查找二分查找——考的多分块查找——没考过 在查找表中插入一个数据元素在查找表中删除一个数据元素 1-1-3、动态查找表 二叉排序树平衡二叉树B_树——考的少哈希表 1-2、关键字
数据元素的某个数据项的值
主关键字唯一标识一个数据元素的关键字次关键字能够标识多个数据元素的关键字。 1-3、平均查找长度
衡量查找算法好坏的依据其关键字和给定值进行过比较的记录个数的期望值即平均查找长度。 二、静态查找
2-1、顺序查找
顺序查找又称线性查找是一种简单的查找算法它按照数据元素的顺序从前往后依次查找目标元素。 顺序存储方式、链式存储方式的查找表顺序查找都可以。 不需要有序 顺序查找成功的平均查找长度 2-2、折半查找
基本思想将有序数组分成两个部分找到中间元素与要查找的关键字进行比较如果相等则查找成功如果要查找的关键字比中间元素小则在左半部分继续查找如果要查找的关键字比中间元素大则在右半部分继续查找。通过不断的缩小查找范围最终可以找到要查找的元素。
示例查找元素16 mid lr/ 2往下取整。 查找失败的情况low在hight的后面。 折半查找只适合顺序存储 2-3、折半查找判定树
将折半查找的过程用一颗二叉树描述当前查找区间的中间位置序号作为根。
示例 查找成功时折半查找的过程恰好走了一条从根结点到被查找结点的路径 与关键字进行比较的次数 被查找结点在树中的层数。 因此折半查找在查找成功时进行比较的关键字个数最多不超过树的深度而具有 n 个结点的判定树的深度为所以折半查找在查找成功时和给定值进行比较的关键字个数最多为。 折半查找的平均查找长度 2-4、真题
真题1 真题2 真题3 真题4 顺序查找最多比较次数n 真题5 真题6 真题7 真题8 真题9 真题10 真题11 真题12
