前面我们学习了三种基本数据结构精品PPT课件.ppt

《前面我们学习了三种基本数据结构精品PPT课件.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、ADT的定义：数据结构的逻辑特性；数据结构上定义的操作；ADT的虚拟实现：逻辑结构的虚拟实现（存储结构）操作的虚拟实现（算法）；ADT应用举例：讲授的方法:前面学习的每一种数据结构都定义了一些常用的操作，如：初始化、访问某数据元素等等，因此，研究操作的实现（不是操作的定义）即算法也是数据结构的范畴。有两个操作在每个数据结构上、在计算机应用中是非常重要的：其一，确定元素的位置——查找；其二，将元素按某种顺序排列——分类后面两章我们分别学习这两类操作的算法（思想、效率、优缺点等等）；第九章查找本章学习各种查找

2、算法，了解算法的思想、效率、优缺点、适用范围等等。预备知识1、查找：在某一数据集合中查找数据元素是否存在，若存在，返回其位置，否则，返回失败信息。2、查找表：被查找数据元素的集合（一般都是一种数据结构，元素的位置是指在该数据结构中的逻辑位置，但是查找方法还依赖与元素的存储，即与存储结构有关），一般是虚拟实现了的逻辑结构（数据结构+存储结构）。3、查找表的种类：静态查找表：数据集合在查找前后不变；动态查找表：数据集合在查找后会改变；注意：查找表一般可以描述为：数据对象D0：D0是具有相同特性的数据元素的集合

3、。每个数据元素含有类型相同的关键字，可唯一标识数据元素。数据关系R：数据元素同属一个集合（关系描述）。4、查找方法：查找表不同，查找方法就会不同。有很多不同的查找方法。5、查找算法的评价：空间：占用的辅助空间少；时间：时间少。查找的基本操作是比较，因此时间主要体现为比较次数。查找成功：最大比较次数——MSL平均比较次数——ASL查找失败：最大比较次数——MSL平均比较次数——ASL§9.1静态查找表的查找静态查找表有很多种，查找方法也不一样，下面介绍几种常见的静态查找表的查找方法。一、静态查找表是顺序或链

4、式存储的线性表——顺序查找1、查找表的要求：线性表2、查找方法：略1、查找表的要求：3、特点：思想简单，对查找表要求少，适应面广；比较次数较大O(n)；（考虑查找概率不相等时应该如何处理？）二、静态查找表是顺序存储的、有序的线性表——折半查找（Fibonacci查找、插值查找）1、查找表的要求：顺序存储、有序的线性表2、查找方法：lowhigmid=(low+hig)/2x=R[mid]OK!!xR[mid]mid+1~higR3、特点：对查找表要求多；比较次数较少O(

5、log2n)；折半查找的过程可以用一棵二叉树表示，称之为“折半查找的判定树”。（构造方法自己总结，该树是唯一的吗？）例如:折半查找在n=11时的判定树如下：一般情况下，表长为n的折半查找的判定树的深度和含有n个结点的完全二叉树的深度相同。假设n=2h-1并且查找概率相等则：在n>50时，可得近似结果：三、静态查找表是树——静态树查找1、查找表的要求：二叉分类树2、查找方法：X与根比较：相等：OK！X<根：在左子树上找X>根：在右子树上找3、特点：类似折半，最大是树的深度；等概率时，折半查找的判定树是最好的

6、；不等概率时，概率高的应该靠近根。四、静态查找表是分块索引表——分块查找1、查找表的要求：顺序存储、分块有序2、查找方法：折半方法确定可能在的块；顺序查找确定元素；3、特点：要建立索引表；效率介于折半和顺序之间；§9.2动态查找表的查找——动态二叉分类树的查找1、查找表的要求：二叉分类树2、查找方法：若二叉排序树为空，则查找不成功；否则1）若给定值等于根结点的关键字，则查找成功；2）若给定值小于根结点的关键字，则继续在左子树上进行查找；3）若给定值大于根结点的关键字，则继续在右子树上进行查找。Btreen

7、ode*find(Btreenode*BST,elentypex)//在以BST为根指针的二叉排队树中查找值为x的结点{if(BST==NULL)returnNULL;//查找失败else{if(BST->data==x)//查找成功returnBST;elseif(BST->data>x)//进入左子树查找returnfind(BST->left,x);else//进入右子树查找returnfind(BST->right,x);}}3、特点：与树的深度有关；对于每一棵特定的二叉排序树，均可按照平均查找长

8、度的定义来求它的ASL值，显然，由值相同的n个关键字构造所得的，不同形态的各棵二叉排序树的平均查找长度的值不同，甚至可能差别很大，例如：由关键字序列1，2，3，4，5构造而得的二叉排序树，ASL=（1+2+3+4+5）/5=3由关键字序列3，1，2，5，4构造而得的二叉排序树，ASL=（1+2+3+2+3）/5=2.2一般情况下，考虑含有n个关键字可能出现的n!种序列出现的可能性相等。不失一般性，假设某个序列中有k个关键字小于