大學(xué)《數(shù)據(jù)結(jié)構(gòu)》第八章：查找-第二節(jié)-順序表的查找

第二節(jié)順序表的查找順序表是指線性表的順序存儲結(jié)構(gòu)，具體數(shù)據(jù)類型定義：typedefstruct{KeyTypekey；infoTypedata；｝NodeType；typedefNodeTypeSeqList[n+1]；//0號單元用作哨兵一、順序查找1、一般順序表的查找算法（1）算法描述intSeqSearch(SeqListR，KeyTypek，intn)｛//R[0]作為哨兵，用R[0].key==k作為循環(huán)下界的終結(jié)條件R[0].key=k；//設(shè)置哨兵i=n；//從后向前掃描while(R[i].key!=k)i--；returni；//返回其下標(biāo)，若找不到，返回0｝（2）算法分析①查找成功的情況：最好的情況比較1次，最壞的情況比較n次查找成功時的平均查找長度=（1+2+3+…+n）/n=②查找失敗時的查找長度=（n+1）③如果查找成功和不成功機會相等，順序查找的平均查找長度為（（n+1）/2+（n+1））/2=

（n+1）2、在遞增有序的順序表的查找算法（1）算法描述intSeqSearchl(SeqListR，KeyTypek，intn)//有序表的順序查找算法｛inti=n；//從后向前掃描，表按遞增排序while(R[i].key>k)i--；//循環(huán)結(jié)束時，要么R[i].key=k，要么R[i].key<kif(R[i].key==k)returni；//找到，返回其下標(biāo)return0；//沒找到，返回O｝（2）算法分析①查找成功的平均查找長度=②查找失敗的平均查找長度=③如果查找成功和不成功機會相等，該算法的平均查找長度為二、二分查找法（每年必考）對有序表可以用查找效率較高的二分查找方法來實現(xiàn)查找運算。1、二分查找法的思想二分查找的思想:首先將待查的k值和有序表R[1…n]的中間位置mid上的記錄的關(guān)鍵字進行比較，若相等，則查找成功，返回該記錄的下標(biāo)mid；否則，若R[mid].key>k，則k在左子表R[1…mid-1]中，接著再在左子表中進行二分查找即可；否則，若R[mid].key<k，則說明待查記錄在右子表R[mid+l…n]中，接著只要在右子表中進行二分查找即可。這樣，經(jīng)過一次關(guān)鍵字的比較，就可縮小一半的查找空間，如此進行下去，直到找到關(guān)鍵字為k的記錄或者當(dāng)前查找區(qū)間為空時(即查找失敗)為止。二分查找的過程是遞歸的。2、實例分析（例題?單選題）對有序表（13，25，36，42，48，56，64，69，78，85，92）用二分查找法查找42和80，所需的比較次數(shù)依次為（）。A．1次和2次B．2次和3次C．3次和2次D．3次和3次隱藏答案【答案】D【解析】按二分查找的基本思想給出查找42的過程如下查找k=42需要比較3次查找成功。按二分查找的基本思想給出查找80的過程如下查找k=80需要比較3次后low>high查找失敗。3、算法描述（1）二分查找遞歸算法intBinSearch(SeqListR，KeyTypek，intlow，inthigh){//在區(qū)間R[low...high]內(nèi)進行二分遞歸，查找關(guān)鍵字值等于k的記錄//1ow的初始值為1，high的初始值為nintmid；if(low<=high){mid=(low+high)／2；if(R[mid].key==k)returnmid；//查找成功，返回其下標(biāo)if(R[mid].key>k)returnBinSearch(R，k，low，mid-1)//在左子表中繼續(xù)查找elsereturnBinSearch(R，k，mid+1，high)//在右子表中繼續(xù)查找｝elsereturn0；｝（2）二分查找非遞歸算法intBinSearch(SeqLiStR，KeyTypek，intn)//初始化上下界{intlow=l，mid，high=n；while(low<=high){mid=(low+high)／2；if(R[mid].key==k)returnmid；//查找成功，返回其下標(biāo)if(R[mid].key>k)high=mid-1；//修改上界elselow=mid+1；//修改下界}return0；//查找失敗，返回0值}4、算法分析二分查找方法可以用一棵判定樹描述，查找任一元素的過程對應(yīng)該樹中從根結(jié)點到相應(yīng)結(jié)點的一條路徑。最短的查找長度為1，最長的查找長度為對應(yīng)判定樹的深度

，平均查找長度為

log2（n+1）-1≈log2（n+1）-1。二分查找方法效率高是有代價的，因為有序表是通過排序而得到的，而排序操作又是比較費時的。二分查找只適用于順序結(jié)構(gòu)上的有序表，對鏈?zhǔn)浇Y(jié)構(gòu)無法進行二分查找。（例題?算法題）對長度為20的有序表進行二分查找法，試畫出它的一棵判定樹，并求等概率情況下的平均查找長度。隱藏答案【解答】假設(shè)長度為20的有序序列為（a1，a2，…，a20），按二分查找法得到的判定樹如下圖所示。等概率情況下的平均查找長度為：（1+2×2+3×4+4×8+5×5）/20=74/20=3.7。5、應(yīng)用實例【例】試寫一算法，利用二分查找算法在有序表R中插入一個元素x，并保持表的有序性。voidBinInsert(SeqListR，KeyTypex，InfoTypey，intn){intlow=1，high=n，mid，inspace，i；intfind=0；//find是作為是否找到與x相等的關(guān)鍵字，先假設(shè)未發(fā)現(xiàn)while(low<=high&&!find){mid=(low+high)／2；if(x<R[mid].key)high=mid-1；elseif(x>R[mid].key)low=mid+1；elsefind=1；}if(find)inspace=mid；//找到關(guān)鍵字與x相等，mid為x的插入位置elseinspace=low//所指向的結(jié)點關(guān)鍵字正好大于x，此時low即為插入位置for(i=n；i>=inspace；i--)R[i+1]=R[i]；//后移結(jié)點，留出插入的空位R[inspace].key=x；//插入結(jié)點，x是該結(jié)點的關(guān)鍵字，y是其他數(shù)據(jù)R[inspace].data=y；}三、索引順序查找索引順序查找又稱分塊查找。它是一種性能介于順序查找和二分查找之間的查找方法。1、索引查找表的存儲結(jié)構(gòu)（1）"分塊有序"的線性表表R[1...n]均分為b塊，前b-1塊中結(jié)點個數(shù)為

，第b塊的結(jié)點數(shù)小于等于s；每一塊中的關(guān)鍵字不一定有序，但前一塊中的最大關(guān)鍵字必須小于后一塊中的最小關(guān)鍵字，即表是"分塊有序"的。（2）索引表抽取各塊中的最大關(guān)鍵字及其起始位置構(gòu)成一個索引表ID[l…b]，即：ID[i](1≤i≤b)中存放第i塊的最大關(guān)鍵字及該塊在表R中的起始位置。由于表R是分塊有序的，所以索引表是一個遞增有序表。【例】下圖就是滿足上述要求的存儲結(jié)構(gòu)，其中R只有18個結(jié)點，被分成3塊，每塊中有6個結(jié)點，第一塊中最大關(guān)鍵字21小于第二塊中最小關(guān)鍵字23，第二塊中最大關(guān)鍵字45小于第三塊中最小關(guān)鍵字48。2、索引查找的基本思想（1）首先查找索引表索引表是有序表，可采用二分查找或順序查找，以確定待查的結(jié)點在哪一塊。（2）然后在已確定的塊中進行順序查找由于塊內(nèi)無序，只能用順序查找。3、索引查找的平均查找長度（1）查找索引表采用二分查找時的平均查找長度ASLblk=log2（b+1）-1+（s+1）/2≈log2（n/s+1）+s/2（2）查找索引表采用順序查找時的平均查找長度ASLblk＝（b+1）/2＋（s+1）/2＝（b+s）/2+1＝（n/s+s）/2+1=（塊數(shù)+塊長）/2+1當(dāng)s取

（即s=b）時，ASLblk

達(dá)到最小值+1，即當(dāng)采用順序查找確定塊時，應(yīng)將各塊中的結(jié)點數(shù)選定為。四、三種查找方法比較1、順序查找優(yōu)點：算法簡單，對表的存儲結(jié)構(gòu)無任何要求。缺點：查找效率低，查找成功的平均查找長度為（n+1)／2，查找失敗的查找長度為（n+1）。2、二分查找優(yōu)點：二分查找的速度快，效率高，查找成功的平均查找長度約為log2(n+1)-l。缺點：要求表以順序存儲表示并且是按關(guān)鍵字有序，使用高效率的排序方法也要花費O(nlog2n)的時間。另外，當(dāng)對表結(jié)點進行插入或刪除時，需要移動大量的元素，所以二分查找適用于表不易變動且又經(jīng)常查找的情況。當(dāng)前講授3、分塊查找優(yōu)點：在表中插入或刪除一個記錄時，只要找到該記錄所屬的塊，就可以在該塊內(nèi)進行插入或刪除運算。因為塊內(nèi)記錄是無序的，所以插入或刪除比較容易，無需移動大量記錄。缺點：是需要增加一個輔助數(shù)組的存儲空間和將初始表塊排序的