数据结构与算法 第3版 教学课件作者 张小莉第6章 查找

第六章查找技术第2页2023年2月17日教学内容：查找的基本概念、线性表查找、树结构查找、散列表查找教学目的：理解查找的基本思想；掌握查找表的几种组织及查找方法。教学重点：查找表的基本概念及查找原理；查找表的几种组织及查找方法。教学难点：查找表的不同组织及查找方法 第3页2023年2月17日 6.1 引言1.查找表 (1)查找表是一种以集合为逻辑结构、以查找为核心的数据结构。(2)由于集合中的数据元素之间是没有“关系”的，因此在查找表的实现时就不受“关系”的约束，而是根据实际应用对查找的具体要求去组织查找表，以便实现高效率的查找。(3)对查找表中常做的运算有：建立查找表、查找、读取表元，以及对表做修改操作（如插入、删除元素）等等。第4页2023年2月17日2.关键码关键码是数据元素（记录）中某个项或组合项的值，用它可以标识一个数据元素。第5页2023年2月17日3.查找查找：是指在含有n个元素的查找表中，找出关键码等于给定值kx的数据元素（或记录）。第6页2023年2月17日4.静态查找 动态查找若对查找表的查找过程不包括对表的修改操作，则此类查找称为静态查找，若在查找的同时插入表中不存在的数据元素，或从查找表中删除已存在的指定元素，则此类查找称为动态查找。第7页2023年2月17日 5平均查找长度-衡量查找效率的指标 由于查找运算的主要操作是关键字的比较，所以，通常把查找过程中对关键字的比较次数的平均值作为衡量一个查找算法效率优劣的标准，称之为平均查找长度（Average Search Length），通常用ASL表示。第8页2023年2月17日6.2线性表查找在本节中，定义线性查找表的顺序存储结构线性查找表的顺序存储结构如下：#define MAXNUM datatype dataMAXNUM；/*/*查找表存储空间*/int n；/*查找表中元素的个数*/第9页2023年2月17日 线性查找表链式存储线性查找表链式存储其结点结构类型定义如下：typedef struct node datatype data；/*元素的数据域*/struct node *next；/*/*下一个元素的指针域*/LSNode,*LSTable；第10页2023年2月17日6.2.1 顺序查找顺序查找又称线性查找，是最基本的查找方法之一。其查找方法为：从表的一端开始，向另一端逐个按给定值kx与关键码进行比较，若找到，查找成功，并给出数据元素在表中的位置；若整个表检测完，仍未找到与kx相同的关键码，则查找失败，给出失败信息。第11页2023年2月17日1顺序表上的查找象顺序表一样，查找表中的数据元素依次顺序存储。顺序查找简单，很容易按下列算法7-1(a)方法实现。第12页2023年2月17日第13页2023年2月17日时间性能：则查找成功时，顺序查找的平均查找长度为：ASL=Pi（n-i+1）ni=1ni=1ASL=（n-i+1）=设每个数据元素的查找概率相等，则等概率情况下有：第14页2023年2月17日2单链表上的查找设查找表组织为带头结点的单链表，在单链表上的顺序查找算法如下。第15页2023年2月17日讨论以下4种方法：1折半查找 *2 插值查找 *3斐波那契查找 4分块查找6.2.2 在顺序存储的有序表上查找第16页2023年2月17日1折半查找 条件：查找表按关键码有序且顺序存储条件：查找表按关键码有序且顺序存储。【例6-1】顺序存储的有序表关键码排列如下，做折半查找。7，14，18，21，23，29，31，35，38，42，46，49，52第17页2023年2月17日 第18页2023年2月17日【例6-1】顺序存储的有序表关键码排列如下，做折半查找。7，14，18，21，23，29，31，35，38，42，46，49，524938291874252312346351421图7-2例7-1描述折半查找过程的判定树折半查找的时间效率为O(log2n)。第19页2023年2月17日2.插值查找：使用条件：顺序存储且按关键码有序且均匀分布。时间性能：O(log2n)(high-low)（7-5）kx-datalow.keyt.datahigh.key-t.datalow.keymid=low+插值查找除要求查找表是顺序存储的有序表外，还要求数据元素的关键字在查找表中均匀分布。以下式取中间点：第20页2023年2月17日3.斐波纳契查找按斐波纳契数列将有序的查找便分割成两个不等的区间：若表长n=F(k)-1,分割点为：mid=F(k-1)-1kk=0或k=1F(k-1)+F(k-2)n2F(k)=（7-6）使用条件：顺序存储且关键码有序。时间性能：O(log2n)第21页2023年2月17日 4分块查找若查找表中的数据元素的关键字是按块有序按块有序的，则可以做分块查找。分块查找又称索引顺序查找，是对顺序查找的一种改进。第22页2023年2月17日树表查找是将查找表按照某种规律建构成树型结构。因为建构的树型结构是按某种规律建立的，因此查找过程也遵循这种规律，可以获得较高的查找效率。6.3 树表的查找 第23页2023年2月17日1.二叉排序树定义 6.3.1 二叉排序树5842987090634555836710特点：中序遍历序列关键码有序中序遍历序列关键码有序。第24页2023年2月17日 以二叉链表作为二叉排序树的存储结构，二叉链表结点的类型定义如下：typedef struct bistnode datatype data;struct bistnode*lchild,*rchild;BiSTNode,*BiSTree;第25页2023年2月17日第26页2023年2月17日第27页2023年2月17日3二叉排序树中插入一个结点设待插入结点的关键码为kx，为将其插入，先要在二叉排序树中进行查找，若查找成功，按二叉排序树定义，待插入结点已存在，不用插入；查找不成功时，则插入之。因此，新插入结点一定是作为叶子结点添加上去的。第28页2023年2月17日第29页2023年2月17日4构造一棵二叉排序树按照读入的关键码序列，构造一棵二叉排序树的算法如下：第30页2023年2月17日【例6-3】记录的关键码序列为：63,90,70,55,67,42,98,83,10,45,58，则构造一棵二叉排序树的过程如下：636390706390557063906755706390426755706390984267557063908398426755706390108398426755706390(1)(6)(3)(4)(5)(2)(8)(7)(9)第31页2023年2月17日从空树开始建立二叉排序树的过程834510425563986770908358451042556398677090(10)(11)108398426755706390(9)第32页2023年2月17日5二叉排序树中删除一个结点设待删结点为p（p为指向待删结点的指针），其双亲结点为f，以下分三种情况进行讨论。(1)p结点为叶结点。fpFPF第33页2023年2月17日(2)p结点只有右子树pR或只有左子树pL。只需将只需将p pR R或或p pL L替换替换f f结点的结点的p p子树即可。子树即可。fFPfpPLFfPLFPfpPRFPL第34页2023年2月17日(3)p结点既有左子树PL又有右子树PR，可按中序遍历保持有序进行调整。fpFPPLS1P1SRPRS2P2SJPJ第35页2023年2月17日删除p结点后，有2种调整方法：直接令p结点的右孩子pl为f相应的子树，将p的原左子树PL作为以pl为根的子树中序遍历的第一个结点 pr的左子树；如图9-7(a)。图9-7(a)按方法进行调整的图示fpFPPLS1P1SRPRS2P2SJPJfFPLS1P1SRPRS2P2SJPJ第36页2023年2月17日SJPJfPFPPlS1P1S2P2SPRfPFPRPlP1P1P2P2SJPJS令*p结点的中序直接后继PR(或中序直接前驱)替换*p结点，再按单支结点的(2)的方法删去PR。图9.8所示以*p结点的直接后继PR替换*p。第37页2023年2月17日第38页2023年2月17日如何使二叉排序树的查找效率提高？如查找表中的关键码顺序为：63,90,70,55,67,42,98,83,10,45,58 和顺序为：10,42,45,55,58 63,67,70,83,90,98的情况，组织的二叉排序树大不相同。第39页2023年2月17日*6.3.2 平衡二叉树（AVL）树1平衡二叉树的定义 91000065504741853060727842-330-202141853060727842-111001 0a.非平衡二叉树b.平衡二叉树第40页2023年2月17日对该子树进行平衡化调整归纳起来有以下四种情况：(1)在某结点左孩子的左子树上插入结点使该结点失衡（LL）；(2)在某结点右孩子的右子树上插入结点使某结点失衡（RR）；(3)在某结点左孩子的右子树上插入结点使某结点失衡（LR）；(4)在某结点右孩子的左子树上插入结点使某结点失衡（RL）。第41页2023年2月17日对于平衡二叉树的定义如下：typedef struct avlnode datatype data;/*数据元素*/int bf;/*平衡因子*/struct avlnode*lchild,*rchild;/*左右孩子指针*/AVLNode,*AVLTree;第42页2023年2月17日(1)LLLL型：做右单旋转调整型：做右单旋转调整a.插入前b.插入后，调整前c.调整后h+1h+1EcBaDx00hBaDcEhh01hxhBaDcEh+121第43页2023年2月17日第44页2023年2月17日(2)RR(2)RR型：做左单旋转调整型：做左单旋转调整BhahEcDh0-1xBhaEcDhh+1-2-1xEh+1cDaBh+100a.插入前b.插入后，调整前c.调整后第45页2023年2月17日第46页2023年2月17日 (3)LR型：做先左后右双向旋转调整hDbh-1GcFh-1hEa001第47页2023年2月17日2h-1GchEaDhbFxh02hDbh-1GcFh-1hEax12-1h-1GhEacDhbFxh00-11型：a.插入后，调整前b.先左旋转c.再右旋转第48页2023年2月17日2型：d.插入后调整前e.先左旋转f.再右旋转h-1cGhEaDhbFxh001h-1GchEaDhbFxh112hDbh-1GcFh-1hEax2-1-1调整策略：调整策略：无论将结点x插入到c的左子树还是右子树，只要使得c的高度增加，调整的方法都是一样的。先对以b为根的子树进行RR型调整，然后再对以a为根的树进行LL型调整。第49页2023年2月17日第50页2023年2月17日(4)RL型：做先右后左双向旋转 这种失衡是因为在失衡结点的右孩子的左子树上插入结点造成的。bhD1Eh-1xac-21Fh-1h-1GhbhD-1Eh-1xac-1GhFh-1h-1-2hDEh-1xGhFh-1h-1b-1ac00调整策略：调整策略：无论将结点x插入到c的左子树还是右子树，只要使得c的高度增加，调整的方法相同。先对以b为根的子树进行LL型调整，然后再对以a为根的树进行RR型调整。调整后的二叉树如图(c)a.插入后，调整前b.先右旋转c.再左旋转第51页2023年2月17日第52页2023年2月17日【例6-4】已知长度为11的表：20,12,6,28,16,36,32,10,2,30,8。请按表中元素的顺序构造一棵平衡二叉排序树，并求其在等概率的情况下查找成功的平均查找长度。第53页2023年2月17日因此，含有n个结点得平衡树的最大深度为：故：在平衡树上进行查找的时间复杂度近似为：(log2n)可证明：当h0时Nh=Fh+2-1,而Fk约等于：其中：则Nh约等于：第54页2023年2月17日