华中科技大学：《计算机算法基础》 算法程序设计

计算机学院0101班吴晴 学号200101183000 算法程序设计 一,比较归弄分奏和快速分类算油 思想:结合课本中的算法结构,分别计算在数据集相同且分别为随机 数,非降序,非增序情况下两种算法所需的时间.数据集为10000 dio. h> #include #include #include #includeslimits. h> #define mAX 1000000 工作数据集为100000 int A[MAX+21 ∥多出的两个为0号和最后一个无穷大 int B[MAX+2] B和C保证排序使用的数据集相同,若作为局部变量会造成 int C[MAX+2 ∥存溢出 void mERGESORT(int low, int high) /归并排序 i int mid if(lowmid)for(k-j, k<=high k++)B0=A(k]; 1++ else for(k=h k<=mid; k++)B=Ak i++;) for(k=low; k<=high; k++)A[k]=B(kI return void QUICKSORT(int m, int p) ∥快速排序将两个函数合为一个 int v, i, k, temp

计算机学院 0101 班 吴晴 学号:2001011830002 1/5 算法程序设计 一,比较归并分类和快速分类算法 思想:结合课本中的算法结构,分别计算在数据集相同且分别为随机 数,非降序,非增序情况下两种算法所需的时间.数据集为 1000000. #include #include #include #include #include #include #define MAX 1000000 //工作数据集为 1000000 int A[MAX+2]; //多出的两个为 0 号和最后一个无穷大 int B[MAX+2]; //B和C保证排序使用的数据集相同,若作为局部变量会造成 int C[MAX+2]; //内存溢出 void MERGESORT(int low,int high) //归并排序 { int mid; if(lowmid) for(k=j;k<=high;k++) {B[i]=A[k];i++;} else for(k=h;k<=mid;k++) {B[i]=A[k];i++;} for(k=low;k<=high;k++) A[k]=B[k]; return; } void QUICKSORT(int m,int p) //快速排序,将两个函数合为一个 { int v,j,k,temp;

