驗(yàn)證試驗(yàn)-折半查找

1、PagePage of8驗(yàn)證實(shí)驗(yàn)一折半查找一、折半查找實(shí)驗(yàn)?zāi)康膶o定的有序數(shù)組（假設(shè)長度為），查找數(shù)組中與給定值相等的元素。二、折半查找實(shí)驗(yàn)過程1、算法思想將數(shù)列按有序化排列（升序），查找過程中采用跳躍式方式查找，即先以有序數(shù)列的中點(diǎn)位置為比較對象，如果要找的元素值小于該中點(diǎn)元素，則將待查序列縮小為前半部分，否則為后半部分。通過一次比較，將查找區(qū)間縮小一半。2、變量:循環(huán)變量J查找次數(shù)計(jì)數(shù)器e需查找的值:剛開始為第一個(gè)值所對應(yīng)的下標(biāo)：剛開始為最后一個(gè)值所對應(yīng)的下標(biāo)i第一個(gè)與最后一個(gè)值所對應(yīng)下標(biāo)和的一半r一維數(shù)組用來存放個(gè)數(shù)據(jù)3、步驟讀取一組個(gè)已升序排列的數(shù)據(jù)。取出個(gè)數(shù)最中間下標(biāo)的數(shù)與關(guān)鍵字進(jìn)行

2、比較，進(jìn)行查找若關(guān)鍵字等于這個(gè)數(shù)的話，則查找成功若關(guān)鍵字小于這個(gè)數(shù)的話，則范圍縮小為表的前半部分若關(guān)鍵字大于這個(gè)數(shù)的話，則范圍縮小為表的后半部分重復(fù)執(zhí)行）過程，直到為止。輸出各次查詢值，總查詢次數(shù)，驗(yàn)證折半算法、折半查找程序代碼對給定的有序數(shù)組（假設(shè)長度為），查找數(shù)組中與給定值相等的元素。定義常量為數(shù)組長度折半查找函數(shù)計(jì)數(shù)查找次次取中間位第次查找顯示每次查找低中高位，查找次數(shù)查到數(shù)據(jù)，跳出循環(huán)查找的大于中位值，查后半部查找的小于中位值，查前半部查到數(shù)據(jù)經(jīng)過總共次查找，找到該數(shù)字，該數(shù)字位于數(shù)組第位顯示查到的數(shù)據(jù)的值，下標(biāo)值，總查找次數(shù)else沒有找到顯示沒有找到折半查找驗(yàn)證程序，設(shè)定被查數(shù)據(jù)有

3、位，設(shè)定為:輸入個(gè)排好序的數(shù)據(jù)請輸入要查詢的數(shù)字（一，輸入小于等于零的數(shù)字退出驗(yàn)證程序）:過大;輸入調(diào)用折半查找函數(shù)請輸入要查詢的數(shù)字（一，輸入小于等于零的數(shù)字退出驗(yàn)證程序）:過大;輸入、折半查找運(yùn)行結(jié)果輸入一個(gè)數(shù)值為1至1個(gè)的有序一維數(shù)據(jù)，查詢2，7，8的結(jié)果的截屏。0、C:IBDOSsyste32c*d.eze半查找監(jiān)證程序，設(shè)定被查數(shù)據(jù)有15位，設(shè)定為：23456789101112131415low=Qhigh=14mid=?low=0high=6low=Qhigh=14mid=?low=0high=6mid=3low=0high=2mid=i福空過總共3次查找，找到該數(shù)字，該數(shù)字位于數(shù)

4、組第2位,輸入要查詢的數(shù)字Q-15,輸入小于等于零的數(shù)字退出驗(yàn)證程序）：?low=0low=0Jiigh=Hmid=?low=0high=6nid=3low=4high=6mid=Slow=6Jiigh=6mid=6至過總共4次查找，找到該數(shù)字，該數(shù)字位于數(shù)組第7位,請輸入要查詢的數(shù)字（1-15,輸入小于等于零的數(shù)字退出驗(yàn)證程序）：8第1次查找low=0high=14nid=?經(jīng)過總共1次查找，找到該數(shù)字，該數(shù)字位于數(shù)組第8位，輸入要查詢的數(shù)字C1-15,輸入小于等于零的數(shù)字退出驗(yàn)證程產(chǎn)）：7、折半查找時(shí)間性能折半算法的時(shí)間復(fù)雜度（）Wg即每經(jīng)過一次比較查找范圍就縮小一半。經(jīng)次計(jì)較可以完成查找

