資源簡(jiǎn)介

(共12張PPT)
09 查找
程序設(shè)計(jì)基礎(chǔ)
順序查找
二分查找
學(xué)習(xí)目標(biāo)
查找是計(jì)算機(jī)中常見的操作之一
例如，查找文件，查找資料，字典中查找單詞等
查找練習(xí)
在一組數(shù)字中查找指定數(shù)字，找到則報(bào)告其位置。如果找不到，也要給出恰當(dāng)提示，說明查找的數(shù)字不存在。
問題
怎樣存儲(chǔ)待查找的數(shù)字？
查找
創(chuàng)建一個(gè)列表，依次加入數(shù)字 23 、32 、56 、12 、17、28六個(gè)數(shù)字，編寫程序在這組數(shù)字中查找用戶輸入的數(shù)字。
例如：用戶輸入查找12，返回其在列表中的位置。用戶輸入查找查找19，要能夠顯示不存在該數(shù)字
練習(xí)
第一個(gè)數(shù)字開始，依次查找第二個(gè)、第三個(gè)數(shù)字，直到找到要找的數(shù)字或查完所有數(shù)字為止。
順序遍歷查找，不要求數(shù)字是有順序的，但是查找效率比較低。一組數(shù)字中數(shù)字越多，所用的時(shí)間可能越長(zhǎng)。
順序查找 3-1
順序查找 3-2
代碼二：
增加“存在”變量作為查找目標(biāo)是否存在的標(biāo)志
開始假設(shè)不存在，將“存在”變量值設(shè)置為0
如果找到變量，將“存在”變量值設(shè)置為1
最后如果“存在”變量值仍為0，說明查找目標(biāo)在列表中不存在
順序查找 3-3
二分查找又稱折半查找，它是一種效率較高的查找方法，應(yīng)用二分查找要求：
1.必須采用順序存儲(chǔ)結(jié)構(gòu)
2.必須按關(guān)鍵字大小有序排列　　
優(yōu)點(diǎn)是比較次數(shù)少，查找速度快，平均性能好
缺點(diǎn)是要求待查表為有序表，且插入刪除困難。因此，折半查找方法適用于不經(jīng)常變動(dòng)而查找頻繁的有序列表 　　
二分查找 4-1
算法思想
首先，假設(shè)表中元素是按升序排列，將表中間位置記錄的關(guān)鍵字與查找關(guān)鍵字比較，如果兩者相等，則查找成功；
否則利用中間位置記錄將表分成前、后兩個(gè)子表，如果中間位置記錄的關(guān)鍵字大于查找關(guān)鍵字，則進(jìn)一步查找前一子表，否則進(jìn)一步查找后一子表。
重復(fù)以上過程，直到找到滿足條件的記錄，使查找成功，或直到子表不存在為止，此時(shí)查找不成功
二分查找 4-2
first 存放子表的起始元素位置
last 存放子表的結(jié)束元素位置
middle 存放子表的中間元素位置
Target 存放待查找的目標(biāo)
二分查找 4-3
二分查找 4-4
遍歷查找
不要求數(shù)據(jù)有序
效率低
二分查找
要求數(shù)據(jù)有序
效率高
上網(wǎng)查詢：還有哪些查找算法？各適用于什么情況？
總結(jié)

展開更多......

收起↑