算法程序设计一,比较归并分类和快速分类算法思想:结合课本中的算法结构,分别计算在数据集相同且分别为随机数,非降序,非增序情况下两种算法所需的时间.数据集为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;
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;
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},
{-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]];
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
编程分析:
算法思想,确定到目的结点最短路径上最后一个点的位置,依次反序进栈,出栈时正好就是最短路径序列了.
这种方法是把求最短长度和求序列两部分分开进行,问哪个才求哪个,而使用二维数组的方法则是把问题结合在一起进行,全部一起求完.
#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;
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;
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},
{-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]];
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
编程分析:
算法思想,确定到目的结点最短路径上最后一个点的位置,依次反序进栈,出栈时正好就是最短路径序列了.
这种方法是把求最短长度和求序列两部分分开进行,问哪个才求哪个,而使用二维数组的方法则是把问题结合在一起进行,全部一起求完.
