题目⌗

实现如下结构体的深拷贝。

type Node struct {
	Data int
	Fields []*Node
}

即指针指向的内存也需要Copy一份。

解析⌗

观察结构体，由于Fields字段里存放的是指向Node结构体的指针切片，深拷贝时要考虑循环引用的问题，如：

struct a :
  data: 1
  fields: b, c
struct b:
  data: 2
  fields: c
struct c:
  data: 3
  fields: a  // 这里循环引用了a， c->a->b, c->a

可以考虑使用map[*Node]*Node来判断是否有环的情况，即用map[src] = dst来保存拷贝过的节点。

代码⌗

代码如下：

package main

import (
	"go/ast"
	"go/token"
)

type Node struct {
	Data int
	Fields []*Node
}

// deep copy
var M map[*Node]*Node
func Dup(src *Node) *Node {
	if src == nil {
		return nil
	}
	node := &Node{
		Data: src.Data,
		Fields: nil,
	}
	M[src] = node
	fields := []*Node{}//make([]*Node, len(src.Fields))
	for i:=0;i<len(src.Fields);i++ {
		var tmp *Node
		if src.Fields[i] != nil {
			// if exist, is loop
			if addr, ok := M[src.Fields[i]]; ok {
				tmp = addr
			} else {
				tmp = Dup(src.Fields[i])
			}
		}
		if tmp != nil {
			fields = append(fields, tmp)
		}
	}
	node.Fields = fields
	return node
}

func main()  {
	M = make(map[*Node]*Node)

	a1 := &Node{
		Data:   1,
		Fields: nil,
	}
	a2 := &Node{
		Data:   2,
		Fields: nil,
	}
	a3 := &Node{
		Data:   3,
		Fields: []*Node{a1, a2},
	}
	a1.Fields = append(a1.Fields, a3)
	da3 := Dup(a3)
    // print ast tree
	_ = ast.Print(token.NewFileSet(),a3)
	_ = ast.Print(token.NewFileSet(),da3)
}

输出如下：

    // a3
     0  *main.Node {
     1  .  Data: 3
     2  .  Fields: []*main.Node (len = 2) {
     3  .  .  0: *main.Node {
     4  .  .  .  Data: 1
     5  .  .  .  Fields: []*main.Node (len = 1) {
     6  .  .  .  .  0: *(obj @ 0) // 指向了0行的obj
     7  .  .  .  }
     8  .  .  }
     9  .  .  1: *main.Node {
    10  .  .  .  Data: 2
    11  .  .  }
    12  .  }
    13  }
    // da3
     0  *main.Node {
     1  .  Data: 3
     2  .  Fields: []*main.Node (len = 2) {
     3  .  .  0: *main.Node {
     4  .  .  .  Data: 1
     5  .  .  .  Fields: []*main.Node (len = 1) {
     6  .  .  .  .  0: *(obj @ 0)  // 同样指向了0行的obj
     7  .  .  .  }
     8  .  .  }
     9  .  .  1: *main.Node {
    10  .  .  .  Data: 2
    11  .  .  .  Fields: []*main.Node (len = 0) {}
    12  .  .  }
    13  .  }
    14  }

再来调试看看运行时的地址情况： a3的信息如下： bd51ff320eef1f13f01579625118d58.png

da3的信息如下：

55bb9aa7a950f59e1bf2d73719fe209.png

可以看到，da3里面的地址与a3均不一样，但是值信息是一样的。