[Q] giup do gium ve giai thuat

[buitruongphuc]

Mô phỏng giai thuật , dùng hàm Merge Sort : nhập vào một chuổi tối đa 20 ký tự kiểu interger, sau đó in ra màn hình từng bước giải thuật đó.
(Đề bài tập lớn của trường mình, xin giúp đở
Cám ơn nhiều.)

[danceswithwolves]

đề nghị các bạn tự làm bài tập của mình, không post lên nhờ người khác giải giúp vì tài liệu về những kiến thức yêu cầu rất phổ biến. Giải thuật MergeSort có thể tìm thấy ở hầu hết giáo trình giải thuật cơ bản.

[CrazyKing]

Một bài hoàn chỉnh về Merge sort ! U nên xem đây là chương trình tham khảo thui , nếu lấy nó mà đem nộp bài thì coi chừng đụng hàng đó !!!


#include<stdio.h>
#include<conio.h>
#include<stdlib.h>
#define True 1
#define False 0
typedef struct INDEX
{
int key;
int vitri;
};
typedef struct ITEM
{
int key;
int huy;
};

int eor;
FILE *fidx,*f,*f1,*f2;
void PrintFile(FILE *f)
{
ITEM temp;
while(!feof(f))
{
if(fread(&temp,sizeof(ITEM),1,f))
// if(temp.huy!=1)
printf("%3d",temp.key);
}
}
void PrintFilefidx(FILE *f)
{
INDEX temp;
while(!feof(f))
{
if(fread(&temp,sizeof(INDEX),1,f))
printf("%3d",temp.key);
}
}
int Find (FILE *fidx,int k)
{
INDEX idx;
int m,l,mid;
long r;
m = sizeof(INDEX);
l = 0;
fseek(fidx,0,SEEK_END);
r = ftell(fidx);
while ( l<=r )
{
mid = ((l+r)/(2*m));
fseek (fidx,mid*m,SEEK_SET);
fread (&idx,sizeof(INDEX),1,fidx);
if (k==idx.key)
return idx.vitri;
else
if (k>idx.key)
l = (mid+1)*m;
else r = (mid-1)*m;
}
return 0;
}
void Add(FILE *fidx,FILE *f,ITEM data)
{
FILE *fid;
INDEX idx,idxtam;
int DaGhi=0;
fid=fopen("tam.cpp","wb");
idx.key = data.key;
fseek(fidx,0,SEEK_END);
idx.vitri = ftell(fidx);
while(!feof(f))
{
if(fread(&idxtam,sizeof(INDEX),1,f))
{
if ((idxtam.key>=idx.key)&&!DaGhi)
{
fwrite(&idx,sizeof(INDEX),1,fid);
DaGhi=1;
}
fwrite(&idxtam,sizeof(INDEX),1,fid);
}
}
if (DaGhi==0)
fwrite(&idx,sizeof(INDEX),1,fid);
fclose(fid);
remove("sl.cpp");
rename("tam.cpp","sl.cpp");
}

void AddData ()
{
ITEM data;
fidx = fopen("l.cpp","a+b");
printf("\n Nhap vao du lieu can them:");
scanf("%d",&data.key);
fwrite(&data,sizeof(ITEM),1,fidx);
fclose(fidx);
fidx = fopen("l.cpp","rb");
f = fopen("sl.cpp","rb");
Add(fidx,f,data);
fclose(f);
fclose(fidx);
}

void FindData()
{
int k;
printf("\n Nhap vao du lieu can tim:");
scanf("%d",&k);
f = fopen("sl.cpp","rb");
if (Find(f,k))
printf("\n Tim thay");
else printf("\n Khong tim thay");
fclose(f);
}

int Item(FILE *f)
{
int curpos;//Current Position
INDEX temp;
curpos=ftell(f);
if(fread(&temp,sizeof(INDEX),1,f)==0)
return 0;
fseek(f,curpos,SEEK_SET);
return 1;
}


