0

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

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();
};

集成堆栈.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;
}

主文件 

#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：对“NodeType”类型的非 const 左值引用无法绑定到“NodeType *”类型的临时对象

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

4

3 回答 3

2

首先，您应该在堆上而不是在堆栈上分配节点。简而言之，要让堆分配而不是堆栈分配，您必须使用“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因此不需要构造函数。但是，您的 print 函数中的条件应该是if (node != NULL)而不是if (node->next != NULL). 考虑您有 0 或 1 个节点的情况。

于 2012-08-29T02:29:23.437 回答
1

您void print(NodeType&);在头文件中写入，而不是像在 .cpp 文件中那样使用指针版本。将更改&为 a *，它将起作用。

（顺便说一句，真的很奇怪的模式）

于 2012-08-29T02:00:59.640 回答
0

您的原型与您的功能使用不匹配。

void print(NodeType&)

在您的实现文件中，您具有以下内容

void print(NodeType *node)

我相信您想要使用 NodeType* 之一，因此请在您的头文件中更改它以反映这一点。

我看到的另一行让我感到困惑的是 print 函数中的 print 行。

std::cout << node->data << " " << std::endl;

为什么每次打印后都要打印一个换行符？我建议将其更改为删除endl打印。

于 2012-08-29T02:05:14.813 回答