數(shù)據(jù)結(jié)構(gòu)實驗五查找與排序的實現(xiàn)

1、真誠為您提供優(yōu)質(zhì)參考資料，若有不當(dāng)之處，請指正。實 驗 報 告課程名稱 數(shù)據(jù)結(jié)構(gòu) 實驗名稱 查找與排序的實現(xiàn) 系別 專業(yè)班級 指導(dǎo)教師11 學(xué)號 姓名 實驗日期 實驗成績 一、實驗?zāi)康?1) 掌握交換排序算法（冒泡排序）的基本思想；(2) 掌握交換排序算法（冒泡排序）的實現(xiàn)方法；(3) 掌握折半查找算法的基本思想；(4) 掌握折半查找算法的實現(xiàn)方法；二、實驗內(nèi)容1. 對同一組數(shù)據(jù)分別進(jìn)行冒泡排序，輸出排序結(jié)果。要求：1) 設(shè)計三種輸入數(shù)據(jù)序列：正序、反序、無序2) 修改程序：a) 將序列采用手工輸入的方式輸入b) 增加記錄比較次數(shù)、移動次數(shù)的變量并輸出其值，分析三種序列狀態(tài)的算法時間復(fù)雜性2.

2、 對給定的有序查找集合，通過折半查找與給定值k相等的元素。3. 在冒泡算法中若設(shè)置一個變量lastexchangeindex來標(biāo)記每趟排序時經(jīng)過交換的最后位置，算法如何改進(jìn)？三、設(shè)計與編碼1.本實驗用到的理論知識2.算法設(shè)計3.編碼package sort_search;import java.util.scanner;public class sort_search /冒泡排序算法public void bubblesort(int r) int temp;int count=0,move=0;boolean flag=true;for(int i=1;i<r.length&&

3、amp;flag;i+)flag=false;count+;for(int j=0;j<r.length-i;j+) if(rj>rj+1)temp=rj;rj=rj+1;rj+1=temp;move+;flag=true;system.out.println("排序后的數(shù)組為：");for(int i=0;i<r.length;i+)system.out.print(ri+" ");system.out.println();system.out.println("比較次數(shù)為："+count);system.out.

4、println("移動次數(shù)為："+move);public static int binarysearch(int r,int key) /折半查找算法int low=0,high=r.length-1;while(low<=high)int mid=(low+high)/2;if(rmid=key)return mid;else if(rmid>key)high=mid-1;elselow=mid+1;return -1; /測試public static void main(string args) sort_search ss=new sort_searc

5、h();int t=new int13;system.out.println("依次輸入13個整數(shù)為：");scanner sc=new scanner(system.in);for(int i=0;i<t.length;i+)ti=sc.nextint();system.out.println("排序前的數(shù)組為： ");for(int i=0;i<t.length;i+)system.out.print(ti+" ");system.out.println();ss.bubblesort(t); /查找while(tru

6、e)system.out.println("請輸入要查找的數(shù)： ");int k=sc.nextint();if(binarysearch(t,k)>0)system.out.println(k+" 在數(shù)組中的位置是第： "+ binarysearch(t,k);elsesystem.out.println(k+" 在數(shù)組中查找不到！"); 四、運行與調(diào)試1. 在調(diào)試程序的過程中遇到什么問題，是如何解決的？問題：在計算比較次數(shù)和移動次數(shù)時，計算數(shù)據(jù)明顯出錯。原因：在進(jìn)行移動和比較的過程中，沒有更新標(biāo)志，導(dǎo)致計數(shù)出錯。解決辦法：在

7、比較和移動的過程中，有進(jìn)行比較和移動的操作時，更新標(biāo)志。然后按標(biāo)志計數(shù)。2. 設(shè)計了哪些測試數(shù)據(jù)？預(yù)計結(jié)果是什么？說明： 測試了int類型數(shù)據(jù)： 241 17 23 45 37 4 31 43 11 89 33 101 177 預(yù)計排序后結(jié)果為：4 11 17 23 31 33 37 43 45 89 101 177 241 比較次數(shù)： 無序：8次 正序：1次 反序：12次 移動次數(shù)： 無序：30次 正序：0次 反序：78次 查找數(shù)33的位置為：5 查找數(shù)101的位置為：10 查找數(shù)100的結(jié)果為：查找不到3. 程序運行的結(jié)果如何 i.無序輸入：ii.正序輸入：iii.反序輸入： 五、總結(jié)與心得六、思考題已知奇偶轉(zhuǎn)換排序如下：第一趟對所有奇數(shù)的i，將ai和ai+1進(jìn)行比較，第二趟對所有偶數(shù)的i,將ai和ai