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