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

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

我已经尝试过设置树的值或地址的其他组合,但没有一个具有预期的效果.例如,*tree = *prevLeft导致无限循环.

附加说明:返回tree和设置"tree = tree.rotateLeftToRoot()"可避免此问题.这是有效的,但是当调用者真的只想调用函数来更新树时,混合效果并要求赋值给返回值似乎很脏.

可以在函数内tree设置prevLeft吗？

Answer 1

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

当要改变类型的变量的值int,则通过一个指向int它的类型的*int,并且修改尖锐的物体:*i = newvalue(分配值是一个int).

也是一样的指针:当要改变指针类型的变量的值*int,则通过一个指向*int它的类型的**int和修改尖锐的物体:*i = &newvalue(分配值是一个*int).

^{传递指针是必需的,因为复制是从您传递的所有内容制作的,并且您只能修改副本.当你传递一个指针,同样的事情发生了:一个副本也取得了该指针的,但我们不修改该指针本身,而是尖锐的价值.}

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

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

所以你有两个选择:

1. 要么写一个简单的函数(不是方法),它**AvlTree可以传递树指针的地址,所以函数可以修改树指针(指向对象)

2. 或者从函数/方法返回树指针,并让调用者将其指定给作为树指针的变量.

解决有关返回树指针的问题:这没有任何问题.看看内置函数append():它将元素附加到切片并返回修改后的切片.您(调用者)必须将返回的切片分配给切片变量,因为append()如果附加元素不适合原始切片,则可以通过分配新切片来修改切片(并​​且由于append()采用非指针,因此修改后的值必须为回).

以下是#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>