数据结构（C语言版）（第三版）（微课版）第7章 查找.pptx

第7章查找

教学要求相关知识点顺序查找、折半查找算法二叉排序树的插入和查找算法哈希表、哈希函数、哈希地址、装填因子哈希函数的选取原则及产生冲突的原因采用开放地址法和链地址法解决冲突时，哈希表的建表方法、查找过程学习重点掌握顺序查找、折半查找、二叉排序树查找以及哈希表查找的基本思想和算法实现。

目录静态查找算法动态查找表哈希表3查找的基本概念124本章小结5

7.1查找的基本概念

7.1查找的基本概念查找的基本概念1.关键字（key）关键字(Key)是数据元素中唯一标识该元素的某个数据项的值，使用基于关键字的查找，查找结果是唯一的。2.查找根据给定的某个值，在数据集合中寻找一个其关键字等于给定值的数据元素。结果分两种情况：（1）查找成功：数据集合中存在相应的数据元素；（2）查找失败：数据集合中不存在关键字等于给定值的数据元素。

7.1查找的基本概念3.查找表（searchtable）由同一数据类型的数据元素构成的数据集合，可以是一个数组或一个链表等数据类型。(1)静态查找表(StaticSearchTable)如果一个查找表的操作只涉及查询某个特定的数据元素是否在查找表中或者检索满足条件的某个特定的数据元素的各属性值，无须修改查找表，这类查找表称为静态查找表。静态查找表适用于：查找表一经生成，便只对其进行查找，而不进行插入和删除操作，或经过一段时间的查找之后，集中地进行插入和删除等修改操作。

7.1查找的基本概念(2)动态查找表(DynamicSearchTable)如果对一个查找表的操作在查找的同时需要动态地插入或删除的查找表则称为动态查找表。动态查找表适用于：查找与插入或删除操作在同一个阶段进行，例如，在某些问题中，当查找成功时，要删除查找的记录，当查找不成功时，要插入被查找的记录。

7.1查找的基本概念4.查找算法的时间复杂度衡量查找算法的优劣，主要是看要查找的值与关键字的比较次数。通常把查找过程中对关键字的最多比较次数和平均比较次数作为衡量一个查找算法效率优劣两个基本技术指标。前者叫做最大查找长度（MaximunSearchLength），简记为MSL。后者叫做平均查找长度（AverageSearchLength），简记ASL，计算公式为：ASL=其中：n是查找表长度；Pi是查找第i个数据元素的概率;Ci是找到第i个数据元素所需进行的比较次数。

7.1查找的基本概念5.查找结构各种数据结构都涉及查找操作，如线性表、队列、栈、树与图等。为提高查找效率，需要专门为查找操作设置数据结构，这种面向查找操作的数据结构成为查找结构(SearchStructure)。本章讨论的查找结构有：静态查找表、动态查找表和哈希表。

7.2静态查找算法

7.2静态查找算法静态查找算法通常采用顺序查找和折半查找。顺序查找顺序查找(SequnceSearch)又称线性查找(LinearSearch)，主要用于在线性表中进行查找。顺序查找通常分为无序表的顺序查找和有序顺序表的顺序查找。

7.2静态查找算法1.无序表的顺序查找（1）基本思想从线性表的一端开始，逐个检查关键字是否满足给定的条件。若查到某个元素的关键字满足给定条件，则查找成功，返回该元素在线性表中的位置；若已经查到表的另一端，还没有找到符合给定条件的元素，则返回查找失败的信息。为了提高查找速度，可在算法中设置“哨兵”。哨兵就是待检查值，将它放在查找方向的“尽头”处，这样免去了在查找过程中每一次比较完之后都要判断查找位置是否越界，从而节省了时间。

7.2静态查找算法(2)静态查找表的顺序存储结构#defineMAXSIZE100typedefintkeyType;typedefstruct{keyTypekey; /*关键字域*/}SElemType;typedefstruct{SElemType*elem;//数据元素存储空间基址intlength; /*表长度*/}SeqTable;

7.2静态查找算法(3)顺序查找算法intSearch_Seq(SSTableST,ElemTypekey)/*在顺序表ST中顺序查找关键字等于key的数据元素。若找到返回该元素在表中的位置；否则返回-1*/{ST.elem[ST.TableLen]=key;/*哨兵*/for(i=0;ST.elem[i].key!=key;++i); /*从前往后找*/if(iST.TableLen)returni;elsereturn-1;/*未找到，返回-1*/}

7.2静态查找算法对于有n个元素的表，给定值ke