c++ - 在传递引用而不是指针时如何为链表分配内存？

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) /* ... */ { }
};

这样的节点将“通过引用”存储其后继节点；但是您必须使用现有节点对其进行初始化! (没有“空”引用这样的东西。)Poultry-Oval Impasse ，你不能这样做。

---

好吧，虽然你继续拒绝发布你的完整代码，但这里是我对你的代码的几乎直截了当的复制/粘贴，它对我来说效果很好:

更新:我正在添加一个功能以在末尾添加一个节点，您可能需要它。

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