1.与查找相关的概念1.1查找表1.2关键字1.3平均查找长度ASL2.线性表的查找2.1顺序查找在顺序查找中下标 为0 的位置通常不存储有效数据专门用来放哨兵。(有效数据从下标为1的位置开始存储)代码优化前不带哨兵的顺序查找// 定义查找表的数据结构顺序表typedefstruct{ElemType*elem;// 动态数组起始地址实际申请 TableLen1 个空间// 有效数据存在 elem[1]、elem[2]....TableLen]。elem[0] 存哨兵位intTableLen;// 表的有效长度表示有效数据的个数}SSTable;// 版本一无哨兵 // 找到则返回该元素的下标找不到返回0intSearch_Seq(SSTable ST,ElemType key){// 从表尾 TableLen 往前找没有哨兵for循环必须同时判断两个条件inti;for(iST.TableLen;i1ST.elem[i]!key;--i);// i1 说明正常找到i0 说明遍历完都没找到// 注i 最多减到0就停不会访问 elem[0]那是哨兵位未存有效数据returni;}代码优化后带哨兵的顺序查找// 定义查找表的数据结构顺序表typedefstruct{ElemType*elem;// 动态数组起始地址实际申请 TableLen1 个空间// 有效数据存在 elem[1]、elem[2]....TableLen]另外elem[0] 存储哨兵位intTableLen;// 表的有效长度表示有效数据的个数}SSTable;// 版本二带哨兵 // 找到则返回该元素的下标找不到返回0intSearch_Seq(SSTable ST,ElemType key){// 【哨兵设置】把 key 存进 elem[0]——正是为它预留的哨兵位// 目的避免循环中反复判断下标是否越界简化循环条件ST.elem[0]key;// 【从后往前遍历查找】// 从表尾下标 TableLen最后一个有效数据向前找// 因有哨兵即使遍历到表头也必然匹配 key循环必停不会越界inti;// ★ i 在循环外声明供 return 使用for(iST.TableLen;ST.elem[i]!key;--i);// 【返回结果】// i 不为0找到返回下标i0命中哨兵表中不存在目标元素查找失败returni;}顺序查找的平均查找长度元素有序的顺序表、元素无序的顺序表的对比2.2折半查找代码// 定义数据元素类型typedefintElemType;// 定义查找表的数据结构顺序表typedefstruct{ElemType*elem;// 动态数组基址指向存储数据的数组首地址intTableLen;// 表的长度表示顺序表中有效元素的个数}SSTable;/********************************************************** 函数功能折半查找二分查找 前提条件顺序表必须有序升序 参数ST 顺序表结构体 key 要查找的关键字 返回值找到返回下标找不到返回 -1 **********************************************************/intBinarySearch(SSTable ST,ElemType key){// 左边界初始指向第一个元素intleft0;// 右边界初始指向最后一个元素intrightST.TableLen-1;intmid;// 区间有效时继续查找while(leftright){// 计算中间位置mid(leftright)/2;// 找到目标返回下标if(ST.elem[mid]key){returnmid;}// key 更小去左半区elseif(keyST.elem[mid]){rightmid-1;}// key 更大去右半区else{leftmid1;}}//当leftright时表示查找失败返回-1return-1;}构造折半查找判定树较复杂构造折半查找判定树的形态重点帮助理解折半查找判定树的图片例题真题1易例题2易例题3中、有坑真题4难在视频的最后2.3分块查找2.3.1分块查找的概念2.3.2例题例题1