版權說明:本文檔由用戶提供并上傳,收益歸屬內容提供方,若內容存在侵權,請進行舉報或認領
文檔簡介
數據結構課程設計報告PAGE5數據結構課程設計實驗報告姓名:顧云康學號:E1114300指導老師:王愛平日期:2013.10.8目錄1課程設計的目的 32需求分析 33課程設計報告內容 33.1概要設計 33.2詳細設計 43.3調試分析 124總結 135程序清單 146參考文獻 147程序運行結果 14附錄 15 clock_tbegin3,end3;doublecost3;begin3=clock(); insertSort(number3,MAX); end3=clock(); cost3=(double)(end3-begin3)/CLOCKS_PER_SEC; //梳排序并計算時間 clock_tbegin4,end4;doublecost4;begin4=clock(); combsort(number4,MAX); end4=clock(); cost4=(double)(end4-begin4)/CLOCKS_PER_SEC;for(intj=0;j<MAX;j++) { printf("%d",number1[j]); }printf("\n");printf("排序完成!\n");printf("快速排序耗時:%lfseconds\n",cost1);printf("冒泡排序耗時:%lfseconds\n",cost2);printf("插入排序耗時:%lfseconds\n",cost3);printf("梳排序耗時:%lfseconds\n",cost4); return0;}插入排序函數:voidinsertSort(inta[],intlen){ inti,j,temp; for(i=1;i<len;i++) { temp=a[i]; for(j=i-1;j>=0;j--) { if(a[j]>temp) { a[j+1]=a[j]; }else { break; } } a[j+1]=temp; }}冒泡排序函數:voidBubble(inta[],intlen){ intlength=len;inti=0;intj=0;for(;i<len;i++) { for(;j<length;j++) { if(a[j]>a[j+1]) { inttemp=a[j];a[j]=a[j+1];a[j+1]=temp; } }length--;j=0; }}快速排序函數:intpartions(intl[],intlow,inthigh){ intprvotkey=l[low];l[0]=l[low];while(low<high) { while(low<high&&l[high]>=prvotkey) --high;l[low]=l[high];while(low<high&&l[low]<=prvotkey) ++low;l[high]=l[low]; }l[low]=l[0];returnlow;}voidqsort(intl[],intlow,inthigh){ intprvotloc;if(low<high) { prvotloc=partions(l,low,high);//將第一次排序的結果作為樞軸qsort(l,low,prvotloc-1);//遞歸調用排序由low到prvotloc-1qsort(l,prvotloc+1,high);//遞歸調用排序由prvotloc+1到high }}voidquicksort(intl[],intn){ qsort(l,1,n);//第一個作為樞軸,從第一個排到第n個}梳排序函數:voidcombsort(inta[],intn){ floatshrink_factor=1.3;intgap=n,swapped=1,swap,i;while((gap>1)||swapped) { if(gap>1)gap=gap/shrink_factor;swapped=0;i=0;while((gap+i)<n) { if(a[i]-a[i+gap]>0) { swap=a[i];a[i]=a[i+gap];a[i+gap]=swap;swapped=1; }++i; } }}3.3調試分析(1)使用隨機數產生函數,產生40000個隨機數,再使用四種算法進行排序,并統計各種算法統計時間。運行截圖如下:(3)由多次試驗結果可得,梳排序和快速排序的排序速度相對較快。4總結通過這次課程設計我認識到了排序功能在解決實際問題中的作用,使我對數據結構的學習有了更進一步的理解。在完成本次課程設計中,我發(fā)現很多理論性知識在實際使用時與單純的理論還是有所差別的,今后我會更加注重培養(yǎng)自己的實踐動手能力。5程序清單見附錄6參考文獻[1]嚴蔚敏,吳偉民編著.數據結構(C語言版)--北京:清華大學出版社,2007.[2]嚴蔚敏,吳偉民米寧編著.數據結構題集(C語言版)--北京:清華大學出版社,2007.[3]/wiki/%E6%A2%B3%E6%8E%92%E5%BA%8F7程序運行結果附錄程序清單:#include"stdafx.h"#include<stdio.h>#include<stdlib.h>#include<time.h>/*用到了time函數,所以要有這個頭文件*/#defineMAX40000//插入排序voidinsertSort(inta[],intlen){ inti,j,temp; for(i=1;i<len;i++) { temp=a[i]; for(j=i-1;j>=0;j--) { if(a[j]>temp) { a[j+1]=a[j]; }else { break; } } a[j+1]=temp; }}//冒泡排序voidBubble(inta[],intlen){ intlength=len;inti=0;intj=0;for(;i<len;i++) { for(;j<length;j++) { if(a[j]>a[j+1]) { inttemp=a[j];a[j]=a[j+1];a[j+1]=temp; } }length--;j=0; }}//快速排序intpartions(intl[],intlow,inthigh){ intprvotkey=l[low];l[0]=l[low];while(low<high) { while(low<high&&l[high]>=prvotkey) --high;l[low]=l[high];while(low<high&&l[low]<=prvotkey) ++low;l[high]=l[low]; }l[low]=l[0];returnlow;}voidqsort(intl[],intlow,inthigh){ intprvotloc;if(low<high) { prvotloc=partions(l,low,high);//將第一次排序的結果作為樞軸qsort(l,low,prvotloc-1);//遞歸調用排序由low到prvotloc-1qsort(l,prvotloc+1,high);//遞歸調用排序由prvotloc+1到high }}voidquicksort(intl[],intn){ qsort(l,1,n);//第一個作為樞軸,從第一個排到第n個}//梳排序voidcombsort(inta[],intn){ floatshrink_factor=1.3;intgap=n,swapped=1,swap,i;while((gap>1)||swapped) { if(gap>1)gap=gap/shrink_factor;swapped=0;i=0;while((gap+i)<n) { if(a[i]-a[i+gap]>0) { swap=a[i];a[i]=a[i+gap];a[i+gap]=swap;swapped=1; }++i; } }}intmain(){ intnumber[MAX]={0}; intnumber1[MAX]={0}; intnumber2[MAX]={0}; intnumber3[MAX]={0}; intnumber4[MAX]={0};inti;srand((unsigned)time(NULL));/*播種子*/for(i=0;i<MAX;i++) { number[i]=rand()%20000;/*產生101以內的隨機整數*/number1[i]=number2[i]=number3[i]=number4[i]=number[i];while(number[i]==0) { number[i]=rand()%20000; number1[i]=number2[i]=number3[i]=number4[i]=number[i]; } }//快速排序并計算時間 clock_tbegin1,end1;doublecost1;begin1=clock(); quicksort(number1,MAX); end1=clock(); cost1=(double)(end1-begin1)/CLOCKS_PER_SEC;//冒泡排序并計算時間 clock_tbegin2,end2;doublecost2;begin2=clock(); Bubble(number2,MAX); end2=clock(); cost2=(double)(end2-begin2)/CLOCKS_PER_SEC; //插入排序并計算時間 clock_tbegin3,end3;doublecost3;begin3=clock(); insertSort(number3,MAX); end3=clock(); cost3=(double)(end3-begin3)/CLOCKS_PER_SEC; //梳排序并計算時間 clock_tbegin4,end4;doublecost4;begin4=clock(); combsort(number4,MAX); end4=clock(); cost4=(double)(end4-begin4)/CLOCKS_P
溫馨提示
- 1. 本站所有資源如無特殊說明,都需要本地電腦安裝OFFICE2007和PDF閱讀器。圖紙軟件為CAD,CAXA,PROE,UG,SolidWorks等.壓縮文件請下載最新的WinRAR軟件解壓。
- 2. 本站的文檔不包含任何第三方提供的附件圖紙等,如果需要附件,請聯系上傳者。文件的所有權益歸上傳用戶所有。
- 3. 本站RAR壓縮包中若帶圖紙,網頁內容里面會有圖紙預覽,若沒有圖紙預覽就沒有圖紙。
- 4. 未經權益所有人同意不得將文件中的內容挪作商業(yè)或盈利用途。
- 5. 人人文庫網僅提供信息存儲空間,僅對用戶上傳內容的表現方式做保護處理,對用戶上傳分享的文檔內容本身不做任何修改或編輯,并不能對任何下載內容負責。
- 6. 下載文件中如有侵權或不適當內容,請與我們聯系,我們立即糾正。
- 7. 本站不保證下載資源的準確性、安全性和完整性, 同時也不承擔用戶因使用這些下載資源對自己和他人造成任何形式的傷害或損失。
最新文檔
- 文明校園演講稿范文300字(8篇)
- 護理見習自我評價
- 工作失職萬能檢討書(6篇)
- 房屋所有權證明范文
- 小區(qū)關于燃放煙花爆竹的承諾書(5篇)
- 幸運是不存在的努力才是硬道理
- 2025年山東淄博沂源縣事業(yè)單位招考115人管理單位筆試遴選500模擬題附帶答案詳解
- 2025年山東濟寧鄒城市事業(yè)單位招聘工作人員(綜合類)113人管理單位筆試遴選500模擬題附帶答案詳解
- 2025年山東濟寧市屬事業(yè)單位招聘47人(教育類)管理單位筆試遴選500模擬題附帶答案詳解
- 開會遲到檢討書范文
- 2023年度四川公需科目:數字經濟與驅動發(fā)展
- 汽車制造業(yè)的柔性生產與敏捷制造
- 五年級上冊小數乘除練習300道及答案
- 不動產抵押登記手續(xù)
- 公安機關執(zhí)法執(zhí)勤規(guī)范用語
- 無人機技術在消防救援中的作用與局限
- 超越指標:存量時代降本增效的利器
- 一年級道德與法治無紙筆期末檢測質量分析
- 形式邏輯期末考試含答案
- 自媒體賬號運營的用戶畫像分析技巧
- 醫(yī)院門窗工程施工方案與施工方法
評論
0/150
提交評論