《数据结构》课程教学资源（PPT课件）第九章 查找

第9章?查找9.1查找的基本概念9.2静态查找9.3动态查找

第9章 查找 9.1 查找的基本概念 9.2 静态查找 9.3 动态查找

本章主要知识点：，查找的基本概念和衡量查找算法效率的标准，静态香找表，主要包括顺序香找方法和索引顺序方法，动态查找表，主要包括二又排序树

本章主要知识点： ● 查找的基本概念和衡量查找算法效率的标准 ● 静态查找表，主要包括顺序查找方法和索引顺序方 法 ● 动态查找表，主要包括二叉排序树

9.1.查找的基本概念查找查询特定元素是否在（数据元素集合）表中的过程若表中存在特定元素，称查找成功，应输出该记录；查找成功否则，称查找不成功（也应输出失败标志或失败位置查找不成功静态查找只查找，不改变数据元素集合内的数据元素，动态查找既查找，又改变（增减）集合内的数据元素，关键字记录中某个数据项的值，可用来识别一个记录例如“学号主关键字可以唯一标识一个记录的关键字次关键字识别若干记录的关键字例如“女

9.1 查找的基本概念 ——若表中存在特定元素，称查找成功，应输出该记录； ——否则，称查找不成功（也应输出失败标志或失败位置） 查 找 查找成功 查找不成功 静态查找 动态查找 关键字 主关键字 次关键字 ——查询特定元素是否在(数据元素集合）表中的过程。 ——只查找，不改变数据元素集合内的数据元素。 ——既查找，又改变（增减）集合内的数据元素。 ——记录中某个数据项的值，可用来识别一个记录 ——可以唯一标识一个记录的关键字 例如“学号” 例如“女” ——识别若干记录的关键字

讨论：如何评估查找方法的优劣？明确：查找的过程就是将给定的K值与文件中各记录的关键建字项进行比较的过程。所以用比较次数的平均值来评估算法的优劣。称为平均查找长度ASLPAverageSearchASLPC二Lengthi=1其中:n是文件记录个数：P;是要查找数据元素的出现概率（通常查找成功，取P：=1/n）C是查找相应数据元素需进行的比较次数物理意义：假设每一元素被查找的概率相同，则查找每一元素所需的比较次数之总和再取平均，即为ASL。显然，ASL值越小，时间效率越高

讨论：如何评估查找方法的优劣？ 明确：查找的过程就是将给定的K值与文件中各记录的关 键字项进行比较的过程。所以用比较次数的平均值来评 估算法的优劣。称为平均查找长度ASL。 其中： n是文件记录个数； Pi是要查找数据元素的出现概率（通常查找成功，取Pi =1/n）; Ci是查找相应数据元素需进行的比较次数。 物理意义：假设每一元素被查找的概率相同，则查找每一元 素所需的比较次数之总和再取平均，即为ASL。 显然，ASL值越小，时间效率越高。 Average Search Length

9.2静态查找静态查找问题数据元素的存储结构主要是顺序存储结构静态查找主要有三种情况：无序序列有序序列索引结构

9.2 静态查找 静态查找主要有三种情况： 无序序列 有序序列 索引结构 静态查找问题数据元素的存储结构主要是顺序存储结构

9.2.1在无序序列中香找在一个无序序列中查找某个数据元素是否存在的算法思想是：从数组的一端开始，用给定数据元素逐个和数组中各数据元素比较，若在数组中查找到要查找的数据元素，则查找成功：否则查找失败

在一个无序序列中查找某个数据元素是否存在的算法思想 是：从数组的一端开始，用给定数据元素逐个和数组中各数据 元素比较，若在数组中查找到要查找的数据元素，则查找成功； 否则查找失败。 9.2.1在无序序列中查找

在无序序列中香找某个数据元素是否存在的函数设计如下：public static int seqSeach(intll a, int elem)/在数组a中顺序查找数据元素elem是否存在。查找成功返回该元素的下标；失败返回-1int n = a.Length ;inti= O;while (i= n) return -1;else return i;

在无序序列中查找某个数据元素是否存在的函数设计如下： public static int seqSeach(int[] a, int elem) { //在数组a中顺序查找数据元素elem是否存在。查找成 功返回该元素的下标；失败返回-1 int n = a.Length ; int i = 0; while (i = n) return -1; else return i; }

顺序查找算法性能评价分析：查找第1个元素所需的比较次数为1：查找第2个元素所需的比较次数为2：查找第n个元素所需的比较次数为n；总计全部比较次数为：1+2十.十n=(1+n)n/2若求某一个元素的平均查找长度，还应当除以n（等概率），即：ASL成功三（1十n）/2，时间效率为O(n)这是查找成功的情况同理：ASL失败=n顺序查找的特点优点：算法简单，且对顺序结构或链表结构均适用。缺点：ASL太大，时间效率太低

顺序查找算法性能评价 分析： 查找第1个元素所需的比较次数为1； 查找第2个元素所需的比较次数为2； . 查找第n个元素所需的比较次数为n； 总计全部比较次数为：1＋2＋.＋n = (1+n)n/2 这是查找成功的情况 若求某一个元素的平均查找长度，还应当除以n（等概率）， 即： ASL成功＝（1＋n）/2 ，时间效率为O(n) 同理：ASL失败＝n 顺序查找的特点 优点：算法简单，且对顺序结构或链表结构均适用。 缺点：ASL 太大，时间效率太低

9.2.2在有序序列中查找1、顺序查找有序序列上顺序查找算法类同无序序列上的查找算法。有序数组中的顺序查找函数如下：public static int orderSeqSearch(intll a, int elem)int n = a.Length;inti= O;while(i=n) return -1;if(a[i] == elem) return i;查找7else return -1;人24589

9.2.2 在有序序列中查找 1、顺序查找 有序序列上顺序查找算法类同无序序列上的查找算法。 有序数组中的顺序查找函数如下： public static int orderSeqSearch(int[] a, int elem){ int n = a.Length; int i = 0; while(i =n) return -1; if(a[i] == elem) return i; else return -1; } 2 4 5 8 9 查找7

设要查找的数据元素在数据元素集合中出现的概率均相等，则有序序列的顺序查找算法查找成功时的平均香查找长度ASL成功为：ASL成功=（1+n） /2查找失败时的平均查找长度ASL失败为：ASL失败~n/2

设要查找的数据元素在数据元素集合中出现的概率均相 等，则有序序列的顺序查找算法查找成功时的平均查找长度 ASL成功为： ASL成功＝（1＋n）/2 查找失败时的平均查找长度ASL失败为： ASL失败 ≈n/2