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

Đề tài: Lỗi xóa DSLK sau khi xử lí DSLK trong hàm.

  1. #1
    Ngày gia nhập
    11 2012
    Bài viết
    14

    Mặc định Lỗi xóa DSLK sau khi xử lí DSLK trong hàm.

    Đầu tiên là source code

    Code:
    #include <iostream>
    using namespace std;
    
    struct NODE
    {
    	short pos;
    	NODE *pNext;
    };
    
    struct LIST
    {
    	NODE *pHead;
    	NODE *pTail;
    };
    
    bool is_Empty(LIST L);
    void Init(LIST &L);
    NODE *create_Node(int pos);
    bool add_Tail(LIST &L, short pos);
    void remove_Node(LIST &L, short pos);
    void remove_List(LIST &L);
    void print_List(LIST L);
    void Josephus(LIST L, short M);
    
    int main()
    {
    	LIST L;
    	Init(L);
    	short N, M;
    	
    	cout << "How many victims are there? ";
    	cin >> N;
    	cout << "Which one do you want to kill first? ";
    	cin >> M;
    	for (int i = 1; i <= N; i++)
    		add_Tail(L, i);
    	Josephus(L, M);
    	remove_List(L);
    	return 0;
    }
    
    bool is_Empty(LIST L)
    {
    	return L.pHead == NULL;
    }
    
    void Init(LIST &L)
    {
    	L.pHead = L.pTail = NULL;
    }
    
    NODE *create_Node(int pos)
    {
    	NODE *pNode = new NODE;
    	if (pNode == NULL)
    		return NULL;
    	pNode->pos = pos;
    	pNode->pNext = NULL;
    	return pNode;
    }
    
    bool add_Tail(LIST &L, short pos)
    {
    	NODE *pNode = create_Node(pos);
    	if (pNode == NULL)
    		return false;
    	if (L.pHead == NULL)
    	{
    		L.pHead = L.pTail = pNode;
    		L.pTail->pNext = L.pHead;
    	}
    	else
    	{
    		pNode->pNext = L.pHead;
    		L.pTail->pNext = pNode;
    		L.pTail = pNode;
    	}
    	return true;
    }
    
    void remove_Node(LIST &L, short pos)
    {
    	NODE *pNode = L.pHead;
    	if (pNode->pNext == pNode)
    		remove_List(L);
    	while ((pNode->pNext)->pos != pos)
    		pNode = pNode->pNext;
    	NODE *pTemp = pNode->pNext;
    	pNode->pNext = pTemp->pNext;
    	if (pTemp == L.pHead)
    	{
    		L.pHead = pTemp->pNext;
    		L.pTail = pNode;
    	}
    	if (pTemp == L.pTail)
    	{
    		L.pTail = pNode;
    	}
    	pTemp = NULL;
    	delete pTemp;
    }
    
    void remove_List(LIST &L)
    {
    	NODE *pNode;
    	while (L.pHead != L.pTail)
    	{
    		pNode = L.pHead;
    		L.pHead = L.pHead->pNext;
    		delete pNode;
    	}
    	L.pHead = NULL;
    	delete L.pHead;	
    }
    
    void print_List(LIST L)
    {
    	cout << L.pHead->pos << " ";
    	NODE *pNode = L.pHead->pNext;
    	while (pNode != L.pHead)
    	{
    		cout << pNode->pos << " ";
    		pNode = pNode->pNext;
    	}
    }
    
    void Josephus(LIST L, short M)
    {
    	LIST Result;
    	Init(Result);
    	NODE *pTemp;
    	NODE *pNode = L.pHead;
    	while (!is_Empty(L))
    	{
    		for (int i = 1; i < M; i++)
    			pNode = pNode->pNext;
    		pTemp = pNode;
    		add_Tail(Result, pNode->pos);
    		remove_Node(L, pNode->pos);
    		pNode = pTemp->pNext;
    	}
    	print_List(Result);
    	remove_List(Result);
    }
    Mình viết code để giải bài toán Josephus. Vấn đề ở đây là sau khi xử lý hàm Josephus() xong, thì mình ko thể nào chạy lệnh remove_List(L) được. Các bạn giúp mình với. Cảm ơn các bạn trước nhé.

    Đây là đề bài toán Josephus:
    Có N người quyết định đi tự sát tập thể bằng cách đứng trong vòng tròn và giết người thứ M quanh vòng tròn, thu hẹp hàng ngũ lại khi lần lượt từng người ngã khỏi vòng tròn. Vấn đề tìm ra thứ tự từng người bị giết. VD: N = 9, M = 5. Output: 5 1 7 4 3 6 9 2 8. Viết chương trình giải quyết bài toán trên.

  2. #2
    Ngày gia nhập
    01 2013
    Bài viết
    1,479

    Bài này dùng DSLK vòng (và đơn, vì đi theo 1 chiều) mới đúng.
    p/s: Nếu đề bài yêu cầu bạn dùng DSLK vòng thì hãy dùng, vì có thuật O(mlogn) cho bài này rồi.

  3. #3
    Ngày gia nhập
    11 2012
    Bài viết
    14

    Mình thử DSLK kép nhưng ghét là khi DSLK chỉ còn 1 phần tử thì xóa ko dc nữa :(
    bạn có thể coi giùm mình, tại sao trên kia, mình ko thể chạy dòng lệnh remove_List(L) trong hàm main() được không?

  4. #4
    Ngày gia nhập
    01 2013
    Bài viết
    1,479

    Trích dẫn Nguyên bản được gửi bởi darkboys Xem bài viết
    Mình thử DSLK kép nhưng ghét là khi DSLK chỉ còn 1 phần tử thì xóa ko dc nữa :(
    bạn có thể coi giùm mình, tại sao trên kia, mình ko thể chạy dòng lệnh remove_List(L) trong hàm main() được không?
    Vấn đề là bạn sai ngay từ đầu khi chọn CTDL, bài này phải dùng DSLK vòng (đi theo vòng tròn mà).

  5. #5
    Ngày gia nhập
    11 2012
    Bài viết
    14

    Mình đã làm lại xong bài này, dùng DSLK vòng như bạn prog10 nói.. Nhưng mình cảm thấy ko hài lòng về cách sử dụng cách giải này vì tốn quá nhiều bộ nhớ. Mấy bác có thể gợi ý giùm e thuật giải khác được không. Bạn prog10 hình như có nói bài này có thuật toán với chi phí là O(mlogn). Bạn cho mình biết ý tưởng nhé.

    Đây là bài mới làm lại của mình..
    Code:
    #include <iostream>
    using namespace std;
    
    struct NODE
    {
    	int pos;
    	NODE *pNext;
    };
    
    struct LIST
    {
    	NODE *pHead;
    	NODE *pTail;
    };
    
    void Init(LIST &L);
    bool add_Tail(LIST &L, int value);
    void remove_List(LIST &L);
    void print_List(const LIST &L);
    void remove_Node(LIST &L, int pos);
    void copy_List(LIST &Copy, const LIST &L);
    void Josephus(const LIST &L, int M);
    bool is_Empty(const LIST &L);
    
    int main()
    {
    	LIST L;
    	Init(L);
    	int N, M;
    	
    	cout << "How many victims are there? ";
    	cin >> N;
    	cout << "Which one do you want to kill first? ";
    	cin >> M;
    	
    	for (int i = 1; i <= N; i++)
    		add_Tail(L, i);
    	cout << "Result: " << endl;
    	Josephus(L, M);
    	remove_List(L);
    	return 0;
    }
    
    bool is_Empty(const LIST &L)
    {
    	return (L.pHead == NULL);
    }
    
    void Init(LIST &L)
    {
    	L.pHead = L.pTail = NULL;
    }
    
    NODE *create_Node(int value)
    {
    	NODE *pNode = new NODE;
    	if (pNode == NULL)
    		return NULL;
    	pNode->pos = value;
    	pNode->pNext = NULL;
    	return pNode;
    }
    
    bool add_Tail(LIST &L, int value)
    {
    	NODE *pNode = create_Node(value);
    	if (pNode == NULL)
    		return false;
    	if (L.pHead == NULL)
    		L.pHead = L.pTail = pNode;
    	else
    	{
    		L.pTail->pNext = pNode;
    		L.pTail = pNode;
    		L.pTail->pNext = L.pHead;
    	}
    	return true;
    }
    
    void remove_List(LIST &L)
    {
    	NODE *pNode;
    	while (L.pHead != L.pTail)
    	{
    		pNode = L.pHead;
    		L.pHead = L.pHead->pNext;
    		delete pNode;
    	}
    	delete L.pTail;
    	L.pHead = L.pTail = NULL;
    }
    
    void print_List(const LIST &L)
    {
    	NODE *pNode = L.pHead;
    	do
    	{
    		cout << pNode->pos << " ";
    		pNode = pNode->pNext;
    	}
    	while (pNode != L.pHead);
    }
    
    void remove_Node(LIST &L, int pos)
    {
    	NODE *pNode = L.pHead;
    	if (pNode->pNext == pNode)
    	{
    		remove_List(L);
    		return;
    	}
    	while ((pNode->pNext)->pos != pos)
    		pNode = pNode->pNext;
    	NODE *pTemp = pNode->pNext;
    	pNode->pNext = pTemp->pNext;
    	if (pTemp == L.pHead)
    	{
    		L.pHead = pTemp->pNext;
    		L.pTail = pNode;
    	}
    	if (pTemp == L.pTail)
    	{
    		L.pTail = pNode;
    	}
    	pTemp = NULL;
    	delete pTemp;
    }
    
    void copy_List(LIST &Copy, const LIST &L)
    {
    	NODE *pNode = L.pHead;
    	while (pNode != L.pTail)
    	{
    		add_Tail(Copy, pNode->pos);
    		pNode = pNode->pNext;
    	}
    	add_Tail(Copy, L.pTail->pos);
    }
    
    void Josephus(const LIST &L, int M)
    {
    	LIST Cpy;
    	Init(Cpy);
    	LIST Result;
    	Init(Result);
    	copy_List(Cpy, L);
    	NODE *pNode = Cpy.pHead;
    	int position;
    	
    	while (!is_Empty(Cpy))
    	{
    		for (int i = 1; i < M; i++)
    			pNode = pNode->pNext;
    		position = pNode->pos;
    		pNode = pNode->pNext;
    		add_Tail(Result, position);
    		remove_Node(Cpy, position);
    	}
    	print_List(Result);
    	remove_List(Result);
    }

  6. #6
    Ngày gia nhập
    01 2013
    Bài viết
    1,479

    Mặc định Lỗi xóa DSLK sau khi xử lí DSLK trong hàm.

    DS vòng chỉ có mỗi *pEntry mà thôi => sai về mặt khái niệm.
    Bài Josephus là cứ qua M node thì xóa node thứ M, ta có thể giải quyết thế này:
    - Sử dụng node giả dẫn thẳng vào *pEntry (bạn gọi là *pHead đấy) là node bắt đầu (*pStart); từ pStart sẽ đi đúng qua M-1 node, dẫn thẳng đến node thứ M-1, lưu lại node này vào *pStart.
    - Từ pStart dẫn thẳng qua node phía sau node M, del node thứ M đi và tiếp tục.
    (Vấn đề nằm ở chỗ khi node *pEntry bị xóa thì phải redirect cho khéo, dùng DS vòng đôi cũng đc, nhầm)

    Còn thuật O(mlogn):
    Gợi ý: Hãy "bẻ" thẳng vòng tròn ra và bắt đầu đếm (và xóa), chỉ có cách đó thì mới tìm ra quy luật mà thôi

  7. #7
    Ngày gia nhập
    12 2012
    Nơi ở
    TIN5A - UNETI
    Bài viết
    167

    mình có bài gần giống bạn xem thử
    PHP Code:

                                
    //BAI TOAN TANG QUA LUU NIEM

    #include <iostream>
    #include<conio.h>
    using namespace std;
    //---------------------------------
    struct Node
    {
        
    int vitri;
        
    Node *next;
    };
    //----------------------------------
    struct DanhSachVong
    {
        
    Node *dau;
        
    Node *duoi;
    };
    //khoi tao
    void KhoiTao(DanhSachVong &ds)
    {
        
    ds.dau ds.duoi NULL;
    }
    //tao nut
    NodeTaoNut(int vt)
    {
        
    Nodep;
        
    = new Node;
        
    p->vitri vt;
        return 
    p;
    }
    //chen vao cuoi danh sach
    void ChenVaoCuoi(DanhSachVong &ds,int vt)
    {
        
    Node *p;
        
    TaoNut(vt);
        if(
    ds.dau==NULL)
        {
            
    ds.dau ds.duoi p;
        }
        else
        {
            
    ds.duoi->next p;
            
    p->next ds.dau;
            
    ds.duoi p;
        }
    }
    //hien thi danh sach
    void HienThi(DanhSachVong ds)
    {
        if(
    ds.dau==NULLcout<<"\n => Danh sach rong ";
        else
        {
            if(
    ds.dau==ds.duoicout<<ds.dau->vitri;
            else
            {
                
    Node *p;
                
    ds.dau;
                do{
                    
    cout<<p->vitri<<"   ";
                    
    p->next;
                }while(
    p!=ds.dau);
            }
        }
    }
    //xoa nut co vi tri la x
    void XoaNut(DanhSachVong &ds,int vt)
    {
        if(
    ds.dau==NULLcout<<"\n => Danh sach rong";
        else
        {
            if(
    ds.dau==ds.duoicout<<"\n => Bai toan da duoc giai ";
            else
            {
                
    Node *p;
                
    //neu chi co hai nut
                
    if(ds.dau->next==ds.duoi)
                {
                    if(
    ds.dau->vitri==vt)
                    {
                        
    ds.dau;
                        
    ds.dau ds.duoi;
                        
    delete p;
                    }
                    else
                    {
                        if(
    ds.duoi->vitri==vt)
                        {
                            
    ds.duoi;
                            
    ds.dau ds.duoi;
                            
    delete p;
                        }
                    }
                }
                
    //tu 3 nut tro len
                
    else
                {
                    
    //neu o dau danh sach
                    
    if(ds.dau->vitri==vt)
                    {
                        
    ds.dau;
                        
    ds.dau ds.dau->next;
                        
    delete p;
                        
    ds.duoi->nextds.dau;
                    }
                    
    //neu o cuoi hoac o giua danh sach
                    
    else
                    {
                        
    //neu o cuoi danh sach
                        
    if(ds.duoi->vitri==vt)
                        {
                            
    ds.duoi;
                            
    Node *m;
                            
    ds.dau;
                            while(
    m->next!=pm->next;
                            
    ds.duoi m;
                            
    delete p;
                            
    ds.duoi->next ds.dau;
                        }
                        
    //neu o giua danh sach
                        
    else
                        {
                            
    Node *m,*n;
                            
    ds.dau;
                            while(
    m->next->vitri!=vtm->next;
                            
    m->next;
                            
    p->next;
                            
    delete p;
                            
    m->next n;
                        }
                    }
                }
            }
        }
    }
    //ham chinh
    int main()
    {
        
    int songuoi;//so nguoi tham gia tro choi
        
    cout<<"\n - So nguoi tham gia tro choi: ";
        
    cin>>songuoi;
        
    int i;
        
    DanhSachVong ds;
        
    KhoiTao(ds);
        for(
    i=1;i<=songuoi;i++) ChenVaoCuoi(ds,i);
        
    cout<<"\n - So thu tu nhung nguoi tham gia tro choi: ";
        
    HienThi(ds);
        
    cout<<"\n\n - Nguoi dem den so nao thi bi loai: ";
        
    int dem;
        
    cin>>dem;
        
    Node *p;
        
    ds.dau;
        if(
    p==NULL) return 0;
        
    0;
        
    bool bixoa false;
        while(
    ds.dau!=ds.duoi)
        {
            
    i++;
            if(
    i==dem)
            {
                
    Node *m;
                
    p;
                
    p->next;
                
    XoaNut(ds,m->vitri);
                
    0;    
                
    bixoa true;
            }
            if(!
    bixoap->next;
            else 
    bixoa false;
        }
        
    cout<<"\n\n - Nguoi thang cuoc o vi tri: ";
        
    HienThi(ds);
        
    getch();
        return 
    0;


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

  1. Bài tập C hỏi về cách xóa toàn bộ dữ liệu trong DSLK đơn
    Gửi bởi shizuoka trong diễn đàn Nhập môn lập trình C/C++
    Trả lời: 4
    Bài viết cuối: 12-09-2012, 01:47 PM
  2. Kỹ thuật C++0x Xóa không được 1 phần tử bất kì và xóa tại vị trí bất kì trong DSLK
    Gửi bởi datinh_o0o7 trong diễn đàn Thắc mắc lập trình C/C++/C++0x
    Trả lời: 7
    Bài viết cuối: 19-03-2011, 10:24 PM
  3. Hàm Xóa phần tử trong dslk đơn. Giúp mình?
    Gửi bởi athang 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: 04-10-2010, 04:42 PM
  4. Làm sao xóa tất cả các phần tử giá trị n trong DSLK?
    Gửi bởi phamvantrang 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: 30-09-2010, 08:30 PM
  5. Xóa số lẻ đầu tiên trong DSLK
    Gửi bởi KENICHI 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: 07-12-2007, 07:01 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