dictionary - 如何链接 LinkedList 节点以映射值

Question

我想实现一个图形数据结构，其中每个节点表示为：

type Node struct {
    root  string
    links []*Node
}

基本上每个节点都有一个值root和一个链接列表，对于每个链接 a 只想存储一个指向它的指针，因为结构的内存将由映射分配和拥有：

rooturl := "root"
graph := Node{rooturl, []*Node{}}
graphMap := make(map[string]Node)
graphMap[rooturl] = graph

当我尝试将指针附加到新创建的节点时，问题就来了：

u := "new node"
// if the link is not stored in the graph not create a new node
if _, exists := graphMap[u]; !exists {
    graphMap[u] = Node{u, []*Node{}}
}
// add the links to the graph
graphMap[rooturl].links = append(graphMap[rooturl].links, &graphMap[u])

我收到两个错误：

无法分配给地图中的结构字段 graphMap[rooturl].links

和

不能取graphMap[u]的地址

我应该如何正确解决这个问题？我还希望graphMap[rooturl].links在追加时需要两次查询地图（但由于我无法获取指针或对它的引用，我不知道如何）

标签： dictionarypointersgolinked-list

Answer 1

你试图实现的事情不可能以你的方式实现。这是关于可寻址性和可分配性。您应该搜索此关键字的语言规范。映射值不可寻址，因此该值中的 struct 字段不可分配。此外，至少对我而言，您的数据结构设计看起来也不是很有效。

在我看来，没有理由将值存储在地图中，参考就足够了

type Node struct {
    root  string
    links []*Node
}
//////
rooturl := "root"
graph := Node{rooturl, []*Node{}}
graphMap := make(map[string]*Node)
graphMap[rooturl] = &graph
u := "new node"
// if the link is not stored in the graph not create a new node
if _, exists := graphMap[u]; !exists {
    graphMap[u] = &Node{u, []*Node{}}
}
// add the links to the graph
graphMap[rooturl].links = append(graphMap[rooturl].links, graphMap[u])

工作示例

如果您更喜欢将实际值保留在地图中，则根本不需要树结构。它看起来像不需要的开销。存储在地图中的信息对于任何操作都足够了。

type Node string
type Graph map[Node][]Node
////
rooturl := Node("root")
graph := make(Graph)
graph[rooturl] = make([]Node, 0)
u := Node("new node")
// if the link is not stored in the graph not create a new node
if node, exists := graph[u]; !exists {
    graph[u] = make([]Node, 0)
    graph[rooturl] = append(graph[rooturl], u)
}

工作示例