struct 指针方法中的指针可以重新分配给另一个实例吗?

问题描述

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

I've been looking into Golang and have been implementing a few data structures to learn how the language works. I've come across the following issue while writing the code for an AVL tree:

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

Assigning the primary pointer from a struct pointer method seems to have no effect outside the scope of the function. E.g. tree.rotateLeftToRoot() doesn't result in tree.left becoming the new tree.

问题: 有没有办法在 Golang 的 struct 指针方法中重新分配指针，还是通常不鼓励这样做?在示例中，这将是 "tree = prevLeft" 行.

Question: Is there a way to reassign the pointer in a struct pointer method in Golang, or is this generally discouraged? In the example this would be the "tree = prevLeft" line.

代码片段:

//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
   }
}

我尝试了设置树的值或地址的其他组合，但都没有达到预期的效果.例如，*tree = *prevLeft 导致无限循环.

I've tried other combinations of setting the value or address of tree, and none of them had the intended effect. For example, *tree = *prevLeft results in an infinite loop.

附加说明:返回 tree 并设置 "tree = tree.rotateLeftToRoot()" 可以避免该问题.这是可行的，但是当调用者真的只想能够调用一个函数来更新树时，混合效果并要求对返回值进行赋值似乎很脏.

Additional note: Returning tree and setting "tree = tree.rotateLeftToRoot()" avoids the issue. This works, but it seems dirty to be mixing effects and requiring assignment to returned values, when the caller really just wants to be able to call a function to update the tree.

tree 可以在函数内设置为 prevLeft 吗?

Can the tree be set to prevLeft from within the function?

推荐答案

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

Pointers are values just like let's say int numbers. The difference is the interpretation of that value: pointers are interpreted as memory addresses, and ints are interpreted as integer numbers.

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

When you want to change the value of a variable of type int, you pass a pointer to that int which is of type *int, and you modify the pointed object: *i = newvalue (the value assigned is an int).

指针也是一样:当你想改变一个指针类型*int的变量的值时，你传递一个指向那个*int的指针，它的类型是**int 并修改指向的对象:*i = &newvalue(分配的值是 *int).

Same goes with pointers: when you want to change the value of a variable of pointer type *int, you pass a pointer to that *int which is of type **int and you modify the pointed object: *i = &newvalue (the value assigned is an *int).

您想修改 *AvlTree 类型的变量.在 Go 中，接收者不能是指向指针的指针.规范:方法声明:

You want to modify a variable of type *AvlTree. In Go the receiver cannot be a pointer to pointer. Spec: Method declarations:

接收者的类型必须是 T 或 *T(可能使用括号)的形式，其中 T 是一个类型名称.T 表示的类型称为接收者基类型；它不能是指针或接口类型，并且必须与方法在同一个包中声明.

所以你有两个选择:

1. 要么写一个简单的函数(不是方法)，它接受一个 **AvlTree 并且你可以传递你的树指针的地址，这样函数就可以修改树指针(指向的对象)

1. either write a simple function (not method) that takes a **AvlTree and you can pass the address of your tree pointer, so the function can modify the tree pointer (the pointed object)

或从您的函数/方法返回树指针，并让调用者将其分配给作为树指针的变量.

or return the tree pointer from your function/method and have the caller assign it to the variable being the tree pointer.

解决您对返回树指针的担忧:这没有错.看看内置函数 append():它追加元素到切片 和 返回修改后的切片.您(调用者)必须将返回的切片分配给切片变量，因为如果附加元素不适合原始元素(并且由于 append() 可能会通过分配新的切片来修改切片code>append() 采用非指针，必须返回修改后的值.

Addressing your concerns regarding returning the tree pointer: there's nothing wrong with that. Take a look at the builtin function append(): it appends elements to a slice and returns the modified slice. You (the caller) have to assign the returned slice to your slice variable, because append() may modify the slice by allocating a new one if the additional elements do not fit into the original (and since append() takes a non-pointer, the modified value must be returned).

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

Here's how the solution going with #1 would look like:

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 上实现了它，以证明它有效.

I've implemented it on the Go Playground to prove it works.

我用过这种类型:

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

为了轻松检查结果，我实现了一些方法来生成 string 表示:

And to easily check the result, I've implemented some methods to produce a string representation:

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
%s%v,%v
%s", tree.value, strings.Repeat("	", n),
        tree.left.str(n+1), tree.right.str(n+1), strings.Repeat("	", n-1))
}

这就是一棵树的构造和转换方式:

And this is how a tree is constructed and transformed:

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>

以及转换后的树(正是您想要的):

And the transformed tree (exactly what you wanted):

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

这篇关于struct 指针方法中的指针可以重新分配给另一个实例吗?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持！