c++与数据结构ppt课件.ppt
《c++与数据结构ppt课件.ppt》由会员分享,可在线阅读,更多相关《c++与数据结构ppt课件.ppt(61页珍藏版)》请在三一办公上搜索。
1、,第十四章 查找和排序,本章课件制作:吴虎统,第三部分 数据结构基础,本章内容, 查找 排序,14.1 查找,1. 查找的基本概念, 查找:在数据元素集合(查找表)中查找关键字与给定值相等的数据元素。 关键字:数据元素中的一个或多个数据项值,它可以惟一标识一个数据元素。 平均查找长度(ASL):,式中,n为查找表的长度;pi为查找第i个元素的概率,在等概率情况下pi等于1/n; Ci为找到第i个元素时的比较次数,2. 顺序查找, 基本思想:用给定值依次与线性表中每个元素的关键字进行比较。如果某个元素的关键字与给定值相同,则查找成功;如果找遍全表也没有发现满足条件的元素,则查找失败。, 要求:
2、查找表必须采用线性表。, 实现一:顺序表类中实现顺序查找的成员函数, 实现二:单链表类中实现顺序查找的成员函数, 顺序查找的平均查找长度, 评价:在用顺序查找方法完成查找时,每进行一次成功查找需要的平均比较次数约为表长度的一半,因此,它的效率较低。适用于在查找表较小的情况下进行查找。,3. 二分查找,要求: 查找表必须采用线性表;必须以顺序方式存储线性表;线性表中所有数据元素必须按照关键字有序排列, 基本思想:将给定值与处于顺序表“中间位置”上的元素的关键字进行比较,若相等则查找成功,若给定值大于关键字则在表的后半部分继续进行二分查找,否则在表的前半部分继续进行二分查找。如此进行下去直至找到满
3、足条件的元素,或当前查找区为空,此时查找失败。,演示:,例子:二分查找函数模板及其测试程序,优点: 查找效率高平均查找长度,缺点: 查找前要将表中元素按关键字有序排列只适用于线性表的顺序存储。适用于那种一经建立就很少改动而又经常需要查找的线性表。,4. 分块查找,要求: 查找表必须采用线性表;待查找的线性表分成若干块。在每一块内,元素的存放是任意的,但在块与块之间元素的存放是有序的,即前一块中任意一个元素的关键字值都必须小于(或大于)后一块中所有元素的关键字值;建立一个索引表,索引表中的每个索引项对应于一块。一个索引项至少应含有两部分信息:一是对应块中最大的关键字值;二是指向对应块中第一个元素
4、的指针, 基本思想:首先在索引表中查找,确定出要查找的元素应该在哪一块中;然后在已确定的那一块内进行顺序查找。, 演示:, 优点:块内元素是任意存放的,插入或删除运算不会造成元素的大量移动。, 缺点:增加了存放索引表的辅助空间及初始时对线性表分块排序的运算大量的插入和删除运算可能会导致各块中元素的数目很不均匀,这会降低查找速度, 平均查找长度:将长度为n的线性表均匀地划分成块,每块中有个结点,即。假定对表中每个元素的查找概率相等,则查找某一块的概率为,查找块中某个结点的概率为, 索引表使用顺序查找:, 索引表使用二分查找:,5. 二叉排序树查找, 二叉排序树的定义:二叉排序树或者是一棵空二叉树
5、,或者是具有以下性质的二叉树:1、若它的左子树非空,则左子树上所有结点的值均小于根结点的值;2、若它的右子树非空,则右子树上所有结点的值均不小于根结点的值;3、左、右子树本身又各是一棵二叉排序树。, 插入操作:,若二叉排序树为空,则新结点为二叉排序树的根结点;否则将新结点的关键字值和根结点的关键字值进行比较,若小于根结点的值,则将新结点插入到左子树中去,否则,插入到右子树中去。此插入过程是递归进行的。, 设有整数序列47,23,56,15,26,89,将其中的值依次插入二叉排序树,56,89,47,23,15,26, 删除操作:,一个结点被删除后,必须保证余下的结点仍然构成一棵二叉排序树。下面
6、分两种情况讨论:,情况一:被删除的结点至少有一棵空子树,方法:使被删结点的那棵非空子树的根成为其双亲结点的相应子女,情况二:被删除的结点有两棵非空的子树,方法一:找到被删除结点在中序遍历序列中的直接后继结点(它一定在被删除结点的右子树中),用此后继结点的值取代被删除结点的值,然后删除此后继结点,由于被删除的后继结点的左子树一定是空子树,所以删除后继结点的过程同情况一。,方法二:用被删除结点在中序遍历序列中的直接前驱结点(该结点的右子树也一定为空)代替被删除的结点,然后删除这个前驱结点。,后继结点,前驱结点, 将结点50删除, 中序遍历:,10,15,30,33,35,37,50,53,55,6
7、2, 查找操作:,对二叉排序树进行中序遍历可以得到一个数据元素由小到大的有序序列。构造二叉排序树的过程即为对无序序列进行排序的过程。,查找思路:,当二叉排序树不为空时,将给定值与根结点的值进行比较,若相等则查找成功。如果给定值小于根结点的值,则在根结点的左子树中继续查找,否则在根结点的右子树中继续查找。当待查找的二叉排序树为空时,查找失败。,平均查找长度:,在二叉排序树中查找成功时走过的是一条从根结点到所寻找结点的一条路径,因此,二叉排序树查找的平均查找长度取决于二叉排序树的深度。, 二叉排序树的蜕变:,二叉排序树是动态生成的,它的形态与各结点插入二叉排序树时的先后顺序有关。当把一组有序值依次
8、插入到一棵二叉排序树时,生成的二叉排序树将蜕变成一棵单支树。例如,由整数序列15,23,26,47,56,89 生成的二叉排序树就是一棵单支树。在单支树中查找时,平均查找长度与顺序查找相同。,6. 哈希查找, 哈希存储(哈希表):,以数据元素的关键字k为自变量,通过一定的函数关系h(称为哈希函数或散列函数)计算出对应的函数值h(k),把这个值解释为数据元素的存储地址并把数据元素存储到相应的存储单元内。h(k)称为哈希地址。, 冲突:,若有两个不同的关键字ki和kj,即ki kj(i j)。但h(ki)=h(kj),这种情况称为冲突。如上例的关键字85和49,其对应的哈希地址都为1,即产生冲突。
9、,例:设有一组关键字值85,72,49,58,15,70,90,38,哈希函数h(k) = k mod 12。则对应的哈希地址为1,0,1,10,3,10,6,2, 采用哈希技术要解决的两个主要问题:,构造一个好的哈希函数,使出现冲突的机会尽可能少些;,设计一个有效的解决冲突的办法, 哈希函数的构造方法,构造哈希函数要考虑以下几点,1) 哈希函数的定义域必须包括要存储的数据元素的全部关键字; 而如果散列表允许有 m 个地址,则哈希函数的值域必须在 0 到 m-1 之间,2)由哈希函数计算出的地址应均匀分布在散列地址空间内,3)哈希函数应该是简单的,能在较短时间内计算出结果,直接定位法,取关键字
10、的某个线性函数作为哈希函数,即h(k)=ak+b。其中,k为关键字,a、b为常数。,常用哈希函数,数学分析法,当关键字的位数比存储区域地址码的位数多时,可以取关键字中位值分布比较均匀的若干位作为哈希函数的值。这种方法适合于所有关键字为已知的情况。,除留余数法,选择一个适当的正整数p (p通常选为不大于哈希表长度 m 的最大素数),用p去除关键字,取其余数作为哈希地址,即h(k)=k%p (pm)。, 解决冲突的方法:开放地址法和链地址法,开放地址法,当冲突发生时形成一个地址序列,按序列顺序逐个检查各地址单元,直至找到一个未被占用的单元为止,将发生冲突的数据元素存入该地址单元中。,线性探查序列,
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- c+ 数据结构 ppt 课件

链接地址:https://www.31ppt.com/p-1480221.html