数据结构课件-11-1静态查找.pptx

数据结构计算机领域本科教育教学改革试点工作计划（“101计划”）研究成果俞勇、张铭、陈越、韩文弢上海交通大学、北京大学、浙江大学、清华大学101

11.1静态查找第11章查找林劼电子科技大学

11.1静态查找3仅作查询和检索操作的查找表。静态查找表“查询”结果“不在查找表中”?数据元素插入到查找表中；“查询”结果为“在查找表中”的数据元素?删除。动态查找表查找表分类

11.1静态查找关键字：是数据元素中某个数据项的值，用以标识一个数据元素。查找过程中，往往是依据数据元素的某个数据项进行查找，这个数据项通常是数据的关键字。若关键字能标识唯一的一个数据元素，则称谓主关键字。若关键字能标识若干个数据元素，则称谓次关键字。张三2016010002男成都1.75

11.1静态查找平均查找长度ASLPi——查找第i个元素的概率Ci——查找第i个元素需要的比较次数ASL=P1C1+P2C2+...+PnCn

11.1.1顺序查找11.1.2折半查找11.1.3索引查找11.1.4作业

11.1静态查找5271394111.1.1顺序查找

11.1.1顺序查找从表中指定位置（一般为最后一个，第0个位置设为岗哨）的记录开始，沿某个方向将记录的关键字与给定值相比较，若某个记录的关键字和给定值相等，则查找成功；反之，若找完整个顺序表，都没有与给定关键字值相等的记录，则此顺序表中没有满足查找条件的记录，查找失败。顺序查找基本思想

11.1.1顺序查找RRi60ikey=64key=6064iiiiiiiiiii

11.1.1顺序查找空间复杂度：时间复杂度：查找算法的基本运算是给定值与顺序表中记录关键字值的比较。O(1)最好情况：最坏情况：平均情况：O(1)O(n)O(n)性能分析

11.1.1顺序查找平均查找长度（ASL）：给定值与关键字比较次数的期望值。对于具有n个记录的顺序表，查找成功时的平均查找长度为：Pi——查找第i个记录的概率Ci——找到第i个记录数据需要比较的次数，对于顺序表，Ci=n-i+1顺序表上顺序查找的平均查找长度

11.1.1顺序查找等概率情况不等概率--每个元素的查找概率已知--每个元素的查找概率未知

11.1.2折半查找有序表：如果顺序表中的记录按关键字值有序，即：R[i].key≤R[i+1].key（或R[i].key≥R[i+1].key），i=1,2,…,n-1，则称顺序表为有序表。1371012124有序表1371312124无序表11.1.2折半查找

11.1.2折半查找将待查关键字与有序表中间位置的记录进行比较，若相等，查找成功，若小于，则只可能在有序表的前半部分，若大于则只可能在有序表的后半部分，因此，经过一次比较，就将查找范围缩小一半，这样一直进行下去直到找到所需记录或记录不在查找表中。查找过程：

11.1.2折半查找RR.length例如:key=64的查找过程如下：highmidlowmidhighmidlow指示查找区间的下界high指示查找区间的上界mid=(low+high)/2low

11.1.3索引查找数据太多，杂乱无章，查找困难！11.1.3索引表查找

11.1.3索引查找建立索引！

索引使用方法11.1.3索引查找先分析数据规律，建立索引再根据索引进行快速定位在定位的地方进行细致有哪些信誉好的足球投注网站

811.1.3索引查找第一个块地址第一个块最大关键字第二个块地址第二个块最大关键字…………第n个块地址第n个块最大关键字先分块，块间有序，就可以快速定位到块490888970……

11.1.3索引查找分块：第Rk块中所有关键字Rk+1块中所有关键字，（k=1,2,…,L-1）2)建立索引项：关键字项：记载该块中最大关键字值；指针项：记载该块第一个记录在表中位置。3)所有索引项组成索引表。索引表的构建

11.1.3索引查找

11.1.3索引查找索引表的查找索引表的查找查找表的查找索引表有序

11.1.3索引查找例子：关键字224886指针171319(n+1)22,12,13,8,9,20,33,42,44,38,24,48,60,58,74,49,86,53查找表建立索引表

11.1.3索引查找例子：关键字224886指针171319(n+1)22,12,13,8,9,20,33,42,44,38,24,48,60,58,74,49,86,53查找关键字k=38

11.1.3索引查找例子：关键字224886指针171319(n