C++ 向链表开头添加节点在 1 次后失败。其他方法也有问题

Question

所以我有一个半工作的链表程序。我只是在使用某些方法时遇到了一些麻烦....我在 bekiw 记录的那些方法都在工作，除了 delete from end 这表现得很奇怪。

我在 Mavericks 上使用 NetBeans，使用 G++ 作为我的编译器和 C++11 Here is a zip of all of the program files

这是我尝试制作的方法的列表:

//working
int size() const;
/kind of 
void addToStart(Node *);
//working
void addToEnd(Node *);
//working
void printList();
//working
bool removeFromStart();
//kind of working
bool removeFromEnd();

//Still working on these
void removeNodeFromList(int);
void removeNodeFromList(string);

现在，我必须运行两次 removeFromEnd() 才能使其正常工作。意思是，我在程序开始时运行它一次，它什么也没做，但随后的每一次，它实际上都执行了删除操作。

对于 addToStart()，如果我只运行一次它就可以工作。即:

• 我可以在程序开始运行一次并打印出列表
• 我可以在使用 addToEnd 后运行一次，但如果我第二次尝试并尝试打印列表，它只会不断吐出我尝试添加的值。

addToEnd() 如果我继续运行它可以完美地找到它，但如果我:

首先使用 addToEnd() 添加项目，然后使用 addToStart() 一次，然后再次尝试使用 addToEnd()。当我打印出列表时，它只打印出两个对象，每个对象都是我尝试插入的最后一个值的拷贝。

void LinkedList::addToEnd(Node* ne) 
{
    Node** q = &myHead;
    while (*q) 
    {
        q = &(*q)->next;
    }

    *q = new Node(ne->itemName, ne->itemNo);
}

void LinkedList::printList() 
{
    Node* p = myHead;
    while (p != NULL) 
    {
        cout << p->itemNo << " " << p->itemName;
        cout << endl;
        p = p->next;
    }

    cout << endl << endl;
}

bool LinkedList::removeFromStart() 
{
    if (myHead == NULL) 
    {
        cout << "List is already empty";
    }
    else 
    {
        myHead = myHead->next;
    }
}

bool LinkedList::removeFromEnd() 
{
    if (myHead == NULL) 
        return false;

    //Empty the list if there's only one element
    if (myHead->next == NULL) 
    {
        delete myHead;
        myHead = NULL;
        myTail = NULL;
        return true;
    }

    // Find the last item in the list
    Node *temp = myHead;
    while (temp->next != myTail) 
    {
        temp = temp->next;
    }

    delete myTail;
    temp->next = NULL;
    myTail = temp;
    return true;
}

此外，仍在尝试找出删除的

void LinkedList::removeNodeFromList(int i) {


//Save the values
Node* p = myHead;
Node* temp = myHead->next;


    while (p) {

        if (p->itemNo == i) {

            p=temp;
        } else {
            p = p->next;
        }

    }

}

Answer 1

你有一个 tail指针，那么为什么要遍历列表以找到结尾？另外，为什么要通过指针传递节点？

void LinkedList::addToEnd(Node ne) 
{
    if (myHead == nullptr) // empty list
    {
        myHead = myTail = new Node(ne);
        myTail->next = nullptr;
    }
    else
    {
        myTail->next = new Node(ne); // assuming Node has an accessible copy constructor
        myTail = myTail->next;
    }
}

removeFromStart函数有内存泄漏:

bool LinkedList::removeFromStart() 
{
    if (myHead == nullptr) 
    {
        cout << "List is already empty";
        return false;
    }


    Node* temp = myHead;
    myHead = myHead->next;
    if (myTail == temp) // if there is only 1 element in the list, head == tail
    {
        myTail = myhead;
    }
    delete temp;
    return true;
}

据推测，removeFromEnd应该去掉尾部:

bool LinkedList::removeFromEnd() 
{
    if (myTail == nullptr) 
        return false;

    // unless you have a doubly-linked list, loop to find 1 before the tail
    Node* temp = nullptr;
    for (temp = myHead; temp && temp->next != myTail; temp = temp->next);


    if (myHead == temp) // when there is only 1 element in the list, head == tail
    {
        delete temp->next;
        myHead = nullptr;
        myTail = nullptr;
    }
    else
    {
        delete temp->next;
        temp->next = nullptr;
        myTail = temp;
    }
    return true;
}

是的，您正在使用 new (在你的 addtoEnd 函数中)，所以你必须使用 delete (不是 free !)。

旁注:使用 std::unique_ptr 可以更好地编写删除代码(你实际上可以通过在任何地方使用它来整体改进代码)这将使你的代码每行大约 4 行。我会把它留给你去实现。