第9章 查找

9.1 基本概念和术语 9.2 静态查找表 9.2.1 顺序查找 9.2.2 折半查找 9.2.3 分块查找 9.3 动态查找表 9.3.1 二叉排序树 9.3.2 平衡二叉树 9.3.3 B-树和B+树 9.4 哈希表 9.4.1 什么是哈希表 9.4.2 哈希函数的构造方法 9.4.3 处理冲突的方法 9.4.5 哈希表的查找和分析 9.5 小结

9.1 基本概念和术语表9-1 某学校招生录取登记表学 号 ┆ 20010983 20010984 20010985 ┆ 姓 名 ┆ 赵剑平 蒋伟峰 郭 娜 ┆ 性别 ┆ 男 男 女 ┆ 出生日期 年 ┆ 1982 1982 1983 ┆ 月 ┆ 11 09 01 ┆ 日 ┆ 05 12 25 ┆ 来 源 总分 ┆ 593 601 598 ┆ 录取专业 ┆ 计算机 计算机 计算机 ┆ ┆ 石家庄一中 保定三中 易县中学 ┆

1 数据项 (也称项或字段): 是具有独立含义的标识单位，是数据不可分割的最小单位。 2 组合项 由若干项、组合项构成。 3 数据元素(记录) 是由若干项、组合项构成的数据单位，是在某一问题中作为整体 进行考虑和处理的基本单位。

9.1 基本概念和术语表9-1 某学校招生录取登记表学 号 ┆ 20010983 20010984 20010985 ┆ 姓 名 ┆ 赵剑平 蒋伟峰 郭 娜 ┆ 性别 ┆ 男 男 女 ┆ 出生日期 年 ┆ 1982 1982 1983 ┆ 月 ┆ 11 09 01 ┆ 日 ┆ 05 12 25 ┆ 来 源 总分 ┆ 593 601 598 ┆ 录取专业 ┆ 计算机 计算机 计算机 ┆ ┆ 石家庄一中 保定三中 易县中学 ┆

4关键码(key) 关键码是数据元素(记录)中某个项或组合项的值，用它可以标 识一个数据元素(记录)。 能唯一确定一个数据元素(记录)的关键码，称为主关键码 (Primary Key);不能唯一确定一个数据元素(记录)的关键码， 称为次关键码(Secondary Key)。

9.1 基本概念和术语表9-1 某学校招生录取登记表学 号 ┆ 20010983 20010984 20010985 ┆ 姓 名 ┆ 赵剑平 蒋伟峰 郭 娜 ┆ 性别 ┆ 男 男 女 ┆ 出生日期 年 ┆ 1982 1982 1983 ┆ 月 ┆ 11 09 01 ┆ 日 ┆ 05 12 25 ┆ 来 源 总分 ┆ 593 601 598 ┆ 录取专业 ┆ 计算机 计算机 计算机 ┆ ┆ 石家庄一中 保定三中 易县中学 ┆

5 查找表(Search Table ) 是由具有同一类型(属性)的数据元素组成的集合(又称为字 典)。分为静态查找表和动态查找表两类: 静态查找表(Static Search Table):仅对查找表进行查找操 作，而不能改变的表； 动态查找表(Dynamic Search Table):对查找表除进行查找 操作外，允许向表中插入或删除表中数据元素的表。

9.1 基本概念和术语表9-1 某学校招生录取登记表学 号 ┆ 20010983 20010984 20010985 ┆ 姓 名 ┆ 赵剑平 蒋伟峰 郭 娜 ┆ 性别 ┆ 男 男 女 ┆ 出生日期 年 ┆ 1982 1982 1983 ┆ 月 ┆ 11 09 01 ┆ 日 ┆ 05 12 25 ┆ 来 源 总分 ┆ 593 601 598 ┆ 录取专业 ┆ 计算机 计算机 计

算机 ┆ ┆ 石家庄一中 保定三中 易县中学 ┆

6.查找(searching) 按给定的某个值kx,在查找表中确定一个其关键码等于kx的数据 元素(记录)。

