IntStack 的 C++ 递归打印函数

Question

我的任务是创建一个打印函数，该函数使用递归来打印单链表(堆栈)的数据。到目前为止，这是我的代码:

IntStack.h

#include <iostream>

struct NodeType
{
    int data;
    NodeType *next;
};

class IntStack
{
private:
    NodeType root;
    int count;
public:
    IntStack(void);
    ~IntStack(void);

    void push(int);
    int pop(void);
    bool isEmpty(void);
    void print(NodeType&);
    int getSize() const;
    NodeType* getRoot();
};

IntStack.cpp

#include "IntStack.h"

IntStack::IntStack()
{
    count = 0;
}

IntStack::~IntStack()
{

}

void IntStack::push(int num)
{
    NodeType newNode;
    newNode.data = num;

    newNode.next = &root;
    root = newNode;

    ++count;
}

int IntStack::pop(void)
{
    // get root data
    // set root equal to root.next
    int num = root.data;
    root = *root.next;
    --count;
    return num;
}

bool IntStack::isEmpty(void)
{
    return (count == 0);
}

void print(NodeType *node)
{
    if (node->next != NULL) {
        std::cout << node->data << " " << std::endl;
        print(node->next);
    }
}

NodeType* IntStack::getRoot()
{
    return &root;
}

int IntStack::getSize() const
{
    return count;
}

main.cpp

#include <iostream>
#include "IntStack.h"

int main()
{
    IntStack stack;
    stack.push(7);
    stack.push(10);
    stack.push(13);
    stack.push(43);
    stack.push(23);
    stack.push(5);
    stack.push(32);
    stack.push(8);

    std::cout << stack.getSize() << " item(s) in the stack." << std::endl;
    std::cout << "Pop item off stack: " << stack.pop() << std::endl;
    std::cout << stack.getSize() << " item(s) in the stack." << std::endl;

    stack.print(stack.getRoot());

    return 0;
}

我在 main.cpp 中的 stack.print(stack.getRoot()) 函数上收到错误:

main.cpp:28:17: Non-const lvalue reference to type 'NodeType' cannot bind to a temporary of type 'NodeType *'

显然，我没有发送指向该函数的指针，但我尝试了各种方法来发送根节点，但都没有成功。非常感谢有关我应该如何进行的任何信息。谢谢

Answer 1

首先，您应该在堆上而不是堆栈上分配节点。简而言之，对于堆分配而不是堆栈分配的东西，您必须使用“new”关键字。

// node1 is stack allocated
NodeType node1;

// node2 is heap allocated
NodeType *node2 = new NodeType;

原因是，当函数返回时，分配给堆栈的任何内容都会过期(被删除)。在您的情况下，您需要将节点保持在函数末尾之外。

因此将 NodeType root; 更改为 NodeType *root; 并在构造函数中将 root 设置为 NULL。

您必须更改推送功能等，才能让您的程序立即运行。

void IntStack::push(int num)
{
    NodeType *newNode = new NodeType; // heap allocated now
    newNode->data = num; // use appropriate dereferencing operator "->"

    newNode->next = root; // root is now a pointer

    root = newNode;

    ++count;
}

要删除一个节点，你会做相反的事情

int IntStack::pop(void)
{
    int num = root->data;

    NodeType *tmp = root; // don't lose the pointer
    root = root->next;
    delete tmp; // heap allocated memory must be freed if it is allocated

    --count;

    return num;
}

向 NodeType 添加构造函数以将变量设置为 NULL 也是一个好主意，因为 当涉及到递归打印节点时，您必须知道何时到达最后一个节点，将由“next”指针为 NULL 指示。

编辑: 我在上面划掉了一条线。由于您将 root 初始化为 NULL，并且 next 始终设置为 root 的值，因此 NodeType 不需要构造函数。但是，打印函数中的条件应该是 if (node != NULL) 而不是 if (node->next != NULL)。考虑您有 0 个或 1 个节点的情况。