數(shù)據(jù)結(jié)構(gòu) 課件 11-1靜態(tài)查找

數(shù)據(jù)結(jié)構(gòu)計算機領(lǐng)域本科教育教學改革試點工作計劃（“101計劃”）研究成果10111.1靜態(tài)查找第11章

查找11.1靜態(tài)查找3僅作查詢和檢索操作的查找表。靜態(tài)查找表“查詢”結(jié)果“不在查找表中”

數(shù)據(jù)元素插入到查找表中；“查詢”結(jié)果為“在查找表中”的數(shù)據(jù)元素

刪除。動態(tài)查找表查找表分類11.1靜態(tài)查找關(guān)鍵字：是數(shù)據(jù)元素中某個數(shù)據(jù)項的值，用以標識一個數(shù)據(jù)元素。查找過程中，往往是依據(jù)數(shù)據(jù)元素的某個數(shù)據(jù)項進行查找，這個數(shù)據(jù)項通常是數(shù)據(jù)的關(guān)鍵字。若關(guān)鍵字能標識唯一的一個數(shù)據(jù)元素，則稱謂主關(guān)鍵字。若關(guān)鍵字能標識若干個數(shù)據(jù)元素，則稱謂次關(guān)鍵字。張三2016010002男成都1.7511.1靜態(tài)查找平均查找長度ASL

Pi——查找第i個元素的概率Ci——查找第i個元素需要的比較次數(shù)ASL=P1C1+P2C2+...+PnCn11.1.1順序查找11.1.2折半查找11.1.3索引查找11.1.4作業(yè)11.1靜態(tài)查找5271394111.1.1順序查找11.1.1順序查找從表中指定位置（一般為最后一個，第0個位置設(shè)為崗哨）的記錄開始，沿某個方向?qū)⒂涗浀年P(guān)鍵字與給定值相比較，若某個記錄的關(guān)鍵字和給定值相等，則查找成功；反之，若找完整個順序表，都沒有與給定關(guān)鍵字值相等的記錄，則此順序表中沒有滿足查找條件的記錄，查找失敗。順序查找基本思想11.1.1順序查找RRi60ikey=64key=6064iiiiiiiiiii11.1.1順序查找空間復雜度：時間復雜度：查找算法的基本運算是給定值與順序表中記錄關(guān)鍵字值的比較。

O(1)最好情況：最壞情況：平均情況：O(1)O(n)O(n)性能分析11.1.1順序查找平均查找長度（ASL）：給定值與關(guān)鍵字比較次數(shù)的期望值。對于具有n個記錄的順序表，查找成功時的平均查找長度為：Pi——查找第i個記錄的概率Ci——找到第i個記錄數(shù)據(jù)需要比較的次數(shù)，對于順序表，Ci=n-i+1順序表上順序查找的平均查找長度11.1.1順序查找等概率情況不等概率--每個元素的查找概率已知--每個元素的查找概率未知11.1.2折半查找有序表：如果順序表中的記錄按關(guān)鍵字值有序，即：R[i].key≤R[i+1].key（或R[i].key≥R[i+1].key），i=1,2,…,n-1，則稱順序表為有序表。1371012124有序表1371312124無序表11.1.2

折半查找11.1.2折半查找將待查關(guān)鍵字與有序表中間位置的記錄進行比較，若相等，查找成功，若小于，則只可能在有序表的前半部分，若大于則只可能在有序表的后半部分，因此，經(jīng)過一次比較，就將查找范圍縮小一半，這樣一直進行下去直到找到所需記錄或記錄不在查找表中。

查找過程：11.1.2折半查找RR.length例如:key=64

的查找過程如下：highmidlowmidhighmidlow

指示查找區(qū)間的下界high

指示查找區(qū)間的上界mid

=(low+high)/2low11.1.3索引查找數(shù)據(jù)太多，雜亂無章，查找困難！11.1.3索引表查找11.1.3索引查找建立索引！索引使用方法11.1.3索引查找先分析數(shù)據(jù)規(guī)律，建立索引再根據(jù)索引進行快速定位在定位的地方進行細致搜索811.1.3索引查找第一個塊地址第一個塊最大關(guān)鍵字第二個塊地址第二個塊最大關(guān)鍵字…………第n個塊地址第n個塊最大關(guān)鍵字先分塊，塊間有序，就可以快速定位到塊490888970……11.1.3索引查找分塊：

第Rk

塊中所有關(guān)鍵字<Rk+1塊中所有關(guān)鍵字，（k=1,2,…,L-1）2)建立索引項：關(guān)鍵字項：記載該塊中最大關(guān)鍵字值；指針項：記載該塊第一個記錄在表中位置。3)所有索引項組成索引表。索引表的構(gòu)建11.1.3索引查找11.1.3索引查找索引表的查找

索引表的查找查找表的查找索引表有序11.1.3索引查找

例子：關(guān)鍵字224886

指針171319(n+1)22,12,13,8,9,20,33,42,44,38,24,48,60,58,74,49,86,53查找表建立索引表11.1.3索引查找

例子：關(guān)鍵字224886

指針171319(n+1)22,12,13,8,9,20,33,42,44,38,24,48,60,58,74,49,86,53查找關(guān)鍵字k=3811.1.3索引查找

例子：關(guān)鍵字224886

指針171319(n+1)22,12,13,8,9,20,33,42,44,38,24,48,60,58,74,49,86,53查找關(guān)鍵字k=5011.1.3索引查找

例子：關(guān)鍵字224886

指針171319(n+1)22,12,13,8,9,20,33,42,44,38,24,48,60,58,74,49,86,53思考：塊內(nèi)查找如何結(jié)束？11.1.4作業(yè)11.1.4作業(yè)數(shù)據(jù)結(jié)構(gòu)1、對有n個元素的有序順序表和無序順序表進行順序搜索,試就下列三種情況分別討論兩者在等搜索概率時的平均搜索長度是否相同?(1)搜索失敗;(2)搜索成功,且表中只有一個關(guān)鍵碼等于給定值k的對象;(3)搜索成功,且表中有若干個關(guān)鍵碼等于給定值k的對象,要求一次搜索找出所有對象。

2、假定對有序表：（3,4,5,7,24,30,42,