河北大学：《数据结构》课程教学资源（PPT教案课件讲稿）第九章 查找

第九章查找 1教学内容:91基本概念与术语 9.2静态查找表 9.3动态查找表 9.4哈希表查找(杂凑法) 2教学目的:()了解查找的基本思想及查找成功和不成功的概念 (2掌握在各种查找表上的查找方法和算法,并能求出相应的平均查找长度 (3)理解并掌握二又排序树、平衡二义树B-树的各种算法 3教学重点:(1)查找表的基本概念及查找原理 (2)查找表的顺序存储结构、顺序表及其类型说明 (3)查找运算在查找表和有序表上的实现 4)三叉排序树的定义、性质及各结点间的键值关系 (5)二叉排序树的查找算法和基本思想: (6)平衡三叉排序树的概念 7)B一树和B+树的概念 (8)散列表及散列存储和散列查找的基本思想 9)各种散列表的组织、解决冲突的方法 0在散列表上实现查找、插入和删除运算的算法 4.教学难点:()理解查找表的逻辑结构是集合,它的运算以查找为核心 (2)一叉排序树上的插入算法 3)衡二叉树的旋转平衡算法 4)散列表上的有关算法 5学时安排:10学时 2021年1月21日 数据结构讲义

2021年1月21日 数据结构讲义 1 第九章 查找 ⒈教学内容：9.1 基本概念与术语 9.2 静态查找表 9.3 动态查找表 9.4 哈希表查找(杂凑法) ⒉教学目的：⑴了解查找的基本思想及查找成功和不成功的概念； ⑵掌握在各种查找表上的查找方法和算法，并能求出相应的平均查找长度； ⑶理解并掌握二叉排序树、平衡二叉树B-树的各种算法。 ⒊教学重点：⑴查找表的基本概念及查找原理； ⑵查找表的顺序存储结构、顺序表及其类型说明； ⑶查找运算在查找表和有序表上的实现； ⑷二叉排序树的定义、性质及各结点间的键值关系； ⑸二叉排序树的查找算法和基本思想； ⑹平衡二叉排序树的概念； ⑺B-树和B+树的概念； ⑻散列表及散列存储和散列查找的基本思想； ⑼各种散列表的组织、解决冲突的方法； ⑽在散列表上实现查找、插入和删除运算的算法。 ⒋教学难点：⑴理解查找表的逻辑结构是集合，它的运算以查找为核心； ⑵二叉排序树上的插入算法； ⑶平衡二叉树的旋转平衡算法； ⑷散列表上的有关算法 ⒌学时安排： 10学时

在英汉字典中查找某个英文单词的中文解释;在新华 字典中查找某个汉字的读音、含义;在对数表、平方根表 中查找某个数的对数、平方根;邮递员送信件要按收件人 的地址确定位置等等。可以说查找是为了得到某个信息而 常常进行的工作。 计算机、计算机网络使信息查询更快捷、方便、准确 要从计算机、计算机网络中查找特定的信息,就需要在计 算机中存储包含该特定信息的表。如要从计算机中查找英 文单词的中文解释,就需要存储类似英汉字典这样的信息 表,以及对该表进行的查找操作。本章将讨论的问题即是 “信息的存储和查找”。 查找是许多程序中最消耗时间的一部分操作。因而 个好的查找方法可以大大提高运行速度。另外,由于计 算机的特性,象对数、平方根等是通过函数求解,无需存 储相应的信息表。 2021年1月21日 数据结构讲义

2021年1月21日 数据结构讲义 2 在英汉字典中查找某个英文单词的中文解释；在新华 字典中查找某个汉字的读音、含义；在对数表、平方根表 中查找某个数的对数、平方根；邮递员送信件要按收件人 的地址确定位置等等。可以说查找是为了得到某个信息而 常常进行的工作。 计算机、计算机网络使信息查询更快捷、方便、准确。 要从计算机、计算机网络中查找特定的信息，就需要在计 算机中存储包含该特定信息的表。如要从计算机中查找英 文单词的中文解释，就需要存储类似英汉字典这样的信息 表，以及对该表进行的查找操作。本章将讨论的问题即是 “信息的存储和查找” 。 查找是许多程序中最消耗时间的一部分操作。因而， 一个好的查找方法可以大大提高运行速度。另外，由于计 算机的特性，象对数、平方根等是通过函数求解，无需存 储相应的信息表

9.1基本概念与术语 2021年1月21日 数据结构讲义

