[计算机软件及应用]ds08-查找

《[计算机软件及应用]ds08-查找》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、基本概念线性表的查找树表的查找散列(Hash)技术第八章查找8.1查找的基本概念查找（Searching）的定义是：在含有n条记录的表（文件）中找出关键字等于给定值K的记录。若找到，则查找成功，返回该记录的信息或该记录在表（文件）中的位置；否则查找失败，返回相关的指示信息。若在查找的同时对表做修改操作（如插入和删除等），则相应的表称之为动态查找表（DynamicSearchTable）。否则称之为静态查找表(StaticSearchTable)。若整个查找过程都在内存进行，则称之为内查找；反之，若查找过程中需要访问外存，则称之为外查找查找表的数据

2、结构表示如何分析算法优劣？主要分析算法运算时所需要的时间和其存储结构占用的内存空间。而对于查找算法，执行的时间通常取决于关键字的比较次数，所以本章经常用平均比较次数，即平均查找长度ASL（AverageSearchLength）其中：1、n是结点的个数；2、Pi是查找第i个结点的概率。若不特别声明，认为每个结点的查找概率相等，即pl=p2……=pn=1/n3、ci是找到第i个结点所需进行的比较次数ASL=平均查找长度ASL（AverageSearchLength）定义为：一、顺序查找(SequentialSearch)基本思想是：从表的一端开始，

3、顺序扫描线性表，依次将扫描到的结点关键字和给定值K相比较。若当前扫描到的结点关键字与K相等，则查找成功；若扫描结束后，仍未找到关键字等于K的结点，则查找失败。8.2线性表的查找基于顺序结构的顺序查找算法类型说明typedefstruct{KeyTypekey；/*KeyType由用户定义*/InfoTypeotherinfo；/*此类型依赖于应用*/}NodeType；typedefNodeTypeSeqlist[n+1]；/*多出0号单元用作监视哨*/具体算法intSeqSearch(SeqlistR，KeyTypeK){/*在顺序表R[1..

4、n]中顺序查找关键字为K的结点，*//*成功时返回找到的结点位置，失败时返回0*/inti；R[0].key=K；/*设置监视哨*/for(i=n；R[i].key!=K;i--)；/*从表后往前找*/returni；/*若i为0，表示查找失败，否则R[i]为要找的结点*/}/*SeqSearch*/算法分析查找成功时的顺序查找的平均查找长度：在等概率情况下，pi=1/n(1≤i≤n)，故成功的平均查找长度为ASL==(n+…+2+1)/n=(n+1)/2即查找成功时的平均比较次数约为表长的一半。顺序查找的缺点查找效率低。顺序查找的优点算法简单，

5、且对表的结构无任何要求，无论是用向量还是用链表来存放结点，也无论结点之间是否按关键字有序，它都同样适用。二分查找又称折半查找，它是一种效率较高的查找方法。二分查找要求：要求线性表是有序表，即表中结点按关键字有序，并且要用向量作为表的存储结构。不妨设有序表是递增有序的。二、二分查找（1）首先确定该区间的中点位置mid=（2）然后将中间位置记录的键值R[mid].key和所给关键字K进行比较：若相等，则查找成功并返回此位置，否则须确定新的查找区间，继续二分查找。二分查找的基本思想是：例：设算法的输入实例中有序的关键字序列为：05，13，19，21，3

6、7，56，64，75，80，88，92。查找的关键字K=21第一步：这里的n=11,mid=(1+11)/2=605，13，19，21，37，56，64，75，80，88，92第二步：mid=(1+5)/2=305，13，19，21，37，56，64，75，80，88，92第三步：mid=(4+5)/2=405，13，19，21，37，56，64，75，80，88，92此时R[mid].key＝K，returnmid＝4。二分查找算法intBinSearch(SeqListR，KeyTypeK){intlow=1，high=n，mid；while

7、(low<=high){mid=(low+high)/2；/*求中间位置*/if(R[mid].key==K)returnmid；if(R[mid].key>K)high=mid-1;elselow=mid+1；}return0；}确定新的查找区间二分查找过程可用二叉树来描述：把当前查找区间的中间位置上的结点作为根，左子表和右子表中的结点分别作为根的左子树和右子树。由此得到的二叉树，称为描述二分查找的判定树(DecisionTree)或比较树(ComparisonTree)。二分查找判定树二分查找判定树的组成如对表R{3，7，11，19，30，1

8、15，136，141}的查找过程：3711193011513614137111930115136141LowmidhighLowmidh