6-2線性表的查找技術(shù)v第六章查找技術(shù)線性表查找結(jié)構(gòu)的類定義學什么？順序查找折半查找類定義constintMaxSize=100;classLineSearch{public:LineSearch(inta[],intn);//構(gòu)造函數(shù)~LineSearch(){}//析構(gòu)函數(shù)為空intSeqSearch(intk);//順序查找intBinSearch(intk);//折半非遞歸查找intBinSearchRecursion(intlow,inthigh,intk);//折半遞歸查找private:intdata[MaxSize];//查找集合為整型intlength;//查找集合的元素個數(shù)};LineSearch::LineSearch(inta[],intn){for(inti=0;i<n;i++)data[i]=a[i];length=n;}不失一般性，假定待查找集合的記錄為int型6-2-2順序查找v第六章查找技術(shù)基本思想順序查找（線性查找）：從線性表的一端向另一端逐個將記錄與給定值進行比較，若相等，則查找成功，給出該記錄在表中的位置；若整個表檢測完仍未找到與給定值相等的記錄，則查找失敗，給出失敗信息i10152461235409855012345678例1查找35，查找25intLineSearch::SeqSearch(intk){inti=0;

while(i<length&&data[i]!=k)i++;if(i<length)returni+1;elsereturn0;}改進的順序查找順序查找的改進：設(shè)置“哨兵”，就是待查值，放在查找方向的盡頭處，免去了每一次比較后都要判斷查找位置是否越界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）對表中記錄的有序性也沒有要求，無論記錄是否按關(guān)鍵碼有序均可順序查找的優(yōu)點：算法簡單而且使用面廣6-2-3折半查找v第六章查找技術(shù)基本思想折半查找（對半查找、二分查找）：在有序表（假設(shè)為遞增）中，取中間記錄作為比較對象：（1）若給定值與中間記錄相等，則查找成功；（2）若給定值小于中間記錄，則在有序表的左半?yún)^(qū)繼續(xù)查找；（3）若給定值大于中間記錄，則在有序表的右半?yún)^(qū)繼續(xù)查找。不斷重復(fù)上述過程，直到查找成功，或查找區(qū)域無記錄，查找失敗

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

71418212329313538012345678lowhigh例3

對于線性表(7,14,18,21,23,29,31,35,38)，元素18的查找過程：查找區(qū)間[0,8]midhigh查找區(qū)間[0,3]midlow查找區(qū)間[2,3]mid查找成功運行實例lowhigh查找區(qū)間[0,8]midhigh查找區(qū)間[0,3]midlow查找區(qū)間[2,3]mid查找區(qū)間[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;/*初始查找區(qū)間是[0,n-1]*/while(low<=high)/*當區(qū)間存在時*/{}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時，判定樹的根結(jié)點是有序表中序號為mid=(low+high)/2的記錄，根結(jié)點的左子樹是與有序表r[low]~r[mid-1]相對應(yīng)的判定樹，根結(jié)點的右子樹是與有序表r[mid+1]~r[high]相對應(yīng)的判定樹。設(shè)查找區(qū)間是[low,high]，判定樹的構(gòu)造方法：Page02顯然，構(gòu)造過程是遞歸定義的例5

設(shè)結(jié)點個數(shù)（查找集合的記錄個數(shù)）為11，請畫出對應(yīng)的判定樹。3構(gòu)造6的左子樹，區(qū)間[1,5]查找區(qū)間[1,11]，中間記錄的序號是6645構(gòu)造3的左子樹，區(qū)間[1,2]12構(gòu)造3的右子樹區(qū)間[4,5]判定樹3611845129構(gòu)造6的右子樹，區(qū)間[7,11]7構(gòu)造9的左子樹區(qū)間[7,8]10構(gòu)造9的右子樹區(qū)間[10,11]例5

設(shè)結(jié)點個數(shù)（查找集合的記錄個數(shù)）為11，請畫出對應(yīng)的判定樹。判定樹折半查找性能分析3691011784512查找記錄的過程是從根結(jié)點到該記錄結(jié)點的路徑，和給定值的比較次數(shù)等于該記錄結(jié)點在樹中的層數(shù)。查找第4個元素比較多少次？查找長度是4的元素有多少個？查找成功情況下，與判定樹的深度有關(guān)，判定樹的深度是多少呢？判定樹深度為時間復(fù)雜度為O(log2n)比較次數(shù)至多為33~4~11~22~34~510~1111~9~108~97~85~66~7691011784512如何確定查找失敗呢？例如查找的元素比第3個元素大比第4個元素?。坎檎也怀?/p>