6-2线性表的查找技术

6-2线性表的查找技术v第六章查找技术线性表查找结构的类定义学什么？顺序查找折半查找类定义constintMaxSize=100;classLineSearch{public:LineSearch(inta[],intn);//构造函数~LineSearch(){}//析构函数为空intSeqSearch(intk);//顺序查找intBinSearch(intk);//折半非递归查找intBinSearchRecursion(intlow,inthigh,intk);//折半递归查找private:intdata[MaxSize];//查找集合为整型intlength;//查找集合的元素个数};LineSearch::LineSearch(inta[],intn){for(inti=0;i<n;i++)data[i]=a[i];length=n;}不失一般性，假定待查找集合的记录为int型6-2-2顺序查找v第六章查找技术基本思想顺序查找（线性查找）：从线性表的一端向另一端逐个将记录与给定值进行比较，若相等，则查找成功，给出该记录在表中的位置；若整个表检测完仍未找到与给定值相等的记录，则查找失败，给出失败信息i10152461235409855012345678例1查找35，查找25intLineSearch::SeqSearch(intk){inti=0;

while(i<length&&data[i]!=k)i++;if(i<length)returni+1;elsereturn0;}改进的顺序查找顺序查找的改进：设置“哨兵”，就是待查值，放在查找方向的尽头处，免去了每一次比较后都要判断查找位置是否越界intLineSearch::SeqSearch(intk){inti=0;

while(i<length&&data[i]!=k)i++;if(i<length)returni+1;elsereturn0;}例2查找35，查找25intLineSearch::SeqSearch(intk){inti=length;

data[length]=k;while(data[i]!=k)i++;if(i<length)returni+1;elsereturn0;}查找方向10152461235409855k0123456789顺序查找的性能查找成功：查找不成功：特别是当待查找集合中元素较多时，不推荐使用顺序查找顺序查找的缺点：查找效率较低（1）对表中记录的存储没有任何要求，顺序存储和链接存储均可（2）对表中记录的有序性也没有要求，无论记录是否按关键码有序均可顺序查找的优点：算法简单而且使用面广6-2-3折半查找v第六章查找技术基本思想折半查找（对半查找、二分查找）：在有序表（假设为递增）中，取中间记录作为比较对象：（1）若给定值与中间记录相等，则查找成功；（2）若给定值小于中间记录，则在有序表的左半区继续查找；（3）若给定值大于中间记录，则在有序表的右半区继续查找。不断重复上述过程，直到查找成功，或查找区域无记录，查找失败

[r1………rmid-1]rmid[rmid+1………rn]k（mid=(1+n)/2）如果k<rmid查找左半区如果k>rmid查找右半区

71418212329313538012345678lowhigh例3

对于线性表(7,14,18,21,23,29,31,35,38)，元素18的查找过程：查找区间[0,8]midhigh查找区间[0,3]midlow查找区间[2,3]mid查找成功运行实例lowhigh查找区间[0,8]midhigh查找区间[0,3]midlow查找区间[2,3]mid查找区间[2,1]highlow>high，查找失败

71418212329313538012345678运行实例例4

对于线性表(7,14,18,21,23,29,31,35,38)，元素15的查找过程：intLineSearch::BinSearch(intk){}非递归算法

return0;/*查找失败，返回0*/intmid,low=0,high=n-1;/*初始查找区间是[0,n-1]*/while(low<=high)/*当区间存在时*/{}mid=(low+high)/2;if(k<data[mid])high=mid-1;elseif(k>data[mid])low=mid+1;elsereturnmid+1;/*查找成功，返回元素序号*/递归算法lowhighmidintLineSearch::BinSearchRecursion(intlow,inthigh,intk){}if(k<r[mid])returnBinSearchRecursion(low,mid-1,k);elseif(k>r[mid])returnBinSearchRecursion(mid+1,high,k);elsereturnmid+1;/*查找成功，返回序号*/

71418212329313538012345678if(low>high)return0;/*递归的边界条件*/mid=(low+high)/2;判定树判定树（折半查找判定树）：描述折半查找判定过程的二叉树（1）当low＞high时，判定树为空；（2）当low≤high时，判定树的根结点是有序表中序号为mid=(low+high)/2的记录，根结点的左子树是与有序表r[low]~r[mid-1]相对应的判定树，根结点的右子树是与有序表r[mid+1]~r[high]相对应的判定树。设查找区间是[low,high]，判定树的构造方法：Page02显然，构造过程是递归定义的例5

设结点个数（查找集合的记录个数）为11，请画出对应的判定树。3构造6的左子树，区间[1,5]查找区间[1,11]，中间记录的序号是6645构造3的左子树，区间[1,2]12构造3的右子树区间[4,5]判定树3611845129构造6的右子树，区间[7,11]7构造9的左子树区间[7,8]10构造9的右子树区间[10,11]例5

设结点个数（查找集合的记录个数）为11，请画出对应的判定树。判定树折半查找性能分析3691011784512查找记录的过程是从根结点到该记录结点的路径，和给定值的比较次数等于该记录结点在树中的层数。查找第4个元素比较多少次？查找长度是4的元素有多少个？查找成功情况下，与判定树的深度有关，判定树的深度是多少呢？判定树深度为时间复杂度为O(log2n)比较次数至多为33~4~11~22~34~510~1111~9~108~97~85~66~7691011784512如何确定查找失败呢？例如查找的元素比第3个元素大比第4个元素小？查找不成