北京化工大学：《数据结构》课程PPT教学课件（C语言描述）第六章 查找

第八章 查找 米

第八章 查找

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 + = = − + = = • − +    = = =