9.1 基本概念和术语7 数据元素类型说明typedef struct {/* 出生日期类型定义 */ char year[5]; /* 年：用字符型表示，宽度为4个字符 */ char month[3]; /* 月：字符型，宽度为 2 */ char date[3]; /* 日：字符型，宽度为 2 */ }BirthDate; typedef struct {/* 数据元素类型定义 */ char number[7]; /* 学号：字符型，宽度为6 */ char name[9]; /* 姓名：字符型，宽度为8 */ char sex[3]; /* 性别：字符型，宽度为2 */ BirthDate birthdate;/*出生日期:构造类型 */ char comefrom[21]; /* 来源：字符型，宽度为20 */ int results; /* 成绩：整型，宽度由 “C语言”决定 */ } ElemType;

9.1 基本概念和术语8 查找表的类型定义 例：用线性表表示查找表： (1)用顺序表来表示查找表： typedef MAXSIZE 1000 typedef struct{//顺序存储结构 ElemType elem[MAXSIZE+1]; int length; }SStable; (2)用单链表表示查找表 typedef struct LNode{ ElemType data; struct LNode *next; }LNode,*LinkList; 用其它形式表示的线性表的类型定义在以后的章节中解释。

9.1 基本概念和术语说明： 本章以后讨论中，涉及的关键码类型和数据元素类型统一说明如下： typedef struct { KeyType key;/*关键码字段，可以是整型、字符型、构造型等*/ …… /* 其它字段 */ } ElemType;

9.2 静态查找表

9.2.1 顺序查找 9.2.2 折半查找 9.2.3 分块查找

9.2 静态查找表(基于线性表的查找)静态查找表结构 静态查找表是数据元素的线性表，可以是基于数组的顺序存储或以线 性链表存储。 typedef MAXSIZE 1000 typedef struct{//顺序存储结构 ElemType elem[MAXSIZE+1]; int length; }SStable; typedef struct LNode{//链式存储结构 ElemType data; struct LNode *next; }LNode,*LinkList;

9.2 静态查找表(基于线性表的查找)9.2.2 顺序查找(Sequential Search) 查找方法：从表的一端开始，向另一端逐个按给定值kx与关 键码进行比较，若找到，查找成功，并给出数据元素在表中的位置； 若整个表检测完，仍未找到与kx相同的关键码，则查找失败，给出 失败信息。

例：给定kx=56,90,在下表中进行顺序查找。0 1 2 3 4 5 6 7 8 9 10 11

19 13 37 21 05

56 75 92 64 80 88

9.2 静态查找表(基于线性表的查找)9.2.1顺序查找

//不设置监视哨的顺序查找算法int search_Seq(SSTable ST,KeyType kx) { i=l.length; while (i>=1&&ST.elem[i].key!=kx) i--; return i; }

9.2 静态查找表(基于线性表的查找)9.2.1 顺序查找 【算法9.1】以顺序存储为例，数据元素从下标为1的数组单元开始存放， 0号单元留空。 int search_Seq(SSTable ST,KeyType kx) { /*在表tbl中

查找关键码为kx的数据元素，若找到返回该元素在数组 中的下标，否则返回0 */ ST.elem[0].key = kx;/* 监视哨*/ for( i = ST.length ; ST.elem[i].key != kx ;i-- ); return i; }

9.2 静态查找表(基于线性表的查找)9.2.1 顺序查找 【性能分析】 分析查找算法的效率，通常用平均查找长度ASL来衡量。 定义：在查找成功时，平均查找长度ASL是指为确定数据元素在 表中的位置所进行的关键码比较次数的期望值。 对一个含n个数据元素的表，查找成功时

n ASL=∑ Pi· i C i=1其中：Pi为表中第i个数据元素的查找概率， Ci为表中第i个数据元素 的关键码与给定值kx相等时，按算法定位关键码的比较次数。

9.2.2 顺序查找 (Sequential Search)9.2.2 顺序查找 【性能分析】 查找成功时，顺序查找的平均查找长度为：

n1 n n+1 =∑─ · (n-i+1) =─ ASL= ∑ Pi· (n-i+1) i=1 i=1 n 2查找不成功时，关键码的比较次数总是n+1次。 算法中的基本工作就是关键码的比较，因此，查找长度的量级就是查 找算法的时间复杂度，其为O(n)。

9.2.2 顺序查找(Sequential Search)9.2.2 顺序查找 顺序查找缺点: 当n很大时，平均查找长度较大，效率低； 优点: 是对表中数据元素的存储没有要求。另外，对于线性链表，只 能进行顺序查找。