2021年1月21日 数据结构讲义 3 9.1 基本概念与术语

以学校招生录取登记表为例,来讨论计算机中表的概念。 出生日期 学号 姓名性 别 来源 总分录取专业 年 月日 20010983赵剑平男 1982 1105 石家庄 593 20010984蒋伟峰男1982 中 计算机 601 计算机 20010985郭娜女 1983 25 保定三中 易县中学 598 计算机 图9.1学校招生录取登记表 2021年1月21日 数据结构讲义

2021年1月21日 数据结构讲义 4 以学校招生录取登记表为例，来讨论计算机中表的概念。 学 号 姓 名 性 别 出生日期 来 源 总分 录取专业 年 月 日 ┆ 20010983 20010984 20010985 ┆ ┆ 赵剑平 蒋伟峰 郭 娜 ┆ ┆ 男 男 女 ┆ ┆ 1982 1982 1983 ┆ ┆ 11 09 01 ┆ ┆ 05 12 25 ┆ ┆ 石家庄一 中 保定三中 易县中学 ┆ ┆ 593 601 598 ┆ ┆ 计算机 计算机 计算机 ┆ 图 9.１ 学校招生录取登记表

1.数据项(也称项或字段) 项是具有独立含义的标识单位,是数据不可分 割的最小单位。如表中“学号”、“姓名” 年”等。项有名和值之分,项名是一个项的标识 用变量定义,而项值是它的一个可能取值,表中 “20010983是项“学号”的一个取值。项具有一 定的类型,依项的取值类型而定 2.组合项 由若干项、组合项构成,表中“出生日期”就 是组合项,它由“年”、“月”、“日”三项组成 2021年1月21日 数据结构讲义

2021年1月21日 数据结构讲义 5 1.数据项 (也称项或字段) 项是具有独立含义的标识单位，是数据不可分 割的最小单位。如表中“学号” 、 “姓名” 、 “年”等。项有名和值之分，项名是一个项的标识， 用变量定义，而项值是它的一个可能取值，表中 “20010983”是项“学号”的一个取值。项具有一 定的类型，依项的取值类型而定。 2.组合项 由若干项、组合项构成，表中“出生日期”就 是组合项，它由“年” 、 “月” 、 “日”三项组成

3.数据元素(记录) 数据元素是由若干项、组合项构成的数据单位,是在某 十问题中作为整体进行考虑和处理的基本单位。数据元素有 担和值之分,表中项名的集合,也即表头部分就是数据元素 的类型;而一个学生对应的一行数据就是一个数据元素的值, 表中全体学生即为数据元素的集合 4.关键码 关键码是数据元素(记录)中某个项或组合项的值,用 它可以标识一个数据元素(记录)。能唯一确定一个数据元 素(记录)的关键码,称为主关键码;而不能唯一确定一个 数据元素(记录)的关键码,称为次关键码。表中“学号” 即可看成主关键码,“姓名”则应视为次关键码,因可能有 同名同姓的学生 2021年1月21日 数据结构讲义

2021年1月21日 数据结构讲义 6 3.数据元素（记录） 数据元素是由若干项、组合项构成的数据单位，是在某 一问题中作为整体进行考虑和处理的基本单位。数据元素有 型和值之分，表中项名的集合，也即表头部分就是数据元素 的类型；而一个学生对应的一行数据就是一个数据元素的值， 表中全体学生即为数据元素的集合。 4.关键码 关键码是数据元素（记录）中某个项或组合项的值，用 它可以标识一个数据元素（记录）。能唯一确定一个数据元 素（记录）的关键码，称为主关键码；而不能唯一确定一个 数据元素（记录）的关键码，称为次关键码。表中“学号” 即可看成主关键码， “姓名”则应视为次关键码，因可能有 同名同姓的学生

5.查找表 是由具有同一类型(属性)的数据元素(记录)组成的 集合。分为静态查找表和动态查找表两类。静态查找表:仅 对查找表进行查找操作,而不能改变的表:动态查找表:对 查找表除进行查找操作外,可能还要进行向表中插入数据元 素,或删除表中数据元素的表。 6.查找 按给定的某个值kx,在查找表中查找关键码为给定值kx 的数据元素(记录) 关键码是主关键码时:由于主关键码唯一,所以查找结 果也是唯一的,一旦找到,查找成功,结束查找过程,并给 出找到的数据元素(记录)的信息,或指示该数据元素(记 录)的位置。要是整个表检测完,还没有找到,则查找失败, 此时,查找结果应给出一个“空”记录或“空”指针。关键 码是次关键码时:需要査遍表中所有数据元素(记录),或 在可以肯定查找失败时,才能结束查找过程。 2021年1月21日 数据结构讲义

