第九章查找 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.组合项 由若干项、组合项构成，表中“出生日期”就 是组合项，它由“年” 、 “月” 、 “日”三项组成