第九章_查找课1

1、1第九章第九章 查查 找找2第九章第九章 查查 找找3第九章第九章 查查 找找4第九章第九章 查查 找找若表中存在特定元素，称查找成功，应输出该记录；若表中存在特定元素，称查找成功，应输出该记录；否则，称查找不成功（也应输出失败标志或失败位置）否则，称查找不成功（也应输出失败标志或失败位置）查找表查找表 查查 找找查找成功查找成功查找不成功查找不成功静态查找静态查找动态查找动态查找关键字关键字主关键字主关键字次关键字次关键字由同一类型的数据元素（或记录）构成的集合。由同一类型的数据元素（或记录）构成的集合。查询查询(Searching)特定元素特定元素是否在表中。是否在表中。只查找，不改变集合

2、内的数据元素。只查找，不改变集合内的数据元素。既查找，又改变（增减）集合内的数据元素。既查找，又改变（增减）集合内的数据元素。记录中某个数据项的值，可用来识别一个记录记录中某个数据项的值，可用来识别一个记录 ( 预先确定的记录的某种标志预先确定的记录的某种标志 ) 可以可以唯一唯一标识一个记录的关键字标识一个记录的关键字例如例如“学号学号”例如例如“女女”是一种数据结构是一种数据结构识别若干记录的关键字识别若干记录的关键字5第九章第九章 查查 找找6取决于查找表的结构，即：记录在查找表中所处的位置。取决于查找表的结构，即：记录在查找表中所处的位置。 查找表本身是一种很松散的结构，因此，为了提高

3、查找表本身是一种很松散的结构，因此，为了提高查找的效率，需要在查找表中的元素之间人为地附加某查找的效率，需要在查找表中的元素之间人为地附加某种确定的关系，换句话说，用另外一种结构来表示查找种确定的关系，换句话说，用另外一种结构来表示查找表，以便按某种规则进行查找。表，以便按某种规则进行查找。 第九章第九章 查查 找找7（2）对查找表常用的操作有）对查找表常用的操作有哪些？哪些？ v查询某个查询某个“特定的特定的”数据元素是否在表中；数据元素是否在表中；v查询某个查询某个“特定的特定的”数据元素的各种属性；数据元素的各种属性；v在查找表中插入一元素；在查找表中插入一元素；v从查找表中删除一元素。

4、从查找表中删除一元素。 （3) 有哪些查找方法？有哪些查找方法？ 查找方法取决于表中数据的排列方式查找方法取决于表中数据的排列方式;讨论：讨论：（1）查找的过程是怎样的？）查找的过程是怎样的？ 给定一个值给定一个值K K，在含有，在含有n n个记录的文件中进行搜索，寻找个记录的文件中进行搜索，寻找一个关键字值等于一个关键字值等于K K的记录，如找到则输出该记录，否则输出的记录，如找到则输出该记录，否则输出查找不成功的信息。查找不成功的信息。例如查字典例如查字典针对静态查找表和动态查找表的查找方法也有所不同针对静态查找表和动态查找表的查找方法也有所不同。“特定的特定的”=关键字关键字8明确：明确

5、：查找的过程就是将给定的查找的过程就是将给定的K K值与文件中各记录的关键字值与文件中各记录的关键字项进行比较的过程。所以用比较次数的平均值来评估算法的优项进行比较的过程。所以用比较次数的平均值来评估算法的优劣。称为劣。称为平均查找长度平均查找长度（ASLASL：average search lengthaverage search length）。）。其中：其中：n n是文件记录个数；是文件记录个数；P Pi i是查找第是查找第i i个记录的查找概率（通常取等概率个记录的查找概率（通常取等概率, ,即即P Pi i =1/n =1/n）; ;C Ci i是找到第是找到第i i个记录时所经历的

6、比较次数。个记录时所经历的比较次数。统计意义上的统计意义上的数学期望值数学期望值物理意义：物理意义：假设每一元素被查找的概率相同，则查找每一假设每一元素被查找的概率相同，则查找每一元素所需的比较次数之总和再取平均，即为元素所需的比较次数之总和再取平均，即为ASLASL。显然，显然，ASLASL值越小，时间效率越高。值越小，时间效率越高。 如何评估查找方法的优劣？如何评估查找方法的优劣？1niiiASLP C910针对静态查找表的查找算法主要有：针对静态查找表的查找算法主要有： 静态查找表的抽象数据类型参见教材静态查找表的抽象数据类型参见教材P216。9.1.1 顺序查找（线性查找）顺序查找（线