int ItemKey(FILE *f)
{
int curpos;//Current Position
INDEX temp;
curpos=ftell(f);
fread(&temp,sizeof(INDEX),1,f);
fseek(f,curpos,SEEK_SET);
return temp.key;
}
void CopyElement(FILE *f1,FILE *f2,int &eor)
{
INDEX temp;
if(fread(&temp,sizeof(INDEX),1,f1))
fwrite(&temp,sizeof(INDEX),1,f2);
if(feof(f1))
eor=True;
else
eor=(temp.key>ItemKey(f1)?True:False);

}
void CopyRun(FILE *f1,FILE *f2)
{
eor=False;
do
{
CopyElement(f1,f2,eor);

}
while(!eor);
}
void PhanPhoi()
{
do
{
CopyRun(f,f1);
if(!feof(f))
CopyRun(f,f2);
}
while(!feof(f));

}
void MergeRun()
{
eor=False;
do
{
if(ItemKey(f1)>ItemKey(f2))
{
CopyElement(f2,f,eor);
if(eor)
CopyRun(f1,f);
}
else
{
CopyElement(f1,f,eor);
if(eor)
CopyRun(f2,f);
}
}
while(!eor);
}
int Merge()
{
int NumRun=0;
while(!feof(f1)&&!feof(f2))
{
if(Item(f2))
{
MergeRun();
NumRun++;
}
else break;
}
while(!feof(f1))
{
if(Item(f1))
{
CopyRun(f1,f);
NumRun++;
}
else break;
}
while(!feof(f2))
{
CopyRun(f2,f);
NumRun++;
}
return NumRun;
}
void NaturalMerge()
{
int i;
int r=0;
do
{
fcloseall();
f=fopen("sl.cpp","rb");
f1=fopen("sl1.cpp","wb");
f2=fopen("sl2.cpp","wb");
PhanPhoi();
fcloseall();
f=fopen("sl.cpp","wb");
f1=fopen("sl1.cpp","rb");
f2=fopen("sl2.cpp","rb");
r=Merge();
fcloseall();
}
while(r!=1);

}
void CreatFile()
{
ITEM num;
int n;
fidx=fopen("l.cpp","w+b");
if(fidx==NULL)
{
printf("\a\n Can't open file");
printf("\n Press any key to quit");
getch();
exit(1);
}
printf("\nNhap vao so phan tu:");
scanf("%d",&n);
for(int i=0;i<n;i++)
{
scanf("%d",&num.key);
fwrite(&num,sizeof(ITEM),1,fidx);
}
fclose(fidx);

}

void CreatIdx()
{
ITEM data;
INDEX idx;
f=fopen("sl.cpp","wb");
fidx=fopen("l.cpp","rb");
while (!feof(fidx))
{
if(fread(&data,sizeof(ITEM),1,fidx))
{
idx.key = data.key;
idx.vitri = ftell(fidx);
fwrite (&idx,sizeof(INDEX),1,f);
}
}
fcloseall();
NaturalMerge();
remove("sl1.cpp");
remove("sl2.cpp");
fcloseall();
}
void XoaTam()
{
int k;
ITEM x;
int vt;
printf("\n Nhap phan tu can xoa:");
scanf("%d",&k);
f = fopen("sl.cpp","rb");
vt=Find(f,k);
fclose(f);
fidx=fopen("l.cpp","r+b");
fseek(fidx,vt-sizeof(ITEM),SEEK_SET);
fread(&x,sizeof(ITEM),1,fidx);
x.huy=1;
fseek(fidx,vt-sizeof(ITEM),SEEK_SET);
fwrite(&x,sizeof(ITEM),1,fidx);
fclose(fidx);
}
void Xoa()
{
FILE *ft,*fidxt;
ITEM x;
INDEX idx;
fidx=fopen("l.cpp","rb");
f=fopen("sl.cpp","rb");
fidxt=fopen("lt.cpp","wb");
ft=fopen("slt.cpp","wb");
while(!feof(f))
{
if(fread(&idx,sizeof(INDEX),1,f))
{
fseek(fidx,idx.vitri-sizeof(ITEM),SEEK_SET);
fread(&x,sizeof(ITEM),1,fidx);
if(x.huy!=1)
{
idx.vitri=ftell(fidxt);
fwrite(&idx,sizeof(INDEX),1,ft);
fwrite(&x,sizeof(ITEM),1,fidxt);
}
}
}
fcloseall();
remove("l.cpp");
remove("sl.cpp");
rename("lt.cpp","l.cpp");
rename("slt.cpp","sl.cpp");
}

void main()
{
clrscr();
CreatFile();
fidx=fopen("l.cpp","rb");
if(fidx==NULL)
{
printf("\a\n Can't open file");
printf("\n Press any key to quit");
getch();
exit(1);
}
PrintFile(fidx);
printf("\n");
fclose(fidx);
CreatIdx();
f=fopen("sl.cpp","rb");
if(f==NULL)
{
printf("\a\n Can't open file");
printf("\n Press any key to quit");
getch();
exit(1);
}
PrintFilefidx(f);
printf("\n");
fclose(f);
/* AddData();
f=fopen("sl.cpp","rb");
if(f==NULL)
{
printf("\a\n Can't open file");
printf("\n Press any key to quit");
getch();
exit(1);
}
PrintFilefidx(f);
printf("\n");
fclose(f);
FindData();*/
XoaTam();
fidx=fopen("l.cpp","rb");
PrintFile(fidx);
printf("\n");
fclose(fidx);
Xoa();
fidx=fopen("l.cpp","rb");
PrintFile(fidx);
printf("\n");
fclose(fidx);
getch();
}


Bye , Have Fun !