Go - 带有数组和丢失值的递归结构

Question

我创建了一个具有父级和子级的 Element 结构，创建了一个名为 SubElement 的辅助函数，以及一个遍历所有子级以进行打印的 String 方法：

package main

import "fmt"

type Element struct {
  parent *Element
  children []Element
  tag string
}

func SubElement(parent *Element, tag string) Element {
  el := Element{}
  el.parent = parent
  el.tag = tag
  parent.children = append(parent.children, el)
  return el
}

func (el Element) String() string {
  s := "<" + el.tag + ">"
  for _, child := range el.children {
    s += child.String()
  }
  s += "</" + el.tag + ">"
  return s
}

func main() {
  root := Element{}
  root.tag = "root"

  a := SubElement(&root, "a")
  b := SubElement(&a, "b")
  SubElement(&b, "c")

  fmt.Println(root) // prints: <root><a></a></root>
  fmt.Println(a) // prints: <a><b></b></a>
  // and so on
}

我遇到的问题是，我选择打印的根节点中只有第一层子节点可用。我确定这与在 parent.children 上使用 append 相关，但缺乏对如何正确解决此问题的理解。

要解决这个问题，我换children到map[int]Element。然后在我的 SubElement func 中，我“附加”了parent.children[len(parent.children)] = el. 然后以正确的顺序进行迭代，循环的 String 方法是for i:= 0; i < len(el.children); i++，访问el.children[i].

不过，我想知道如何使用数组正确执行此操作。谢谢

Answer 1

解释为什么 []Element 版本不起作用的答案。

结构被复制为值。在 中SubElement，您创建了一个Element结构，然后当您附加它时，实际上附加了该结构的一个全新副本。当您返回 el 并将其分配给a时，会生成另一个副本。的地址a不是Element附加的地址。

因此，您可能会变得棘手并获取实际在切片中的元素的地址，这甚至可能看起来像是在测试用例中工作，但是保留这些指针存在问题，例如您在将其存储回来时所做的在Element.parent。问题是后续追加可以重新分配切片，现在您保留的指针指向一些孤立的内存而不是当前有效的切片。

如果 []*Element 版本解决了其他一些问题，那么它们很可能是存储随后孤立的指针的问题。

可以用结构切片来实现树，但需要清楚地理解，将指针保留在切片中通常是错误的。由于存储父指针并不安全，因此最好将其从结构中移除。

package main

import "fmt"

func main() {
    tree := Element{tag: "head"}
    tree.SubElement("tier-1")
    tree.children[0].SubElement("tier-2")
    tree.children[0].SubElement("tier-2")
    tree.SubElement("tier-1")
    tree.children[1].SubElement("tier-2")
    fmt.Println(tree)
}

type Element struct {
    children []Element
    tag      string
}

func (parent *Element) SubElement(tag string) {
    parent.children = append(parent.children, Element{tag: tag})
}

func (el Element) String() string {
    s := "<" + el.tag + ">"
    for _, child := range el.children {
        s += child.String()
    }
    s += "</" + el.tag + ">"
    return s
}

这段代码至少有效；但是如果您有其他使用指针的代码，或者使用父指针的代码，则必须重新考虑。