结构指针方法中的指针可以重新分配给另一个实例吗？

Question

我一直在研究 Golang 并实现了一些数据结构以了解该语言的工作原理。我在为 AVL 树编写代码时遇到了以下问题：

从结构指针方法分配主指针似乎在函数范围之外没有影响。例如。 tree.rotateLeftToRoot() 不会导致 tree.left 成为新树。

问题：有没有办法在 Golang 的结构指针方法中重新分配指针，或者通常不鼓励这样做？在示例中，这将是 "tree = prevLeft" 行。

代码片段：

//Graphical representation of t.rotateLeftToRoot():
//      t                  L
//   L     R     ->    LL     t
//LL LR                     LR  R
func (tree *AvlTree) rotateLeftToRoot() {
   if tree == nil {
      return
   }
   prevLeft := tree.left
   if prevLeft != nil {
      tree.left = prevLeft.right //tree.left passed root its right branch
      prevLeft.right = tree      //tree becomes tree.left's right branch
      tree.updateHeight()
      prevLeft.updateHeight()
      tree = prevLeft            //desired behaviour: tree.left becomes the new tree
                                 //actual behaviour: no effect when function returns
   }
}

我试过设置树的值或地址的其他组合，其中 none 达到了预期的效果。例如，*tree = *prevLeft 导致无限循环。

附加说明：返回 tree 并设置 "tree = tree.rotateLeftToRoot()" 可避免此问题。这行得通，但是当调用者真的只是想调用一个函数来更新树时，混合效果并要求分配给返回值似乎很脏。

可以从函数中将 tree 设置为 prevLeft 吗？

Answer 1

指针是值，就像我们说 int 数字一样。不同之处在于对该值的解释：指针被解释为内存地址，ints 被解释为整数。

当你想改变int类型变量的值时，你传递一个指向int类型*int的指针，然后修改指向的对象: *i = newvalue（分配的值是 int）。

指针也是如此：当你想改变指针类型*int的变量的值时，你传递一个指向*int类型**int的指针，并且您修改指向的对象：*i = &newvalue（分配的值是 *int）。

^{需要传递一个指针，因为你传递的所有内容都会生成一个副本，你只能修改这个副本。当你传递一个指针时，同样的事情会发生：一个副本也由那个指针组成，但我们不是在修改指针本身，而是修改 pointed 值。}

您要修改 *AvlTree 类型的变量。在 Go 中，接收者不能是指向指针的指针。 Spec: Method declarations:

The receiver's type must be of the form T or *T(possibly using parentheses) where T is a type name. The type denoted by T is called the receiver base type; it must not be a pointer or interface type and it must be declared in the same package as the method.

所以你有两个选择：

要么写一个简单的函数（不是方法）接受一个 **AvlTree 并且你可以传递你的树指针的地址，这样函数就可以修改树指针（指向的对象)
或 return 来自 function/method 的树指针，并让调用者将其分配给作为树指针的变量。

解决您对 return树指针的担忧：这没有任何问题。看看内置函数 append()：它将元素附加到切片和 return 修改后的切片。您（调用者）必须将 returned 切片分配给您的切片变量，因为如果附加元素不适合原始切片，append() 可能会通过分配一个新切片来修改切片（并且由于 append()取一个非指针，修改后的值必须returned).

#1 的解决方案如下所示：

func rotateLeftToRoot(ptree **AvlTree) {
    tree := *ptree
    if tree == nil {
        return
    }
    prevLeft := tree.left
    if prevLeft != nil {
        tree.left = prevLeft.right
        prevLeft.right = tree
        tree = prevLeft
    }
    *ptree = tree
}

我已经在 Go Playground 上实现了它以证明它有效。

我用过这种：

type AvlTree struct {
    value string
    left  *AvlTree
    right *AvlTree
}

为了方便地检查结果，我实现了一些方法来生成 string 表示：

func (tree *AvlTree) String() string { return tree.str(1) }

func (tree *AvlTree) str(n int) string {
    if tree == nil {
        return "<nil>"
    }
    return fmt.Sprintf("%q\n%s%v,%v\n%s", tree.value, strings.Repeat("\t", n),
        tree.left.str(n+1), tree.right.str(n+1), strings.Repeat("\t", n-1))
}

这就是树的构造和转换方式：

tree := &AvlTree{
    value: "t",
    left: &AvlTree{
        value: "L",
        left: &AvlTree{
            value: "LL",
        },
        right: &AvlTree{
            value: "LR",
        },
    },
    right: &AvlTree{
        value: "R",
    },
}
fmt.Println(tree)
rotateLeftToRoot(&tree)
fmt.Println(tree)

原树（未变换）：

"t"
    "L"
        "LL"
            <nil>,<nil>
        ,"LR"
            <nil>,<nil>

    ,"R"
        <nil>,<nil>

以及转换后的树（正是您想要的）：

"L"
    "LL"
        <nil>,<nil>
    ,"t"
        "LR"
            <nil>,<nil>
        ,"R"
            <nil>,<nil>

结构指针方法中的指针可以重新分配给另一个实例吗？

Can the pointer in a struct pointer method be reassigned to another instance?

methods

tree

pointers

go