C++ 链表向后插入

Question

我正在尝试创建一个 insert a node to the back of the list using linked list 的函数。我是使用链表的新手，我尝试了许多不同的方法在列表末尾进行插入，但似乎没有任何效果。 main传递值one at a time，插入2 4 5 8 9，输出为2 0 0 0 0。我不知道是什么导致了这个问题。

.h

class Node
{
public:
    Node() : data(0), ptrToNext(NULL) {}
    Node(int theData, Node *newPtrToNext) : data(theData), ptrToNext(newPtrToNext){}
    Node* getPtrToNext() const { return ptrToNext; }
    int getData() const { return data; }
    void setData(int theData) { data = theData; }
    void setPtrToNext(Node *newPtrToNext) { ptrToNext = newPtrToNext; }
    ~Node(){}
private:
    int data;
    Node *ptrToNext;    //pointer that points to next node
};

class AnyList
{
public:
    AnyList();  
        //default constructor
    void print() const;
        //Prints all values in the list.
    void destroyList();
        //Destroys all nodes in the list.
    ~AnyList();
        //destructor
    int getNumOfItems();
    void insertBack(int b);
    void deleteFirstNode();

private:
    Node *ptrToFirst; //pointer to point to the first node in the list
    int count;        //keeps track of number of nodes in the list
};

.cpp

void AnyList::insertBack(int b)
{
    Node *temp = new Node;

    if (ptrToFirst == NULL)
    {
        temp->setData(b);
        ptrToFirst = temp;
    }
    else
    {
        Node *first = ptrToFirst;
        while (first->getPtrToNext() != NULL)
        {
            first = first->getPtrToNext();
        }
        first->setPtrToNext(temp);
    }
}

Answer 1

首先，您确实应该使用 std::list 或 std::forward_list class 而不是手动实现节点处理：

#include <list>

class AnyList
{
public:
    void print() const;
        //Prints all values in the list.
    void destroyList();
        //Destroys all nodes in the list.
    int getNumOfItems() const;
    void insertBack(int b);
    void deleteFirstNode();

private:
    std::list<int> nodes; //nodes in the list
};

void AnyList::print() const
{
    for (std::list<int>::const_iterator iter = nodes.begin(); iter != nodes.end(); ++iter)
    {
        int value = *iter;
        // print value as needed...
    }
}

void AnyList::destroyList()
{
    nodes.clear();
}

void AnyList::getNumOfItems() const
{
    return nodes.size();
}

void AnyList::insertBack(int b)
{
    nodes.push_back(b);
}

void AnyList::deleteFirstNode()
{
    if (!nodes.empty())
        nodes.pop_front();
}

也就是说，您的手动实施失败了，因为您可能没有正确管理节点（但您没有展示您正在做的一切）。它应该看起来像这样：

class Node
{
public:
    Node() : data(0), ptrToNext(NULL) {}
    Node(int theData, Node *newPtrToNext) : data(theData), ptrToNext(newPtrToNext) {}
    ~Node() {}
    Node* getPtrToNext() const { return ptrToNext; }
    int getData() const { return data; }
    void setData(int theData) { data = theData; }
    void setPtrToNext(Node *newPtrToNext) { ptrToNext = newPtrToNext; }
private:
    int data;
    Node *ptrToNext;    //pointer that points to next node
};

class AnyList
{
public:
    AnyList();  
        //default constructor
    ~AnyList();
        //destructor
    void print() const;
        //Prints all values in the list.
    void destroyList();
        //Destroys all nodes in the list.
    int getNumOfItems() const;
    void insertBack(int b);
    void deleteFirstNode();

private:
    Node *ptrToFirst; //pointer to point to the first node in the list
    Node *ptrToLast;  //pointer to point to the last node in the list
    int count;        //keeps track of number of nodes in the list
};

AnyList:AnyList()
    : ptrToFirst(NULL), ptrToLast(NULL), count(0)
{
}

void AnyList::print() const
{
    for (Node *temp = ptrToFirst; temp != NULL; temp = temp->getPtrToNext())
    {
        int value = temp->getData();
        // print value as needed...
    }
}

AnyList::~AnyList()
{
    destroyList();
}

void AnyList::destroyList()
{
    Node *temp = ptrToFirst;
    ptrToFirst = ptrToLast = NULL;
    count = 0;

    while (temp != NULL)
    {
        Node *next = temp->getPtrToNext();
        delete temp;
        temp = next;
    }
}

int AnyList::getNumOfItems() const
{
    return count;
}

void AnyList::insertBack(int b)
{
    Node *temp = new Node(b, NULL);

    if (ptrToFirst == NULL)
        ptrToFirst = temp;

    if (ptrToLast != NULL)
        ptrToLast->setPtrToNext(temp);

    ptrToLast = temp;
    ++count;
}

void AnyList::deleteFirstNode()
{
    if (ptrToFirst == NULL)
        return;

    Node *temp = ptrToFirst;
    ptrToFirst = temp->getPtrToNext();

    if (ptrToLast == temp)
        ptrToLast = NULL;

    delete temp;
    --count;
}

C++ 链表向后插入

C++ Linked list insert back

linked-list

c++11