计算机学院0101班吴晴 学号200101183000 V=Am]; k=p+1 if(v) if(tm hour. ml=newtime->tm min sI=newtime->tm sec ftime( &timebuffer tl=timebuffer. millitm process(x,y); time( &long time newtime =localtime( &long time ) ∥到结束时的时间 h2=newtime->tm hour: s2=newtime->tm sec ftime( &timebuffer t2=timebuffer. millitm. temp=24*60*1000*(h2-hl)+60000(m2-m1)+1000(52-s1)+12t1;/求时间差,即运行时间 printf("It\t%.5d ms", temp) t int i AMAX+1=INT MAX

计算机学院 0101 班 吴晴 学号:2001011830002 2/5 v=A[m]; j=m; k=p+1; if(jv); if(jtm_hour; m1=newtime->tm_min; s1=newtime->tm_sec; _ftime( &timebuffer ); t1=timebuffer.millitm; process(x,y); time( &long_time ); newtime = localtime( &long_time ); //得到结束时的时间 h2=newtime->tm_hour; m2=newtime->tm_min; s2=newtime->tm_sec; _ftime( &timebuffer ); t2=timebuffer.millitm; temp=24*60*1000*(h2-h1)+60000*(m2-m1)+1000*(s2-s1)+t2-t1;//求时间差,即运行时间 printf("\t\t%5d ms",temp); } void main() { int i; A[MAX+1]=INT_MAX;

计算机学院0101班吴晴 学号200101183000 printf("ItItMERGESORTttQUiCKsoRT\n"); printf("Rand: " ∥随机时的比较 for(il; #includesfloat. h> #define n6 #define mAX Flt max float DIST[N+1 float COSTIN+lIN+1}={{-1,-1,-1,-1,-1,-1,-1} i-1, 0, 20, 15, MAX, MAX, MAX;

计算机学院 0101 班 吴晴 学号:2001011830002 3/5 printf("\t\tMERGESORT\t\tQUICKSORT\n"); printf("Rand:"); //随机时的比较 for(i=1;i #include #include #define N 6 #define MAX FLT_MAX float DIST[N+1]; float COST[N+1][N+1]={ {-1,-1, -1, -1, -1, -1, -1}, {-1,0, 20, 15, MAX,MAX,MAX}

计算机学院0101班吴晴 学号200101183000 -1,2,0,MAX,MAx,10,30} i-1, MAX, 4, 0, MAX, MAX, 10) F-1, MAX, MAX, MAX, 0, MAX, MAX; i-1, MAX, MAX, MAX, 15, 0, MAX) F-1, MAX, MAX, MAX, 4, 10, 0) int PATHN+lI )于存放到目的结点最短路径上最后一个点的位置 int STACKINI ∥利用PAIH函数通过栈操作来求出最短路径序列 bool S[N+l ∥判断改结点是否已进行比较 void SHORTEST PATHS(inty)∥/生成最短路径的贪心算法 t int i, num, u; for(i1; KDisTu+CoSTu) i DIST[=DIST[u+COSTu][] PATHI=u; int finding ∥找找周围路径最短的结点 float temp=MAX; for(i1; K<=N; i++) if(s[=0) if(DIST[]<temp & dist[!=0) i temp=DIST( eturn() int path (int v, int 1) ∥通过栈反序查找 if(PATHSTACKi-1=v) t STACK[G=PATHSTACKi-1ll

计算机学院 0101 班 吴晴 学号:2001011830002 4/5 {-1,2, 0, MAX,MAX,10, 30}, {-1,MAX,4, 0, MAX,MAX,10}, {-1,MAX,MAX,MAX,0, MAX,MAX}, {-1,MAX,MAX,MAX,15, 0, MAX}, {-1,MAX,MAX,MAX,4, 10, 0}}; int PATH[N+1]; //用于存放到目的结点最短路径上最后一个点的位置 int STACK[N]; //利用PATH函数通过栈操作来求出最短路径序列 bool S[N+1]; //判断改结点是否已进行比较 void SHORTEST_PATHS(int v) //生成最短路径的贪心算法 { int i,num,u; for(i=1;i DIST[u]+COST[u][i]) { DIST[i]=DIST[u]+COST[u][i]; PATH[i]=u; } } } int findmin() //找找周围路径最短的结点 { int i,j; float temp=MAX; for(i=1;i<=N;i++) { if(S[i]==0) if(DIST[i]<temp && DIST[i]!=0) { temp=DIST[i]; j=i; } } return(j); } int path(int v,int i) //通过栈反序查找 { int s=1; if(PATH[STACK[i-1]]!=v) { STACK[i]=PATH[STACK[i-1]];

计算机学院0101班吴晴 学号200101183000 s+=path(v, i+1) return s id main( void) printf("input the number: " scanf("%d", &m) SHORTEST PATHS(m) for(i1; K=1;j-) printf("-%d"STACK[-1); printf("It\distance: %3.Of ", DIST[) getch(; 运行结果: input the number: 2 from 2 to 1: 2-1 distance. 2 from 2 to 3: 2-1-3 distance: 17 from 2 to 4: 2-5-4 distance: 25 from 2 to 5: 2-5 distance: 10 from 2 to 6: 2-1-3-6 distance: 27 编程分析 算法思想:确定到目的结点最短路径上最后一个点的位置依次反序进栈出栈时正好就 是最短路径序列了 这种方法是把求最短长度和求序列两部分分开进行问哪个才求哪个,而使用二维数组的 方法则是把问题结合在一起进行,全部一起求完

计算机学院 0101 班 吴晴 学号:2001011830002 5/5 s+=path(v,i+1); } return s; } void main(void) { int i,j,m; printf("input the number:"); scanf("%d",&m); SHORTEST_PATHS(m); for(i=1;i=1;j--) printf("-%d",STACK[j-1]); printf("\t\tdistance:%3.0f ",DIST[i]); } } getch(); } 运行结果: input the number:2 from 2 to 1:2-1 distance: 2 from 2 to 3:2-1-3 distance: 17 from 2 to 4:2-5-4 distance: 25 from 2 to 5:2-5 distance: 10 from 2 to 6:2-1-3-6 distance: 27 编程分析: 算法思想: 确定到目的结点最短路径上最后一个点的位置,依次反序进栈,出栈时正好就 是最短路径序列了. 这种方法是把求最短长度和求序列两部分分开进行,问哪个才求哪个,而使用二维数组的 方法则是把问题结合在一起进行,全部一起求完