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

實(shí)驗(yàn)五查找與排序?qū)嶒?yàn)課程名：數(shù)據(jù)結(jié)構(gòu)與算法專業(yè)班級：12級軟件工程1班學(xué)號(hào)：201240450149姓名：劉浩實(shí)驗(yàn)時(shí)間：6.146.2134節(jié)實(shí)驗(yàn)地點(diǎn)：K4-201指導(dǎo)教師：鄧丹君一、實(shí)驗(yàn)?zāi)康暮鸵?、掌握查找的不同方法，并能用高級語言實(shí)現(xiàn)查找算法。2、熟練掌握順序表的查找方法和有序順序表的折半查找算法。3、掌握常用的排序方法，并能用高級語言實(shí)現(xiàn)排序算法。4、深刻理解排序的定義和各種排序方法的特點(diǎn)，并能加以靈活運(yùn)用。5、了解各種方法的排序過程及依據(jù)的原則，并掌握各種排序方法的時(shí)間復(fù)雜度的分析方法。二、實(shí)驗(yàn)內(nèi)容1、順序表的順序查找。解答：（1）源代碼：#include<stdio.h>#defineMAX_LENGTH100#defineMAXSIZE100typedefintKeyType;/*順序查找表的存儲(chǔ)類型*/typedefstruct{KeyTypekey;}SSELEMENT;typedefstruct{SSELEMENTr[MAXSIZE];intlen;}SSTABLE;intseq_search(KeyTypek,SSTABLE*st){/*順序表上查找元素*/ intj; j=st->len;/*順序表元素個(gè)數(shù)*/ st->r[0].key=k;/*st->r[0]單元作為監(jiān)視哨*/ while(st->r[j].key!=k)j--;/*順序表從后向前查找*/ returnj;/*j=0,找不到；j<>0找到*/}main(){ inti,j,t,k;SSTABLEa; printf("請輸入查找表中的元素（按從小到大的順序輸入,以-99作為結(jié)束標(biāo)志）：\n"); for(j=0;i!=-99;j++) { scanf("%d",&i); a.r[j].key=i; } a.len=j+1;printf("請輸入待查找的元素：\n"); scanf("%d",&k); t=seq_search(k,&a); if(t==0) printf("找不到待查找的元素。\n"); else printf("待查找的元素在第%d位\n",t+1);}（2）運(yùn)行結(jié)果：（alt+printscreen）（3）運(yùn)行結(jié)果分析：程序中定義了一個(gè)結(jié)構(gòu)體數(shù)組用于存放關(guān)鍵字key，查找時(shí)當(dāng)k等于關(guān)鍵字key時(shí)返回k的位置，當(dāng)k=0時(shí)，說明不存在這樣的關(guān)鍵字。返回0.2、有序順序表的二分查找的算法。解答：（1）源代碼：（2）運(yùn)行結(jié)果：（alt+printscreen）#include<stdio.h>#defineMAX_LENGTH100#defineMAXSIZE100typedefintKeyType;/*順序查找表的存儲(chǔ)類型*/typedefstruct{KeyTypekey;}SSELEMENT;typedefstruct{SSELEMENTr[MAXSIZE];intlen;}SSTABLE;intsearch_bin(SSTABLE*a,KeyTypek,intlow,inthigh){ intmid; while(low<=high)/*low表示當(dāng)前表中第1個(gè)元素所在下標(biāo)*/ /*high表示當(dāng)前表中最后一個(gè)元素所在下標(biāo)*/ { mid=(low+high)/2;/*mid表示當(dāng)前表中中間一個(gè)元素所在下標(biāo)*/ if(a->r[mid].key==k)break; elseif(a->r[mid].key>k)high=mid-1; elselow=mid+1; } if(low>high) mid=-1; returnmid; }main(){ inti,j,t,k;SSTABLEa; printf("請輸入查找表中的元素（按從小到大的順序輸入,以-99作為結(jié)束標(biāo)志）：\n"); for(j=0;i!=-99;j++) { scanf("%d",&i); a.r[j].key=i; } a.len=j+1;printf("請輸入待查找的元素：\n"); scanf("%d",&k); t=search_bin(&a,k,1,a.len); if(t==0) printf("找不到待查找的元素。\n"); else printf("待查找的元素在第%d位\n",t+1);}（3）運(yùn)行結(jié)果分析：折半查找法是效率較高的一種查找方法。假設(shè)有已經(jīng)按照從小到大的順序排列好的五個(gè)整數(shù)a0~a4，要查找的數(shù)是X，其基本思想是：設(shè)查找數(shù)據(jù)的范圍下限為l=1，上限為h=5，求中點(diǎn)m=（l+h）/2，用X與中點(diǎn)元素am比較，若X等于am，即找到，停止查找；否則，若X大于am，替換下限l=m+1，到下半段繼續(xù)查找；若X小于am，換上限h=m-1，到上半段繼續(xù)查找；如此重復(fù)前面的過程直到找到或者l>h為止。如果l>h，說明沒有此數(shù)，打印找不到信息，程序結(jié)束。3、排序：編制程序，分別用各種排序方法進(jìn)行排序。解答：（1）源代碼：#include<stdio.h>#include<malloc.h>#defineMAXSIZE100typedefstruct{intkey;intdata;}RECNODE[100];intcreateList(RECNODE*r){intj,k;printf("\n\n輸入待排序數(shù)據(jù)(整數(shù)，以空格隔開，0結(jié)束):");k=0;scanf("%d",&j);while(j!=0){k++;r[k]->key=j;scanf("%d",&j);}returnk;}voidfrontdisplayList(RECNODE*r,intn){inti;printf("\n排序前:");for(i=0;i<n;i++)printf("%d",r[i+1]->key);printf("\n\n");}voidreardisplayList(RECNODE*r,intn){inti;printf("\n\n排序后:");for(i=0;i<n;i++)printf("%d",r[i+1]->key);printf("\n\n");}voidinsertsort(RECNODE*r,intn){/*直接插入排序*/ inti,j; for(i=2;i<=n;i++) {r[0]->key=r[i]->key;j=i-1;/*r[0]是監(jiān)視哨，j表示當(dāng)前已排好序列的長度*/ while(r[0]->key<r[j]->key)/*確定插入位置*/ {r[j+1]->key=r[j]->key;j--;} r[j+1]->key=r[0]->key;/*元素插入*/ }}voidbublesort(RECNODE*r,intn){/*簡單交換排序:冒泡排序*/ inti,j; inttemp; for(i=1;i<n;i++) for(j=n-1;j>=i;j--) if(r[j+1]->key<r[j]->key) {temp=r[j+1]->key;r[j+1]->key=r[j]->key;r[j]->key=temp;}}intpartition(RECNODE*r,int*low,int*high){/*一趟快速排序,返回i,產(chǎn)生了兩個(gè)獨(dú)立的待排子序列*/ inti,j; int temp; i=*low;j=*high; temp=r[i]->key;/*樞軸記錄保存在temp變量中*/ do{while((r[j]->key>=temp)&&(i<j))j--;/*j指針記錄和樞軸記錄比較*/ if(i<j){r[i]->key=r[j]->key;i++;} while((r[i]->key<=temp)&&(i<j))i++;/*i指針記錄和樞軸記錄比較*/ if(i<j){r[j]->key=r[i]->key;j--;}}while(i!=j); r[i]->key=temp;/*樞軸記錄的排序位置確定在i*/ returni;}voidquicksort(RECNODE*r,intstart,intend){/*快速排序*/ inti; if(start<end) {i=partition(r,&start,&end);/*一趟快速排序,返回i,產(chǎn)生了兩個(gè)獨(dú)立的待排子序列*/ quicksort(r,start,i-1);/*對兩個(gè)獨(dú)立的待排子序列分別遞歸調(diào)用快速排序算法*/ quicksort(r,i+1,end);}}voidselesort(RECNODE*r,intn){/*簡單選擇排序*/ inti,j,k; inttemp; for(i=1;i<n;i++) {k=i;/*k:最小關(guān)鍵字的初始位置*/ for(j=i+1;j<=n;j++) if(r[j]->key<r[k]->key) k=j;/*k:跟蹤記錄當(dāng)前最小關(guān)鍵字的位置*/ if(k!=i)/*最小關(guān)鍵字元素和待排序列的第一個(gè)元素交換*/ {temp=r[i]->key;r[i]->key=r[k]->key;r[k]->key=temp;} }}voidsift(RECNODE*r,inti,intm){/*i是根結(jié)點(diǎn)編號(hào),m是以i結(jié)點(diǎn)為根的子樹中最后一個(gè)結(jié)點(diǎn)的編號(hào)*/ intj; inttemp; temp=r[i]->key; j=2*i;/*j為i根結(jié)點(diǎn)的左孩子*/ while(j<=m) {if(j<m&&(r[j]->key<r[j+1]->key)) j++;/*當(dāng)i結(jié)點(diǎn)有左右孩子時(shí),j取關(guān)鍵字大的孩子結(jié)點(diǎn)編號(hào)*/ if(temp<r[j]->key)/*按堆定義調(diào)整,并向下一層篩選調(diào)整*/ {r[i]->key=r[j]->key;i=j;j=2*i;} elsebreak;/*篩選調(diào)整完成,跳出循環(huán)*/ } r[i]->key=temp;}voidheapsort(RECNODE*r,intn){/*堆排序:n為r表中記錄數(shù),從r[1]開始放起*/ inti; inttemp; for(i=n/2;i>=1;i--) sift(r,i,n);/*將無序序列建成大堆*/ for(i=n;i>=2;i--) {temp=r[1]->key;/*堆頂及堆尾元素交換*/ r[1]->key=r[i]->key; r[i]->key=temp; sift(r,1,i-1);/*交換后,從第一個(gè)元素開始調(diào)整為大堆,每次記錄個(gè)數(shù)少一個(gè)*/ }}voidmerge(RECNODE*r,intlow,intm,inthigh){/*兩相鄰的有序表(一個(gè)從low到m;另一個(gè)從m+1到high)*//*合并為一個(gè)有序表(從low到high)*/ RECNODEr1[MAXSIZE];/*合并時(shí)用的緩沖向量*/ inti,j,k; i=low; j=m+1; k=0; while(i<=m&&j<=high)/*兩相鄰的有序表合并*/ if(r[i]->key<=r[j]->key) {r1[k]->key=r[i]->key;i++;k++;} else {r1[k]->key=r[j]->key;j++;k++;} while(i<=m)/*有序表剩余部分處理*/ {r1[k]->key=r[i]->key;i++;k++;} while(j<=high) {r1[k]->key=r[j]->key;j++;k++;} for(i=low,k=0;i<=high;i++,k++)/*緩沖向量r1復(fù)制到原來的r中*/ r[i]->key=r1[k]->key;}voidmerge_one(RECNODE*r,intlenth,intn){/*二路歸并中的"一趟歸并"算法*/ inti=0; while(i+2*lenth-1<n) {merge(r,i,i+lenth-1,i+2*lenth-1);/*兩子序列長度相等的*/ i=i+2*lenth;}/*情況下調(diào)用merge*/ if(i+lenth-1<n-1) merge(r,i,i+lenth-1,n-1);/*序列中的余留部分處理*/}voidmergesort(RECNODE*r,intn){/*二路歸并排序算法*/ intlenth=1;/*有序子序列長度初始值=1*/ while(lenth<n) {merge_one(r,lenth,n);/*調(diào)用"一趟歸并"的算法*/ lenth=2*lenth;}/*有序子序列長度加倍*/}main(){ inti,j,k; RECNODE*r; r=(RECNODE*)malloc(sizeof(RECNODE)); k=createList(r);printf("請選擇要進(jìn)行的排序種類：1——直接插入排序，2——冒泡排序，3——快速排序，4——簡單選擇排序，5——堆排序，6——二路歸并排序。\n"); scanf("%d",&i); switch(i) { case1:frontdisplayList(r,k);insertsort(r,k);reardisplayList(r,k);break;case2:frontdisplayList(r,k);bublesort(r,k);reardisplayList(r,k);break; case3:frontdisplayList(r,k);quicksort(r,1,k);reardisplayList(r,k);break; case4:frontdisplayList(r,k);selesort(r,k);reardisplayList(r,k);break; case5:frontdisplayList(r,k);heapsort(r,k);reardisplayList(r,k);break;