大學(xué)計(jì)算機(jī)基礎(chǔ) 課件 10.4.1順序查找

大學(xué)計(jì)算機(jī)基礎(chǔ)——基于計(jì)算思維（Windows10+Office2016）第10章算法思維與運(yùn)用10.4.1順序查找10.4查找算法查找算法在手機(jī)中查找聯(lián)系人查找是從較大的數(shù)據(jù)集中找出或定位某個(gè)給定值（鍵值）的過(guò)程在圖書(shū)館中查找圖書(shū)問(wèn)題4順序查找數(shù)據(jù)文件“data1.txt”中，有若干英語(yǔ)單詞（每行一個(gè)），現(xiàn)從鍵盤(pán)輸入一個(gè)單詞，請(qǐng)?jiān)谖募胁檎以撛~，若找到則給出其位置（第幾行），若沒(méi)找到，提示“nofound”。1．問(wèn)題分析由于數(shù)據(jù)集是存儲(chǔ)在文本文件中的，所以首先要按順序讀出這些數(shù)據(jù)存放到某數(shù)組中，然后在數(shù)組中查找。但這些數(shù)據(jù)是無(wú)序的，所以只能從數(shù)組第1個(gè)元素（或最后1個(gè)元素）開(kāi)始，按正序（或逆序）逐個(gè)掃描每個(gè)元素是否和鍵值相等，若相等則數(shù)組下標(biāo)即為其位置，若掃描結(jié)束都不相等，則表明沒(méi)有所查的數(shù)據(jù)（稱為查找失?。?，所以稱這種查找算法為順序查找（sequentialsearch）。123456鍵值正序逆序順序查找問(wèn)題4順序查找2．算法實(shí)現(xiàn)（1）設(shè)計(jì)main子圖粗框圖在main中應(yīng)完成的功能是：①調(diào)用input子程序讀文件到數(shù)組a中。②輸入鍵值存入key中。③調(diào)用search子程序在數(shù)組a中查找key。④調(diào)用output子程序輸出查找結(jié)果。①②③④問(wèn)題4順序查找2．算法實(shí)現(xiàn)（2）設(shè)計(jì)讀文件子程序input該子程序的目的就是將文本文件中的數(shù)據(jù)讀出到數(shù)組a中，所以a應(yīng)作為其輸出參數(shù)。a數(shù)組的大小n也應(yīng)作為輸出參數(shù)返回，以便控制查找范圍，本題中n是動(dòng)態(tài)的，由文件長(zhǎng)度決定。順序查找讀文件子程序input問(wèn)題4順序查找2．算法實(shí)現(xiàn)（3）設(shè)計(jì)順序查找子程序searchsearch的功能是從a數(shù)組的第1個(gè)元素開(kāi)始到最后第n個(gè)元素，逐個(gè)掃描并和鍵值key比較，并返回一個(gè)值表示找到還是未找到，找到了還要返回所在位置。1234...nkeysearch返回一個(gè)值找到未找到所在位置問(wèn)題4順序查找2．算法實(shí)現(xiàn)（3）設(shè)計(jì)順序查找子程序search注意在search中不做最后的輸出處理，而是在output子程序中輸出結(jié)果，所以輸入?yún)?shù)有a、n、key，再增加2個(gè)輸出參數(shù)，一個(gè)輸出參數(shù)flag，目的是用來(lái)區(qū)分不同種狀態(tài)。例如flag=0表示沒(méi)找到，flag=1表示找到，通常稱flag為狀態(tài)變量，另一個(gè)輸出參數(shù)為找到時(shí)的位置wz。問(wèn)題4順序查找2．算法實(shí)現(xiàn)（3）設(shè)計(jì)順序查找子程序search在search中，查找前可以分別賦給狀態(tài)變量和找到的位置一個(gè)初值（flag=0，wz=0），然后構(gòu)造一個(gè)循環(huán)結(jié)構(gòu)（設(shè)循環(huán)變量為i，初始值i=1，循環(huán)結(jié)束條件是i>n），在循環(huán)體內(nèi)判斷a[i]=key是否成立，若成立則狀態(tài)變量發(fā)生改變（flag=1），同時(shí)保存當(dāng)前位置wz=i，但循環(huán)不會(huì)中途結(jié)束，還會(huì)繼續(xù)，所以可以在循環(huán)結(jié)束條件中再增加一個(gè)條件，或者找到了（即flag=1），也結(jié)束循環(huán)；而若a[i]=key不成立，則繼續(xù)循環(huán)判斷，此時(shí)狀態(tài)變量一直不變化（flag=0）。所以循環(huán)結(jié)束后，通過(guò)flag返回的值就可判斷找到還是沒(méi)找到。順序查找子程序search問(wèn)題4順序查找2．算法實(shí)現(xiàn)（4）設(shè)計(jì)輸出子程序output根據(jù)search子程序查找的結(jié)果分別輸出：若找到了（flag=1），則輸出其位置wz，若沒(méi)找到（flag=0），則顯示輸出“nofound”，所以其只要2個(gè)輸入?yún)?shù)flag和wz。順序查找輸出子程序output問(wèn)題4順序查找2．算法實(shí)現(xiàn)（5）完善main子圖當(dāng)所有子程序設(shè)計(jì)好后，