基本概念与术语 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相同 的关键码,若查找失败,给出失败信息提示