Từ 1 tới 6 trên tổng số 6 kết quả

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

  1. #1
    Ngày gia nhập
    09 2008
    Nơi ở
    Thanh Pho Hồ Chi Minh
    Bài viết
    8

    Mặc định 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;
    }
    Con đường IT lắm gian nan.

  2. #2
    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ố.
    code ra gió bão

  3. #3
    Ngày gia nhập
    09 2008
    Nơi ở
    Thanh Pho Hồ Chi Minh
    Bài viết
    8

    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.
    Con đường IT lắm gian nan.

  4. #4
    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
    code ra gió bão

  5. #5
    Ngày gia nhập
    09 2008
    Nơi ở
    Thanh Pho Hồ Chi Minh
    Bài viết
    8

    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é.
    Con đường IT lắm gian nan.

  6. #6
    Ngày gia nhập
    03 2009
    Nơi ở
    C:\Windows\system32
    Bài viết
    18

    Mặc định 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 &ds1DSLKD &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 &ds1DSLKD &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));


Các đề tài tương tự

  1. Cấu trúc dữ liệu Mergesort bằng DSLK kép - Lỗi Mergesort.exe or any of the DLLs it has loaded?
    Gửi bởi xjke trong diễn đàn Thắc mắc CTDL & Giải thuật
    Trả lời: 0
    Bài viết cuối: 07-12-2011, 03:30 AM
  2. DSLK các giải thuật sắp xếp và tìm kiếm
    Gửi bởi soda_chanhmuoi trong diễn đàn Thủ thuật, Tutorials CTDL & Giải thuật
    Trả lời: 6
    Bài viết cuối: 15-11-2011, 10:31 AM
  3. Tìm source thuật toán Polyphase MergeSort ?
    Gửi bởi Timberlake520 trong diễn đàn Thắc mắc lập trình C/C++/C++0x
    Trả lời: 2
    Bài viết cuối: 03-05-2011, 05:00 PM
  4. Tìm source thuật toán Polyphase MergeSort ?
    Gửi bởi Timberlake520 trong diễn đàn Nhập môn lập trình C/C++
    Trả lời: 0
    Bài viết cuối: 03-05-2011, 12:29 PM
  5. Các giải thuật sắp xếp trong DSLK. Giúp mình với?
    Gửi bởi thai.co trong diễn đàn Thắc mắc lập trình C/C++/C++0x
    Trả lời: 6
    Bài viết cuối: 26-10-2010, 10:48 PM

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