提升篇课件提高第7章

1、主讲人第1章绪第5章树主讲人第1章绪第5章树和二叉第2章线性第6章第3章栈和队列第7章查找第4章串、数组和广义第8章排第7章查找第7章查找板块一：本章基础板块一：本章基础巩固7.1 查找的基本概查找表由同一类型的数7.1 查找的基本概查找表由同一类型的数据元素（静态查找表）的集查找的同时对查找表不做修改操作（动态查找表查找的同时对查找表具有修改操和删除中某个数据项的中某个数据项的值，可用来识别唯一标识数据元可以标识若干个数据元关键字的平均比较次数，也称平均搜关键字的平均比较次数，也称平均搜索长度ASL(Average Search SL 的个的概率 (通常认为pi =1/n) 线性表的查一、顺

2、序查找（线性查找线性表的查一、顺序查找（线性查找应用范围顺序表或线性链表表示的静态查表内应用范围顺序表或线性链表表示的静态查表内间无顺序表的表typedefstruct*R;/表基第2章在顺序表L中查找值为eLocateELem(SqListL,ElemTypee) for (i=0;i L.length;i+)if(L.elemi=e)returnreturn改进：把待查关键字key存入表头（“哨兵”），第2章在顺序表L中查找值为eLocateELem(SqListL,ElemTypee) for (i=0;i L.length;i+)if(L.elemi=e)returnreturn改进：

3、把待查关键字key存入表头（“哨兵”），空间复杂度：一个辅助空间时间复杂度查找成功时的平空间复杂度：一个辅助空间时间复杂度查找成功时的平均查找长设表中查找概率相2算法简单，对表结构无任何要求（顺序和链式n很算法简单，对表结构无任何要求（顺序和链式n很大时查找效率较改进措施：非等概率查找时，可按照行排序练习:判断对查找概率相等时，ASL相同查找概率不等时，如果从前向后查找，则按查找概率由大到小排列的有序表其L要比无序表L小。n个数练习:判断对查找概率相等时，ASL相同查找概率不等时，如果从前向后查找，则按查找概率由大到小排列的有序表其L要比无序表L小。n个数存在一维数组A1.n中，在进行顺序查找

4、时这n个数的排列有序或无序其平均查找长度ASL不同折半查找（非递归算法设表长为n，low、high和mid中点,k初始时，令让k与mid若k=Rmid.key若kRmid.key，则重复上述操作，直至lowhigh折半查找（非递归算法设表长为n，low、high和mid中点,k初始时，令让k与mid若k=Rmid.key若kRmid.key，则重复上述操作，直至lowhigh【算法描述】-算法【算法描述】-算法折半查找（递归算法if(lowhigh)return/折半查找（递归算法if(lowhigh)return/查找不到时返回if(key等于emmid.key) returnelse if

5、(key小于else. /递归查找过程：每次将待所在区间比顺序查查找过程：每次将待所在区间比顺序查找效率高,时间复杂度O(log2 适用条件：采用顺于链式结结构的有序表一块中数值小（含每个子表的起始地址（即头指针）索引17第2第3第189一块中数值小（含每个子表的起始地址（即头指针）索引17第2第3第189 对索引表使用折半查找法（ 对索引表使用折半查找法（因为索引表是有序表 确定了待查关键字所在的子表后，在子表内采用顺查找法（因为各是无序表查找效率对索引表查找的对块内查找的 n1)n查找效率对索引表查找的对块内查找的 n1)n s) 2ASLbs log(log2n 2个数，n/s即块的数S

6、的优点和删除比较容易，无需进行优点和删除比较容易，无需进行大量移动缺点：要增加一个索引空间并对初始索引表进行排序运适用情况：如果线性表既要快速查找又经常动态变化，则可采用分块找7.3表结构在查找过程中动态7.3表结构在查找过程中动态生对于给定值若表中存在，则成功返回否关键字等于的二叉排序树或是空树，或是满足如下性质的二叉(1非空，则上所有结点的值均于根结点的值(2二叉排序树或是空树，或是满足如下性质的二叉(1非空，则上所有结点的值均于根结点的值(2非空，则上所有结点的值均于等于根结点的值(3本身又各是一棵二叉排序】（1）（2）若二叉排序树非空，将给定值key字T-data.key进行比较】（1

7、）（2）若二叉排序树非空，将给定值key字T-data.key进行比较 若key小于T-data.key，则进一步；key大于T-data.key，则进一步。平均查找长度和二叉树的形态有关最好：log平均查找长度和二叉树的形态有关最好：log2n（形态匀称，与二分查找的判定树相似:（n+1)/2（单支树是平衡二叉树平衡因子:该结点深度之差的绝1与是平衡二叉树平衡因子:该结点深度之差的绝1与的高度练习：判断下列二叉树是否AVL2-010100练习：判断下列二叉树是否AVL2-010100100如果在一棵AVL一个新结点，就有可能造成失衡，此时如果在一棵AVL一个新结点，就有可能造成失衡，此时重新

8、调整树的结构，使之恢复转LL称调整平衡过程为保证二叉排序的次序不RRLRRL哈希表的查：的哈希函优点：查找哈希表的查：的哈希函优点：查找速度极快O(1),查找效率与元素个数n哈希表的查哈希表的查例若将学生信息按如下方式存入计算机将2001011810201的所有信息存入V01例若将学生信息按如下方式存入计算机将2001011810201的所有信息存入V01单元将2001011810202的所有信息存入V02单元将2001011810231的所有信息存入V31单元查找2001011810216的信息，可直例数据元素序列(14，23，39，9，25，11)，若规定每个元素k地址H（k）k，请画9例

9、数据元素序列(14，23，39，9，25，11)，若规定每个元素k地址H（k）k，请画99根据哈希函数查找key=9,H(9)=9号地址，若内容为9则成功若查不到，则9根据哈希函数查找key=9,H(9)=9号地址，若内容为9则成功若查不到，则返回一个特殊值，如空。已知一组关键字13, 哈希表长为已知一组关键字13, 哈希表长为(1，即m2345678911121431139113，H1=(1+1)(1，即m2345678911121431139113，H1=(1+1)0123456789101234567891关键字无序表查找有序关键字无序表查找有序表折半查找使用平均查找长度ASL来衡量查找算法，ASL表中填入的数 的哈