【数据结构与算法】查找.ppt

《【数据结构与算法】查找.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第九章查找9.1静态查找表9.1.1顺序表的查找9.1.2有序表的查找9.2动态查找表9.2.1二叉排序树和二叉平衡树9.3哈希(Hashing)表(散列表)第九章查找查找表(searchtable):同一类型数据元素构成的集合。查找操作:(1)查询某个“特定的”数据元素是否在查找表中;(2)检索某个“特定的”数据元素的各种属性;(3)在查找表中插入一个数据元素;(4)从查找表中删除某个数据元素.静态查找表:对查找表只作(1)、(2)操作；动态查找表：可以对查找表作(1)-(4)操作。有关查找的“词”的含义关键字(KEY):数据元素(或记录)的某

2、个数据项的值,用以标识一个数据元素(或记录).可以唯一标识一个记录的关键字称为主关键字(PrimaryKey);否则称为次关键字(SecondaryKey).查找(Searching)根据给定的值,在查找表中确定一个关键字等于给定值的记录或数据元素.9.1静态查找表可以用顺序表，也可以用线性链表来表示静态查找表。顺序表的查找typedefstruct{//静态查找表的顺序存储结构ElemType*elem;intlength;}SSTable;elemlengthkey012...length-1length顺序查找（SequentialSear

3、ch）intSearch_Seq(SSTableST,KeyTypekey){ST.elem[0].key=key;//“哨兵”for(i=ST.length;!EQ(ST.elem[i].key,key);--i);returni;}性能分析：设Pi为查找表中第i个记录的概率(取Pi=1/n)；Ci为找到第i个记录所需的查找次数。则nASL=PiCi=nP1+(n-1)P2+...+2Pn-1+Pni=1=[n+(n-1)+...+2+1]*1/n=(n+1)/2若查找成功与不成功的概率相同，即Pi=1/2n，ASL=nP1+(n-1)P2+

4、...+2Pn-1+Pn+(n+1)/2=(n+1)*3/4有序表的查找:折半查找（BinarySearch）确定待查记录的区间，逐步缩小范围直到找到或找不到该记录为止。例子：数据元素有序表如下,查找关键字key=21的数据元素。21(05，13，19，21，37，56，64，75，80，88，92）下标:0123456789101105，13，19，21，37，56，64，75，80，88，92lowmidhighmid=[(low+high)/2];key=ST.elem[mid].key查找成功;当key

5、ey时,下一个待查区间为[low,mid-1]05，13，19，21，37，56，64，75，80，88，92lowmidhigh当key>ST.elem[mid].key时下一个待查区间为[mid+1,high]折半查找的性能分析查找上例中所有元素的判定二叉树为6314795102118判定树判定树上每个结点需要的查找次数刚好为该结点所在的层数.查找成功时查找次数不会超过判定树的深度n个结点的判定树的深度为[log2n]+1.折半查找的算法复杂度为[log2n]+19.2动态查找表9.2.1二叉排序树什么是二叉排序树(BinarySor

6、tTree)?二叉排序树是空树,或者是具有以下性质的二叉树:(1)若左子树非空,则左子树上所有结点的值均小于它的根结点的值;(2)若右子树非空,则右子树上所有结点的值均大于它的根结点的值;(3)它的左、右子树也分别为二叉排序树。二叉排序树举例45123375378100249061二叉排序树查找过程：从根结点出发，结点的值与key进行比较：（1）相等时查找成功；（2）key较大时，沿右子树继续查找（无右子树表明查找失败）；（3）key较小时，沿左子树继续查找（无左子树表明查找失败）。其中序遍历序列:3,12,24,37,45,53,61,78,9

7、0,100二叉排序树的生成(插入结点)二叉排序树的生成(连续进行插入操作)例如:对{45,24,53,45,12,24,90}关键字序列的二叉排序树生成过程如下:452412534524125390452453452445二叉排序树结点的删除(保持二叉排序树的特性及次序)设被删除的结点为*p,其父结点为*f,并不失一般性假设*p为*f的左孩子,则(1)若*p为叶结点,即PL和PR均为空.直接删除不会影响树结构;(2)若*p只有PL或只有PR.只要令PL或PR直接成为其双亲结点*f的左孩子即可,这样也不会影响树结构;(3)若*p有PL也有PR.为保

8、持中序遍历二叉树的序列不变,可以有两种处理方法:其一是令PL为*f的左子树,PR为*s的右子树(*s为中序遍历PL的最后一个结点);其二