西交《数据结构》faq（八）

Andy老师

西交《数据结构》FAQ（八）
第九章 查找
1、静态查找表相关概念
数据对象：同类元素集，具可识别比较的关键字
存储结构：查找表采用顺序，记录按逻辑顺序存放
查找方法：逐个比较表中的各个记录的关键字
2、顺序表等几率查找的算法思想和性能分析。
对数据元素按顺序存储结构存储的查找。
算法思想：


算法：
设哨兵，保证可以停下来，提高效率。
此算法最简单直观，但显示出查找最基本的要做的事。
原始算法：


书上算法：


静态查找——查找表的内容不变
动态查找——查找表的内容受插入，删除的影响。
性能分析（同类好坏评比用数据论说）
时间/空间r[0..n],i=n+2
时间复杂性：时间主要耗于何处？看算法主要工作量干了些什么？—key比较次数。
只考虑查找到成功的情况，即
，则

考虑查找成功和不成功的情况，即
，则

平均查找长度ASL
查找成功时的=（n+1）/2
查找不成功时的= n+1
查找算法平均查找长度=（n+1）*3/4
平均查找长度ASL 查找所需要比较次数的期望值
n记录的表，成功查找的ASL=
；不成功，n+1次。
pi要查元素处于第i位的几率。
ci查i元素时已做比较次数。


设要查元素位于何处是等几率的，即
。
3、顺序表查找结论
优点 简单，要求低，附加空间少，方法直截了当、适应面广；
缺点 等几率不科学。
从头做起太呆板。对已有序的key，不能利用。费时。
适于 无序、简单、小表情况；
可用于数组，链表表示的线性表、分类/分类的均可用。
改进 成功率高的元素置放位置前提。
改步长，大踏步快点。
4、有序表折半查找的思想和性能分析
有序表：静态查找表中，各个记录按关键字大小顺序排列。
当表中key已有序的情况下顺序法不够聪明
折半查找法：通过与中间位置上的元素进行比较，每次确定待查记录的所在范围，将比较元素的范围缩小一半，逐次比较直到找到或找不到该记录为止。


例：李咏“幸运52”猜价格1000~1200
1180（1,3,5,7,9）key=7，顺序4次，折半2次。
性能分析
查找过程可以借助二叉树（称为判定二叉树）来描述，分析
构造判定二叉树：以中间元素为例，所有小于中间元素的数据组成左子树，大于中间元素的数据组成右子树。
（5，13,19,21,37,56,64,75,80,88,92）


内结点：成功查找，在树中
外结点：不成功查找，不在树中。
查找记录的过程恰好走了一条从根到该结点的路径，比较次数=路径上的结点数=此结点所在的层数。比较成功时的比较次数
树的深度。本内容由易百网整理发布
网址 www.openhelp100.com
QQ 515224986