1、查找表和查找效率的概念
查找表是指由同一类型的数据元素构成的集合。分为静态查找表和动态查找表。
1.1 静态查找表
1、查询某个特定元素是否在查找表的集合当中2、查询某个特定元素的各种属性
1.2 动态查找表
1、在查找表中插入一个数据元素2、在查找表中删除一个元素
1.3 关键字
它是数据元素的某个数据项的值。用来识别该元素。主关键字是唯一能表示该元素的值。次关键字用来表示多个数据元素的关键字。
1.4 查找
根据给定的值在查找表中查询是否存在一个其关键字等于给定值的记录或者数据元素。
1.5 平均查找长度
关键字和给定值进行比较的记录个数的平均值。也是衡量查找算法好坏的依据。
2、顺序查找
从数据集合的一端,逐个记录的关键字和给定值进行比较,找到则为查找成功。整个数据集合比较完后仍然找不到,则为查找失败。顺序查找适用于顺序存储和链式存储。其平均查找长度为(n+1)/2.顺序查找算法简单、适应性广。当数据集合数据量大的话,查询效率会较低。
3、折半查找
折半查找也称为二分查找。平均查找长度:(n+1)/n*log^2(n+1) -1,当n值较大 log^2(n+1) -1折半查找效率比顺序查找高,它比较合适顺序存储和关键字有序排列。所以折半查找适合数据表不经常变动,查询频率