我一直在研究 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
从函数内部?
最佳答案
指针是值,就像我们说 int
数字。不同之处在于该值的解释:指针被解释为内存地址,int
s 被解释为整数。
当您想要更改 int
类型变量的值时,你传递一个指向 int
的指针类型为 *int
,然后修改指向的对象:*i = newvalue
(分配的值为 int
)。
指针也一样:当你想改变指针类型的变量的值时 *int
,你传递一个指向 *int
的指针类型为 **int
然后修改指向的对象:*i = &newvalue
(分配的值为 *int
)。
传递指针是必需的,因为您传递的所有内容都会生成副本,并且您只能修改副本。当你传递一个指针时,同样的事情会发生:该指针也有一个副本,但我们不是在修改指针本身,而是修改指向的值。
您想修改 *AvlTree
类型的变量.在 Go 中,接收者不能是指向指针的指针。 Spec: Method declarations:
The receiver's type must be of the form
T
or*T
(possibly using parentheses) whereT
is a type name. The type denoted byT
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.
所以你有2个选择:
**AvlTree
并且您可以传递树指针的地址,因此该函数可以修改树指针(指向的对象)解决您对返回树指针的担忧:这没有错。看看内置函数
append()
:它将元素附加到 slice 并返回修改后的 slice 。您(调用者)必须将返回的 slice 分配给 slice 变量,因为 append()
如果附加元素不适合原始元素,则可以通过分配新元素来修改 slice (并且由于 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>
关于pointers - 可以将结构指针方法中的指针重新分配给另一个实例吗?,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/64003640/