5、過程。四、折半查找小結(jié)折半查找是一種高效的查找方法。它可以明顯減少比較次數(shù)，提高查找效率，而且程序?qū)崿F(xiàn)也較為簡單。但是，折半查找的先決條件是查找表中的數(shù)據(jù)元素必須有序，而對所有數(shù)據(jù)元素按大小排序是非常費(fèi)時(shí)的操作，因而，還需撐握更高效的排序與查詢方法。協(xié)同作業(yè)試驗(yàn)四直方圖0年811月一、實(shí)驗(yàn)要求直方圖1.關(guān)鍵碼的數(shù)據(jù)類型是整型，且用數(shù)組存儲(chǔ)；2.求出每個(gè)關(guān)鍵碼在數(shù)組中出現(xiàn)的次數(shù)；3.輸出直方圖。二、實(shí)驗(yàn)流程直方圖三、算法思想直方圖1.建立一個(gè)與關(guān)鍵碼個(gè)數(shù)相同的數(shù)組，數(shù)組元素為一個(gè)結(jié)構(gòu)體，包含關(guān)鍵碼及頻率累加計(jì)數(shù)器。利用數(shù)組下標(biāo)與關(guān)鍵碼的對應(yīng)關(guān)系（本例中，數(shù)組下標(biāo)對應(yīng)關(guān)鍵碼減1），把輸入的需統(tǒng)計(jì)關(guān)

6、鍵碼對應(yīng)到相應(yīng)的數(shù)組元素，并對該元素中的頻率累加器進(jìn)行計(jì)數(shù)，統(tǒng)計(jì)其出現(xiàn)頻率。2.使用冒泡排序法，對數(shù)組以頻率數(shù)為序進(jìn)行降序排列，輸出整個(gè)數(shù)組內(nèi)容，使用此算法能非常簡潔的表示直方圖。四、算法說明直方圖說明：使用結(jié)構(gòu)體，是為了確保排序時(shí)關(guān)鍵碼與頻率之間的對應(yīng)關(guān)系，可以以少量空量換取較簡潔的程序設(shè)計(jì)與時(shí)間性能。五、算法設(shè)計(jì)概要直方圖自定義結(jié)構(gòu)，用于存放關(guān)鍵碼及關(guān)鍵碼出現(xiàn)的次數(shù)關(guān)鍵碼關(guān)鍵碼出現(xiàn)的次數(shù)直方圖結(jié)構(gòu)數(shù)組臨時(shí)結(jié)構(gòu)體用于排序交換的臨時(shí)變量循環(huán)變量循環(huán)變量關(guān)鍵碼，對應(yīng)直方圖結(jié)構(gòu)數(shù)組下標(biāo)六、步驟1）初始化直方圖結(jié)構(gòu)，定義每個(gè)關(guān)鍵碼，初始化關(guān)鍵碼頻率累加計(jì)數(shù)器為02）循環(huán)接受關(guān)鍵碼，并且根據(jù)輸入的關(guān)鍵

7、碼找到相對應(yīng)的元素，對關(guān)鍵碼頻率累加計(jì)數(shù)器累加計(jì)數(shù)3）對直方圖中進(jìn)行排序,排序規(guī)則根據(jù)關(guān)鍵碼出現(xiàn)的頻率降序4）輸出直方圖七、時(shí)間性能直方圖本程序中，使用了冒泡算法對數(shù)組進(jìn)行了排序，這也是本程序中最大的時(shí)間復(fù)雜度，所以本程序與冒泡排序算法的時(shí)間復(fù)雜度一致為。八、運(yùn)行結(jié)果直方圖九、直方圖一一程序代碼直方圖輸1入0次數(shù)10次統(tǒng)5計(jì)數(shù)字1-存放預(yù)定數(shù)據(jù)如果僅用數(shù)組，無法解決排序后，被統(tǒng)計(jì)數(shù)與頻率的對應(yīng)關(guān)系存放出現(xiàn)次數(shù)初始化請輸入數(shù)據(jù)，測試數(shù)據(jù)范圍控制在之間:/如果輸入有誤，則繼續(xù)循環(huán)，直到輸入正確后，累加計(jì)數(shù)器，進(jìn)行下個(gè)數(shù)據(jù)的輸入if(key5)輸入數(shù)據(jù)有誤，請重新輸入冒泡排序法對數(shù)組進(jìn)行排序關(guān)鍵碼頻率十、小結(jié)直方圖本實(shí)驗(yàn)，我們小組采用了一維結(jié)構(gòu)數(shù)組，比較好的解決了關(guān)鍵碼與頻率在排序后，無法對應(yīng)的問題。如果采用一維數(shù)組，關(guān)鍵碼由數(shù)組下標(biāo)承擔(dān)，數(shù)組元素表示頻率，這樣，排完序后，關(guān)鍵碼與頻率完全對不上號，頻率