sắp xếp từ điển trong lập trình c/c++,tạo 1 mảng 1 chiều chứa các từ tiếng anh lấy từ file http://blackberryvietnam.net/threads/du-lieu-tu-dien-cho-ung-dung-ddict.897/ . sau đó dùng các thuật toán sắp xếp để sắp xếp mảng trên theo thứ tự và so sánh thời gian thực hiện các thuật toán.
lưu ý:để thuận tiện việc thao tác, chỉ lấy các từ đơn dưới 15 kí tự, các từ tiếng anh được tách ra từ dữ liệu từ điển việt-anh. (không phải từ điển anh-việt).
trong code dưới đây, dữ liệu nguồn là file va.dd, danh sách các từ tiếng anh lọc ra được và sắp xếp được đưa vào file av.dd.
*đây là bài tập đồ án của thầy Toàn UIT, dưới đây chỉ là các code sắp xếp, phần main() thì các bạn chỉnh sửa lại cho phù hợp với yêu cầu của đồ án, phần main() là ý kiến sáng tạo để hoàn thành bài tập, tôi chỉ viết đơn giản như vậy để chạy thử xem code sắp xếp có chạy đúng hay không thôi.
#include<iostream>
#include<time.h>
using namespace std;
void bang(char *a,char *b);
void doi(char *a,char *b);
//các thuật toán sắp xếp
void interchange(char s[][15],int k);
void select(char s[][15],int n);
void bubble(char s[][15],int n);
void insert(char s[][15],int n);
void insertbinary(char s3[][15],int k);
void shacker(char s[][15],int n);
void shell(char s[][15],int n);
void quick(char s[][15],int l,int r);
void heap(char s[][15],int n);
void merge(char a[][15],int n);
void main()
{
//lấy các từ tiếng anh đưa vào chuỗi s3
FILE *t,*t1;
char s[300];
char *s1,*s2,s3[50000][15];
t = fopen("E:\\va.dd","r");
t1=fopen("E:\\av.dd","w+");
while(fgets(s,300,t)!=NULL)
{
s1=strstr(s,"##");
if(s1!=NULL)
{
s2=strstr(s1,"|-");
if(s2!=NULL && strlen(s2)<15) fputs(s2+2,t1);
}
}
rewind(t1);
int k=0;
while(fgets(s,15,t1)!=NULL)
{
strcpy(s3[k],s);
k++;
}
int n=k;
//sắp xếp
cout<<"\ndang sap xep...";
double tg;
double a=clock();
shell(s3,k);//kiểu sắp xếp. thay bằng các kiểu sắp xếp khác nhau để so sanh thời gian
//đang dùng shell sort..
double b=clock();
cout<<"\nda xep xong!\nthoi gian sap xep la: "<<(b-a)/1000<<" giay.";
rewind(t1);
for(int i=0;i<k;i++) fputs(s3[i],t1);
fcloseall();
system("pause");
}
void chinh(char s[][15],int l,int r)
{
int j=2*l+1;
while(j<=r)
{
if(j<r && stricmp(s[j],s[j+1])<0) j++;
if(stricmp(s[l],s[j])>=0) return;
else
{
doi(s[l],s[j]);
l=j;
j=2*l+1;
}
}
}
void taoheap(char s[][15],int n)
{
int l=n/2-1;
while(l>=0)
{
chinh(s,l,n-1);
l--;
}
}
void heap(char s[][15],int n)
{
int r=n-1;
taoheap(s,n);
while(r>0)
{
doi(s[0],s[r]);
r--;
if(r>0) chinh(s,0,r);
}
}
void quick(char s[][15],int l,int r)
{
int i=l,j=r,m=(l+r)/2;
while(i<=j)
{
while(stricmp(s[i],s[m])<0) i++;
while(stricmp(s[j],s[m])>0) j--;
if(i<=j)
{
doi(s[i],s[j]);
i++;j--;
}
}
if(i<r) quick(s,i,r);
if(j>l) quick(s,l,j);
}
void shacker(char s[][15],int n)
{
int l=0,r=n-1,k=n-1,i;
while(l<r)
{
for(i=r;i>l;i--)
if(stricmp(s[i],s[i-1])<0){ doi(s[i],s[i-1]);k=i;}
l=k;
for(i=l;i<r;i++)
if(stricmp(s[i],s[i+1])>0){doi(s[i],s[i+1]);k=i;}
r=k;
}
}
void bubble(char s[][15],int n)
{
for(int i=0;i<n-1;i++)
for(int j=n-1;j>i;j--)
if(stricmp(s[j],s[j-1])<0) doi(s[j],s[j-1]);
}
void insert(char s[][15],int n)
{
for(int i=1;i<n;i++)
{
char x[15];
bang(x,s[i]);
int j=i-1;
while(stricmp(s[j],x)>0 && j>=0)
{
bang(s[j+1],s[j]);
j--;
}
bang(s[j+1],x);
}
}
void interchange(char s[][15],int k)
{
for(int i=0;i<k-1;i++)
for(int j=i+1;j<k;j++)
if(stricmp(s[i],s[j])>0) doi(s[i],s[j]);
}
void select(char s[][15],int n)
{
int dem=0;
for(int i=0;i<n-1;i++)
{
int m=i;
for(int j=i+1;j<n;j++)
if(stricmp(s[m],s[j])>0) m=j;
doi(s[i],s[m]);
}
}
void shell(char s[][15],int n)
{
int h[10]={10129,1678,437,256,134,62,5,3,2,1},k=10;
int i,j,len,step;
char x[15];
for(step=0;step<k;step++)
{
len=h[step];
for(i=len;i<n;i++)
{
bang(x,s[i]);
j=i-len;
while(j>=0 && stricmp(s[j],x)>0)
{
bang(s[j+len],s[j]);
j=j-len;
}
bang(s[j+len],x);
}
}
}
void insertbinary(char s3[][15],int k)
{
//sắp xếp chèn nhị phân
int l,r,m,i,j,dem=0;
char x[15];
for(i=1;i<k;i++)
{
l=0;r=i-1;
for(j=0;j<strlen(s3[i]);j++) x[j]=s3[i][j];x[j]='\0';
while(l<=r)
{
m=(l+r)/2;
if(stricmp(x,s3[m])<0) r=m-1;
else l=m+1;
}
for(j=i;j>l;j--) bang(s3[j],s3[j-1]);
bang(s3[l],x);
}
}
void bang(char *a,char *b)//phép gán
{
int i;
for(i=0;i<strlen(b);i++) a[i]=b[i];
a[i]='\0';
}
void doi(char *a,char *b)//hoán đổi vị trí
{
int i;
char c[300];
for(i=0;i<strlen(a);i++) c[i]=a[i];c[i]='\0';
for(i=0;i<strlen(b);i++) a[i]=b[i];a[i]='\0';
for(i=0;i<strlen(c);i++) b[i]=c[i];b[i]='\0';
}
void phanphoi(char a[][15],int n,char b[][15],int &nb,char c[][15],int &nc,int k)
{
int pa,pb,pc,i;
pa=pb=pc=0;
while(pa<n)
{
i=0;
while(i<k && pa<n)
{
bang(b[pb++],a[pa++]);
i++;
}
i=0;
while(i<k && pa<n)
{
bang(c[pc++],a[pa++]);
i++;
}
}
nb=pb;nc=pc;
}
int min(int a,int b)
{
if(a<b) return a;
return b;
}
void tron(char a[][15],int n,char b[][15],int nb,char c[][15],int nc,int k)
{
int pa,pb,pc,kb,kc,ib,ic;
pa=pb=pc=ib=ic=0;
while(nb>0 && nc>0)
{
kb=min(k,nb);
kc=min(k,nc);
if(stricmp(b[pb+ib],c[pc+ic])<=0)
{
bang(a[pa++],b[pb+ib]);
ib++;
if(ib==kb)
{
while(ic<kc)
{
bang(a[pa++],c[pc+ic]);
ic++;
}
pb+=kb;pc+=kc;nb-=kb;nc-=kc;
ib=ic=0;
}
}
else
{
bang(a[pa++],c[pc+ic]);
ic++;
if(ic==kc)
{
while(ib<kb)
{
bang(a[pa++],b[pb+ib]);
ib++;
}
pb+=kb;pc+=kc;nb-=kb;nc-=kc;
ib=ic=0;
}
}
}
}
void merge(char a[][15],int n)
{
char (*b)[15]=new char[50000][15];
char (*c)[15]=new char[50000][15];
int nb,nc,k=1;
while(k<n)
{
phanphoi(a,n,b,nb,c,nc,k);
tron(a,n,b,nb,c,nc,k);
k*=2;
}
delete [](*b);
delete [](*c);
}
file sắp xếp từ điển
//tác giả code: Trần Khánh Toàn - ĐH CNTT
.png)
.png)
.png)
.png)
