# Đề tài: Giải thuật MergeSort bằng DSLK

1. ## Giải thuật MergeSort bằng DSLK

Bạn nào hãy giải thích giúp mình xem đã sai chổ nào nhé. (Ở giải thuật MergeSort còn mấy còn mấy cái kia thì đã ổn). Thank you very much.
Code:
```#include "khaiBao.h"
#include <iostream>
using namespace std;
//cai dat constructor
DSLKD::DSLKD()
{
this->dau=this->cuoi=NULL;
}
//cai dat xinNut
TRONUT DSLKD::xinNut(kieuDL duLieu)
{
TRONUT p;
//xin vung nho
p=new NUT;
if(p==NULL)
{
cout<<"Khong du bo nho ! ";
exit(1);
}
p->duLieu=duLieu;
p->tiep=NULL;
return p;
}
//cai dat themCuoi
void DSLKD::themCuoi(TRONUT p)
{
if(this->dau==NULL) //DS rong
this->dau=this->cuoi=p;
else //DS da co nut
{
this->cuoi->tiep=p;
this->cuoi=p;
}
}
//cai dat taoDS
void DSLKD::taoDS()
{
kieuDL duLieu;
cout<<"Nhap du lieu";
cin>>duLieu;
while (duLieu!=0)
{
TRONUT p=xinNut(duLieu);
this->themCuoi(p);
cout<<"Nhap du lieu :";
cin>>duLieu;
}
}
//cai dat duyetDS
void DSLKD::duyetDS()
{
TRONUT p=this->dau;
while(p!=NULL)
{
cout<<"Dia chi : "<<p<<"\t"
<<"Du lieu : "<<p->duLieu<<"\t"
<<"Dia chi tiep : "<<p->tiep<<"\n";
p=p->tiep;
}
}
//cai dat huyDS
void DSLKD::huyDS()
{
TRONUT p=this->dau;
while(this->dau!=NULL)
{
this->dau=this->dau->tiep;
delete p;
p=this->dau;
}
}
//cai dat destructor
DSLKD::~DSLKD()
{
this->huyDS();
}
//cai dat timNut
TRONUT DSLKD::timNut(kieuDL duLieu)
{
TRONUT p;
p=this->dau;
while(p!=NULL) //chua di het
{
if(p->duLieu==duLieu)
return p; //tim thay
else
p=p->tiep;
}
return p; //khong tim thay
}
//cai dat ham xoaNut
/*void DSLKD::xoaNut(TRONUT p)
{
if(p==this->dau) //xoa nut o dau
this->dau=this->dau->tiep;
else
{
//tim nut truocp
TRONUT truocp=this->dau;
while(truocp->tiep!=p)
truocp=truocp->tiep;
if(p==this->cuoi)
this->cuoi=truocp;
this->cuoi->tiep=NULL;
}
delete p;
}*/
//cai dat phuong thuc sap xep theo noi dung
void DSLKD::sXND()
{
TRONUT min;
TRONUT p;
TRONUT q;
for(p=this->dau;p->tiep;p=p->tiep)
{
min=p;
for(q=p->tiep;q;q=q->tiep)
if(q->duLieu <min->duLieu)
min=q;
//hoan vi
hoanVi(min->duLieu, p->duLieu);
}
}
//cai dat ham hoan vi
void DSLKD::hoanVi(kieuDL &a, kieuDL &b)
{
kieuDL tam;
tam=a;
a=b;
b=tam;
}

/////////////////////////////////////////////////////////////////////////////////////
void DSLKD::sXMergeSort()
{
DSLKD dS, dS1, dS2;
if(this->dau == this->cuoi)
return;
dS1.dau = dS1.cuoi = NULL;
dS2.dau = dS2.cuoi = NULL;
DistributeDS(dS, dS1, dS2);
dS1.sXMergeSort();
dS2.sXMergeSort();
mergeDS(dS, dS1, dS2);
}
void DSLKD::DistributeDS(DSLKD &dS, DSLKD &dS1, DSLKD &dS2)
{
TRONUT p;
//DSLKD dS, dS1, dS2;
do
{
p = this->dau;
this->dau = p->tiep;
p->tiep = NULL;
dS1.themCuoi(p);
}
while((this->dau) && (p->duLieu <= this->dau ->duLieu));
if(this->dau)
DistributeDS(dS, dS2, dS1);
else
this->cuoi = NULL;
}
void DSLKD::mergeDS(DSLKD &dS, DSLKD &dS1, DSLKD &dS2)
{
TRONUT p;
//DSLKD dS, dS1, dS2;
while((dS1.dau) && (dS2.dau))
{
if(dS1.dau->duLieu <= dS2.dau ->duLieu)
{
p = dS1.dau;
dS1.dau = p->tiep;
}
else
{
p = dS2.dau;
dS2.dau = p->tiep;
}
p->tiep = NULL;
dS.themCuoi(p);
}
if(dS1.dau)
{
this->cuoi->tiep = dS1.dau;
this->cuoi = dS1.cuoi;
}
else if(dS2.dau)
{
this->cuoi->tiep = dS2.dau;
this->cuoi = dS2.cuoi;
}
//dS1.dau = NULL;
//dS1.cuoi = NULL;
//dS2.dau = NULL;
//dS2.cuoi = NULL;
}```

