第八章 查找 米
第八章 查找
8.1基本概念与术语 8.2基于线性表的查找 8.3基于树表的查找 8.4哈希表的查找 米
8.1 基本概念与术语 8.2 基于线性表的查找 8.3 基于树表的查找 8.4 哈希表的查找
基本概念与术语 Q数据元素 是由若干数据项构成的数据单位,在某一问题中作为整 体进行考虑和处理的基本单位,也称为记录。 。关键码 是数据元素(记录)中某个数据项的值,用它可以表示 一个数据元素(记录)。能唯一确定一个数据元素(记录) 的关键码,称为主关键码;而不能唯一确定一个数据元素 (记录)的关键码,称为次关键码
基本概念与术语 数据元素 是由若干数据项构成的数据单位,在某一问题中作为整 体进行考虑和处理的基本单位,也称为记录。 关键码 是数据元素(记录)中某个数据项的值,用它可以表示 一个数据元素(记录)。能唯一确定一个数据元素(记录) 的关键码,称为主关键码;而不能唯一确定一个数据元素 (记录)的关键码,称为次关键码
查找表 是由具有同一类型(属性)的数据元素(记录)组成的 集合。分为静态查找表和动态查找表两类。 对查找表除进行查找操 作外,可能还要进行向 仅对查找表进行查找操 表中插入数据元素或删 作,而不改变的表。 除数据元素的表
查找表 是由具有同一类型(属性)的数据元素(记录)组成的 集合。分为静态查找表和动态查找表两类。 对查找表除进行查找操 作外,可能还要进行向 表中插入数据元素或删 除数据元素的表。 仅对查找表进行查找操 作,而不改变的表
。查找 按给定的某个值k,在查找表中查找关键码为给定值k的 数据元素(记录)的过程,又称为检索。 查找结果: ①查找成功→输出该记录的有关信息或指示其在表中的 位置; ②查找不成功→输出不成功的信息或给出一个空记录或 空指针
查找 按给定的某个值k,在查找表中查找关键码为给定值k的 数据元素(记录)的过程,又称为检索。 查找结果: ① 查找成功→ 输出该记录的有关信息或指示其在表中的 位置; ② 查找不成功→ 输出不成功的信息或给出一个空记录或 空指针
o平均查找长度ASL(Average Search Length) 为确定数据元素在查找表中的位置,需要和给定值进行 比较的关键字个数的期望值。作为衡量查找算法好坏的依据。 ASL-PC 查找第个数据元素时已进行过的 关键字比较次数 查找表中第个数据元素的概率
平均查找长度ASL(Average Search Length) 为确定数据元素在查找表中的位置,需要和给定值进行 比较的关键字个数的期望值。作为衡量查找算法好坏的依据。 = = n i 1 ASL PiCi 查找表中第i个数据元素的概率 查找第i个数据元素时已进行过的 关键字比较次数
基于线性表的查找 一、顺序查找(Sequential Search) 1、是一种最基本、最简单的查找方法; 2、它是用给定的关键字值与表里各个记录的关键 字 逐个进行比较; 3、对顺序分配和链式分配都适用;
基于线性表的查找 一、顺序查找(Sequential Search) 1、 是一种最基本、最简单的查找方法; 2、 它是用给定的关键字值与表里各个记录的关键 字 逐个进行比较; 3、 对顺序分配和链式分配都适用;
4、 查找思想: 从表的一端开始,向另一端逐个按给定值k与 记 录的关键码进行比较,若找到,查找成功,并给出 记 录在表中的位置;若整个表检测完仍未找到与k相同 的关键码,若查找失败,给出失败信息提示
4、 查找思想: 从表的一端开始,向另一端逐个按给定值k与 记 录的关键码进行比较,若找到,查找成功,并给出 记 录在表中的位置;若整个表检测完仍未找到与k相同 的关键码,若查找失败,给出失败信息提示
查找表 给定关键字 int SeqSearch(SqTable tb1,ElemType k) tb1.elem[0].key=k; for(i=tb1.length;tb1.elem[i].key<>k;i--); return i;。 查找成功:返回位置; 查找不成功:返回0
int SeqSearch(SqTable tb1,ElemType k) { tb1.elem[0].key=k; for(i=tb1.length;tb1.elem[i].key<>k;i--); return i; } 查找表 给定关键字 查找成功:返回位置; 查找不成功:返回0
查找成功时: ASL-C- i=I n =1n-i+ i=1 n+1 2 查找不成功时:比较次数为n+1 ∴.T(n)=o(n)
查找成功时: 查找不成功时: 比较次数为n+1 ∴ T(n)=O(n) 2 n 1 (n i 1) n 1 (n i 1) n 1 ASL PC n i 1 n i 1 n i 1 i i + = = − + = = • − + = = =