数据结构导论第6章查找表.ppt

第6章　查找表 查找(Search)的相关概念 查找：就是在数据集合中寻找满足某种条 件的数据对象。 查找表：是由同一类型的数据元素(或记录)组成的数据集合。 查找的结果通常有两种可能： 查找成功，即找到满足条件的数据对象。 查找不成功，或查找失败。作为结果， 报告一些信息，如失败标志、失败位置等。 对查找表经常进行的操作: 1）查询某个“特定的”数据元素是否在查找表中； 2）检索某个“特定的”数据元素的各种属性； 3）在查找表中插入一个数据元素； 4）从查找表中删去某个数据元素。 关键字(Key)：数据元素(记录)中某个数据项的值，用以标识一个数据元素。 主关键字：可唯一地标识一个数据元素的关键字。 次关键字：用以识别若干记录的关键字。 使用基于主关键字的查找，查找结果应是唯一的。 如何进行查找？ 查找的方法取决于查找表的结构。 由于查找表中的数据元素之间不存在明显的组织规律，因此不便于查找。 为了提高查找的效率，需要在查找表中的元素之间人为地附加某种确定的关系，换句话说， 用另外一种结构来表示查找表 衡量一个查找算法的时间效率的标准是： 在查找过程中关键字的平均比较次数或平均读写磁盘次数(只适合于外部查找)，这个标准也称为平均查找长度ASL(Average Search Length)，通常它是查找结构中对象总数 n 或文件结构中物理块总数 n 的函数。 算法所需要的存储量和算法的复杂性等问题。 6.2静 态 查 找 表 静态查找表用顺序表作为存储结构 在静态查找表中，数据对象存放于数组中，利用数组元素的下标作为数据对象的存放地址。查找算法根据给定值x，在数组中进行查找。直到找到x在数组中的存放位置或可确定在数组中找不到x为止。 6.2.1顺序表的查找 (Sequential Search) 静态查找表的顺序存储结构为: #define maxsize 静态查找表的表长 typedef struct { ElemType item[maxsize+1]; // 存储数据元素的数组空间，0号单元留空 int n; // 表的长度 } sqtable; int Search_sqtable(sqtable R, KeyType k){ //顺序查找的算法，0号元素为监视哨 int i； R.item[0].key=k; for (i=R.n; R.item[i].key!=K ; --i); return i;} 查找过程：从表中最后一个元素开始，顺序用各元素的关键字与给定值K进行比较，若找到与其值相等的元素，则查找成功，给出该元素在表中的位置；否则，若直到第一个记录仍未找到关键字与x相等的对象，则查找失败。 顺序查找的时间性能 设查找第 i 个元素的概率为 pi，查找到第 i 个元素所需比较次数为 ci，则查找成功的平均查找长度: 在顺序查找情形，ci = n-i +1, i = 1, ?, n，因此 在等概率情形，pi = 1/n, 。 6.2.2 有序表的查找 上述顺序查找表的查找算法简单，但平均查找长度较大，特别不适用于表长较大的查找表。 若以有序表表示静态查找表，则查找过程可以基于“折半”进行。 折半查找(二分查找，Binary Search) 折半查找：先求位于查找区间正中的对象的下标mid，用其关键字与给定值K比较: R.item[mid]. Key = K，查找成功； R.item[mid]. Key K，把查找区间缩小到表的前半部分，再继续进行对分查找； R.item[mid]. Key K，把查找区间缩小到表的后半部分，再继续进行对分查找。 每比较一次，查找区间缩小一半。如果查找区间已缩小到一个对象，仍未找到想要查找的对象，则查找失败。 折半查找： （1）mid= (low+high)/2」 （2）比较 R.item[mid]. Key = = K? 如果 R.item[mid]. Key = = K，则查找成功，返回mid值 如果 R.item[mid]. Key K，则置high=mid-1 如果 R.item[mid]. Key K，则置low=mid+1 (3) 重复计算mid 以及比较R.item[mid]. Key与 K， 当lowhigh时，表明查找不成功，查找结束。 int Search_Bin ( sqtable R, KeyType K) { low = 1; high = R.length;