数据结构查找的技术1——静态查找表.ppt

若查找概率无法事先测定，则查找过程采取的改进办法是，在每次查找之后，将刚刚查找到的记录直接移至表尾的位置上。 在不等概率查找的情况下，ASLss 在 Pn≥Pn-1≥···≥P2≥P1 时取极小值 Evaluation only. Created with Aspose.Slides for .NET 3.5 Client Profile 5.2.0.0. Copyright 2004-2011 Aspose Pty Ltd. 上述顺序查找表的查找算法简单， 但平均查找长度较大，特别不适用于表长较大的查找表。 二、有序查找表 若以有序表表示静态查找表，则查找过程可以基于“折半”进行。 Evaluation only. Created with Aspose.Slides for .NET 3.5 Client Profile 5.2.0.0. Copyright 2004-2011 Aspose Pty Ltd. 折半查找 使用条件： 线性表中的记录必须按关键码有序； 必须采用顺序存储。 基本思想：在有序表中，取中间记录作为比较对象，若给定值与中间记录的关键码相等，则查找成功；若给定值小于中间记录的关键码，则在中间记录的左半区继续查找；若给定值大于中间记录的关键码，则在中间记录的右半区继续查找。不断重复上述过程，直到查找成功，或所查找的区域无记录，查找失败。 Evaluation only. Created with Aspose.Slides for .NET 3.5 Client Profile 5.2.0.0. Copyright 2004-2011 Aspose Pty Ltd. ST.elem ST.length 例如: key=64 的查找过程如下： low high mid low mid high mid low 指示查找区间的下界 high 指示查找区间的上界 mid = (low+high)/2 Evaluation only. Created with Aspose.Slides for .NET 3.5 Client Profile 5.2.0.0. Copyright 2004-2011 Aspose Pty Ltd. 第九章 查 找 Evaluation only. Created with Aspose.Slides for .NET 3.5 Client Profile 5.2.0.0. Copyright 2004-2011 Aspose Pty Ltd. 本章的主要内容是: 查找的基本概念（难度系数*） 静态查找表（难度系数**） 动态查找表（难度系数****） 哈希表（难度系数***） Evaluation only. Created with Aspose.Slides for .NET 3.5 Client Profile 5.2.0.0. Copyright 2004-2011 Aspose Pty Ltd. 何谓查找表 ？ 查找表是由同一类型的数据元素(或记录)构成的集合。 由于“集合”中的数据元素之间存在着松散的关系，因此查找表是一种应用灵便的结构。 查找的基本概念 Evaluation only. Created with Aspose.Slides for .NET 3.5 Client Profile 5.2.0.0. Copyright 2004-2011 Aspose Pty Ltd. 对查找表经常进行的操作: 1）查询某个“特定的”数据元素是否在查找表中； 2）检索某个“特定的”数据元素的各种属性； 3）在查找表中插入一个数据元素； 4）从查找表中删去某个数据元素。 Evaluation only. Created with Aspose.Slides for .NET 3.5 Client Profile 5.2.0.0. Copyright 2004-2011 Aspose Pty Ltd. 不涉及插入和删除操作的查找 。 涉及插入和删除操作的查找。 查找的基本概念 静态查找适用于：查找集合一经生成，便只对其进行查找，而不进行插入和删除操作，或经过一段时间的查找之后，集中地进行插入和删除等修改操作； 动态查找适用于：查找与插入和删除操作在同一个阶段进行，例如当查找成功时，要删除查找到的记录，当查找不成功时，要插入被查找的记录。 静态查找表 动态查找表 Evaluation only. Created with Aspose.Slides for .NET 3.5 Client Profile 5.2.0.0. Copyright 2