Xoá nhiều phần tử danh sách liên kết đôi

Cho em hỏi về hàm removeMultiNodeS, khi em sử dụng riêng biệt 2 hàm removeHead và removeTail thì code vẫn hoạt động bình thường, còn khi thêm 2 hàm đó vào removeMiltiNodes thì code lại không chạy ạ, em cảm ơn mọi người.

#include <iostream>
using namespace std;
struct DNode
{
    int info;
    DNode *pNext, *pPrev;
};
struct DList
{
    DNode *pHead, *pTail;
};
void init(DList &L)
{
    L.pHead = L.pTail = NULL;
}
DNode *GetNode(int x)
{
    DNode *p = new DNode;
    p->info = x;
    p->pNext = p->pPrev = NULL;
    return p;
}
void addHead(DList &L, int x)
{
    DNode *newele = GetNode(x);
    if (L.pHead == NULL)
    {
        L.pHead = L.pTail = newele;
    }
    else
    {
        newele->pNext = L.pHead;
        L.pHead->pPrev = newele;
        L.pHead = newele;
    }
}
void addTail(DList &L, int x)
{
    DNode *newele = GetNode(x);
    if (L.pTail == NULL)
    {
        L.pHead = L.pTail = newele;
    }
    else
    {
        L.pTail->pNext = newele;
        newele->pPrev = L.pTail;
        L.pTail = newele;
    }
}
void createList(DList &L)
{
    int a;
    do
    {
        cin >> a;
        if (a != -1)
            addTail(L, a);
        else
            break;
    } while (true);
}
void printList(DList L)
{
    DNode *p = L.pHead;
    if (L.pHead == NULL)
    {
        cout << "List is empty";
        return;
    }
    while (p != NULL)
    {
        cout << p->info << " ";
        p = p->pNext;
    }
}
void addAfter(DList &L, int x, int y)
{
    DNode *newele = GetNode(y);
    DNode *p = L.pHead;
    int flag = 0;
    if (L.pHead == NULL)
    {
        cout << "\nCan't find the value " << x;
        return;
    }
    while (p != NULL)
    {
        flag = 1;
        if (p->info == x)
        {
            if (p->pNext == NULL)
            {
                addTail(L, y);
                return;
            }
            else
            {
                newele->pNext = p->pNext;
                newele->pPrev = p;
                p->pNext->pPrev = newele;
                p->pNext = newele;
                break;
            }
        }
        p = p->pNext;
    }
    if (flag == 0)
        cout << "\nCan't find the value " << x;
}
void addBefore(DList &L, int x, int y)
{
    DNode *p = L.pHead;
    int flag = 0;
    if (L.pHead == NULL)
    {
        cout << "\nCan't find the value " << x;
        return;
    }
    while (p != NULL)
    {
        DNode *newele = GetNode(y);
        if (p->info == x)
        {
            flag = 1;
            if (p->pPrev == NULL)
            {
                addHead(L, y);
                return;
            }
            else
            {
                newele->pNext = p;
                newele->pPrev = p->pPrev;
                p->pPrev->pNext = newele;
                p->pPrev = newele;
                break;
            }
        }
        p = p->pNext;
    }
    if (flag == 0)
        cout << "\nCan't find the value " << x;
}
void addAfterMulti(DList &L, int x, int y)
{
    DNode *p = L.pHead;
    int flag = 0;
    if (L.pHead == NULL)
    {
        cout << "\nCan't find the value " << x;
        return;
    }
    while (p != NULL)
    {
        DNode *newele = GetNode(y);
        if (p->info == x)
        {
            flag = 1;
            if (p->pNext == NULL)
            {
                addTail(L, y);
            }
            else
            {
                newele->pNext = p->pNext;
                newele->pPrev = p;
                p->pNext->pPrev = newele;
                p->pNext = newele;
            }
        }
        p = p->pNext;
    }
    if (flag == 0)
        cout << "\nCan't find the value " << x;
}
void addBeforeMulti(DList &L, int x, int y)
{
    DNode *p = L.pHead;
    int flag = 0;
    if (L.pHead == NULL)
    {
        cout << "\nCan't find the value " << x;
        return;
    }
    while (p != NULL)
    {
        DNode *newele = GetNode(y);
        if (p->info == x)
        {
            flag = 1;
            if (p->pPrev == NULL)
            {
                addHead(L, y);
            }
            else
            {
                newele->pNext = p;
                newele->pPrev = p->pPrev;
                p->pPrev->pNext = newele;
                p->pPrev = newele;
            }
        }
        p = p->pNext;
    }
    if (flag == 0)
        cout << "\nCan't find the value " << x;
}
void removeHead(DList &L)
{
    DNode *p = L.pHead;
    L.pHead = L.pHead->pNext;
    L.pHead->pPrev = NULL;
    p->pNext = NULL;
    delete p;
    p = NULL;
}
void removeTail(DList &L)
{
    DNode *p = L.pTail;
    L.pTail = L.pTail->pPrev;
    L.pTail->pNext = NULL;
    p->pPrev = NULL;
    delete p;
    p = NULL;
}
void removeNode(DList &L, int x)
{
    DNode *p = L.pHead;
    while (p != NULL)
    {
        if (p->info == x)
        {
            if (p == L.pHead)
            {
                removeHead(L);
                return;
            }
            else if (p == L.pTail)
            {
                removeTail(L);
                return;
            }
            DNode *k = p;
            p->pPrev->pNext = p->pNext;
            p->pNext->pPrev = p->pPrev;
            delete k;
            return;
        }
        p = p->pNext;
    }
}
void removeMultiNodeS(DList &L, int x)
{
    DNode *p = L.pHead;
    while (p != NULL)
    {
        if (p->info == x)
        {
            if (p == L.pHead)
            {
                removeHead(L);
            }
            else if (p == L.pTail)
            {
                removeTail(L);
            }
                DNode *k = p;
                p->pPrev->pNext = p->pNext;
                p->pNext->pPrev = p->pPrev;
                delete k;
        }
        p = p->pNext;
    }
}
int main()
{
    DList L;
    init(L);
    int x, y, choice;
    char c;
    cout << "MENU:";
    cout << "\n1. Create a DList";
    cout << "\n2. Print the DList";
    cout << "\n3. Insert a value at the front";
    cout << "\n4. Insert a value at the end";
    cout << "\n5. Insert a value after a given value (only for the first value found)";
    cout << "\n6. Insert a value before a given value (only for the first value found)";
    cout << "\n7. Insert a value after a given value (for all the same values)";
    cout << "\n8. Insert a value before a given value (for all the same values)";
    cout << "\n9. Delete the first element";
    cout << "\n10. Delete the last element";
    cout << "\n11. Delete the first element containing a specific value";
    cout << "\n12. Delete all elements storing a particular value";
    cout << "\n13. Delete the element after a specific value (only for the first one found)";
    cout << "\n14. Delete the element before a specific value (only for the first one found)";
    cout << "\n15. Delete all elements after a specific value";
    cout << "\n16. Delete all elements before a specific value";
    cout << "\n17. Delete all elements";
    cout << "\n20. Exit" << endl;
    while (true)
    {
        cout << "\n\t\tPLEASE SELECT YOUR CHOICE: ";
        cin >> choice;
        switch (choice)
        {
        case 1:
            cout << "\nEnter your positive integers until you enter -1 to finish: ";
            createList(L);
            break;
        case 2:
            cout << "\nYour current DList: ";
            printList(L);
            break;
        case 3:
            cout << "\nEnter a number: ";
            cin >> x;
            addHead(L, x);
            break;
        case 4:
            cout << "\nEnter a number: ";
            cin >> x;
            addTail(L, x);
            break;
        case 5:
            cout << "\nEnter two numbers: ";
            cin >> x >> y;
            addAfter(L, x, y);
            break;
        case 6:
            cout << "\nEnter two numbers: ";
            cin >> x >> y;
            addBefore(L, x, y);
            break;
        case 7:
            cout << "\nEnter two numbers: ";
            cin >> x >> y;
            addAfterMulti(L, x, y);
            break;
        case 8:
            cout << "\nEnter two numbers: ";
            cin >> x >> y;
            addBeforeMulti(L, x, y);
            break;
        case 9:
            removeHead(L);
            break;
        case 10:
            removeTail(L);
            break;
        case 11:
            if (L.pHead == NULL)
            {
                cout << "\nList is empty. Can't delete";
                break;
            }
            cout << "\nEnter a number: ";
            cin >> x;
            removeNode(L, x);
            break;
        case 12:
            if (L.pHead == NULL)
            {
                cout << "\nList is empty. Can't delete";
                break;
            }
            cout << "\nEnter a number: ";
            cin >> x;
            removeMultiNodeS(L, x);
            break;
        case 20:
            cout << "\nGOOD BYE";
            return 0;
        }
    }
    return 0;
}

