Можно ли создать связанный список в стеке в C ++?

Question

Я только начал изучать C ++ пару недель назад. Так что теперь у меня есть эта школьная проблема с назначением, которая просит меня реализовать связанный список без использования «new» или чего-либо, связанного с динамическим распределением памяти (и не может использовать ADT из STL). Проф говорит, что все может быть сделано в стеке, но как? Я работаю над этим с пятницы и до сих пор застрял на этом совершенно безуспешно.

Там написано: Держите стопку имен файлов, которые читаются. Используйте следующую структуру данных для стека:

struct Node { 
string fileName; 
Node *link; 
}; 

Я пытался избежать использования new, но он всегда выдает мне «ошибку сегментации» или «ошибку BUS», когда я передаю заголовок списка в рекурсивный вызов метода. Любые идеи о том, как я могу обойти это ??

Answer 1

Разница между кучей и стеком главным образом (не только, но главным образом ради этого вопроса), где память выделяется и как она освобождается. Когда вы хотите выделить узел в куче, вы говорите new Node, и система предоставит вам память, отследит, какие чанки используются, а какие свободны, и предоставит вам возможность освободить чанк один раз. тебе это больше не нужно.

Но вы также можете иметь пул узлов в массиве в стеке. (Автоматические переменные являются переменными стека.) Вы можете «выделить» из этого пула, отслеживать, какие узлы в массиве используются, а какие свободны, и помечать неиспользуемые как свободные, которые вам больше не нужны. Однако, поскольку размер массива фиксирован во время компиляции, это означает, что у вас есть максимальная длина для вашего списка.

Answer 2

Я создал небольшой образец, который может вас вдохновить. Я создаю односвязный список элементов в стеке. Обратите внимание, как список создается в обратном порядке и как рекурсия используется для «выделения» нужного вам количества элементов. Также обратите внимание, как список передается в качестве параметра. Надеюсь, это поможет, удачи.

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

Answer 3

Возможно, вам следует поговорить со своим профессором и уточнить требования, поскольку из вашего описания это выглядит как очень странное задание для нового программиста на С ++. Требование реализации связанного списка с памятью только в стеке, по меньшей мере, странно.

Answer 4

После вызова функции для этой функции назначается стек.

Единственный способ получить больше выделенной стековой памяти - вызвать другую функцию. Который мог бы затем вызвать другую функцию. Который мог бы затем вызвать другую функцию. Или, может быть, они все могут быть одной и той же функции ...

Каждый вызов функции имеет свой собственный стек фиксированного размера, но сам график вызова функции является стеком этих переменных стека.

Answer 5

Используйте alloca() вместо функции malloc() для динамического выделения памяти в кадре стека функции вызывающей стороны вместо кучи. Вам не нужно беспокоиться об освобождении памяти, поскольку она автоматически освобождается при возврате функции.

текст ссылки

Answer 6

Без особой информации:

Требуется ли рекурсивная реализация? Когда вы делаете рекурсивный вызов, вы получаете новый стек. Может быть, вы могли бы использовать итеративный подход.

Answer 7

Думайте о массивах. Может быть, больше одного, если требуется.

Answer 8

Можно использовать оператор адреса C ++ (&) для получения указателя на объект в стеке вместо динамического выделения памяти с помощью new .

Поскольку создание связанного списка таким способом имеет сомнительное значение, кроме как домашнее задание, я не уверен, действительно ли это требуется. Без примера кода трудно сказать, где именно проблема.

Answer 9

Чтобы "создать связанный список в стеке", обычно вы используете функцию, подобную alloca, чтобы получить больше стековой памяти. Однако это не похоже на то, что вас просят сделать.

Звучит так, как будто вы должны хранить стек в стеке, а не произвольный связанный список. Как подсказка, общий синтаксис того, что вы хотите сделать:

void push(struct Node *oldHead, String elem) {
    struct Node newHead;
    head.fileName = elem;
    head.next = oldHead.
    struct Node *head = &newHead
    // then you need to continue what you're doing in this function, since
    // returning will effectively pop the stack.

Существуют (нетривиальные) методы для реализации полноценных списков мусора по этим направлениям, но это выходит за рамки того, что вы делаете.

Answer 10

Если вы знаете, сколько имен файлов вам нужно сохранить, вы можете использовать массив struct Node и построить свой список из этого.

Используя итерацию, возможной альтернативой является использование одного объекта struct Node в вашей функции и передача указателя на него в рекурсивном вызове, где вы используете указатель для следующей ссылки на объект Node в кадре стека этих функций. *

Обратите внимание, что в последнем случае список действителен только для самой глубокой рекурсии, список снова разбивается, когда рекурсивные вызовы возвращаются своему вызывающему.