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

计算机学院0101班吴晴 学号200101183000 算法程序设计 一,比较归弄分奏和快速分类算油 思想:结合课本中的算法结构,分别计算在数据集相同且分别为随机 数,非降序,非增序情况下两种算法所需的时间.数据集为10000 dio. h> #include<conio. h> #include<stdlib. h #includestime h> #include<sys/timeb. h> #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(low<high) i mid=(low+high)/2 MERGESORT(low, mid) MERGESORT(mid+l, high) MERGE(low, mid, high); void merge( nt low, int mid int high)∥归并两个已分类的集合 k. h while(h<=mid&&j<=high) if(A[h]<=A[]){B[=A[h],h++; else( BGFA0: j++ if(h>mid)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<stdio.h> #include<conio.h> #include<stdlib.h> #include<time.h> #include<sys/timeb.h> #include<limits.h> #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(low<high) { mid=(low+high)/2; MERGESORT(low,mid); MERGESORT(mid+1,high); MERGE(low,mid,high); } return; } void MERGE(int low,int mid,int high) //归并两个已分类的集合 { int i,j,k,h; h=i=low,j=mid+1; while(h<=mid&&j<=high) { if(A[h]<=A[j]) { B[i]=A[h]; h++; } else { B[i]=A[j]; j++; } i++; } if(h>mid) 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(<k) i for(: j<k i do j++,i while(Ank<v); dof k--;i while(Ak>v) if(<k)( temp=A[; Al=A[k]; A(k]=temp: i A[m=A[k] A[k]=v; QUICKSORT(m, k-1) QUICKSORT(k+l, p) void count(int x, int y, void process(int, int)) ∥计算运行时间 t int hl, h2, ml, m2, sl, S2, tl, t2, temp: struct timeb timebuffer struct tm李 newtime time t long time time( &long time newtime =localtime( &long time ) ∥|到初始时的时间 hI=newtime->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(j<k) { for(;j<k;) { do{ j++; } while(A[j]<v); do{ k--; }while(A[k]>v); if(j<k) { temp=A[j]; A[j]=A[k];A[k]=temp; } } A[m]=A[k]; A[k]=v; QUICKSORT(m,k-1); QUICKSORT(k+1,p); } } void count(int x,int y,void process(int,int)) //计算运行时间 { int h1,h2,m1,m2,s1,s2,t1,t2,temp; struct _timeb timebuffer; struct tm *newtime; time_t long_time; time( &long_time ); newtime = localtime( &long_time ); //得到初始时的时间 h1=newtime->tm_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; <=MAX 1++) Ci=Ai=rando count(l, MAX, MERGESORT for(i=l; i <=MAX 1++) BO=A[; for(i-l; i<=MAX; i++)AO=C[] count(l, MAX, QUICKSORT printf("InNotDEC ∥排降序时的比较 for(i1; K<=MAX; i++)Ai=BO count(l, MAX, MERGESORT) for(i=l; K <=MAX; i++)AG=C count(l, MAX, QUICKSORT: printf("InNotINC: ) ∥增序时的比较 for(i=l; K<=MAX; 1++) Al=BIMAX-i+ll count(1, MAX, MERGESORT) for(i=l; i<=MAX; i++)AG=C[MAX-i+1l count(l, MAX, QUICKSORT: getcho 运行结果: MERGESORT QUICKSORT 517ms 322ms NotDeC 322ms 314ms NotINc 401ms 325ms 编程分析 获得的结果是一个非线性结果,个人认为与CPU频率,操作系统所分配的时间片有关有时 会出现不合常理的结果但总体来说快速排序法的运行速度要快于归并排序法一般数据集在 非减时的排序所用时间要小于非增时排序所用的时间后者与随机时排序所用的时间的关系 很难区分 二,算节上的草源录短路径算油仅求出了从草娜点到其它所有结 点的录短路径长度。在此基础上,扩光算油劝能,使得新算油在 找出这些录经路径长度的同肘,也能求出路径上的结点序列。(以 习题316为例) 思想:多增加两个数组,一个用于存放到目的结点最短路径上最后一个点的位置,另一个则作 为栈使用 #include<stdio. h> #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<=MAX;i++) C[i]=A[i]=rand(); count(1,MAX,MERGESORT); for(i=1;i<=MAX;i++) B[i]=A[i]; for(i=1;i<=MAX;i++) A[i]=C[i]; count(1,MAX,QUICKSORT); printf("\nNotDEC:"); //非降序时的比较 for(i=1;i<=MAX;i++) A[i]=B[i]; count(1,MAX,MERGESORT); for(i=1;i<=MAX;i++) A[i]=C[i]; count(1,MAX,QUICKSORT); printf("\nNotINC:"); //非增序时的比较 for(i=1;i<=MAX;i++) A[i]=B[MAX-i+1]; count(1,MAX,MERGESORT); for(i=1;i<=MAX;i++) A[i]=C[MAX-i+1]; count(1,MAX,QUICKSORT); getch(); } 运行结果: MERGESORT QUICKSORT Rand: 517ms 322ms NotDEC: 322ms 314ms NotINC: 401ms 325ms 编程分析: 获得的结果是一个非线性结果，个人认为与 CPU 频率，操作系统所分配的时间片有关,有时 会出现不合常理的结果,但总体来说快速排序法的运行速度要快于归并排序法.一般数据集在 非减时的排序所用时间要小于非增时排序所用的时间.后者与随机时排序所用的时间的关系 很难区分.. 二,算书上的单源最短路径算法仅求出了从单源点到其它所有结 点的最短路径长度。在此基础上，扩充算法功能，使得新算法在 找出这些最短路径长度的同时，也能求出路径上的结点序列。(以 习题 3.16 为例) 思想:多增加两个数组,一个用于存放到目的结点最短路径上最后一个点的位置,另一个则作 为栈使用. #include<stdio.h> #include<conio.h> #include<float.H> #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; K<=N; i++) S[]=0 DIST[=COSTVJ0 PATHI=V S[v]=1; DSTV]=0 for(num=2; num<=N-1; num++) t u=finding S[u=1; for(i-l; K<=N; i++) if(s[==0 & dist[>DisTu+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<=N;i++) { S[i]=0; DIST[i]=COST[v][i]; PATH[i]=v; } S[v]=1; DIST[v]=0; for(num=2;num<=N-1;num++) { u=findmin(); S[u]=1; for(i=1;i<=N;i++) if(S[i]==0 && DIST[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<=N; i++) f if(il=m) i printf("\nfrom %d to %d: ", m, 1) STACK[O= printf("%d", m); for(j=path(m, 1) P>=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<=N;i++) { if(i!=m) { printf("\nfrom %d to %d: ",m,i); STACK[0]=i; printf("%d",m); for(j=path(m,1);j>=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 编程分析: 算法思想: 确定到目的结点最短路径上最后一个点的位置,依次反序进栈,出栈时正好就 是最短路径序列了. 这种方法是把求最短长度和求序列两部分分开进行,问哪个才求哪个,而使用二维数组的 方法则是把问题结合在一起进行,全部一起求完