c++ - 如何为这个自定义 C++ List 类实现删除函数？

Question

我有一个名为 myList 的自定义列表，其工作方式如下:

// creating and adding:
myList<int> numbers;
numbers.add(10);
numbers.add(20);

// listing each item:
int n
while (numbers.nextItems(n)) {
        std::cout << m;
}

这是 myList 的源代码:

template<class T>
class myList
{

    struct eachItem
    {
        T  data;
        eachItem *nextItem;

        eachItem(eachItem *p = NULL)
        {
            nextItem = p;
        }

    }; // end of eachItem

    eachItem *beginning;
    eachItem *current;

    myList(const myList&);

public:
    myList()
    {
        current = beginning = new eachItem;
    }

    void add(const T& dat);
    bool nextItems(T& dat);

    ~myList();
};


template <class T>
myList<T>::~myList()
{
    eachItem *p;
    while ((p = beginning) != NULL)
    {
        beginning = p->nextItem;
        delete p;
    }
}

template <class T>
void myList<T>::add(const T& dat)
{
    eachItem *eachI;

    for (eachI = beginning; eachI->nextItem != NULL; eachI = eachI->nextItem);

    eachItem *newList = new eachItem(*eachI);

    eachI->data = dat;

    eachI->nextItem = newList;
}

template <class T>
bool myList<T>::nextItems(T& dat)
{

    if (current->nextItem == NULL)
    {
        current = beginning;

        return(false);
    }

    dat = current->data;


    current = current->nextItem;

    return(true);
}

现在，我想为这个自定义列表类添加一个删除功能。我希望它像这样工作:

numbers.remove(10)

我有很多不同的尝试，但我无法让它发挥作用。

这是我的尝试:

template <class T>
void myList<T>::remove(const T& dat)
{
    eachItem *eachI;

    for (eachI = beginning; eachI->nextItem != dat; eachI = eachI->nextItem);

    eachItem *newList = new eachItem(*eachI);
    eachI->nextItem = newList;


    eachItem *eachI2; // from the deleted to the actual end

    for (eachI2 = eachI->nextItem; eachI2->nextItem != NULL; eachI2 = eachI2->nextItem);

    eachItem *newList2 = new eachItem(*eachI2);
    eachI2->nextItem = newList2;
}

Answer 1

首先，您的 for 循环条件应该是 eachI->nextItem->data!=dat 以便您比较数据，而不是比较下一个节点的地址和数据

void myList<T>::remove(const T& dat)
{
    //Special acse for deleting first node
    if(beginning!=NULL && beginning->data==dat)
    {
        eachItem *toDelete = beginning;
        beginning = beginning->nextItem;
        current = beginning;
        delete toDelete;
        return;
    }
    eachItem *eachI;

    for (eachI = beginning;eachI!=NULL && eachI->nextItem->data != dat; eachI = eachI->nextItem);
    //if eachI=NULL then data to be deleted is not found
    if(eachI==NULL)
    {
        cout<<dat<<" not found in this list, so not deleted\n";
        return;   //no further processing required.
    }

    //After this for eachI->nextItem will point to node that is to be deleted
    eachItem *toDelete = eachI->nextItem;
    //now remove link between eachI and toDelete
    //i.e. let eachI->next point to toDelete->nextItem
    eachI->nextItem = toDelete->nextItem;
    //Therefore skipping toDelete
    //Now tieing up loose ends(delete the node)
    delete toDelete;

}

同时更改您的添加功能

void myList<T>::add(const T& dat)
{

    if(beginning==NULL)
    {
        beginning = new eachItem;
        current=beginning;
        beginning->data = dat;
        return;
    }
    eachItem *eachI;
    for (eachI = beginning;eachI->nextItem != NULL; eachI = eachI->nextItem);
    eachItem *newList = new eachItem;

    newList->data = dat;

    eachI->nextItem = newList;
    newList->nextItem = NULL;
}

还有你的构造函数

myList()
{
    current = beginning = NULL;
}

主要功能和输出

int main()
{
    myList<int> numbers;
    numbers.add(10);
    numbers.add(20);
    numbers.add(30);
    numbers.add(40);
    int m;
    while (numbers.nextItems(m)) {
        std::cout << m;
    }
cout<<"\n";
    numbers.remove(10);
    while (numbers.nextItems(m)) {
        std::cout << m;
    }
    cout<<"\n";
    numbers.remove(30);
    while (numbers.nextItems(m)) {
        std::cout << m;
    }
    return 0;
}

OUTPUT 10203040 203040 2040

我没看到它在哪里 永远陷入循环