数据结构第八章.ppt
《数据结构第八章.ppt》由会员分享,可在线阅读,更多相关《数据结构第八章.ppt(84页珍藏版)》请在课桌文档上搜索。
1、,数据结构(DATA STRUCTURE),计算机科学与技术学院,2,第九章 查找,基本概念静态索引结构 动态索引结构散列,3,基本概念,查找表:由同一类型的数据元素(记录)构成的集合。分为静态查找表和动态查找表两类静态查找表:仅对查找表进行查找操作,而不能改变的表动态查找表:对查找表除进行查找操作外,可能还要进行向表中插入数据元素,或删除表中数据元素的表。查找:简单地说,查找就是给定一个值 K,在含有众多数据元素的查找表中找出关键字等于给定值 K 的记录。,4,查找也是计算机中经常遇到的操作。特别是当问题所涉及的数据量相当大时,查找的效率就显得格外重要。查找运算的主要操作是关键字的比较,所以
2、,通常把查找过程中需要执行的关键字的平均比较次数(也称为平均查找长度)作为衡量一个查找算法效率优劣的标准。,5,9.1 静态查找表,9.1.1 顺序表的查找 又称线性查找,是最基本的查找方法之一基本思想:从表的一端开始,向另一端逐个按给定值 k 与关键码进行比较,若找到,表明查找成功;若直到所有元素都比较完毕,仍未找到与k 相同的关键码,则表明查找失败。适用的数据结构:顺序表、线性链表算法实现:静态查找表的顺序存储结构:typedef struct ElemType*elem;/*数组基址*/int length;/*表长度*/SSTable;,6,算法:int S_search(SSTabl
3、e ST,KeyType k)ST.elem0.key=k;/作为监测哨兵*/for(i=ST.length;ST.elemi.key!=k;i-);/*从表尾端向前找*/return i;/*返回k元素在数组中的下标,否则返回0*/,设置哨兵的好处:在顺序表中总可以找到待查结点。否则,必须将判断条件 i=0 加进 for 语句。,7,4)性能分析:,分析查找算法的效率,通常用平均查找长度ASL衡量在查找成功时,平均查找长度ASL是指为确定数据元素在表中的位置所进行的关键字比较次数的期望值。其中:Pi为查找表中第i个数据元素的概率;Ci为查找表中第 i 个元素所需比较次数。查找成功时,顺序查找
4、的平均查找长度为:查找不成功时,关键码的比较次数总是n+1次,8,9.1.2 有序表的查找,有序表即是表中数据元素按关键码升序或降序排列;二分查找又称为折半查找 适用的数据结构:顺序存储的有序表基本思想:在有序表中,取中间元素作为比较对象,若给定值与中间元素的关键码相等,则查找成功;若给定值小于中间元素的关键码,则在中间元素的左半区继续查找;若给定值大于中间元素的关键码,则在中间元素的右半区继续查找。不断重复上述查找过程,直到查找成功,或所查找的区域无数据元素,查找失败。,9,假设静态查找表ST递增有序,折半查找过程为:low=1;high=length;/设置初始区间 若lowhigh,返回
5、查找失败信息/当前查找区间为空,查找失败 若lowhigh,mid=(low+high)/2;/取中点 a.若 k ST.elemmid.key,low=mid+1;转/查找在右半区进行 c.若 k=ST.elemmid.key,返回元素在表中位置/查找成功,3)算法实现,10,举例,05 13 19 21 37 56 64 75 80 88 92,05 13 19 21 37 56 64 75 80 88 92,05 13 19 21 37 56 64 75 80 88 92,查找K=85的过程(查找失败),05 13 19 21 37 56 64 75 80 88 92,11,4)性能分析
6、:,从折半查找过程看,以表的中点为比较对象,并以中点将表分割为两个子表,对定位到的子表继续这种操作。因而对表中每个数据元素的查找过程可用二叉树描述,称此描述查找过程的二叉树为判定树。查找表中任一元素的过程,即是判定树中从根到该元素结点路径上各结点关键码的比较次数,也即该元素结点在树中的层次数。,12,例:05 13 19 21 37 56 64 75 80 88 92,判定树:,借助于判定树很容易求得二分查找的平均查找长度。设结点总数为:树中第 k 层上的结点个数不超过:,13,因此,在等概率假设下,二分查找的平均查找长度为:二分查找的算法复杂度为:优点:查找的效率较高 缺点:要求被查找序列事
7、先按关键字排好序,而排序本身是一种很费时的运算;另外,二分查找只适用于顺序存储结构。,14,9.1.3 索引顺序表的查找(分块查找),是一种性能介于顺序查找和二分查找之间的查找算法1)数据结构设置:将长度为 n 的查找表Rn均分成b块(子表),要求:每一块中的关键字不一定有序,但前一块中的最大关键字必须小于后一块中的最小关键字,即要“分块有序”。建立索引表IDb,其中IDi存放第 i 块中的最大关键字及该块在查找表中的起始位置。由于表Rn分块有序,所以索引表IDb递增有序。,15,首先查找索引表ID,以确定待查结点在哪一分块(由于索引项按关键码字有序,可用顺序或折半查找)然后,在已确定的那一块
8、中进行顺序查找。3)算法实现数据结构定义:长度为 n 的查找表采用顺序表:SSTable ST索引表的结构 typedef struct/*索引表结点结构*/keytype key;int addr;IDtable;IDtabel IDb;/*索引表*/,2)算法基本思想:,16,4)性能分析:,分块查找由索引表查找和子表查找两步完成,故整个算法的平均查找长度是两次查找的平均查找长度之和。ASL=ASL索引表+ASL子表 设查找表长为 n,分为 b个子表,每块中均有s=n/b 个元素 若用二分查找来确定块,则分块查找的平均查找长度约为:若用顺序查找来确定块,则分块查找的平均查找长度约为:对于后
9、一种情况,当 时,平均查找长度为极小值。在实用中,可根据表的具体情况进行分块。,17,分块查找的性能介于顺序查找和二分查找之间,例如对长度为10000的线性表,它们的平均查找长度分别是:顺序查找:ASL=(n+1)/2=5000 分块查找:ASL=log2(b+1)-1+(S+1)/2 57 或 ASL=(b+1)/2+(S+1)/2=101 二分查找:ASL=log2(n+1)-1 14 优点:把线性表分成若干逻辑子表,提高了查找效率 缺点:增加了一索引存储空间,和将初始表进行分块的运算,18,9.2 动态查找表,9.2.1 二叉排序树(Binary Search Tree)定义:二叉搜索树
10、或者是一棵空树,或者是具有下列性质的二叉树:每个结点都有一个作为搜索依据的关键码(key),所有结点的关键码互不相同。左子树(如果存在)上所有结点的关键码都小于根结点的关键码。右子树(如果存在)上所有结点的关键码都大于根结点的关键码。左子树和右子树也是二叉排序树。2)存储结构:二叉链表,19,几个二叉排序树的例子,20,3)二叉排序树上的查找算法,在二叉排序树上进行搜索,是一个从根结点开始,沿某一个分支逐层向下进行比较判等的过程。假设想要在二叉排序树中搜索关键字为 x 的元素,搜索过程从根结点开始。如果给定值等于根结点的关键码,则搜索成功。如果给定值小于根结点的关键码,则继续递归搜索根结点的左
11、子树;否则,递归搜索根结点的右子树。,21,二叉搜索树的搜索 插入新结点88,每次结点的插入,都要从根结点出发搜索插入位置,然后把新结点作为叶结点插入。,22,查找过程走了一条从根到该元素结点路径,比较次数等于该结点所在层次数。其中:Pi 查找某元素的概率,等概率情况下 1/n Ci 该元素结点在二叉排序树中的层次数 最坏情况:单支树(树的高度达到最大)ASL=(n+1)/2 最好情况:与二叉判定树相似 ASL=log2(n+1)-1 平均:O(nlog2n),4)查找分析,23,5)二叉排序树的插入,在插入之前,先使用搜索算法在树中检查要插入元素是否已经存在。搜索成功:树中已有这个元素,不再
12、插入。搜索不成功:把新元素加到搜索停止的地方。新插入的结点一定是一个新添加的叶子结点,并且是查找不成功时查找路径上访问的最后一个结点的左孩子或右孩子结点。二叉排序树生成:从空树出发,经过一系列的查找、插入操作之后,可生成一棵二叉排序树。,24,6)二叉排序树的删除,在二叉搜索树中删除一个结点时,必须将因删除结点而断开的二叉链表重新链接起来,同时确保二叉搜索树的性质不会失去。为保证在执行删除后,树的搜索性能不至于降低,还需要防止重新链接后树的高度增加。删除叶结点,只需将其双亲结点指向该结点的指针清空,再释放它即可。被删结点无右子树,可以拿该结点左孩子结点顶替它的位置,再释放它。被删结点无左子树,
13、可以拿该结点右孩子结点顶替它的位置,再释放它。,25,被删结点左、右子树都存在,有两种处理方式:用该结点的左孩子代替该结点,将其右子树插入到中序遍历该结点左子树时最后访问结点的右孩子上。用该结点的直接前驱或直接后继代替该结点,在处理其前驱或后继的删除问题。算法:P230-231,26,27,29,9.2.2 AVL树 高度平衡的二叉排序树,1)AVL树的定义,一棵AVL树或者是空树,或者是具有下列性质的二叉排序树:它的左子树和右子树都是AVL 树,且左子树和右子树的高度之差的绝对值不超过 1。,高度不平衡的二叉搜索树 高度平衡的二叉搜索树,30,结点的平衡因子(BF-Balance Facto
14、r):任一结点的左子树的高度减去右子树的高度所得的高度差称为该结点的平衡因子BF。根据AVL树的定义,任一结点的平衡因子只能取-1,0 和 1。如果一个结点的平衡因子的绝对值大于1,则这棵二叉排序树就失去了平衡,不再是AVL树。如果一棵二叉排序树是高度平衡的,它就成为 AVL树。如果它有 n 个结点,其高度可保持在O(log2n),平均查找长度也可保持在O(log2n)。,31,2)如何构造平衡二叉排序树,基本思想:在构造二叉排序树的过程中,每当插入一个新结点时,首先检查是否因插入而破坏了树的平衡性。若是,则找出其中最小不平衡子树,在保持二叉排序树特性的前提下,调整最小不平衡子树中各结点之间的
15、连接关系,以达到新的平衡。最小不平衡子树:以离插入结点最近,且平衡因子绝对值大于 1 的结点作为根的子树。假设二叉排序树的最小不平衡子树的根结点为 A,则有四种形态需要调整,32,LL型右旋,33,RR型 左旋,E,34,LR型先左旋后右旋,35,RL型先右旋后左旋,36,9.2.3 B-树,为什么采用B_树和B+树:大量数据存放在外存中,由于海量数据,不可能一次调入内存,要多次访问外存。硬盘的驱动受机械运动制约,速度慢。主要矛盾变为减少访外次数。在1970年由R bayer和E macreight 提出用B_树作为索引组织文件。提高访问速度、减少时间。,E.G:用二叉树组织文件,当文件的记录
16、个数为 100000时,要找到给定关键字的记录,需访问外存17次(log100000),50,25,10,75,15,35,60,90,20,30,40,55,70,80,95,索引文件,数据文件,文件头,可常驻内存,37,一棵 m 阶B-树是一棵平衡的 m 路搜索树,它或者是空树,或者是满足下列性质的m叉树:树中每个结点至多有 m 棵子树。若根结点不是叶子结点至少有 2 棵子树。除根结点以外的所有非终端结点至少有 m/2棵子树。所有的非终端结点中包含以下信息数据:(n,A0,K1,A1,K2,Kn,An)其中:Ki(i=1,2,n)为关键字,且KiKi+1,Ai为指向子树根结点的指针(i=0



- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 数据结构 第八

链接地址:https://www.desk33.com/p-229786.html