bai tap cau truc du lieu va giai thuat

Tiêu đề: bai tap cau truc du lieu va giai thuat Tue Mar 16, 2010 11:35 am

//truoc khi chay cac pac lap hai thu muc o o c ten la thuNghiem va ketQua ok;
#include
#include
#include
#include
//#include
//#include
#define step 5000
FILE *f;
clock_t dau,cuoi;
char *tenFile[10]=
{ "C://thuNghiem/data00.txt",
"C://thuNghiem/data01.txt",
"C://thuNghiem/data02.txt",
"C://thuNghiem/data03.txt",
"C://thuNghiem/data04.txt",
"C://thuNghiem/data05.txt",
"C://thuNghiem/data06.txt",
"C://thuNghiem/data07.txt",
"C://thuNghiem/data08.txt",
"C://thuNghiem/data09.txt" };

void khoiTaoFile()
{
int i,j;
long int n=300000;//so phan tu cua file cai nay chay hoi lau cac pac co the giam so luongphan tu xuong de chay cho nhanh
for(i=0;i<10;++i)
{
f=fopen(tenFile[i],"wt");
if(f==NULL)
{
perror("\n\tLy Do 02: ");
exit(1);
}
fprintf(f,"%ld\n",n);
srand(time(0));
for(j=0;j fprintf(f,"%ld\n",rand());
fclose(f);
n+=step;
}
}

void Coppy(long int a[],long int b[],int n)
{
for(long int i=0;i b[i]=a[i];
}

int timKiemTT(long int a[],long int n,int x)
{
int i=0;
while ((i if(i return -1;
}

void hoanVi(long int &a,long int &b)
{
long int tam;
tam=a;
a=b;
b=tam;
}

void sapXepCTT(long int a[],long int n)
{
long int i,j,vTMin;
for(i=0;i {
vTMin=i;
for(j=i+1;j if(a[j] hoanVi(a[i],a[vTMin]);
}
}

void sapXepChTTNP(long int a[],long int n)
{
long int j,i;
for( i=1;i {
//chen phan tu a[i] vao day co thu tu a[0]..a[i-1]
long int x=a[i],l=1,r=i-1,m;
//tim vi tri chen
while(i<=r)
{
m=(r+l)/2; //tim vi tri m thich hop
if(a[j] else l=m+1;
}
for( j = i-1 ; j >=l ; j--)
a[j+1] = a[j]; // doi cac phan tu dung sau x
a[l] = x; //chen x vao;
}
}

void sapXepChTT(long int a[],long int n)
{
long int j,i;
for( i=1;i {
//chen phan tu a[i] vao day co thu tu a[0]..a[i-1]
long int x=a[i],j=i-1;
//tim vi tri chen
while((a[j]>x) && (j>=0))
{
a[j+1]=a[j]; //doi cho
j--; //di sang trai
}
a[j+1]=x; //chen x vao;
}
}

void sapXepNB(long int a[],long int n)
{
for(long int i=0;i for(long int j=n-1;j>i;--j)
if(a[j-1]>a[j]) hoanVi(a[j],a[j-1]); //doi cho
}

void main()
{
//chdir("C:\\");
//mkdir("thuNghiem");
//chdir("C:\\");
//mkdir("ketQua");
khoiTaoFile();
long int *tam,*tam1,n;
int i,j;
float t;
FILE *ketQua;
ketQua=fopen("C://ketQua/KQTK.txt","wt");
if(ketQua==NULL)
{
perror("\n\tLy Do 00: ");
getch();
exit(1);
}
for(i=0;i<10;++i)
{
f=fopen(tenFile[i],"rt");
if(f==NULL)
{
perror("\n\tLy Do 01: ");
getch();
exit(1);
}
printf("file thu %d\n",i+1);
fscanf(f,"%ld",&n);
fprintf(ketQua,"\n\tFILE THU %d \n N=%ld",i+1,n);
printf("co %ld phan tu\n",n);
tam=(long int *)malloc(n*sizeof(long int));
tam1=(long int *)malloc(n*sizeof(long int));
for(j=0;j fscanf(f,"%ld",tam+j);
printf("loaded file thu %d\n",i+1);
//kq=timKiemTT(tam,n,x);
//thoi gian tim kiem bang phuong phap chon tt
Coppy(tam,tam1,n); // sao luu mang tam vao tam 1
dau=clock();
sapXepCTT(tam,n);
cuoi=clock();
t=(float)(cuoi-dau)/CLOCKS_PER_SEC;
fprintf(ketQua,"\nTTCTT t%d = %0.3f s",i+1,t);
printf("sap xep bang phuong phap CTT mat %0.2f",t);
//thoi gian sap xep bang phuong phap chen truc tiep
Coppy(tam1,tam,n); // sao luu mang tam1 vao tam
dau=clock();
sapXepChTT(tam,n);
cuoi=clock();
t=(float)(cuoi-dau)/CLOCKS_PER_SEC;
fprintf(ketQua,"\nTTChTT t%d = %0.3f s",i+1,t);
printf("\nsap xep bang phuong phap ChTT mat %0.2f",t);
//thoi gian sap xep bang phuong pap chen tt viet bang pp nhi phan
Coppy(tam1,tam,n); // sao luu mang tam1 vao tam
dau=clock();
sapXepChTTNP(tam,n);
cuoi=clock();
t=(float)(cuoi-dau)/CLOCKS_PER_SEC;
fprintf(ketQua,"\nTTChTTNP t%d = %0.3f s",i+1,t);
printf("\nsap xep bang phuong phap ChTTNP mat %0.2f",t);
//thoi gian sap xep bang pp noi bot
Coppy(tam1,tam,n); // sao luu mang tam 1 vao tam
dau=clock();
sapXepNB(tam,n);
cuoi=clock();
t=(float)(cuoi-dau)/CLOCKS_PER_SEC;
fprintf(ketQua,"\nTTNB t%d = %0.3f s\n",i+1,t);
printf("\nsap xep bang phuong phap NP mat %0.2f",t);

free(tam1);
free(tam);
fclose(f);
printf("\nxong file thu %d\n\n",i+1);
}
fclose(ketQua);
printf("\n\tTHANH CONG");
getch();
} Smile

//hom nay noi hung len post len day may bai tap linh tinh pac nao thay pac nao thay khong vua mac thi cu gop y