第8章查找 静态查找表 二叉排序 平衡二叉树(AD树) 验希表
◼ 静态查找表 ◼ 二叉排序树 ◼ 平衡二叉树（AVL树） ◼ 哈希表
81静态查找表 查找( Search)的概念 查找:就是在数据集合中寻找满足某种条 件的数据对象。 查找表:是由同一类型的数据元素(或记录) 组成的数据集合。 查找的结果通常有两种可能 ◆查找成功,即找到满足条件的数据对象。 ◆查找不成功,或查找失败。作为结果, 报告一些信息,如失败标志、失败位置等
查找(Search)的概念 8.1 静态查找表 ◼ 查找：就是在数据集合中寻找满足某种条 件的数据对象。 ◼ 查找表：是由同一类型的数据元素(或记录) 组成的数据集合。 ◼ 查找的结果通常有两种可能： ◆ 查找成功，即找到满足条件的数据对象。 ◆查找不成功，或查找失败。作为结果， 报告一些信息，如失败标志、失败位置等
衡量一个查找算法的时间效率的标准是:在查 找过程中关键字的平均比较次数或平均读写磁 盘次数(只适合于外部查找),这个标准也称为 平均查找长度AL(4 average search length),通 常它是查找结构中对象总数n或文件结构中物 理块总数n的函数。 另外衡量一个查找算法还要考虑算法所需要的 存储量和算法的复杂性等问题。 在静态查找表中,数据对象存放于数组中,利 用数组元素的下标作为数据对象的存放地址。 查找算法根据给定值x,在数组中进行查找。 直到找到x在数组中的存放位置或可确定在数 组中找不到为止
衡量一个查找算法的时间效率的标准是：在查 找过程中关键字的平均比较次数或平均读写磁 盘次数(只适合于外部查找)，这个标准也称为 平均查找长度ASL(Average Search Length)，通 常它是查找结构中对象总数 n 或文件结构中物 理块总数 n 的函数。 另外衡量一个查找算法还要考虑算法所需要的 存储量和算法的复杂性等问题。 在静态查找表中，数据对象存放于数组中，利 用数组元素的下标作为数据对象的存放地址。 查找算法根据给定值x，在数组中进行查找。 直到找到x在数组中的存放位置或可确定在数 组中找不到x为止
811顺序表的查找( Sequential Search) 所谓顺序查找,又称线性查找,主要用于在线性结构中进 行查找 存储结构: ty pedef struct ElemType *elem; int length 3 SSTable 查找过程:从表中最后一个元素开始,顺序用各元素的关键 字与给定值进行比较,若找到与其值相等的元素,则查找成 功,给出该元素在表中的位置;否则,若直到第一个记录仍 未找到关键字与x相等的对象,则查找失败
8.1.1顺序表的查找 (Sequential Search) 所谓顺序查找，又称线性查找，主要用于在线性结构中进 行查找。 存储结构： typedef struct{ ElemType *elem; int length; } SSTable; 查找过程：从表中最后一个元素开始，顺序用各元素的关键 字与给定值x进行比较，若找到与其值相等的元素，则查找成 功，给出该元素在表中的位置；否则，若直到第一个记录仍 未找到关键字与x相等的对象，则查找失败
算法8.1 Search_ Seq(ssTable ST, KeyType key) /顺序查找的算法,0号元素为监视哨 int i STelem oj. key=key; for(=STlength; !EQ(STelemi. key, key); -1); return i
算法8.1 Search_Seq(SSTable ST, KeyType key){ //顺序查找的算法，0号元素为监视哨 int i； ST.elem[0].key=key; for (i=ST.length; !EQ(ST.elem[i].key,key);--i); return i; }