7、性查找）9.1.2 折半查找（二分或对分查找）折半查找（二分或对分查找）9.1.4 分块查找（索引顺序查找）分块查找（索引顺序查找）11 顺序查找：即用逐一比较的办法顺序查找关键字，这顺序查找：即用逐一比较的办法顺序查找关键字，这显然是最直接的办法。显然是最直接的办法。v对对顺序结构顺序结构如何线性查找？；如何线性查找？；v对对单链表结构单链表结构如何线性查找？函数虽未给出，但也如何线性查找？函数虽未给出，但也很容易编写；只要知道头指针很容易编写；只要知道头指针headhead就可以就可以“顺藤摸顺藤摸瓜瓜”；v对对非线性树结构非线性树结构如何顺序查找如何顺序查找? ?可借助各种遍历操可借助各

8、种遍历操作！作！12数据元素存储空间基址，建数据元素存储空间基址，建表时按实际长度分配，表时按实际长度分配，0号单元留空号单元留空表长度表长度13能不能把i= 0 加进加进 for语句。语句。1516 例：查找例：查找 key = 8 的结点所在的数组元素的下标的结点所在的数组元素的下标012n-3n-2n-1ni数组数组 ST.elemkey8100100813012n-3n-2n-1ni数组数组 ST.elemkey8100100813012n-3n-2n-1n数组数组 ST.elemkey8100100813i012n-3n-2n-1n数组数组 ST.elemkey8100100813i

9、17012n-3n-2n-1n数数组组 ST.elemkey8100100813ii = n-2012n-3n-2n-1n数数组组 ST.elemkey8100100813ii = n-2 查找成功，则查找成功，则 i 是是key 值为值为 8 的结点所在的结点所在的数组元素的下标。的数组元素的下标。18012n-3n-2n-1ni数数组组 ST.elemkey8100100713012n-3n-2n-1ni数数组组 ST.elemkey8100100713012n-3n-2n-1n数数组组 ST.elemkey8100100713i012n-3n-2n-1n数数组组 ST.elemkey81

10、00100713i012n-3n-2n-1n数数组组 ST.elemkey8100100713i012n-3n-2n-1n数数组组 ST.elemkey8100100713i19012n-3n-2n-1n数数组组 ST.elemkey8100100713i012n-3n-2n-1n数数组组 ST.elemkey8100100713i012n-3n-2n-1n数组数组 ST.elemkey8100100713i012n-3n-2n-1n数组数组 ST.elemkey8100100713i012n-3n-2n-1n数组数组 ST.elemkey8100100713i012n-3n-2n-1n数组数

11、组 ST.elemkey8100100713i20012n-3n-2n-1n数数组组 ST.elemkey查查找找失失败败，则则 i = 0; 8100100713012n-3n-2n-1n数数组组 ST.elemkey查查找找失失败败，则则 i = 0; 8100100713 查找失败，则查找失败，则i=0。21返回特殊标志，例如返回空记录或空返回特殊标志，例如返回空记录或空指针。前例中设立了指针。前例中设立了“哨兵哨兵”，就是将关，就是将关键字送入末地址键字送入末地址ST.elemST.elem0 0.key.key使之结束使之结束并返回并返回 i=0i=0。讨论讨论 查找效率怎样计算？查

12、找效率怎样计算？用平均查找长度用平均查找长度ASL衡量。衡量。讨论讨论 查不到怎么办？查不到怎么办？22讨论讨论 如何计算如何计算ASL？分析：分析：查找第查找第1个元素所需的比较次数为个元素所需的比较次数为1；查找第查找第2个元素所需的比较次数为个元素所需的比较次数为2；查找第查找第n个元素所需的比较次数为个元素所需的比较次数为n；总计全部比较次数为：总计全部比较次数为：12n = (1+n)n/2未考虑查找不成功的未考虑查找不成功的情况：查找哨兵所需情况：查找哨兵所需的比较次数为的比较次数为n+1n+1这是查找成功的情况这是查找成功的情况若求某一个元素的平均查找次数，还应当除以若求某一个元

