高职高专现代信息技术系列教材：《数据结构》课程教学资源（PPT课件）第七章 查找

第7章找 本章中介绍下列主要内容: 静态查找表及查找算法:顺序查找、折半查找 动态查找表及查找算法:二叉排序树 哈希表及查找算法 请单鼠标左键换页! 返出

第7章 查找 本章中介绍下列主要内容： ⚫ 静态查找表及查找算法：顺序查找、折半查找 ⚫ 动态查找表及查找算法：二叉排序树 ⚫ 哈希表及查找算法 退出

7.1基本概念 7.2静态查拨 7.3动态查拨 7.4哈表 请单鼠标左键换页!

7.1 基本概念 7.2 静态查找 7.3 动态查找 7.4 哈希表

71基本概念 查找表用于査找的数据元素集合称为查找表。查 找表由同一类型的数据元素(或记录)构成。 静态查找表若只对查找表进行如下两种操作: (1)在查找表中查看某个特定的数据元素是否在查找 表中,(2)检索某个特定元素的各种属性,则称这类 查找表为静态查找表。静态查找表在査找过程中查找 表本身不发生变化。对静态查找表进行的查找操作称 为静态查找。 请单鼠标左键换页!

7.1 基本概念 查找表 用于查找的数据元素集合称为查找表。查 找表由同一类型的数据元素（或记录）构成。 静态查找表 若只对查找表进行如下两种操作： （1）在查找表中查看某个特定的数据元素是否在查找 表中，（2）检索某个特定元素的各种属性，则称这类 查找表为静态查找表。静态查找表在查找过程中查找 表本身不发生变化。对静态查找表进行的查找操作称 为静态查找

动态查找表若在查找过程中可以将查找表中不存 在的数据元素插入,或者从查找表中删除某个数据元 素,则称这类查找表为动态查找表。动态查找表在查 找过程中查找表可能会发生变化。对动态查找表进行 的查找操作称为动态查找。 关键字是数据元素中的某个数据项。唯一能标识 数据元素(或记录)的关键字,即每个元素的关键字 值互不相同,我们称这种关键字为主关键字;若查找 表中某些元素的关键字值相同,称这种关键字为次关 键字。例如,银行帐户中的帐号是主关键字,而姓名 是次关键字。 请单鼠标左键换页!

动态查找表 若在查找过程中可以将查找表中不存 在的数据元素插入，或者从查找表中删除某个数据元 素，则称这类查找表为动态查找表。动态查找表在查 找过程中查找表可能会发生变化。对动态查找表进行 的查找操作称为动态查找。 关键字 是数据元素中的某个数据项。唯一能标识 数据元素（或记录）的关键字，即每个元素的关键字 值互不相同，我们称这种关键字为主关键字；若查找 表中某些元素的关键字值相同，称这种关键字为次关 键字。例如，银行帐户中的帐号是主关键字，而姓名 是次关键字

查找在数据元素集合中查找满足某种条件的数据 元素的过程称为查找。最简单且最常用的查找条件是 “关键字值等于某个给定值”,在查找表搜索关键字 等于给定值的数据元素(或记录)。若表中存在这样 的记录,则称查找成功,此时的查找结果应给出找到 记录的全部信息或指示找到记录的存储位置;若表中 不存在关键字等于给定值的记录,则称查找不成功 此时查找的结果可以给出一个空记录或空指针。若按 主关键字查找,査找结果是唯一的;若按次关键字查 找,结果可能是多个记录,即结果可能不唯 请单鼠标左键换页!

查找 在数据元素集合中查找满足某种条件的数据 元素的过程称为查找。最简单且最常用的查找条件是 “关键字值等于某个给定值”，在查找表搜索关键字 等于给定值的数据元素（或记录）。若表中存在这样 的记录，则称查找成功，此时的查找结果应给出找到 记录的全部信息或指示找到记录的存储位置；若表中 不存在关键字等于给定值的记录，则称查找不成功， 此时查找的结果可以给出一个空记录或空指针。若按 主关键字查找，查找结果是唯一的；若按次关键字查 找，结果可能是多个记录，即结果可能不唯一