2021年1月21日 数据结构讲义 7 5.查找表 是由具有同一类型（属性）的数据元素（记录）组成的 集合。分为静态查找表和动态查找表两类。静态查找表：仅 对查找表进行查找操作，而不能改变的表；动态查找表：对 查找表除进行查找操作外，可能还要进行向表中插入数据元 素，或删除表中数据元素的表。 6.查找 按给定的某个值kx，在查找表中查找关键码为给定值kx 的数据元素（记录）。 关键码是主关键码时：由于主关键码唯一，所以查找结 果也是唯一的，一旦找到，查找成功，结束查找过程，并给 出找到的数据元素（记录）的信息，或指示该数据元素（记 录）的位置。要是整个表检测完，还没有找到，则查找失败， 此时，查找结果应给出一个“空”记录或“空”指针。关键 码是次关键码时：需要查遍表中所有数据元素（记录），或 在可以肯定查找失败时，才能结束查找过程

7.数据元素类型说明 在手工绘制表格时,总是根据有多少数据项,每个数 据项应留多大宽度来确定表的结构,即表头的定义。然后, 再根据需要的行数,画出表来。在计算机中存储的表与手 工绘制的类似,需要定义表的结构,并根据表的大小为表 分配存储单元。以图9.1为例,用C语言的结构类型描述 之 /*出生日期类型定义米/ typedef struct f char year l5 /米年:用字符型 小, 14个字符* char month[31 /*月:字符型,宽度为2*/ char date 3 /*日:字符型,宽度为2*/ BIrthdAte: 2021年1月21日 数据结构讲义

2021年1月21日 数据结构讲义 8 7.数据元素类型说明 在手工绘制表格时，总是根据有多少数据项，每个数 据项应留多大宽度来确定表的结构，即表头的定义。然后， 再根据需要的行数，画出表来。在计算机中存储的表与手 工绘制的类似，需要定义表的结构，并根据表的大小为表 分配存储单元。以图 9.１为例，用C语言的结构类型描述 之。 /* 出生日期类型定义 */ typedef struct { char year[5]； /* 年：用字符型表示，宽度为4个字符 */ char month[3]； /* 月：字符型，宽度为 2 */ char date[3]； /* 日：字符型，宽度为 2 */ }BirthDate；

/*数据元素类型定义米 typedef struct char number [7 *学号:字符型,宽度为6 char name *姓名:字符型,宽度为8*/ char sex31 /*性别:字符型,宽度为2* BirthDate birthdate /*出生日期:构造类型,由该类型的宽度确定 char comefrom[21];牌来源:字符型,宽度为20*/ int results: /*成绩:整型,宽度由“程序设计C语言工具软件”决定 y Elem Type 2021年1月21日 数据结构讲义

2021年1月21日 数据结构讲义 9 /* 数据元素类型定义 */ typedef struct { char number[7]； /* 学号：字符型，宽度为6 */ char name[9]； /* 姓名：字符型，宽度为8 */ char sex[3]； /* 性别：字符型，宽度为2 */ BirthDate birthdate； /* 出生日期：构造类型，由该类型的宽度确定 */ char comefrom[21]； /* 来源：字符型，宽度为20 */ int results； /* 成绩：整型，宽度由 “程序设计C语言工具软件”决定 */ } ElemType；

以上定义的数据元素类型,相当于手工绘制的表头。 要存储学生的信息,还需要分配一定的存储单元,即给出 表长度。可以用数组分配,即顺序存储结构;也可以用链 式存储结构实现动态分配。 本章以后讨论中,涉及的关键码类型和数据元素类型 统一说明如下: typedef struct KeyType ley: /*关键码字段,可以是整型、字符串型、构造 类型等* /*其它字段* y ElemType; 2021年1月21日 数据结构讲义 10

2021年1月21日 数据结构讲义 10 以上定义的数据元素类型，相当于手工绘制的表头。 要存储学生的信息，还需要分配一定的存储单元，即给出 表长度。可以用数组分配，即顺序存储结构；也可以用链 式存储结构实现动态分配。 本章以后讨论中，涉及的关键码类型和数据元素类型 统一说明如下： typedef struct { KeyType key； /* 关键码字段，可以是整型、字符串型、构造 类型等*/ …… /* 其它字段 */ } ElemType；