13、素的平均查找次数，还应当除以n（等概率），（等概率），即：即： ASL（1n）/2 ，时间效率为，时间效率为 O(n)23成功时的平均查找长度成功时的平均查找长度) 1(4321) 1(211nninnASLni查找成功时查找不成功时24 顺序查找的优缺点：顺序查找的优缺点：25折半查找（又称二分查找或对分查找）折半查找（又称二分查找或对分查找）这是一种容易想到的查找方法。这是一种容易想到的查找方法。先给数据排序先给数据排序（例如按升序排好），形成（例如按升序排好），形成有序表有序表，然后再将，然后再将keykey与正中元素相比，若与正中元素相比，若keykey小，则缩小至右半部内查找；再取其

14、中小，则缩小至右半部内查找；再取其中值比较，每次缩小值比较，每次缩小1/21/2的范围，直到查找成功或失败为止。的范围，直到查找成功或失败为止。v 对对顺序表结构顺序表结构如何编程实现折半查找算法？如何编程实现折半查找算法？ 见后面例子见后面例子，或见教材（，或见教材（P219P219）v 对对单链表结构单链表结构如何折半查找？如何折半查找？ 无法实现！无法实现！因全部元素的定位只能从头指针因全部元素的定位只能从头指针headhead开始开始v 对对非线性非线性(树树)结构结构如何折半查找？如何折半查找？ 可借助二叉排序树来查找（属动态查找表形式）。可借助二叉排序树来查找（属动态查找表形式）。

15、 26 运算步骤运算步骤：(1) (1) low =1,high =11 ,mid =6 low =1,high =11 ,mid =6 ，待查范围是，待查范围是 1,111,11；(2) (2) 若若 ST.elemmid.key ST.elemmid.key key keykey，说明，说明keykey low ,midlow ,mid-1-1 ， 则令：则令：high =midhigh =mid1 1; ;重算重算 mid mid ；(4)(4)若若 ST.elem mid .key ST.elem mid .key = key= key，说明查找成功，元素序号，说明查找成功，元素序号=

16、mid;=mid;结束条件结束条件（1 1）查找成功）查找成功 ： ST.elemmid.key = keyST.elemmid.key = key （2 2）查找不成功）查找不成功 ： highlow highlow （意即区间长度小于（意即区间长度小于0 0）解：解： 先设定先设定3个辅助标志个辅助标志: low,high,midlow,high,mid，折半查找举例：LowLow指向待查元素指向待查元素所在区间的下界所在区间的下界highhigh指向待查元素所指向待查元素所在区间的上界在区间的上界midmid指向待查元素所在指向待查元素所在区间的中间位置区间的中间位置 已知如下已知如下1

17、1个元素的个元素的有序表有序表：（05 13 19 21 37 56 64 75 80 88 92）, 请查找关键字为请查找关键字为21 和和85的数据元素。的数据元素。显然有：显然有：mid= (low+high)/2 27012mid=4 但但 key=9 10, 向左向左key4891011131934567high=7low=1012mid=4 但但 key=9 8, 向向右右key4891011131934567high=3（mid-1）low=1012mid=2; 但但 key=9 8, 向向右右key4891011131934567high=3（mid-1）low=1012key

18、4891011131934567high=3low=3（mid+1）mid=2012key4891011131934567high=3low=3（mid+1）mid=230012key4891011131934567high=3low=3012key4891011131934567high=3low=3012m id=3; 但但 key=9 中中 点点 值值 也也 为为 9 ，找找 到到key4891011131934567high=3low =3012m id=3; 但但 key=9 中中 点点 值值 也也 为为 9 ，找找 到到key4891011131934567high=3low =3

19、31012mid=4 但但 key=5 10, 向左向左key4891011131934567high=7low=1012mid=4 但但 key=5 10, 向左向左key4891011131934567high=7low=1012mid=4key4891011131934567high=3（mid-1）low=1012mid=4key4891011131934567high=3（mid-1）low=132012mid=2key4891011131934567high=3low=1012mid=2key4891011131934567high=3low=1012mid=2; 但但 key=5

20、 8, 向向左左key4891011131934567high=3low=1012mid=2; 但但 key=5 4, 向向右右key4891011131934567high=1low=1012mid=1; 但但 key=5 4, 向向右右key4891011131934567high=1low=1012mid=1; 但但 key=5 4, 向向右右key4891011131934567high=1low=2 （mid+1）失失败败条条件件：low high; 处处于于间间隙隙中中的的键键值值导导致致这这种种情情况况！012mid=1; 但但 key=5 4, 向向右右key489101113

21、1934567high=1low=2 （mid+1）012mid=1; 但但 key=5 4, 向向右右key4891011131934567high=1low=2 （mid+1）失失败败条条件件：low high; 处处于于间间隙隙中中的的键键值值导导致致这这种种情情况况！3536mjjj112讨论讨论 若关键字不在表中，怎样得知和停止？若关键字不在表中，怎样得知和停止？典型标志是：当查找范围的上界典型标志是：当查找范围的上界下界时停止查找。下界时停止查找。讨论讨论 二分查找的效率（二分查找的效率（ASLASL平均查找长度）平均查找长度）1次比较就查找成功的元素有次比较就查找成功的元素有1个

22、（个（20），即中间值；），即中间值；2次比较就查找成功的元素有次比较就查找成功的元素有2个（个（21），即），即1/4处（或处（或3/4）处；）处；3次比较就查找成功的元素有次比较就查找成功的元素有4个（个（22），即），即1/8处（或处（或3/8）处）处 4次比较就查找成功的元素有次比较就查找成功的元素有8个（个（23），即），即1/16处（或处（或3/16）处）处 则第则第m次比较时查找成功的元素会有（次比较时查找成功的元素会有（2m-1）个；）个；为方便起见，假设表中全部为方便起见，假设表中全部n个元素个元素 2m-1个个，此时就不讨论第此时就不讨论第m次比较后还有剩余元素的情况了。次

23、比较后还有剩余元素的情况了。全部比较总次数为全部比较总次数为120221322423m2m1 推推导导过过程程37平均每个数据的查找时间还要除以平均每个数据的查找时间还要除以n，所以：所以：（详细推导过程见教材（详细推导过程见教材P221的附录的附录1）课堂练习课堂练习（多项选择）：（多项选择）：采用链式存贮结构采用链式存贮结构 记录的长度记录的长度128 采用顺序存贮结构采用顺序存贮结构 记录按关键字递增有序记录按关键字递增有序nnnnjnASLmjj2211log1) 1(log121使用折半查找算法时，要求被查文件：使用折半查找算法时，要求被查文件：上述平均查找长度（ASL）计算成立的前

24、提是第m次比较时恰好剩余2m-1个。个。38填空：填空：假设在有序线性表假设在有序线性表a20上进行折半查找，则比较一上进行折半查找，则比较一次查找成功的结点数为次查找成功的结点数为1；比较两次查找成功的结点；比较两次查找成功的结点数为数为 2 ；比较四次查找成功的结点数为；比较四次查找成功的结点数为 8 ；平均查找长度为平均查找长度为 3.7 。 显然，平均查找长度显然，平均查找长度O（log2n）5次（次（25）。但具体是）。但具体是多少次，则不应当按照公式多少次，则不应当按照公式) 1(log12nnnASL来计算（来计算（即（即（21log221）/204.6次并不正确！次并不正确！）

25、。因为这是在假）。因为这是在假设设n2m-1的情况下推导出来的公式。的情况下推导出来的公式。应当用穷举法罗列：应当用穷举法罗列：全部元素的查找次数为（全部元素的查找次数为（122438455）74； ASL74/20=3.7 ！39查找过程可用查找过程可用二叉树二叉树描述：每个记录用一个结点表示；结点描述：每个记录用一个结点表示；结点中值为该记录在表中位置，这个描述查找过程的二叉树称为中值为该记录在表中位置，这个描述查找过程的二叉树称为判定树判定树。n个元素的表的折半查找的判定树是唯一的，即：判个元素的表的折半查找的判定树是唯一的，即：判定树由表中元素个数决定。定树由表中元素个数决定。 找到有

26、序表中任一记录的过程就是找到有序表中任一记录的过程就是：走了一条从根结点到与：走了一条从根结点到与该记录相应的结点的路径。该记录相应的结点的路径。 比较的关键字个数：比较的关键字个数：为该结点在判定树上的层次数。为该结点在判定树上的层次数。 查找成功时查找成功时比较的关键字个数比较的关键字个数最多不超过树的深度最多不超过树的深度 d : d = log2 n + 1 查找不成功的过程查找不成功的过程 就是走了一条从根结点到外部结点的路就是走了一条从根结点到外部结点的路径。径。折半查找效率分析法（参见教材折半查找效率分析法（参见教材P220）：）：4041是一种顺序查找的另一种改进方法。是一种顺

27、序查找的另一种改进方法。先让数据先让数据分块有序分块有序，即分成若干子表，要求每个子表中的数，即分成若干子表，要求每个子表中的数值（用关键字更准确）都比后一块中数值小（但子表内部未必值（用关键字更准确）都比后一块中数值小（但子表内部未必有序）。有序）。然后将各子表中的然后将各子表中的最大关键字最大关键字构成一个构成一个索引表索引表，表中还要包，表中还要包含每个子表的起始地址（即头指针）。含每个子表的起始地址（即头指针）。索引表索引表最大关键字起始地址2212138920334244382448605874498653第第1 1块块第第2 2块块第第3 3块块224886例：例：22488617

28、13特点：块间有特点：块间有序，块内无序序，块内无序42387363521406012345678947索引索引顺序表顺序表83660147块最大关键字块最大关键字块起始地址块起始地址索引表索引表块最大关键字有序块最大关键字有序块内关键字无序（也可有序）块内关键字无序（也可有序）387363521406012345678947索引索引顺序表顺序表83660147块最大关键字块最大关键字块起始地址块起始地址索引表索引表块最大关键字有序块最大关键字有序块内关键字无序（也可有序）块内关键字无序（也可有序）434445查找步骤查找步骤分两步进行分两步进行： 对索引表使用折半查找法（因为索引表是有序表）

29、；对索引表使用折半查找法（因为索引表是有序表）； 确定了待查关键字所在的子表后，在子表内采用顺序确定了待查关键字所在的子表后，在子表内采用顺序查找法（因为各子表内部是无序表）；查找法（因为各子表内部是无序表）；查找效率：查找效率：ASL=LASL=Lb b+L+Lw w对索引表查找的对索引表查找的ASL对块内查找的对块内查找的ASL)21(log2) 1(log22nASLnssnASLbsbsS为每块内部的记录个数，为每块内部的记录个数，n/s即块的数目即块的数目例如当例如当n=9n=9，s=3s=3时时，ASLASLbsbs= =3.53.5, ,而折半而折半法为法为3.13.1, ,顺序

30、法为顺序法为5 5。46查查找找算算法法 存存储储结结构构 优优点点 缺缺点点 适适用用于于 顺顺序序查查找找 顺顺序序结结构构 链链表表结结构构 算算 法法 简简 单单 且且 对对 表表 的的结结构构无无任任何何要要求求 查查找找效效率率低低 n n 较较小小的的表表的的查查找找和和查查找找较较少少但但改改动动较较多多的的表表( (用用链链表表作作存存储储结结构构) ) 二二分分查查找找 顺顺序序结结构构 查查找找效效率率高高 关关键键字字要要有有序序且且只只能能用用顺顺序序存存储储结结构构实实现现 特特 别别 适适 用用 于于 一一 经经 建建 立立 就就 很很少少 改改 动动 又又 经经

31、 常常 需需 要要 查查 找找 的的线线性性表表 分分块块查查找找 顺顺序序结结构构 链链表表 在在 表表 中中 插插 入入 或或 删删 除除记记 录录 时时 就就 只只 要要 在在 该该记记录录所所属属块块内内操操作作，因因 为为 块块 内内 记记 录录 的的 存存放放是是随随意意的的，所所以以插插入入和和删删除除比比较较容容易易 要要增增加加一一个个辅辅助助数数组组的的存存储储空空间间，并并要要进进行行将将初初始始表表分分块块排排序序运运算算 适适用用于于有有分分块块特特点点的的记记录录，如如 一一 个个 学学 校校 的的 学学 生生 登登 记记 表表可可按按系系号号或或班班号号分分块块。

32、 4748查找表查找表：用于频繁进行插入、删除、查找的：用于频繁进行插入、删除、查找的查找表。查找表。 特点：特点：表结构本身是在查找过程中动态生成的。表结构本身是在查找过程中动态生成的。 要求：要求：即对于给定值即对于给定值key，若表中存在其关键字，若表中存在其关键字等于等于key的记录，则查找成功返回，否则插入关的记录，则查找成功返回，否则插入关键字等于键字等于491定义：定义：二叉排序树。二叉排序树。 50（a）（b）练：下列练：下列2种图形中，哪个不是二叉排序树种图形中，哪个不是二叉排序树 ？-或是一棵空树；或者是具有如下性质的非空二叉树：或是一棵空树；或者是具有如下性质的非空二叉树

33、： （1 1）左子树的所有结点均小于根的值；）左子树的所有结点均小于根的值； （2 2）右子树的所有结点均大于根的值；）右子树的所有结点均大于根的值； （3 3）它的左右子树也分别为二叉排序树）它的左右子树也分别为二叉排序树。讨论：讨论：对左图中序遍历后的结果是什么？对左图中序遍历后的结果是什么？511222503001102009910523021612225030011020099105230216LNPEMCYLNPEMCY522. 2. 将数据元素构造成二叉排序树的优点：将数据元素构造成二叉排序树的优点： 查找过程与顺序结构有序表中的查找过程与顺序结构有序表中的折半查找折半查找相似，查

34、找效率高；相似，查找效率高； 中序遍历中序遍历此二叉树，将会得到一个关键字的有序序列（此二叉树，将会得到一个关键字的有序序列（即实现即实现了排序运算了排序运算）；）； 如果查找不成功，能够方便地将被查元素如果查找不成功，能够方便地将被查元素插入到二叉树的叶子插入到二叉树的叶子结点结点上，而且插入或删除时只需修改指针而不需移动元素。上，而且插入或删除时只需修改指针而不需移动元素。注：注：若若数据元素的数据元素的输入顺序不同，则得输入顺序不同，则得到的二叉排序树形态也不同！到的二叉排序树形态也不同！这种既查找又插入的过程称为这种既查找又插入的过程称为动态查找动态查找。二叉排序树既有类似于折半查找的

35、特性，又采用了二叉排序树既有类似于折半查找的特性，又采用了链表存储，它是动态查找表的一种适宜表示。链表存储，它是动态查找表的一种适宜表示。一、二叉排序树（二叉查找树）一、二叉排序树（二叉查找树）533二叉排序树的查找算法：二叉排序树的查找算法：5412225030011020099105230216122250300110200991052302165556查找不成功查找不成功n注意：注意：5745452424535312129090如果待如果待查找的关键字序列输入顺序为：查找的关键字序列输入顺序为：（2424，5353， 4545，4545，1212，2424，9090），），2424535

36、3454512129090查查找找成成功功，返返回回查查找找成成功功，返返回回讨论讨论1 1：二叉排序树的插入和查找操作：二叉排序树的插入和查找操作 则生成二叉排序则生成二叉排序树的过程为：树的过程为：例例：输入待查找的关键字序列输入待查找的关键字序列= =（4545，2424，5353，4545，1212，2424，9090）则生成的二叉排则生成的二叉排序树形态不同：序树形态不同：查查找找成成功功，返返回回查查找找成成功功，返返回回5812225030011028099122122991222509912225011099122250300110995912225030011099Tp280

37、12225030011099Tp2806012225030011099Tf：null12225030011099Tf：null12225030011099fTKey=28012225030011099fTKey=2806112225030011099fTKey=28012225030011099fTKey=280f12225030011099T:nullKey=280f12225030011099T:nullKey=280p12225030011099280p1222503001109928062仍然保仍然保持二叉排序树的特性持二叉排序树的特性1560703020506030205015607

38、03020506030205063641221222502503003001101102002009999105105230230216216400400450450500500被删结点被删结点被删结点被删结点122122250250300300200200230230216216400400450450500500110110105105删除删除删除删除99991221222502503003001101102002009999105105230230216216400400450450500500被删结点被删结点被删结点被删结点122122250250300300200200230230216216400400450450500500110110105105删除删除删除删除99996512225030011020099105230216400450500被删结点被删结点122250300230216400450500删除删除2001109910512225030011020099105230216400450500被删结点被删结点1222503002