是否可以在C++中的堆栈上创建链接列表？

Question

几周前我刚开始学习C++.所以现在我有这个学校作业问题,要求我实现链接列表而不使用"新"或任何与动态分配内存有关(并且不能使用STL中的任何ADT).教授说一切都可以在堆栈上完成,但是如何？自上周五以来我一直在研究这个问题并且仍然坚持这一点,绝对没有运气.

它说:保持一堆文件名被读取.对堆栈使用以下数据结构:

struct Node { 
string ?leName; 
Node *link; 
}; 

我试图避免使用新的,但当我将列表的头部传递给递归方法调用时,它总是给我"分段错误"或"总线错误".关于我如何解决这个问题的任何想法？

Answer 1

堆和堆栈之间的区别主要是(不仅是,但主要是为了这个问题)分配内存的方式以及如何释放内存.当你想在堆上分配一个节点时,你说new Node并且系统将为你提供内存,跟踪使用哪些块以及哪些块是免费的,并且一旦你做了,就会为你提供释放块的方法.再也不需要了.

但是你也可以在堆栈中的数组中有一个节点池.(自动变量是堆栈变量.)您可以从该池"分配",跟踪阵列中的哪些节点以及哪些节点是空闲的,并将未使用的节点标记为不再需要它们的免费节点.但是,由于数组的大小在编译时是固定的,这意味着您的列表具有最大长度.

Answer 2

我已经创建了一个你可能会觉得鼓舞人心的小样本.我在堆栈上创建了一个单独链接的元素列表.注意如何反向创建列表以及如何使用递归来"分配"所需的itmes数量.还要注意列表如何作为参数传递给参数.希望这有帮助,祝你好运.

#include <cstdio>

using namespace std;

struct Node {
    Node* next_;
    int value_;
};

// Creates a linked list of nodes containing raising values.
void intList(Node* prevNode, int restValue) {
    if (restValue) {
       // A node on the stack, which is linked to list created so far.
       Node node;
       node.next_ = prevNode;
       node.value_ = restValue; 
       // Create a next node or print this list if rest runs to zero.
       intList(&node, rest - 1);
    }
    else {
    // Depest recursion level, whole list is complete.
    for (Node* iter = prev; iter; iter = iter->next_)
        printf("item %d\n", iter->value_);
    }
}

int main() {
    intList(NULL, 10);
}