2. Thành viên nhiệt tình
Ngày gia nhập
04 2008
Bài viết
336
cậu đừng chép lại code trong sách 1 cách máy móc, trong sách viết = C nên có 3 đối số, còn đây là C++ viết theo class nên giảm bớt đi được 1 đối số.

3. Tôi không có chép trong sách. Vì tôi mới học C++, mong bạn chỉ giúp mình. Mình rất muốn học hỏi.

4. Thành viên nhiệt tình
Ngày gia nhập
04 2008
Bài viết
336
phần này trên lớp mình cũng đang được dạy và thấy code cậu giống trong sách khá nhiều nên nói vậy, nếu có sai thì bạn bỏ qua cho.
Trở lại vấn đề của bạn, ngay hàm sXMergeSort()
Code:
```void DSLKD::sXMergeSort()
{
DSLKD dS, dS1, dS2;
if(this->dau == this->cuoi)
return;
dS1.dau = dS1.cuoi = NULL;
dS2.dau = dS2.cuoi = NULL;
DistributeDS(dS, dS1, dS2);
dS1.sXMergeSort();
dS2.sXMergeSort();
mergeDS(dS, dS1, dS2);
}```
giả sử code DistributeDS của bạn đúng 100% thì chạy vẫn sai vì bạn chưa gán dS cho cái gì cả mà đã Distribute nó ...
tương tự cho mergeDS.

thay vì như vậy bạn hãy xem *this là dS và bỏ bớt tham số dS kia đi

5. Cám ơn bạn đã góp ý, mình cố gắng xem lại, mình cũng thấy có vấn đề, nhưng không biết chổ nào. Vì mình cũng hổng kiến thức nhiều. Mình làm lại nếu có gì bạn sẽ giúp mình nhé.

6. ## Giải thuật MergeSort bằng DSLK

đoạn code này mình viết, bạn xem được không nhé:
PHP Code:
``` void DSLKD::distributeDS(DSLKD &ds1, DSLKD &ds2) {     TRONUT p;     do     {         p=this->dau;         this->dau=p->tiep;         p->tiep=NULL;         ds1.themCuoi(p);     }while((this->dau) && (p->duLieu<=this->dau->duLieu));     if(this->dau)         this->distributeDS(ds2,ds1);     else         this->cuoi=NULL; } void DSLKD::tron2DS(DSLKD &ds1, DSLKD &ds2) {     TRONUT p;     while((ds1.dau!=NULL) && (ds2.dau!=NULL))     {         if(ds1.dau->duLieu <= ds2.dau->duLieu)         {             p=ds1.dau;             ds1.dau=ds1.dau->tiep;         }         else         {             p=ds2.dau;             ds2.dau=ds2.dau->tiep;         }         p->tiep=NULL;         this->themCuoi(p);     }     if(ds1.dau)     {         p=ds1.dau;         p->tiep=NULL;         this->themCuoi(p);     }     else         if(ds2.dau)         {             p=ds2.dau;             p->tiep=NULL;             this->themCuoi(p);         } } void DSLKD::tronTN() {     DSLKD *ds1, *ds2;     ds1= new DSLKD;     ds2= new DSLKD;     if(this->dau==this->cuoi)         return;     this->distributeDS(*(ds1),*(ds2));     ds1->tronTN();     ds2->tronTN();     this->tron2DS(*(ds1),*(ds2)); }  ```

#### Quyền hạn của bạn

• Bạn không thể gửi đề tài mới
• Bạn không thể gửi bài trả lời
• Bạn không thể gửi các đính kèm
• Bạn không thể chỉnh sửa bài viết của bạn