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

01在等概率查找的情况下，顺序表查找的平均查找长度为：02对顺序表而言，Ci=n-i+103ASL=nP1+(n-1)P2++2Pn-1+Pn若查找概率无法事先测定，则查找过程采取的改进办法是，在每次查找之后，将刚刚查找到的记录直接移至表尾的位置上。01在不等概率查找的情况下，ASLss在Pn≥Pn-1≥···≥P2≥P1时取极小值02上述顺序查找表的查找算法简单，但平均查找长度较大，特别不适用于表长较大的查找表。若以有序表表示静态查找表，则查找过程可以基于“折半”进行。0102二、有序查找表折半查找使用条件：线性表中的记录必须按关键码有序；必须采用顺序存储。基本思想：在有序表中，取中间记录作为比较对象，若给定值与中间记录的关键码相等，则查找成功；若给定值小于中间记录的关键码，则在中间记录的左半区继续查找；若给定值大于中间记录的关键码，则在中间记录的右半区继续查找。不断重复上述过程，直到查找成功，或所查找的区域无记录，查找失败。ST.elemST.length例如:key=64的查找过程如下：lowhighmidlowmidhighmidlow指示查找区间的下界high指示查找区间的上界mid=(low+high)/2第九章查找01020304查找的基本概念（难度系数*）静态查找表（难度系数**）动态查找表（难度系数****）哈希表（难度系数***）本章的主要内容是:01何谓查找表？03由于“集合”中的数据元素之间存在着松散的关系，因此查找表是一种应用灵便的结构。04查找的基本概念02查找表是由同一类型的数据元素(或记录)构成的集合。02010304查询某个“特定的”数据元素是否在查找表中；在查找表中插入一个数据元素；检索某个“特定的”数据元素的各种属性；从查找表中删去某个数据元素。对查找表经常进行的操作:查找的基本概念不涉及插入和删除操作的查找。涉及插入和删除操作的查找。静态查找适用于：查找集合一经生成，便只对其进行查找，而不进行插入和删除操作，或经过一段时间的查找之后，集中地进行插入和删除等修改操作；动态查找适用于：查找与插入和删除操作在同一个阶段进行，例如当查找成功时，要删除查找到的记录，当查找不成功时，要插入被查找的记录。静态查找表动态查找表是数据元素（或记录）中某个数据项的值，用以标识（识别）一个数据元素（或记录）。若此关键字可以识别唯一的一个记录，则称之谓“主关键字”。关键字若此关键字能识别若干记录，则称之谓“次关键字”。50女李爽000525女齐梅000447女刘楠000325男张亮000238男王刚0001年龄性别姓名职工号1972.92003.71979.92003.71990.4工作时间1根据给定的某个值，在查找表中确定一个其关键字等于给定值的数据元素或（记录）。2查找3若查找表中存在这样一个记录，则称“查找成功”。查找结果给出整个记录的信息，或指示该记录在查找表中的位置；否则称“查找不成功”。查找结果给出“空记录”或“空指针”。由于查找表中的数据元素之间不存在明显的组织规律，因此不便于查找。为了提高查找的效率，需要在查找表中的元素之间人为地附加某种确定的关系，换句话说，用另外一种结构来表示查找表。01查找的方法取决于查找表的结构。02如何进行查找？9.1静态查找表9.2动态查找树表9.3哈希表主要采用顺序查找技术和折半查找技术。主要采用二叉排序树的查找技术。静态查找和动态查找均适用，主要采用散列技术。查找算法的性能查找算法时间性能通过关键码的比较次数来度量。关键码的比较次数与哪些因素有关呢？平均查找长度：将查找算法进行的关键码的比较次数的数学期望值定义为平均查找长度，即：ASL?==niiicp1ci取决于算法；pi与算法无关，取决于具体应用。如果pi是已知的，则平均查找长度只是问题规模的函数。9.1静态查找表数据对象D：数据关系R：D是具有相同特性的数据元素的集合。每个数据元素含有类型相同的关键字，可唯一标识数据元素。数据元素同属一个集合。ADTStaticSearchTable{Create(ST,n);Traverse(ST,Visit());Search(ST,key);}ADTStaticSearchTableDes