數(shù)據(jù)結構實驗五-查找與排序的實現(xiàn)

實驗報告課程名稱數(shù)據(jù)結構實驗名稱查找與排序得實現(xiàn)系別專業(yè)班級指導教師１1學號姓名實驗日期實驗成績一、實驗目得掌握交換排序算法（冒泡排序)得基本思想;掌握交換排序算法（冒泡排序)得實現(xiàn)方法；掌握折半查找算法得基本思想；掌握折半查找算法得實現(xiàn)方法;二、實驗內容對同一組數(shù)據(jù)分別進行冒泡排序，輸出排序結果。要求：設計三種輸入數(shù)據(jù)序列：正序、反序、無序修改程序:將序列采用手工輸入得方式輸入增加記錄比較次數(shù)、移動次數(shù)得變量并輸出其值,分析三種序列狀態(tài)得算法時間復雜性對給定得有序查找集合,通過折半查找與給定值k相等得元素。在冒泡算法中若設置一個變量lａstEｘchaｎｇｅIndex來標記每趟排序時經過交換得最后位置,算法如何改進？三、設計與編碼1、本實驗用到得理論知識2、算法設計３、編碼packａｇesoｒt_seaｒch；imｐoｒｔjavａ、utｉl、Sｃａnner；ｐuｂliｃｃlassＳoｒｔ_Sｅaｒch｛／/冒泡排序算法?ｐuｂｌｉcvoiｄBubblｅSoｒt（ｉntr[］){ ｉnttemp;? ｉｎｔcouｎt＝0，move=0；? ｂｏｏｌeanｆlaｇ=trｕｅ;? fｏｒ(intｉ＝1;i〈r、lｅnｇｔh＆＆flag；i++){?? ｆlaｇ=fａlse；?? cｏｕｎt++；? ｆor（inｔｊ=０;j<r、leｎgｔｈ－i;j＋＋）{ if(ｒ[ｊ］＞ｒ[j＋1]）{ ? teｍp=ｒ[j]；? ??ｒ［ｊ］=ｒ［j+1］; r［j+1］＝temp； ?? moｖe＋+； flａg＝true;? ? }???｝? ｝??Ｓystem、oｕt、priｎtｌｎ（＂排序后得數(shù)組為:”）;? for（iｎti=０;i〈r、length；ｉ++）{? ?Systｅｍ、oｕt、prinｔ（r［ｉ］＋"”);? ｝ Sysｔｅｍ、out、println（)；? System、out、printlｎ(＂比較次數(shù)為:"+cｏunt)；??Systeｍ、oｕt、prｉnｔｌn（"移動次數(shù)為:”＋ｍove); ｝?ｐublicｓtatiｃｉntＢinaｒySeaｒcｈ（iｎｔr[],intkey)｛//折半查找算法? iｎｔlow=０，hｉgh=ｒ、ｌeｎｇtｈ-1；? whｉｌe（ｌow＜=hｉgh）{? inｔmiｄ=（low+hｉgh）/2；? ?if（r［ｍｉd］==key)｛ ?ｒetuｒnmｉd； ??｝ ??elseif(r［mid］>ｋｅy)｛ high=miｄ—1；?? ｝?? elsｅ{ ???lｏw=mid＋１; ??｝ ?}??retｕrn－１；?}//測試 publｉcｓtaｔicvoidmain（Ｓtｒing[］ａrgs)｛? Ｓoｒｔ_Ｓearchsｓ=newSoｒt＿Searｃh(）； ｉｎtｔ［]=nｅwint［1３]；? Sｙsｔｅｍ、oｕt、prinｔln(”依次輸入１3個整數(shù)為："）；? Ｓcannerｓc＝newScanner（Sｙstem、in）； ?ｆor（ｉnti=0;ｉ〈t、length；i++）｛ ??t[i］=sｃ、nextＩnt()； ?}??Syｓtｅm、ｏuｔ、pｒｉnｔｌｎ("排序前得數(shù)組為："）;? for（iｎｔi=0；i＜t、length；ｉ+＋）｛? Sysｔem、ouｔ、print（t［ｉ］+"”）；? } ?Systｅm、ｏut、pｒintln(）；??ｓｓ、BubblｅSort(t）;//查找 ?ｗｈile（true）{??Sｙstｅm、oｕt、ｐｒinｔｌｎ（＂請輸入要查找得數(shù):”); ? ?intk=ｓc、nexｔInt（）; ?if（BｉnarySeａrch(t,k）>0） System、oｕt、println（k＋＂在數(shù)組中得位置就是第：＂+BｉnａrySeａrcｈ(t,k）)；??ｅｌse ??Sｙsｔeｍ、oｕｔ、prｉntｌn（k+”在數(shù)組中查找不到！"）；? }?}｝四、運行與調試在調試程序得過程中遇到什么問題,就是如何解決得?問題:在計算比較次數(shù)與移動次數(shù)時，計算數(shù)據(jù)明顯出錯。原因:在進行移動與比較得過程中，沒有更新標志，導致計數(shù)出錯。解決辦法：在比較與移動得過程中,有進行比較與移動得操作時，更新標志.然后按標志計數(shù)。設計了哪些測試數(shù)據(jù)?預計結果就是什么?說明:測試了ｉｎt類型數(shù)據(jù)：24117234５３７43１43１１89３310１177預計排序后結果為:４11172331333７４345８9101177241比較次數(shù)：=1\*GB３\*MＥRGEFORMＡT①無序：8次＝2\＊ＧＢ3\*MＥＲGＥFＯRＭAT②正序：1次=3\＊GB3\*MEＲＧＥＦORMAT③反序：12次移動次數(shù):=1\＊GＢ3\＊ＭERＧEＦORMAT①無序：３0次=2\＊ＧＢ3＼*MERGＥFORＭAT②正序:0次=3\*ＧB3＼＊ＭＥRGEFORMＡT③反序:78次查找數(shù)3３得位置為：5查找數(shù)１01得位置為：10查找數(shù)100得結果為：查找不到程序運行得結果如何=１＼*ROＭAN＼＊MERGEFOＲMATＩ、無序輸入:=2\＊ＲOＭAＮ\*MERGEFORＭATII、正序輸入:=3\＊ROMＡＮ\*MERGEFＯRMATＩII、反序輸入：五、總結與心得六、思考題已知奇偶轉換排序如下：第一趟對所有奇數(shù)得i，將a[i]與a［i＋１］進行比較