快速排序與二分查找-實(shí)驗(yàn)四.doc

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