實(shí)驗(yàn)報(bào)告排序與查找

1、電 子 科 技 大 學(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)大樓 實(shí)驗(yàn)時(shí)間： 5月20日 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)大樓 實(shí)驗(yàn)時(shí)間：5月20日一、實(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)原理：快速排序的基本思想是：通過(guò)一躺排序?qū)⒁判虻臄?shù)據(jù)分割成獨(dú)立的兩部分，其中一部分的所有數(shù)據(jù)都比另外一不部分的所有數(shù)據(jù)都要小，然后再按次方法對(duì)這兩部分?jǐn)?shù)據(jù)分別進(jìn)行快速排序，整個(gè)排序過(guò)程可以遞歸進(jìn)行，

2、以此達(dá)到整個(gè)數(shù)據(jù)變成有序序列。 假設(shè)要排序的數(shù)組是A1AN，首先任意選取一個(gè)數(shù)據(jù)（通常選用第一個(gè)數(shù)據(jù)）作為關(guān)鍵數(shù)據(jù)，然后將所有比它的數(shù)都放到它前面，所有比它大的數(shù)都放到它后面，這個(gè)過(guò)程稱為一躺快速排序。一躺快速排序的算法是： 1）設(shè)置兩個(gè)變量I、J，排序開(kāi)始的時(shí)候I：=1，J：=N 2）以第一個(gè)數(shù)組元素作為關(guān)鍵數(shù)據(jù)，賦值給X，即X：=A1； 3）從J開(kāi)始向前搜索，即（J：=J-1），找到第一個(gè)小于X的值，兩者交換； 4）從I開(kāi)始向后搜索，即（I：=I+1），找到第一個(gè)大于X的值，兩者交換； 5）重復(fù)第3、4步，直到I=J。 二分法查找（折半查找）的基本思想： （1）確定該區(qū)間的中點(diǎn)位置：mid

3、=（low+high）/2    min代表區(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.key>a，則由表的有序性可知，Rmid.key右側(cè)的值都大于a，所以等于a的關(guān)鍵字如果存在，必然在Rmid.key左邊的表中,這時(shí)high=mid-1; B)如果Rmid.key<a,則等于a的關(guān)鍵字如果存在，必然在Rmid.key右邊的表中。這時(shí)low=mid； C)如果Rmid.key=

4、a，則查找成功。 （3）下一次查找針對(duì)新的查找區(qū)間，重復(fù)步驟（1）和（2） （4）在查找過(guò)程中，low逐步增加，high逐步減少，如果high<low，則查找失敗。五、實(shí)驗(yàn)?zāi)康模罕緦?shí)驗(yàn)通過(guò)實(shí)現(xiàn)快速排序和折半查找算法，使學(xué)生理解如何實(shí)現(xiàn)快速查找和排序的基本算法思想。通過(guò)練習(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語(yǔ)言集成開(kāi)發(fā)環(huán)境。八、數(shù)據(jù)結(jié)構(gòu)與程序：#include<

5、;stdio.h>#include<stdlib.h>#define MAX 1000#define FROMFILE 1typedef struct JD int key;JD;int binsrch(JD r,int n,int k) int low,high,mid,found; low=1; high=n; found=0; while(low<=high)&&(found=0) mid=(low+high)/2; if(k>rmid.key) low=mid+1; else if(k=rmid.key) found=1; else hig

6、h=mid-1; if(found=1) return(mid); else return(0);void quicksort(JD r,int low,int high)int i,j,k;JD x;if(low>=high)return;i=low;j=high;x=ri;while(i<j)while(i<j)&&(rj.key>=x.key)j-;if(i<j)ri=rj;i+;while(i<j)&&(ri.key<=x.key)i+;if(i<j)rj=ri;j-;ri=x;quicksort(r,lo

7、w,j-1);quicksort(r,j+1,high);/快速排序 int main() printf("歡迎使用快速排序與二分查找。nn"); #ifdef FROMFILE printf("請(qǐng)輸入你所要查找的數(shù)組長(zhǎng)度:"); int length; scanf("%d",&length); getchar(); JD alength+1; a0.key=0; int i; for(i=1;i<=length;i+) printf("輸入第%d個(gè)數(shù)字:",i); scanf("%d&qu

8、ot;,&ai.key); getchar(); #else FILE *fp; fp = fopen("test.txt","r"); if(!fp) printf("文件不存在!"); return 0; JD aMAX; a0.key=0; int i=1; while (fscanf(fp,"%d",&ai+.key)!=EOF); int length=i-1; printf("文件內(nèi)的信息:"); for (i=1;i<length;i+) printf(&qu

9、ot;%d ",ai.key); printf("n"); length-; fclose(fp); #endif quicksort(a,0,length); printf("n"); int key; printf("請(qǐng)輸入你想查找的數(shù)字:"); scanf("%d",&key); getchar(); printf("n"); int location=binsrch(a,length,key); printf("位置 :"); for(i=1;i&l

10、t;=length;i+) printf("%3d ",i); printf("n"); printf("數(shù)字 :"); for(i=1;i<=length;i+) printf("%3d ",ai.key); printf("n"); if(location) int count=0; printf("目標(biāo)數(shù)字出現(xiàn)的位置:"); for (i=1;i<=length;i+) if (ai.key=alocation.key) printf("%d ",i); count+; printf("n數(shù)字%d出現(xiàn)的次數(shù):%dn",alocation.key,count); else printf("該數(shù)字不存在!nn"); return 0;九、程序運(yùn)行結(jié)果：十、實(shí)驗(yàn)結(jié)論： 此次操