查找(cházhǎo)基本概念静态查找表:查找表一旦建立，在以后的查找过程中就不会改变。它所对应(duìyìng)的查找算法属于静态查找技术。动态查找表：查找表建立后，在后来的查找过程中仍会改变查找表的内容。它所对应(duìyìng)的查找算法属于动态查找技术。动态查找的例子——词汇统计问题。就是统计一篇文章中使用了多少词汇以及每个词汇的使用次数。解决方法是先建立一个空的查找表，以后每读到一个词就在查找表中查询一下，如果该词汇存在则将其使用次数加一，否则将新词插入到查找表中并设使用次数为一次。显然，这个查找表是不断扩张的。平均查找长度：为了确定数据元素在查找表中的位置，需要(xūyào)将给定值和表中的数据元素的关键字进行比较的次数的期望值。平均查找长度ASL的计算方法为：静态(jìngtài)查找技术1．顺序查找顺序查找的方法是从表的一端开始，逐一(zhúyī)比较给定的数据key和表中数据元素的关键字x的值，若两个数据一致则查找成功，同时给出该数据元素在表中的位置，否则查找失败。顺序查找算法C++语言(yǔyán)描述如下：intSqSearch(SSTable&L,KeyTypekey){intk=0;while(k<L.length&&L.data[k].x!=key)k++;if(k<L.length)returnk+1;//返回数据元素位置elsereturn0;}该算法若查找成功，则函数返回值为目标元素在表中的位置，否则返回0。这里元素位置从1开始算起。在上述算法中为了避免“出界”，需在循环中作k<L.length的判断，这使算法的执行时间几乎增加一倍。为提高效率，对查找表的结构改动如下：适当设置数组长度，将元素存于data[1]至data[length-1]中，在0号单元预存待查找数据key作为监视哨。改写(gǎixiě)查找过程为从后往前查找。因为循环查找过程至少会在0号单元停止，这样就不必在每一次循环中都判别是否数组出界。改进的顺序查找算法C++语言描述如下：intSqSearch(SSTable&L,KeyTypekey){L.data[0].x=key;//监视哨intk=L.length;while(L.data[k].x!=key)k=k-1;//从后往前(wǎnꞬqián)找returnk;//找不到时，k为0}该算法若查找成功，则函数返回值为目标元素在表中的位置，否则返回0。下面分析一下改进(gǎijìn)的顺序查找算法的时间性能。对于改进(gǎijìn)的顺序查找而言，找到第i个元素的比较次数Ci=n-i+1，所以在等概率查找的情况下，顺序表查找的平均查找长度为：2．折半查找(cházhǎo)(也称二分查找(cházhǎo))顺序查找(cházhǎo)表的查找(cházhǎo)算法简单，但平均查找(cházhǎo)长度较大。如果顺序查找(cházhǎo)表的元素按照关键字的值有序存放，那么可利用高效的折半查找(cházhǎo)来完成查询。假定元素按关键字的值升序排列，折半查找(cházhǎo)的思路是将给定的数据与有序表中间位置的元素做比较，若两者相等则查找(cházhǎo)成功；若前者小于后者则在中间位置左边的元素中继续查找(cházhǎo)；若前者大于后者则在中间位置右边的元素中继续查找(cházhǎo)。不断重复这一过程直到查找(cházhǎo)成功，或者直到查找(cházhǎo)区间缩小为一个元素时却仍未找到目标，则查找(cházhǎo)失败。折半查找算法(suànfǎ)的步骤描述如下：①设置查找区间初值，设下界low=0，设上界high=length-1。②若low≤high则计算中间位置mid=(low+high)/2。③若key<data[mid]，则设high=mid-1并继续执行步骤②；若key>data[mid]，则设low=mid+1并继续执行步骤②；若key=data[mid]则查找成功，返回目标元素位置mid+1（位置从1计数）。④若当low=high时，key!=data[mid]则查找失败，返回0。折半查找算法的C++语言描述如下：intBinSearch(SSTable&L,KeyTypekey){intlow,high,mid;low=0;high=L.length-1;//设置查找区间初值while(low<=high){mid=(low+high)/2;if(key==L.data[mid].x)returnmid+1;//查找成功elseif(key<L.data[mid].x)hi