查找表的存储结构查找表是一种非常灵活的数据 结构,对于不同的存储结构,其查找方法不同。为了 提高查找速度,有时会采用一些特殊的存储结构。本 章将介绍以线性结构、树型结构及哈希表结构为存储 结构的各种查找算法。 查找算法的时间效率查找过程的主要操作是关键 字的比较,所以通常以“平均比较次数”来衡量查找 算法的时间效率。 请单鼠标左键换页!

查找表的存储结构 查找表是一种非常灵活的数据 结构，对于不同的存储结构，其查找方法不同。为了 提高查找速度，有时会采用一些特殊的存储结构。本 章将介绍以线性结构、树型结构及哈希表结构为存储 结构的各种查找算法。 查找算法的时间效率 查找过程的主要操作是关键 字的比较，所以通常以“平均比较次数”来衡量查找 算法的时间效率

72静态查找 正如本章第一节所述:静态查找是指在静态查找 表上进行的查找操作,在查找表中查找满足条件的数 据元素的存储位置或各种属性。本节将讨论以线性结 构表示的静态查找表及相应的查找算法。 请单鼠标左键换页!

7.2 静态查找 正如本章第一节所述：静态查找是指在静态查找 表上进行的查找操作，在查找表中查找满足条件的数 据元素的存储位置或各种属性。本节将讨论以线性结 构表示的静态查找表及相应的查找算法

7.2.1顺序查找 1.顺序查找的基本思想 顺序查找是一种最简单的查找方法。其基本思想 是将查找表作为一个线性表,可以是顺序表,也可以 是链表,依次用查找条件中给定的值与查找表中数据 元素的关键字值进行比较,若某个记录的关键字值与 给定值相等,则查找成功,返回该记录的存储位置, 反之,若直到最后一个记录,其关键字值与给定值均 不相等,则查找失败,返回查找失败标志。 请单赤鼠标左键换页!

7.2.1 顺序查找 1. 顺序查找的基本思想 顺序查找是一种最简单的查找方法。其基本思想 是将查找表作为一个线性表，可以是顺序表，也可以 是链表，依次用查找条件中给定的值与查找表中数据 元素的关键字值进行比较，若某个记录的关键字值与 给定值相等，则查找成功，返回该记录的存储位置， 反之，若直到最后一个记录，其关键字值与给定值均 不相等，则查找失败，返回查找失败标志

2.顺序表的顺序查找 下面是顺序表的类型定义: define maX num100/用于定义表的长度 ypedef struct elemtypet keytype key anytype otheritem Se list MaX NUmis item; 假设在查找表中,数据元素个数为n(n< MAX NUM) 并分别存放在数组的下标变量a-an中。 请单鼠标左键换页!

2. 顺序表的顺序查找 下面是顺序表的类型定义： #define MAX_NUM 100 //用于定义表的长度 typedef struct elemtype{ keytype key; anytype otheritem; }Se_List[MAX_NUM],Se_Item; 假设在查找表中，数据元素个数为n（n<MAX_NUM）， 并分别存放在数组的下标变量a[1]~a[n]中

下面我们给出顺序查找的完整算法。 int seq search(Se List a, keytype k) {在顺序表中查找关键字值等于k的记录, /若查找成功,返回该记录的位置下标序号,否则返回0 while (i<=n & ai key !=k i++ if (i<=n) retrun i; else return U, 请单鼠标左键换页!

下面我们给出顺序查找的完整算法。 int seq_search (Se_List a，keytype k) {//在顺序表中查找关键字值等于k的记录， //若查找成功，返回该记录的位置下标序号，否则返回0 i=1; while (i<=n && a[i].key != k) i++; if (i<=n) retrun i; else return 0; }