第10章 查找

《第10章 查找》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、第10章查找10.1查找的基本概念本章小结10.2线性表的查找10.3树表的查找10.4哈希表查找10.1查找的基本概念被查找的对象是由一组记录组成的表或文件,而每个记录则由若干个数据项组成,并假设每个记录都有一个能惟一标识该记录的关键字。在这种条件下,查找的定义是：给定一个值k,在含有n个记录的表中找出关键字等于k的记录。若找到,则查找成功,返回该记录的信息或该记录在表中的位置；否则查找失败,返回相关的指示信息。采用何种查找方法?(1)使用哪种数据结构来表示“表”,即表中记录是按何种方式组织的。(2)表中关键字的次序。是对无序集合查找还是对有序集合查找

2、?若在查找的同时对表做修改运算(如插入和删除),则相应的表称之为动态查找表,否则称之为静态查找表。由于查找运算的主要运算是关键字的比较,所以通常把查找过程中对关键字需要执行的平均比较次数(也称为平均查找长度)作为衡量一个查找算法效率优劣的标准。平均查找长度ASL(AverageSearchLength)定义为：其中,n是查找表中记录的个数。pi是查找第i个记录的概率,一般地,均认为每个记录的查找概率相等,即pi=1/n(1≤i≤n),ci是找到第i个记录所需进行的比较次数。10.2线性表的查找在表的组织方式中,线性表是最简单的一种。三种在线性表上进行查找

3、的方法：(1)顺序查找(2)二分查找(3)分块查找。因为不考虑在查找的同时对表做修改,故上述三种查找操作都是在静态查找表上实现的。查找与数据的存储结构有关,线性表有顺序和链式两种存储结构。本节只介绍以顺序表作为存储结构时实现的顺序查找算法。定义被查找的顺序表类型定义如下：#defineMAXL<表中最多记录个数>typedefstruct{KeyTypekey;/*KeyType为关键字的数据类型*/InfoTypedata;/*其他数据*/}NodeType;typedefNodeTypeSeqList[MAXL];/*顺序表类型*/10.2.1顺序查

4、找顺序查找是一种最简单的查找方法。它的基本思路是：从表的一端开始,顺序扫描线性表,依次将扫描到的关键字和给定值k相比较,若当前扫描到的关键字与k相等,则查找成功；若扫描结束后,仍未找到关键字等于k的记录,则查找失败。例如,在关键字序列为{3,9,1,5,8,10,6,7,2,4}的线性表查找关键字为6的元素。顺序查找过程如下：开始:39158106724第1次比较:39158106724i=0第2次比较:39158106724i=1第3次比较:39158106724i=2第4次比较:39158106724i=3第5次比较:39158106724i=4第6

5、次比较:39158106724i=5第7次比较:39158106724i=6查找成功,返回序号6顺序查找的算法如下(在顺序表R[0..n-1]中查找关键字为k的记录,成功时返回找到的记录位置,失败时返回-1)：intSeqSearch(SeqListR,intn,KeyTypek){inti=0;while(i=n)return-1;elsereturni;}从顺序查找过程可以看到(不考虑越界比较i

6、查找表中最后一个记录R[n-1]时,需比较n次,即ci=i。因此,成功时的顺序查找的平均查找长度为：查找成功时的平均比较次数约为表长的一半。10.2.2二分查找二分查找也称为折半查找要求线性表中的结点必须己按关键字值的递增或递减顺序排列。它首先用要查找的关键字k与中间位置的结点的关键字相比较,这个中间结点把线性表分成了两个子表,若比较结果相等则查找完成;若不相等,再根据k与该中间结点关键字的比较大小确定下一步查找哪个子表,这样递归进行下去,直到找到满足条件的结点或者该线性表中没有这样的结点。例如,在关键字有序序列{2,4,7,9,10,14,18,26,

7、32,40}中采用二分查找法查找关键字为7的元素。二分查找过程如下：开始:2479101418263240low=0high=9mid=(0+9)/2=4第1次比较:2479101418263240low=0high=3mid=(0+3)/2=1第2次比较:2479101418263240low=2high=3mid=(2+3)/2=2第3次比较:2479101418263240R[2].key=7查找成功,返回序号2其算法如下(在有序表R[0..n-1]中进行二分查找,成功时返回记录的位置,失败时返回-1)：intBinSearch(SeqListR,

8、intn,KeyTypek){intlow=0,high=n-1,mid;whi