第10章查找 10.1查找的基本概念 10.2线性表的查找 10.3树表的查找 10.4哈希衰查找 本章小结
第10章 查找 10.1 查找的基本概念 本章小结 10.2 线性表的查找 10.3 树表的查找 10.4 哈希表查找
10.1查找的基本概念 被查找的对象是由一组记录组成的表或文件而每个记录则 由若干个数据项组成并假设每个记录都有一个能惟一标识该记 录的关键字 在这种条件下查找的定义是:给定一个值k在含有n个记录 的表中找出关键字等于k的记录。若找到则查找成功返回该记 录的信息或该记录在表中的位置;否则查找失败返回相关的指 示信息
10.1 查找的基本概念 被查找的对象是由一组记录组成的表或文件,而每个记录则 由若干个数据项组成,并假设每个记录都有一个能惟一标识该记 录的关键字。 在这种条件下,查找的定义是：给定一个值k,在含有n个记录 的表中找出关键字等于k的记录。若找到,则查找成功,返回该记 录的信息或该记录在表中的位置；否则查找失败,返回相关的指 示信息
采用何种查找方法 1)使用哪种数据结构来表示“表”,即表中记录是按何 种方式组织的。 (2)表中关键字的次序。是对无序集合查找还是对有序 集合查找? 若在查找的同时对表做修改运算(如插入和删除),则 相应的表称之为动态查找表否则称之为静态查找表
采用何种查找方法? (1) 使用哪种数据结构来表示“表” ,即表中记录是按何 种方式组织的。 (2) 表中关键字的次序。是对无序集合查找还是对有序 集合查找? 若在查找的同时对表做修改运算(如插入和删除),则 相应的表称之为动态查找表,否则称之为静态查找表
由于查找运算的主要运算是关键字的比较所以通常把查找 过程中对关键字需要执行的平均比较次数也称为平均查找长度) 作为衡量一个查找算法效率优劣的标准。平均查找长度 ASL(Average Search Length)定义为: AsL=∑pc 其中n是查找表中记录的个数。p是查找第个记录的概 率一般地均认为每个记录的查找概率相等即p=1/(1≤≤m),c1 是找到第个记录所需进行的比较次数
由于查找运算的主要运算是关键字的比较,所以通常把查找 过程中对关键字需要执行的平均比较次数(也称为平均查找长度) 作为衡量一个查找算法效率优劣的标准。平均 查找长度 ASL(Average Search Length)定义为： = = n i 1 i i ASL p c 其中,n是查找表中记录的个数。pi是查找第i个记录的概 率,一般地,均认为每个记录的查找概率相等,即pi=1/n(1≤i≤n),ci 是找到第i个记录所需进行的比较次数
10.2线性表的查找 在表的组织方式中线性表是最简单的一种。三种在线性表上 进行查找的方法: (1)顺序查找 (2)二分查找 (3)分块查找。 因为不考虑在查找的同时对表做修改故上述三种查找操作都 是在静态查找表上实现的
10.2 线性表的查找 在表的组织方式中,线性表是最简单的一种。三种在线性表上 进行查找的方法： (1) 顺序查找 (2) 二分查找 (3) 分块查找。 因为不考虑在查找的同时对表做修改,故上述三种查找操作都 是在静态查找表上实现的
查找与数据的存储结构有关,线性表有顺序和链式两种存储 结构。本节只介绍以顺序表作为存储结构时实现的顺序查找算 法。定义被查找的顺序表类型定义如下: # define maXl typedef struct KeyType key; / KeyType为关键字的数据类型*/ InfoType data;/其他数据*/ 3 Nodetype; typedef Node Type Seqlist IMAXL;/顺序表类型*
查找与数据的存储结构有关,线性表有顺序和链式两种存储 结构。本节只介绍以顺序表作为存储结构时实现的顺序查找算 法。定义被查找的顺序表类型定义如下： #define MAXL typedef struct { KeyType key; /*KeyType为关键字的数据类型*/ InfoType data; /*其他数据*/ } NodeType; typedef NodeType SeqList[MAXL]; /*顺序表类型*/
10.2.1顺序查找 顺序查找是一种最简单的查找方法。 它的基本思路是:从表的一端开始,顺序扫描线性表,依次将扫 描到的关键字和给定值k相比较,若当前扫描到的关键字与k相等, 则查找成功;若扫描结束后,仍未找到关键字等于k的记录则查 找失败
10.2.1 顺序查找 顺序查找是一种最简单的查找方法。 它的基本思路是：从表的一端开始,顺序扫描线性表,依次将扫 描到的关键字和给定值k相比较,若当前扫描到的关键字与k相等, 则查找成功；若扫描结束后,仍未找到关键字等于k的记录,则查 找失败
例如在关键字序列为3,9,1,5,8,10,6,7,2,4}的线性表查找关 键字为6的元素。 顺序查找过程如下:
例如,在关键字序列为{3,9,1,5,8,10,6,7,2,4}的线性表查找关 键字为6的元素。 顺序查找过程如下：
开始:39158106724 第1次比较:39158106724 i=0 第2次比较:39158106724 i=1 第3次比较:39158106724 i=2 第4次比较:39158106724 i=3 第5次比较:39158106724 第6次比较:39158106724 i=5 第7次比较:39158106724 i=6 查找成功返回序号6
开始: 3 9 1 5 8 10 6 7 2 4 第1次比较: 3 9 1 5 8 10 6 7 2 4 i=0 第2次比较: 3 9 1 5 8 10 6 7 2 4 i=1 第3次比较: 3 9 1 5 8 10 6 7 2 4 i=2 第4次比较: 3 9 1 5 8 10 6 7 2 4 i=3 第5次比较: 3 9 1 5 8 10 6 7 2 4 i=4 第6次比较: 3 9 1 5 8 10 6 7 2 4 i=5 第7次比较: 3 9 1 5 8 10 6 7 2 4 i=6 查找成功,返回序号6
顺序查找的算法如下(在顺序表R[0m1]中查找关键字为k的 记录成功时返回找到的记录位置失败时返回-1): int Seqsearch(seqlist r, int n, KeyType k) int i=0; while(i=n) return -1: ese return i:
顺序查找的算法如下(在顺序表R[0..n-1]中查找关键字为k的 记录,成功时返回找到的记录位置,失败时返回-1)： int SeqSearch(SeqList R,int n,KeyType k) { int i=0; while (i=n) return -1; else return i; }