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

4孑科技大學(xué)課程名稱(chēng):數(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日2023—2023?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)室名稱(chēng):軟件實(shí)驗(yàn)室二、實(shí)驗(yàn)項(xiàng)目名稱(chē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)行，以此達(dá)成整個(gè)數(shù)據(jù)變成有序序列。假設(shè)要排序的數(shù)組是A[l]……A[N],一方面任意選取一個(gè)數(shù)據(jù)（通常選用第一個(gè)數(shù)據(jù)）作為關(guān)健數(shù)據(jù)，然后將所有比它的數(shù)都放到它前面，所有比它大的數(shù)都放到它后面，這個(gè)過(guò)程稱(chēng)為一躺快速排序。一躺快速排序的算法是：1）設(shè)立兩個(gè)變量I、J,排序開(kāi)始的時(shí)候I:=l,J：=N2）以第一個(gè)數(shù)組元素作為關(guān)鍵數(shù)據(jù),賦值給X,即X:=AJ];3）從J開(kāi)始向前搜索，BP（J：=J-1），找到第一個(gè)小于X的值，兩者互換；4）從I開(kāi)始向后搜索，即（I：=1+1）,找到第一個(gè)大于X的值，兩者互換；5）反復(fù)第3、4步，直到I=J。二分法查找（折半查找）的基本思想：（1）擬定該區(qū)間的中點(diǎn)位置:mid=（1ow+high）/2min代表區(qū)間中間的結(jié)點(diǎn)的位置，low代表區(qū)間最左結(jié)點(diǎn)位置，high代表區(qū)間最右結(jié)點(diǎn)位置（2）將待查a值與結(jié)點(diǎn)mid的關(guān)鍵字（下面用R[mid].key）比較，若相等，則查找成功，否則擬定新的查找區(qū)間:A）假如R[mid].key>a,則由表的有序性可知,R[mid].key右側(cè)的值都大于a,所以等于a的關(guān)鍵字假如存在,必然在R[mid].key左邊的表中，這時(shí)high=mid—1;B）假如R[mid].keyva,則等「a的關(guān)鍵字假如存在,必然在R[mid].key右邊的表中。這時(shí)1ow=mid;C）假如R[mid].key=a,則查找成功。（3）下一次查找針對(duì)新的查找區(qū)間，反復(fù)環(huán)節(jié)（1）和（2）（4）在查找過(guò)程中，low逐步增長(zhǎng),high逐步減少，假如highvlow,則查找失敗。五、實(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)折半查找算法，并在環(huán)節(jié)（2）排序后的序列上，進(jìn)行任意地查找，并輸出查詢(xún)結(jié)果。七、實(shí)驗(yàn)器材（設(shè)備、元器件）：PC機(jī)一臺(tái)，裝有C語(yǔ)言集成開(kāi)發(fā)環(huán)境。八、數(shù)據(jù)結(jié)構(gòu)與程序：inc1ude<stdio.h>inc1ude<stdlib.h>defineMAX1000^defineFROMFILE1typedefstruetJI）{intkey;}JI);intbinsrch(JDr[],intn,intk){intlow,high,mid,found;1ow=1;high=n;found=0;whi1e((1ow<=high)&&(found==0)){mid=(1ow+high)/2;if(k>r[mid].key)1ow=mid+1;elseif(k==r[mid].key)found=1;elsehigh=mid-l;)if(found==l)return(mid)；elsereturn(0)；)voidquicksort(JDr[],int1ow,inthigh){sinti,j,k;。JDx;oif(1ow>=high)return；ai=1ow;。j=high；，x=r[i];while(i<j){§whi1e((i<j)&&(r[j].key>=x.key))j-;ooif(i<j){r[i]=r[j];i++；)3owhi1e((i<j)&&(r[i].key<=x.key))i++;。if(i<j){r[j]=r[i]；j—;})§r[i]=x;3quicksort(r,low,j—1);quicksort(r,j+1,high);}//快速排序intmain(){printf("歡迎使用快速排序與二分查找。\n\n");#ifdefFROMFILEprintf(〃請(qǐng)輸入你所要查找的數(shù)組長(zhǎng)度:〃)；int1ength;scanf("%d”,&length)；getchar();JDa[length+1];a[0].key=0;inti;for(i=l;i<=1ength;i++){printf("輸入第%d個(gè)數(shù)字："，i);scanf("%d”,&a[i].key);getchar()；)#elseFILE*fp；fp=fopen("test.txt","r");if(!fp)printf(〃文獻(xiàn)不存在!〃)；return0;)JDa[MAX];a[0].key=0；inti=1;while(fscanf(fp,"%d”,&a[i++].key)!=EOF);intlength=i-1;printf("文獻(xiàn)內(nèi)的信息:");for(i=l;i<length;i++){printf(*%d",a[i].key)；)printf('\n");length—;fclose(fp)；。#endifquicksort(a,0,length);intkey;printf(〃請(qǐng)輸入你想查找的數(shù)字:〃)；scanf(〃/d",&key);getchar();printf("\n");intlocation=binsrch(a,1ength,key);printf(〃位置：〃)；for(i=l；i<=1ength;i++)(printfC%3d",i);)printf("\n")；printf(〃數(shù)字：〃)；for(i=1;i<=1ength；i++){printf(螺3du,a[i].key);)printf("\n，z);if(location){intcount=0;printf(〃目的數(shù)字出現(xiàn)的位置:〃)；for(i=1;i<=lcngth；i++){if(a[i].key==a[1ocation].key){printf("%d”,i);count++;))printf(，z\n數(shù)字％d出現(xiàn)的次數(shù):%d\n”,a[location].key,count);)eIse{printf("該數(shù)字不存在!\n'n");)return0;)九、程序運(yùn)營(yíng)結(jié)果：

區(qū)安任意鍵繼續(xù)...輸入你想查找的數(shù)字：4書(shū)快速排序與二，'C:\Users\Admini$trator\Desktop\^^SSl.exe"由125365735:3爨數(shù)數(shù)數(shù)數(shù)饕數(shù)程J11234567891輸蒯區(qū)安任意鍵繼續(xù)...輸入你想查找的數(shù)字：4書(shū)快速排序與二，'C:\Users\Admini$trator\Desktop\^^SSl.exe"由125365735:3爨數(shù)數(shù)數(shù)數(shù)饕數(shù)程J11234567891如輸俅置：12345678g10例子：123335556?該