吉林师范大学计算机学院《数据结构》课件：8.ppt

数据结构（C语言版）第9章　　查找  9.1 基本概念 1.查找表?? 查找表是由同一类型的数据元素 （或记录）构成的集合。表中的每个记录由若干个数据项构成，其中可以唯一地标识一个记录的数据项称为主关键字。 2. 查找操作类型?? ① 在查找表中查询某个记录是否存在?? ② 检索某个记录的各种属性?? ③ 在查找表中插入一个记录?? ④ 从查找表中删除一个记录  3.查找表类型?? 根据对查找表所进行查找操作的不同，查找表可被分为两类：?? ① 静态查找表?? ② 动态查找表 4.平均查找长度?? 为确定记录在查找表中的位置，通常把查找过程中对关键字需要进行的比较次数，称为平均查找长度ASL。 9.2 顺序查找 1. 基本思想：???? 当以顺序表或线性链表表示静态查找表时，可采用顺序查找法。?? 顺序查找的过程为：从表的一端开始，顺序扫描线性表，依次将扫描到的记录关键字与给定值K相比较，若相等，则查找成功；若扫描结束后，仍未找到，则查找失败。 2.程序实现 　 例1　输入静态表的元素个数,(例如：5)，然后输入各个元素（字符） .以查找某元素。 　　　 3.性能分析：??　 在等概率的情况下，顺序查找成功时的平均查找长度为：?? 　ASL = (n+1) / 2?? 不成功时的平均查找长度为：?? 　ASL = n+1。?? 所以顺序查找的平均查找长度为：?? 　ASL= 3(n+1) / 4。?? 当记录的查找概率不相等时，应把记录从大到小重新排列，以提高查找效率。在查找概率无法预先确定时，可以在记录中附设一个频度域，并使顺序表中的记录始终按访问频度非递减有序排列。?? 　顺序查找的优点是：算法简单，且对表的结构无任何要求。缺点是：查找效率低，当n较大时，不宜采用顺序查找。  ? 9.3 二分查找___有序表的查找 1. 基本思想： 　 又称“折半查找”，先确定待查记录所在的范围（区间），然后逐步缩小范围直到找到或找不到该记录为止。 例如： 　　　P219 2.程序实现 　　　 例2　利用二分查找实现例1。P220 3.性能分析：??　 判定树 说明：?? 折半查找的过程可以用二叉判定树来描述。通过对相应二叉判定树的分析可知：?? 折半查找在查找成功时，和给定值进行比较的关键字个数至多为 ┏log2n ┓ +1，查找不成功时的比较次数最多也不超过┏ log2n ┓ +1。?? 折半查找在查找成功时的平均查找长度为：ASL=log2(n+1)-1，折半查找的平均性能和最坏性能相当接近。?? 优点：查找的效率比顺序查找高。局限性：要求查找表有序；?? 另外，只适用于顺序存储结构。 ?9.4 分块查找___索引顺序表的查找 　　　又称“索引顺序查找”，是顺序查找的一种改进方法，是一种性能介于顺序查找和二分查找之间的一种查找方法。在查找法中，除表本身外，尚需建立一个“索引表”。 ASL比顺序查找有了很大改进，但远不及折半查找。 9.5 静态树表的查找 基本概念：?? ????次优查找树的查找类似于折半查找。若次优查找树为空，则查找不成功，否则，首先将给定值key和其根结点的关键字进行比较，若相等，则查找成功，该根结点的记录即为所求；否则将根据给定值key小于或大于根结点的关键字而分别在左子树或右子树中继续查找直至查找成功或不成功为止。???? 由于查找过程恰是走了一条从根到待查记录所在结点（或叶子结点）的一条路径，进行过比较的关键字个数不超过树的深度，因此次优查找树的平均查找长度和logn成正比。???? 在记录的查找概率不等时，可用次优查找树表示静态查找树，故又称静态树表。 9.6 动态查找表 _____ 二叉排序树的查找 1.二叉排序树的概念: 二叉排序树是一种动态树表。?? 二叉排序树的定义：二叉排序树或者是一棵空树，或者是一棵具有如下性质的二叉树：??? ⑴ 若它的左子树非空，则左子树上所有结点的值均小于根结点的值；????⑵ 若它的右子树非空，则右子树上所有结点的值均大于根结点的值；????⑶ 左、右子树本身又各是一棵二叉排序树。 二叉排序树的性质： 按中序遍历二叉排序树，所得到的中序遍历序列是一个递增有序序列。 2.二叉排序树的插入: ???在二叉排序树中插入新结点，要保证插入后的二叉树仍符合二叉排序树的定义。? 插入过程：若二叉排序树为空，则待插入结点*S作为根结点插入到空树中；?? 当非空时，将待插结点关键字S-key和树根关键字t-key进行比较， 若s-key ==