数据结构 第9章 查找.ppt

1.数据结构课程、2、8.1基本概念8.2静态查找表8.3动态查找表8.4哈希表，第8章查找，第8、11和12章的内容被省略，因为操作系统课程将涵盖。3，8.1基本概念，如果表中有特定的元素，则认为搜索成功，并应输出记录。否则，表示搜索不成功(也应输出故障标志或故障位置)。搜索表搜索成功。搜索未成功。静态搜索不成功。动态搜索是关键。副钥匙。是同一类型的数据元素(或记录)的集合。查询(搜索)表中是否有特定元素。仅搜索，不会更改集合中的数据元素。查找并改变(增加或减少)集合中的数据元素。记录中数据项的值可用于识别记录(预定记录的某个标记)。可以唯一地标识记录的关键字，如“学生编号”或“女性”，这是一种数据结构。识别几个记录的关键词。4，(2)查找表的常见操作是什么？查询表中是否有“特定”数据元素；查询“特定”数据元素的各种属性；将元素插入查找表；从查找表中删除元素。(3)有哪些搜索方法？搜索方法取决于表中数据的排列。(1)什么是搜索过程？给定一个k值，搜索包含n条记录的文件，找到一条键值等于k的记录，如果找到，输出该记录，否则，输出搜索不成功的信息。例如，查找字典，静态查找表和动态查找表的查找方法也不同。【具体】=关键词，5，(4)如何评价搜索方法的优缺点？很明显，搜索过程是将给定的k值与文件中每个记录的关键项目进行比较的过程。因此，使用平均比较次数来评估算法。这被称为平均查找长度。其中：n是文件记录的数量；是搜索第一条记录的搜索概率(通常是相等的概率，即=1/n)；配置项是找到我的记录时经历的比较次数。统计数学期望值和物理意义：假设找到每个元素的概率是相同的，找到每个元素所需的比较时间的总和被再次平均，即ASL。显然，美国手语值越小，时间效率越高。静态查找表的主要搜索算法是：8.2静态查找表。关于静态查找表的抽象数据类型，请参见教材P216。第一，顺序搜索(线性搜索)第二，二进制搜索(二进制或二进制搜索)第三，静态树表搜索第四，块搜索(索引顺序搜索)，7，第一，顺序搜索(也称为线性搜索)，(1)顺序表的内部存储结构：typedefstruct ElemType * elem/表基地址，单元格0为空。表容量是所有元素的长度；/表长度，即表中数据元素的数量表；顺序搜索：通过逐一比较来顺序搜索关键词，这显然是最直接的方法。如何线性找到序列结构？参见下页示例或教材P216；如何线性找到单链表的结构？虽然没有给出函数，但它也很容易编写。只要你知道头部指针的头部，你就可以“沿着成功的道路前进”。如何依次找到非线性树结构？可以使用各种遍历操作！(2)算法的实现：要搜索的关键字存储在页眉或页脚(通常称为“哨兵”)，这可以加快执行速度。例如，如果要搜索的特定值关键字存储在序列表的标题中(如单元0)，则序列搜索的实现方案是：从后向前逐个比较！intsearch _ seq (sstablest，key typekey)/在序列表ST中，查找具有相同键的元素；如果成功，返回其位置信息，否则返回0ST.elem0。key=key/设置岗哨可以避免在搜索过程的每一步都检查搜索是否完成。当n1000时，搜索时间将减少一半。对于(I=标准长度；圣埃林一世。钥匙。=键。-I)；/不要用于(I=n；i0；-i)或(I=1；i=n。I)return I；/如果循环直到到达单元号0才结束，则表示循环不成功，并返回值0 (i=0)。论成功/search _ seq，9，返回特殊标志，如空记录或空指针。在前面的例子中，设置了一个“哨兵”，将钥匙发送到最后一个地址圣埃勒姆0。键结束它并返回i=0。讨论如何计算搜索效率。是通过平均查找长度ASL测量的。如果我找不到它，我该怎么办？如何计算美国手语？分析：查找第一个元素所需的比较次数为1；找到第二个元素所需的比较次数是2；找到第n个元素所需的比较次数是n；不管搜索是否成功，比较的总数是：1 2 n=(1 n) n/2:找到哨兵所需的比较数是n 1，这是一个成功的搜索。如果找到一个元素的平均搜索次数，也应该除以n(等概率)，即ASL=(1 n)/2，时间效率为0(n)、10、2和2，二进制搜索(也称为二进制搜索或二进制搜索)。优点：算法简单，适用于序列结构或链表结构。缺点：手语太长，时间效率太低。这是一种易于思考的搜索方法。首先对数据进行排序(例如，按升序)以形成一个有序的表，然后将键与中间元素进行比较。如果密钥很小，它将被缩小到搜索的右半部分。然后取中间值进行比较，每次缩小范围1/2，直到搜索成功或失败。如何编写序列表结构来实现二进制搜索算法？参见下一页的例子，或者参见教科书(P219)关于如何找到单个链表结构的一半。无法实现！因为所有的元素只能从头指针定位，非线性(树)结构如何减半？可以通过二进制排序树(以动态查找表的形式)找到。我们如何改进？(1)低=1，高=11，中=6，要检查的范围是1，11；(2)如果圣埃勒姆中部。键盘键，指示键低，中-1，然后：高=中-1；重新计算中间值；(4)如果圣埃勒姆mid。key=key，搜索成功，元素编号=mid结束条件：(1)成功搜索：圣埃勒姆中部。key=key (2)搜索不成功：highLow(即间隔长度小于0)，解决方法：第一组3个辅助标志：low、high、mid、半搜索示例：Low指向要检查的元素所在的间隔的下限，high指向要检查的元素所在的间隔的上限，Mid指向要检查的元素所在的间隔的中间位置，并且下面的11个元素的有序表是已知的：(05131923121337请找到关键字为21和85的数据元素。很明显，中间值=(低高)/2。这个例子是自测题中的一个算法问题，建议在计算机上进行验证。如果关键字不在表中，您如何知道并停止？的典型标志是当搜索范围的上限小于或等于下限时停止搜索。(2)讨论了二元搜索的效率。经过一次比较，有一个元素(20)是中间值。经过两次比较，成功找到2 (21)个元素，即1/4(或3/4)个位置；经过3次比较发现有4 (22)个元素成功，即1/8(或3/8) 经过4次比较发现有8 (23)个元素成功，即1/16(或3/16) 然后在m次比较中发现有(2m-1)个元素成功；为了方便起见，假设表中的所有n个元素=2m-1，并且在第m次比较之后还有剩余元素的情况将在此时不再讨论。比较总数为120 221 322 423.m2m-1=，派生过程，13，每个数据的平均搜索时间除以n，因此：(详见教材P221附录1派生过程)，课堂练习(多项选择):(a)使用链式存储结构b，记录长度 128c。使用顺序存储结构d。记录按关键字和升序排列。使用二进制搜索算法时，需要搜索文件：思考：假设在有序线性表a20上执行二进制搜索，平均搜索长度为14。搜索过程可以用二叉树来描述：每个记录由一个节点来表示；节点中值是记录在表中的位置。描述搜索过程的二叉树叫做决策树。用于n元素表的二进制搜索的决策树是唯一的，即决策树由表中元素的数量决定。在有序表中查找任何记录的过程是遵循从根节点到对应于r的节点的路径比较的关键字数：决策树中节点的级别数。当搜索成功时，所比较的关键字数量最多不应超过树的深度d:d=log2n1。如果所有节点的空指针字段被设置为指向方形节点的指针，则方形节点被称为决策树的外部节点。相应地，圆形节点是内部节点。不成功搜索的过程是从根节点到外部节点的路径。(见教材P220):15，3，静态树表搜索，讨论2:当有序表中每条记录的搜索概率不相等时，如何查找？首先，应该清楚的是，半搜索方法不一定是最好的！(见教材P222)，改进：如果每个记录概率被视为二叉树的权重，则改为研究具有最小加权路径长度的二叉树(类似于最优二叉树)。讨论1:对于有序表还有其他搜索算法吗？静态最优搜索树算法具有高时间成本。实用算法：近似最优搜索树(次优搜索树)(见教材P222225)，如斐波那契搜索和插值搜索(见教材P221-222)，16，4，块搜索(索引序列搜索)，这是另一种改进的序列搜索方法。首先，数据以有序的方式被分成几个子表，要求每个子表中的值(更准确地说是关键字)小于后一个块中的值(但是子表的内部部分不一定是有序的)。然后，每个子表中的最大关键字被形成索引表，并且该表还包含每个子表的起始地址(即标题指针)。索引表，最大关键字，起始地址，第一个块，第二个块，第三个块，22，48，86，示例：特征：块间有序，块内无序，17，搜索步骤分两步进行：(1)索引表使用二进制搜索方法(因为索引表是有序表)；(2)在确定待搜索关键字所在的子表后，在子表中采用顺序搜索方法(因为每个子表都是无序表)；搜索效率：ASL=Lb Lw，ASL用于索引表搜索，ASL和S用于块搜索是每个块中的记录数，n/s是块数，例如，当n=9和s=3时，ASL，S=3.5，而二进制方法是3.1，顺序方法是5，18。特征：二叉排序树的定义，二叉排序树的插入和删除，二叉排序树的搜索分析，四叉平衡二叉树，8.3动态查找表，搜索过程中动态生成的表结构，要求：对于给定的值键，如果表中有一条记录的键等于键，搜索将成功返回；否则，插入一个关键字等于该关键字的记录。典型的动态表-二进制排序树，19，二进制排序树的定义，练习：下列两种图中哪一种不是二进制排序树？或者一棵空树；或者是非空的二叉树，具有以下性质：(1)左子树的所有节点都小于根的值；(2)右子树的所有节点都大于根的值；(3)它的左右子树也分别是二叉排序树。遍历(a)中的顺序的结果是什么？20、二进制和二进制排序树的插入和删除具有将数据元素构造成二进制排序树的优点：搜索过程类似于序列结构有序表中的二进制搜索，搜索效率高；(2)如果中间顺序遍历该二叉树，将获得关键字的有序序列(即，已经实现了排序操作)；(3)如果搜索不成功，被检查的元素可以容易地插入到二叉树的叶节点中，并且在插入或删除时只需要修改指针而不移动元素。注意：如果数据元素的输入顺序不同，得到的二进制排序树也不同！搜索和插入的过程称为动态搜索。二叉排序树不仅具有类似于二叉搜索的特性，而且使用链表存储，这是动态查找表的一种合适的表示。，21，45，如果要搜索的关键字序列的输入顺序是：(24，53，45，45，12，24，90)，24，讨论1:二进制排序树的插入和搜索操作，那么生成二进制排序树的过程是：例如：输入要搜索的关键字序列=(45，24，53，45，12，24，90)，那么生成的二进制排序树具有不同的形状：22，参见教科书P228算法9.5(b)，一个“二合一”算法如下：23，BSTSARCH(K，t)/K是要搜索的关键字，t是根节点指针p=t；/p是指针，而(p！=NULL)事例 K=数据(p):搜索成功，返回 K data(p): q=p；P=R_child(p)/继续向右搜索、获取；数据=K；l _ child=空；r _ child=空；/搜索不成功，生成了一个新节点s，并将其插入到二进制排序树中 t=null:p=s；/如果t为空，则插入的节点s作为根节点Kdata(q): R _ child(q)=s；returnOK，24，对于二进制排序树，删除树上的一个节点相当于删除有序序列中的一条记录，删除后应保持二进制排序树的特征。(删除链接列表非常方便)。讨论2:二叉排序树的删除以及如何删除节点。假设：*p表示被删除节点的指针；P1和PR分别代表*P的左和右子指针；*f表示*p的父节点指针；假设*p是*f的左子。可能有三种情况：右子树与公共关系；SL是Q的右子节点(*S的父节点)，*p是叶子：删除此节点时，可以直接修改*f指针字段；*p只有一个子树(或左或右):让P1或PR是*f的左子树；*p有两个子树：情况最复杂 25，* P有两个子树，如何删除？分析：让我们假设删除前中间序列的遍历顺序是：。显然，P的直接前兆是S想要删除P，而其他元素的相对位置不会改变。有两种解决方法：方法1:让*p的左子树是*f的左子树，让*p的右子树是*s的右子树；/即FL=PLFR=公共关系；方法2:让*s替换*p/*s作为*p的左子树的最左下叶，26，2:1:例如：请从下面的二进制排序树中删除节点P。在二进制排序树上找到一个关键字等于给定值的节点的过程实际上是从根到节点的路径。比较的关键字数=该节点的级别数；最大比较次数=树的深度(或高度)，即log2n12。二叉排序树的平均搜索长度为：三叉和二叉排序树的搜索分析，其中：ni是每层中的节点数；Ci是节点所在的级别数；m是树的深度。最坏的情况：插入的n个元素从一开始就被排序，变成了一棵树！这时，树的深度是n；搜索效率与顺序搜索相同。最好的情况是它与二进制搜索中的决策树相同(形式相对平衡)，以及3)具有n个关键字的二进制排序树的平均搜索长度：被设置为对于每个树状态具有相同的出现概率，并且对于每