资源描述：
《数据结构 第7章 查找课件.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、数据结构与算法第七讲：查找开场白30/07/20212内容提要查找概论静态查找表动态查找表哈希表30/07/20213查找概论查找表(SearchTable)：同一类型的数据元素（或记录）构成的集合。关键字(Key)：数据元素中某个数据项的值，又称键值。若某关键字可以唯一地标记一个记录，则称主关键字(PrimaryKey)。对于可以识别多个数据元素的关键字，称为次关键字(SecondaryKey)。查找(Searching)就是根据给定的某个值，在查找表中确定一个其关键字等于给定值的数据元素（或记录）。主关键码主关键字数据元素(记
2、录）次关键字数据项（字段）30/07/20214查找表的种类静态查找表(StaticSearchTable):只作查找操作的查找表。主要操作：（1）查询某个“特定的”数据元素是否在查找表中（2）检索某个“特定的”数据元素和各种属性。应用：查字典/查个人信息等动态查找表(DynamicSearchTable):在查找过程中同时插入查找表中不存在的数据元素，或者从查找表中删除已经存在的某个数据元素。主要操作：（1）查找时插入数据元素（2）查找时删除数据元素应用：清理网站的注册用户等查找结构：为提高查找效率而专门为查找操作设置的数据结构
3、如：线性表/树/散列表等。30/07/20215内容提要查找概论静态查找表动态查找表哈希表30/07/20216顺序表查找顺序查找(SequentialSearch)又叫线性查找，是最基本的查找技术。从表中第一个（或最后一个）记录开始，逐个进行记录的关键字和给定值比较，若某个记录的关键字和给定值相等，则查找成功，找到所查的记录；如果直到最后一个（或第一个）记录，其关键字和给定值比较都不等，则表中没有所查记录，查找不成功。30/07/20217顺序表查找算法/*顺序查找,a为数组,n为要查找的数组个数,key为要查找的关键字，朴素版
4、*/intSequential_Search(int*a,intn,intkey){inti;for(i=1;i<=n;i++){if(a[i]==key)returni;}return0;}/*有哨兵顺序查找，改进版*/intSequential_Search2(int*a,intn,intkey){inti;a[0]=key;/*设置a[0]为关键字值，我们称之为“哨兵”*/for(i=n;a[i]!=key;--i);returni;/*返回0则说明查找失败*/}/*有哨兵顺序查找，教科书版*/intSearch_Seq(S
5、STableST,KeyTypekey){ST.elem[0].key=key;for(i=ST.length;!EQ(ST.elem[i].key,key);--i);returni;}/*静态查找表*/typedefstruct{ElemType*elem;intlength;}SSTable;30/07/20218查找操作的性能分析平均查找长度(AverageSearchLength)：为确定记录在查找表中的位置，需和给定值进行比较的关键字个数的期望值。对于含有n个记录的表，查找成功时的平均查找长度为：其中：Pi为查找表中第
6、i个记录的概率，且顺序查找分析：假设n=ST.length，则顺序查找的平均查找长度为假设每个记录的查找概率相等，即则等概率情况下顺序查找的平均查找长度为假设各个记录的查找概率不相等且已知，记录该如何排列才能提高检索效率？如果查找概率预先未知，如何提高检索效率？如果考虑查找不成功的情况，平均查找长度如何计算？(假设查找成功与不成功的可能性相同)30/07/20219有序表查找书架上的书有序排放，查找起来比无序排列来得快。有序表查找算法折半查找插值查找斐波那契查找30/07/202110折半查找及算法实现intBinary_Sear
7、ch(int*a,intn,intkey){intlow,high,mid;low=1;high=n;while(low<=high){mid=(low+high)/2;if(keya[mid])low=mid+1;elsereturnmid;}return0;}/*调用参数*/a={0,1,16,24,35,47,59,62,73,88,99}n=10key=62折半查找技术，又称二分查找。它的前提是线性表中的记录必须是关键码有序且采用顺序存储。基本思想是：在有序表中，
8、取中间记录作为比较对象，若给定值与中间记录的关键字相等，则查找成功；若小于，则在中间记录的左半区继续查找，否则在右半区继续查找。不断重复，直到查找成功（或失败）。99887362594735241610a下标987654321010lowhighm
