浙江大學(xué)城市學(xué)院實(shí)驗(yàn)報(bào)告課程名稱數(shù)據(jù)結(jié)構(gòu)基礎(chǔ)實(shí)驗(yàn)項(xiàng)目名稱實(shí)驗(yàn)三算法和算法分析學(xué)生姓名專業(yè)班級(jí)學(xué)號(hào)實(shí)驗(yàn)成績指導(dǎo)老師（簽名）日期實(shí)驗(yàn)?zāi)康暮鸵?.通過對(duì)算法的分析，了解提高算法的運(yùn)算速度和降低算法的存儲(chǔ)空間之間的矛盾。2.通過對(duì)算法復(fù)雜度的分析，掌握計(jì)算時(shí)間復(fù)雜度和空間復(fù)雜度的基本方法。3.初步掌握測試算法運(yùn)行時(shí)間的基本方法。實(shí)驗(yàn)內(nèi)容根據(jù)算法編寫程序已知輸入x，y，z三個(gè)不相等的整數(shù)，試根據(jù)如下算法（N-S圖）編寫一個(gè)C語言函數(shù)，實(shí)現(xiàn)三個(gè)數(shù)從小到大順序的輸出。三個(gè)數(shù)排序算法的N-S圖提示：一個(gè)矩形框里的處理可能用一條C語句實(shí)現(xiàn)，也可能用多條C語句實(shí)現(xiàn)。例如：“x?y：t=x;x=y;y=t;”。并且，N-S圖中不包括變量的定義，但在C語言函數(shù)中，變量必須先定義再使用。要求：把該程序存放在文件test1_3_1.cpp中，編譯并調(diào)試程序，直到正確運(yùn)行。并請(qǐng)分析：該算法要進(jìn)行___3___次比較，在最好的情況下需要交換數(shù)據(jù)元素___0___次，在最壞的情況下需要交換數(shù)據(jù)元素___3___次。2、測試算法的運(yùn)行時(shí)間在此，我們通過一個(gè)比較兩個(gè)算法執(zhí)行效率的程序例子，掌握測試算法運(yùn)行時(shí)間的基本方法。這里涉及到C語言中標(biāo)準(zhǔn)的函數(shù)庫sys/timeb。sys/timeb函數(shù)庫中提供了處理與時(shí)間相關(guān)的函數(shù)。其中函數(shù)ftime的功能是獲取當(dāng)前的系統(tǒng)時(shí)間。步驟1：輸入兩個(gè)C語言主程序test1_3_2.cpp和test1_3_3.cpp。主文件(test1_3_2.cpp)：#include<stdio.h>#include<sys/timeb.h>//時(shí)間函數(shù)voidmain(){1timebt1,t2;2longt;3doublex,sum=1,sum1;4inti,j,n;5printf("請(qǐng)輸入x，n：");6scanf("%lf,%d",&x,&n);7ftime(&t1); //求得當(dāng)前時(shí)間8for(i=1;i<=n;i++)9{10sum1=1;11for(j=1;j<=i;j++)12sum1=sum1*(-1.0/x);13sum+=sum1;14}15ftime(&t2); //求得當(dāng)前時(shí)間16t=(t2.time-t1.time)*1000+(litm);//計(jì)算時(shí)間差，轉(zhuǎn)換成毫秒17printf("sum=%lf用時(shí)%ld毫秒\n",sum,t);}【附錄----源程序】test1_3_1.cpp#include<stdio.h>voidmain(){ intri,repeat; inti,x,y,z,temp; printf("Enerrepeat:"); scanf("%d",&repeat); for(ri=1;ri<=repeat;ri++){ intchange=0; printf("\nEnterx,y,z:"); scanf("%d%d%d",&x,&y,&z); if(x>y) { temp=x;x=y;y=temp;change++; } if(x>z) { temp=x;x=z;z=temp;change++; } if(y>z) { temp=y;y=z;z=temp;change++; } printf("Aftersort:x=%d,y=%d,z=%d\n",x,y,z); printf("Change:%d\n",change); }}test1_3_4.cpp#include<stdio.h>#include<sys/timeb.h>voidmain(){ timebt1,t2; longt; inti,n; intri,repeat; printf("Enerrepeat:"); scanf("%d",&repeat); for(ri=1;ri<=repeat;ri++) { doublefact=1,sum=0.5; printf("\nEntern:"); scanf("%d",&n); ftime(&t1); for(i=2;i<=n;i++) { fact*=i; s