当前课程知识点：数据结构 > 第7章 查找 > 7.1 概念和术语 > 讲解
同学们好，本章
我们来学习查找
这一章，包含以下五部分内容
我们先来看第一部分，概念和术语，第一个概念
关键字
在实际应用当中，我们要找的数据元素
它们往往是结构类型
或者说是复合类型
换句话说
这时候的数据元素，是包含若干个数据项的
讲到数据项
我们不得不提几个相关的概念
第一个，主关键字
Primary Key，简称PK
它是指，能够唯一标识数据元素的数据项
比如学号，在一个学校当中，学号是能够唯一确定一个学生的
所以，学号可以作为主关键字
第二个概念，次关键字，Secondary Key
它是指，可能对应多个数据元素的数据项
比如姓名
即使在一个班级内部
姓名也有可能是重复的
为了后面方便描述算法
我们这里起了一个别名，叫关键字类型
我们把它定义成整型
这主要是为了编程方便
这里有个结构体，第一个成员
就是我们刚才定义的关键字类型
它是数据元素的主关键字
其他的成员，我们并不关心
因为，在讲这一章查找相关的算法的时候
我们并不关心数据元素中
除了关键字之外的那些成员
然后，给这个结构体起个别名，叫ElemType，代表要查找的数据元素
它的类型
另外
需要说一下的是
主关键字
有时候，也称为主键
这是对Key这个单词的不同翻译
在数据库当中
也有类似的概念
第二个概念，查找表，Search Table，简单地说
查找表就是查找的范围
就是
若干具有相同类型的数据元素，构成的集合
我们将来就在这个集合里面，去找某一个数据元素
查找表可以分为静态查找表和动态查找表
静态查找表，是指只读的查找表
比如，我们要找一个关键字，找到了，我们返回这个关键字对应着的数据元素它的位置
找不到，我们什么都不做
或者说，只返回一个特殊的值
用来表示找不到
只读的查找表，叫静态查找表
动态查找表，是指可读写的查找表
比如，我们找到了，除了返回找到的这个数据元素它的位置之外
我们很可能去删除
找到的这个元素
找不到，我们很可能要去插入找不到的这个元素
所以，它会去改写、去修改查找表，这时候的查找表
叫动态查找表
是可读写的
同样，为了方便编程
我们这里，先给出静态查找表
它的结构体定义，第一个成员，是指针类型，指向ElemType类型的数据
我们将来，就是把这个首地址，当作一个数组名来用
给定了首地址，这一段连续的存储空间
长度(容量)到底有多少呢
我们用第二个成员来表示
它是代表连续存储空间的首地址
也就是elem这个数组
它的长度
我们现在约定，下标0处不存元素
这主要是为了方便后面编程
也就是说
长度为length的数组
它最多只存放length-1个元素
因为，下标0处，我们约定不存元素
换句话说
第i个元素就存在
elem下标i的位置
然后，我们用typedef起一个别名SSTable，就是Static Search Table，静态查找表
第三个概念，查找，这个概念
其实大家都很熟悉
在查找表中找到关键字
等于给定关键字k的数据元素
我们在若干个数据元素构成的集合当中
给你一个关键字k
然后，你按照这个k，去找到相应的数据元素
它的位置，就可以了
这就是查找
第四个概念，平均查找长度
Average Search Length
简称ASL
它的定义是，查找成功时，进行元素的比较次数的期望值
我们把它记成Pi*Ci，最后求和
Ci是指找元素i，经历的比较次数
这个C，代表Compare(比较)
而Pi是指找第i个元素
它的概率
所有的Pi乘上Ci，累加求和，就是平均查找长度
我们在查找表当中，去找第i个元素
它们的概率之和，是等于1的
这个是毫无疑问的
因为查找成功
给定n个元素
你去找第1个元素
找最后一个元素，找中间某个元素
要找的那个元素，肯定是这n个元素当中的一个
所以，找第i个元素的概率累加之和，是1
另外
为了方便计算，我们通常只考虑等概率的情况
也就是说，找第i个元素它的概率，是1/n
这时候，Pi
就等于1/n
ASL就是(Ci累加求和)/n
也就是Ci它的均值
-讲解
-作业
-讨论1
-讨论2
-1.1 数据结构是什么
--讲解
--作业
-1.2 概念和术语
--讲解
--作业1
--作业2
-1.3 抽象数据类型
--讲解（上）
--讲解（下）
--作业
-1.4 算法及其设计要求
--讲解
--作业
-1.5 算法分析与度量
--讲解（上）
--讲解（下）
--作业1
--作业2
--讨论
-2.1 概念及ADT
--讲解
--作业
-2.2 线性表的顺序实现——顺序表
--讲解（上）
--讲解（中）
--讲解（下）
--作业1
--作业2
-2.3 线性表的链式实现——链表
--讲解（上）
--讲解（中）
--讲解（下）
--作业1
--作业2
-2.4 线性表的应用——多项式
--讲解
--作业
-讨论
-3.1 栈的定义及ADT
--讲解
--作业
-3.2 栈的顺序实现——顺序栈
--讲解
--作业
-3.3 栈的应用
--讲解
--作业
-3.4 栈与递归
--讲解（上）
--讲解（下）
--作业
-3.5 队列的定义及ADT
--讲解
--作业
-3.6 队列的顺序实现——循环队列
--讲解（上）
--讲解（下）
--作业
-讨论
-4.1 数组的定义
--讲解
--作业
-4.2 数组的顺序实现
--讲解
--作业1
--作业2
-4.3 特殊矩阵的压缩存储
--讲解
--作业
-4.4 稀疏矩阵的压缩存储
--讲解（上）
--讲解（下）
--作业
-讨论
-5.1 概念及术语
--讲解
--作业
-5.2 二叉树及其性质
--讲解
--作业1
--作业2
-5.3 二叉树的存储
--讲解
--作业
-5.4 二叉树的遍历及创建
--讲解（上）
--讲解（下）
--作业
-5.5 线索二叉树
--讲解
--作业
-5.6 树与森林
--讲解
--作业
-5.7 Huffman树
--讲解（上）
--讲解（下）
--作业
-讨论
-6.1 概念和术语
--讲解
--作业
-6.2 存储与实现
--讲解（上）
--讲解（下）
--作业
-6.3 遍历
--讲解（上）
--讲解（下）
--作业
-6.4 最小生成树
--讲解（上）
--讲解（下）
--作业1
--作业2
-6.5 拓扑排序
--讲解
--作业
-6.6 最短路径
--讲解
--作业
-讨论
-7.1 概念和术语
--讲解
--作业
-7.2 静态查找表
--讲解（上）
--讲解（下）
--作业
-7.3 二叉排序树
--讲解（上）
--讲解（下）
--作业
-7.4 平衡二叉树
--讲解
--作业
-7.5 哈希表
--讲解（上）
--讲解（下）
--作业
-讨论
-8.1 概念
--讲解
--作业
-8.2 插入排序
--讲解（上）
--讲解（下）
--作业
-8.3 交换排序
--讲解（上）
--讲解（下）
--作业
-8.4 选择排序
--讲解（上）
--讲解（中）
--讲解（下）
--作业
-8.5 归并排序
--讲解
--作业
-讨论
