Как вы выделяете память для связанного списка при передаче его ссылки вместо указателя?

Question

Как вы выделяете память для списка ссылок при передаче его ссылки вместо указателя?

Например:

struct node {
  string info;
  node *next;

};

void add(node &aNode){


//if I use
node *newNode;
newNode = new node;
aNode.next = newNode; //aNode.next = newNode; doesn't work either

//allocating on heap seems to give segmentation error.


}


int main() {                                                        

  node *aNode;
  aNode = new node;
  add (aNode);


}

Compiler error: error: invalid initialization of reference of type ‘node&’ from expr

в качестве альтернативы, если я использую

int main() {                                                        

  node aNode;
  add (aNode);
  add (aNode);
  aNode.next->next->info = "abc";
  string a = aNode.next->next->info;


}

Это дает ошибку сегментации.

Так возможно ли выделить связанный список только с его ссылкой?(это C ++)

Answer 1

должно быть

node * newNode = new node;
aNode.next = newNode

Вы должны позаботиться об удалении вручную, например, проверьте, не занято ли aNode.next (и удалите, если оно есть).

Далее, подпись функции add должна выглядеть следующим образом:

void add(node & aNode) { ... }

Кстати, STL поставляется с хорошим <forward_list>; -)

---

Трудно сказать, что вы на самом деле спрашиваете, но, исходя из названия вопроса, возможно, вы имеете в виду структуру узла, подобную этой:

struct Node {
  Node & next;
  /* payload data */
  Node(Node & n) : next(n) /* ... */ { }
};

Такой узел будет хранить своего преемника "по ссылке"; но вам придется инициализировать его с существующим узлом! (Нет такого понятия, как «нулевая ссылка».) * * * * * * * * * * * * * * * * * * * * * * * * * * *

---

Хорошо, пока вы продолжаете отказываться публиковать свой полный код, вот моя почти буквальная копия / вставка вашего кода, которая отлично работает со мной:

Обновление: Я добавляю функцию для добавления узла в конце, что может потребоваться.

#include <string>

struct node {
  std::string info;
  node *next;
  node(std::string i = "") : info(i), next(NULL) { }
};

void add(node &aNode)
{
  node *newNode;
  newNode = new node;
  aNode.next = newNode;
}

void add_at_end(node &aNode, std::string value = "")
{
  node *newNode, *n = &aNode;
  while (n->next) n = n->next; // move to the end

  newNode = new node(value);
  n->next = newNode;
}

int main()
{
  node aNode, bNode;
  add(aNode);
  add_at_end(bNode, "Hello");
  add_at_end(bNode, "World");
  add_at_end(bNode, "!");
}

Компилировать с g++ -o prog prog.cpp -W -Wall -pedantic.

---

Наконец, вот STL способ достижения того же самого:

#include <forward_list>
#include <string>
int main() {
  std::forward_list<std::string> bList;
  bList.push_front("Hello");
  bList.push_front("World");
  bList.push_front("!");
}

Answer 2

Во втором варианте main() вы звоните add(aNode) дважды.Но вы предоставляете ему один и тот же параметр каждый раз.Таким образом, хотя вы создаете два новых node объекта, один из них теряется навсегда ( утечка памяти ).И aNode.next заканчивает тем, что указывает на другого.aNode.next->next не является допустимым указателем, поэтому ошибка при попытке доступа к чему-либо через него

В зависимости от того, чего вы хотите достичь, вы можете попробовать это:

node aNode;
add(aNode);        // Basically does: aNode.next = new node;
add(*aNode.next);  // Basically does: aNode.next->next = new node;

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

Answer 3

Попробуйте

int main() {                                                        

  node *aNode;
  aNode = new node;
  add (*aNode);
}

Вы должны передать ссылку на объект, а не указатель.

Я проверил ваш код и не получил ошибку сегментации при размещении в стеке: http://ideone.com/gTRIG.

---

Мое предложение:

#include <string>
using namespace std;

struct node {
  string info;
  node *next;
  node(string str): info(str), next(NULL) {}
  ~node() { if(next != NULL) delete next; }
  node *add(string info){
    node *newNode = new node(info);
    return aNode.next = newNode;
  }
};

int main(){
  node rootNode("My rootnode");
  node *nxt = rootNode.add("Next node");
  nxt->add("Last node");
  // No need to call delete, because destructor will clear heap
}