Bạn thêm lời gọi hàm removeHead(L); và sau đó cho phép chương trình thực thi tiếp đoạn code này:

DNode *k = p;
p->pPrev->pNext = p->pNext;
p->pNext->pPrev = p->pPrev;
delete k;

p đang ở head và p->prev, có gì không ổn ở đây không?

Bạn thêm lời gọi hàm removeTail(L); và sau đó bạn cho phép chương trình thực thi đoạn code này:

DNode *k = p;
p->pPrev->pNext = p->pNext;
p->pNext->pPrev = p->pPrev;
delete k;

p đang ở tail và p->next, có gì không ổn ở đây không?

Mình tạm sửa lại code bạn như sau (chỉ với mục đích fix lỗi crash, còn phần logic bạn tự làm thêm cho đúng):

void removeMultiNodeS(DList &L, int x)
{
    DNode *p = L.pHead;
    while (p != NULL)
    {
        if (p->info == x)
        {
            if (p == L.pHead)
            {
                removeHead(L);
                continue; // add this line
            }
            else if (p == L.pTail)
            {
                removeTail(L);
                break; // and this line
            }
            
            DNode *k = p;
            p->pPrev->pNext = p->pNext;
            p->pNext->pPrev = p->pPrev;
            delete k;
        }
        p = p->pNext;
    }
}
4 Likes
83% thành viên diễn đàn không hỏi bài tập, còn bạn thì sao?