快速排序與二分查找-實驗四.doc

電 子 科 技 大 學(xué)實 驗 報 告 課程名稱： 數(shù)據(jù)結(jié)構(gòu)與算法 學(xué)生姓名： 陳*浩 學(xué) 號： * 點名序號： * 指導(dǎo)教師： 錢* 實驗地點： 基礎(chǔ)實驗大樓A508 實驗時間： 2015.6.3 2014-2015-2學(xué)期 信息與軟件工程學(xué)院實 驗 報 告(四)學(xué)生姓名：陳*浩 學(xué) 號：* 導(dǎo)教師：錢*實驗地點：基礎(chǔ)實驗大樓A508 實驗時間：2015.6.3一、 實驗室名稱：軟件實驗室 二、 實驗項目名稱：數(shù)據(jù)結(jié)構(gòu)與算法快速排序與二分查找三、 實驗學(xué)時：4四、實驗原理： 快速排序的基本思想是：通過一躺排序?qū)⒁判虻臄?shù)據(jù)分割成獨立的兩部分，其中一部分的所有數(shù)據(jù)都比另外一不部分的所有數(shù)據(jù)都要小，然后再按次方法對這兩部分數(shù)據(jù)分別進行快速排序，整個排序過程可以遞歸進行，以此達到整個數(shù)據(jù)變成有序序列。 假設(shè)要排序的數(shù)組是A1AN，首先任意選取一個數(shù)據(jù)（通常選用第一個數(shù)據(jù)）作為關(guān)鍵數(shù)據(jù)，然后將所有比它的數(shù)都放到它前面，所有比它大的數(shù)都放到它后面，這個過程稱為一躺快速排序。一躺快速排序的算法是： 1）設(shè)置兩個變量I、J，排序開始的時候I：=1，J：=N 2）以第一個數(shù)組元素作為關(guān)鍵數(shù)據(jù)，賦值給X，即X：=A1； 3）從J開始向前搜索，即（J：=J-1），找到第一個小于X的值，兩者交換； 4）從I開始向后搜索，即（I：=I+1），找到第一個大于X的值，兩者交換； 5）重復(fù)第3、4步，直到I=J。 二分法查找（折半查找）的基本思想： （1）確定該區(qū)間的中點位置：mid=（low+high）/2min代表區(qū)間中間的結(jié)點的位置，low代表區(qū)間最左結(jié)點位置，high代表區(qū)間最右結(jié)點位置 （2）將待查a值與結(jié)點mid的關(guān)鍵字（下面用Rmid.key）比較，若相等，則查找成功，否則確定新的查找區(qū)間： A)如果Rmid.keya，則由表的有序性可知，Rmid.key右側(cè)的值都大于a，所以等于a的關(guān)鍵字如果存在，必然在Rmid.key左邊的表中,這時high=mid-1; B)如果Rmid.keya,則等于a的關(guān)鍵字如果存在，必然在Rmid.key右邊的表中。這時low=mid； C)如果Rmid.key=a，則查找成功。 （3）下一次查找針對新的查找區(qū)間，重復(fù)步驟（1）和（2） （4）在查找過程中，low逐步增加，high逐步減少，如果highlow，則查找失敗。五、實驗?zāi)康模罕緦嶒炌ㄟ^實現(xiàn)快速排序和折半查找算法，使學(xué)生理解如何實現(xiàn)快速查找和排序的基本算法思想。通過練習(xí)，加強對算法的理解，提高編程能力。六、實驗內(nèi)容： （1）實現(xiàn)數(shù)據(jù)序列的輸入; （2）實現(xiàn)快速排序算法,并對輸入的序列排序后輸出； （3）實現(xiàn)折半查找算法,并在步驟(2)排序后的序列上,進行任意地查找,并輸出查詢結(jié)果。七、實驗器材（設(shè)備、元器件）：PC機一臺，裝有C/C+語言集成開發(fā)環(huán)境。八、數(shù)據(jù)結(jié)構(gòu)及程序/* * *快速查找與二分排序 * * *陳家浩 * * *2015.6.6 * */#include#define MAX 100int DataMAX+1 = 0;int Quick_Part(int Data,int i,int j); /一趟排序int Quick_Sort(int Data,int s,int t); /遞歸排序int Quick_Find(int Data,int data,int n); /二分查找int main(void)int choose = -1; /選擇功能int i,k,data;int n; /數(shù)據(jù)序列長度while(1)printf(+-排序與查找-+n| 1:輸入數(shù)據(jù)序列 |n| 2:序列排序 |n| 3:查找信息 |n| 0:退出 |n+-+-+n 請選擇：);scanf(%d,&choose);switch(choose)case 1:printf(請輸入序列數(shù)據(jù)個數(shù)：);scanf(%d,&n);if(nMAX)printf(數(shù)據(jù)過多!nn);break;elseprintf(請輸入數(shù)據(jù)序列：n);for(i = 1;i = n;i+)scanf(%d,&Datai);printf(讀取成功！nn);break;case 2:Quick_Sort(Data,1,n); /快速排序printf(排序成功！序列如下：n);for(i = 1;i = n;i+)printf(%d ,Datai);printf(nn);break;case 3:printf(請輸入待查找的數(shù)據(jù)：);scanf(%d,&data);k = Quick_Find(Data,data,n); /二分法查找if(k)printf(查找成功！數(shù)據(jù)%d位于序列第 %d 位。nn,data,k);elseprintf(查找失敗！沒有你要查找的數(shù)據(jù)！nn);break;default:return 0;int Quick_Part(int Data,int i,int j) /快速排序Data0 = Datai;while(i j)while(i j) & (Data0 = Dataj)j -; /右邊目標元比劃分元大，j往左移if(i j)Datai = Dataj; /比劃分元小的關(guān)鍵字交換到左邊i +;while(i = Datai)i +; /左邊目標元比劃分元小，i往右移if(i s)Quick_Sort(Data,s,i-1); /遞歸調(diào)用排序if(it)Quick_Sort(Data,i+1,t); /遞歸調(diào)用排序return 0;int Quick_Find(int Data,int data,int n) /二分查找int low = 1;int high = n;int mid;while(low Datamid)low = mid +1;elsehigh = mid -1;return 0; /查找失敗返回0九、程序運行結(jié)果：十、實驗結(jié)論：通過實現(xiàn)快速排序和折半查找算法，基本達到了實驗?zāi)康?。快速排序的基本思想是每次確定一個劃分元，將比劃分元大的數(shù)據(jù)存儲到劃分元右邊，比他小的存儲到他左邊，通過遞歸排序?qū)崿F(xiàn)整個順序表的排序。然而，其中的遞歸調(diào)用很難，需要思考其中參數(shù)的變化，這需要細心。十一、總結(jié)及心得體會：1、對錯誤輸入的解決方案還有待完善；2、快速排序遞歸調(diào)用結(jié)束的條件需要慎重考慮，否則極易陷入死循環(huán)。例如課本上的while(st)結(jié)束