基本算法查找-完整版PPT

1、查找定義：給定一個(gè)值K，在含有n個(gè)結(jié)點(diǎn)的表中找出關(guān)鍵字等于給定值K的結(jié)點(diǎn)。若找到，則查找成功，返回該結(jié)點(diǎn)的信息或該結(jié)點(diǎn)在表中的位置；否則查找失敗，返回相關(guān)的提示信息。分為：順序查找、二分查找基本算法-查找2022/9/12是一種最簡(jiǎn)單的查找方法基本思想：從表的一端開始，順序掃描線性表，依次將掃描到的結(jié)點(diǎn)關(guān)鍵字和給定值K相比較，若相等則查找成功；若掃描結(jié)束后，仍未找到則查找失敗。順序查找2022/9/12順序查找的算法：VAR K:ktype; R:array 1.n of ktype;t = false; for i:=1 to n do if Ri=k then begin t:=true;

2、 break; end; if t then writeln( i ) else writeln(No answer!);順序查找2022/9/12算法分析：平均查找長(zhǎng)度ASL ASL = (n+2+1)/n = (n+1)/2 成功 ASL = n 不成功優(yōu)點(diǎn)：適合線性表、鏈?zhǔn)奖砣秉c(diǎn)：效率低，當(dāng)n較大時(shí)，不宜采用順序查找順序查找2022/9/12是一種效率較高的查找方法要求：線性表是有序表基本思想：（設(shè)Rlow.high當(dāng)前查找區(qū)間）確定中間位置mid=(low+high)/2將Rmid與給定值K比較，若相等，則查找成功返回此位置；否則須確定新的查找區(qū)間，繼續(xù)用二分查找。若RmidK，則新的

3、查找區(qū)間是左子表R1.mid-1若RmidK，則新的查找區(qū)間是右子表Rmid+1.n二分查找（折半查找）2022/9/12Procedure binsearch ( VAR R:array1.n of ktype; K:ktype );VAR low,high,mid :integer;BEGIN low:=1; high:=n; while lowK then high:=mid-1 else low:=mid+1; end; writeln(No answer!); END;二分查找算法：2022/9/12算法分析優(yōu)點(diǎn)：效率高缺點(diǎn)：只適合線性表，鏈表上無法實(shí)現(xiàn)二分查找有序表二分查找2022/9/121、對(duì)18個(gè)元素的有序表作二分查找，則查找A3的比較序列的下標(biāo)為（ ） A、1-2-3 B、9-5-2-3 C、9-5-3 D、9-4-2-32、在順序表（2，5，7，10，14，15，18，23，35，41，52）中，用二分查找12，所需的關(guān)鍵字比較的次數(shù)為（ ） A、2 B、3 C、4 D、5練習(xí)2022/9/12DC3、利用逐點(diǎn)插入法建立序列50，72，43，85，75，20，35，45，65，30對(duì)應(yīng)的二叉