我的迭代函数有什么问题？

huangapple
go评论122阅读模式
英文:

What is wrong with my iterate function

问题

我正在尝试迭代一个简单的链表。这应该很简单，但是它不起作用。问题出在iterate函数中。

  1. package main
  3. import (
  4. 	"fmt"
  5. 	"time"
  6. )
  8. type Node struct {
  9. 	Next  *Node
  10. 	Value int
  11. }
  13. func main() {
  14. 	//Load up 100 *Node in a linked list (albeit a simple one)
  15. 	head := &Node{Value: 0}
  16. 	current := head
  17. 	for i := 1; i < 100; i++ {
  18. 		current.Next = &Node{Value: i}
  19. 		current = current.Next
  20. 		fmt.Printf("current %p %+v\n", current, current)
  21. 	}
  23. 	iterate(head)
  24. }
  26. //Iterate through the list starting at head. It never 
  27. //advances past the first "Next", loops forever.
  28. func iterate(head *Node) {
  29. 	for n := head.Next; n != nil; head = n {
  30. 		fmt.Printf("head %+v n %+v\n", head, n)
  31. 		time.Sleep(time.Second * 1)
  32. 	}
  33. }

iterate函数的输出结果如下：

  1. head &{Next:0x20818c230 Value:0} n &{Next:0x20818c280 Value:1}
  2. head &{Next:0x20818c280 Value:1} n &{Next:0x20818c280 Value:1}
  3. head &{Next:0x20818c280 Value:1} n &{Next:0x20818c280 Value:1}
  4. head &{Next:0x20818c280 Value:1} n &{Next:0x20818c280 Value:1}
  5. head &{Next:0x20818c280 Value:1} n &{Next:0x20818c280 Value:1}

出于好奇，我尝试了另一个版本的iterate循环，它使用一个函数来获取.Next。我的想法是，也许head.Next总是指向原始head，因为存在某种循环优化。但这个理论似乎是错误的。

  1. func iterate(head *Node) {
  2. 	getNext := func (n *Node) *Node {
  3. 		return n.Next
  4. 	}
  6. 	for n := getNext(head); n != nil; head = n {
  7. 		fmt.Printf("head %+v n %+v\n", head, n)
  8. 		time.Sleep(time.Second * 1)
  9. 	}
  10. }

天哪，我是不是看不到问题所在？我在循环体执行后将head设置为n，即下一个节点。难道下一个head.Next不应该返回后续的节点，直到我们到达一个空节点并退出循环吗？

--- 更新 ---

我对iterate进行了以下修改，现在更加简洁且正确：

  1. func iterate(head *Node) {
  2. 	for ; head != nil; head = head.Next {
  3. 		fmt.Printf("head %+v head.Next %+v\n", head, head.Next)
  4. 	}
  5. }
英文:

I am attempting to iterate over a simple linked list. This should be so simple, but it's not working. The iterate function contains the issue.

  1. package main
  3. import (
  4. 	&quot;fmt&quot;
  5. 	&quot;time&quot;
  6. )
  8. type Node struct {
  9. 	Next  *Node
  10. 	Value int
  11. }
  13. func main() {
  14. 	//Load up 100 *Node in a linked list (albeit a simple one)
  15. 	head := &amp;Node{Value: 0}
  16. 	current := head
  17. 	for i := 1; i &lt; 100; i++ {
  18. 		current.Next = &amp;Node{Value: i}
  19. 		current = current.Next
  20. 		fmt.Printf(&quot;current %p %+v\n&quot;, current, current)
  21. 	}
  23. 	iterate(head)
  24. }
  26. //Iterate through the list starting at head. It never 
  27. //advances past the first &quot;Next&quot;, loops forever.
  28. func iterate(head *Node) {
  29. 	for n := head.Next; n != nil; head = n {
  30. 		fmt.Printf(&quot;head %+v n %+v\n&quot;, head, n)
  31. 		time.Sleep(time.Second * 1)
  32. 	}
  33. }

The output of iterate looks something like:

  1. head &amp;{Next:0x20818c230 Value:0} n &amp;{Next:0x20818c280 Value:1}
  2. head &amp;{Next:0x20818c280 Value:1} n &amp;{Next:0x20818c280 Value:1}
  3. head &amp;{Next:0x20818c280 Value:1} n &amp;{Next:0x20818c280 Value:1}
  4. head &amp;{Next:0x20818c280 Value:1} n &amp;{Next:0x20818c280 Value:1}
  5. head &amp;{Next:0x20818c280 Value:1} n &amp;{Next:0x20818c280 Value:1}

For kicks I tried another version of the iterate loop that uses a function to fetch .Next. My thinking was that maybe head.Next was always pointing at my original head due to some sort of loop optimization. That theory seems incorrect.

  1. func iterate(head *Node) {
  2. 	getNext := func (n *Node) *Node {
  3. 		return n.Next
  4. 	}
  6. 	for n := getNext(head); n != nil; head = n {
  7. 		fmt.Printf(&quot;head %+v n %+v\n&quot;, head, n)
  8. 		time.Sleep(time.Second * 1)
  9. 	}
  10. }

Gosh, am I just not seeing it? I set head to n after the loop body executes which is equal to the next Node. Shouldn't the next head.Next return the subsequent Node until we get to a nil node and exit the loop?

--- Update ---

I've come up with the following modification to iterate which is so much cleaner and actually correct now:

  1. func iterate(head *Node) {
  2. 	for ; head != nil; head = head.Next {
  3. 		fmt.Printf(&quot;head %+v head.Next %+v\n&quot;, head, head.Next)
  4. 	}
  5. }

答案1

得分: 4

查看For语句规范：

  • 循环的“初始化语句”部分（n := head.Next）只会被评估一次。
  • 后置语句会将head重置为n的初始值（getNext(head)）。

因此导致了无限循环。

将n := getNext(head)放在循环内部会更好，就像这个可工作的示例一样：

  1. for n := head; n != nil; head = n {
  2.     fmt.Printf("head %+v n %+v\n", head, n)
  3.     time.Sleep(time.Second * 1)
  4.     n = head.Next
  5. }
英文:

Looking at the For statement spec:

  • The "init statement" part of your loop (n := head.Next) is evaluated only once.
  • The post statement keeps resetting head to the initial value of n (getNext(head)).

Hence the inifinite loop.

Putting n := getNext(head) within the loop should be better, as in this working example:

  1. for n := head; n != nil; head = n {
  2. 	fmt.Printf(&quot;head %+v n %+v\n&quot;, head, n)
  3. 	time.Sleep(time.Second * 1)
  4. 	n = head.Next
  5. }

答案2

得分: 3

n := head.Next 只运行一次。

在 for ①; ②; ③ { ④ } 中，

它运行 ① - ②④③ - ②④③ - ②④③ - ...

所以你应该将迭代放在 ③ 中，当然，你也可以将其放在 ② 或 ④ 中，但这不太明显。

英文:

n := head.Next just run once.

in for ①; ②; ③ { ④ }

it runs ① - ②④③ - ②④③ - ②④③ - ...

so you should put the iteration in ③, of course, you can put it in ② or ④ but it's not very obvious.

huangapple
  • 本文由 发表于 2015年2月27日 14:58:00
  • 转载请务必保留本文链接：https://go.coder-hub.com/28759275.html
  • go
  • linked-list
  • loops
  • pointers
匿名

发表评论

匿名网友

:?: :razz: :sad: :evil: :!: :smile: :oops: :grin: :eek: :shock: :???: :cool: :lol: :mad: :twisted: :roll: :wink: :idea: :arrow: :neutral: :cry: :mrgreen:

确定