转到

本文介绍了转到 - 使用容器/堆实现优先级队列的处理方法，对大家解决问题具有一定的参考价值，需要的朋友们下面随着小编来一起学习吧！ 问题描述 总的来说，我试图使用优先级队列来实现Dijkstra的算法。

根据golang-nuts的成员，在Go中执行此操作的惯用方式是使用具有自定义底层数据结构的堆接口。所以我创建了Node.go和PQueue.go，如下所示：

// Node.go 包pqueue 类型节点struct {行int col int myVal int sumVal int } func（ n * Node）Init（r，c，mv，sv int）{ n.row = r n.col = c n.myVal = mv n.sumVal = sv } func（n * Node）Equals（o * Node）bool { return n.row == o.row&& n.col == o.col }

和PQueue.go：

// PQueue.go 包pqueue 导入container / vector importcontainer / heap type PQueue struct { data vector.Vector size int } func（pq * PQueue ）Init（）{ heap.Init（pq）} func（pq * PQueue）IsEmpty（）bool { return pq.size == 0 $ b func（pq * PQueue）Push（i interface {}）{ heap.Push（pq，i） pq.size ++ } func（pq * PQueue）Pop（）接口{} { pq.size-- return heap.Pop（pq）} func（pq * PQueue）Len（）int { return pq.size } func（pq * PQueue）Less（i，j int） bool { I：= pq.data.At（i）。（Node） J：= pq.data.At（j）。（Node） return（I.sumVal + I.myVal） （J.sumVal + J.myVal）} func（pq * PQueue）Swap（i，j int）{ temp：= pq.data.At（i ）。（Node） pq.data.Set（i，pq.data.At（j）。（Node）） pq.data.Set（j，temp）}

和main.go :(行动在SolveMatrix中）

// Euler 81 软件包主要 导入fmt导入io / ioutil importstrings importstrconv import./pqueue const MATSIZE = 5 const MATNAME =matrix_small.txt func main（）{ var matrix [MATSIZE] [MATSIZE] int contents，err：= ioutil.ReadFile（MATNAME） if err！= nil { panic（FILE IO ERROR！）} inFileStr：= string（contents）yrows：= strings.Split（inFileStr，\\\， - 1）行 = 0;行< MATSIZE; row ++ { byrows [row] =（byrows [row]）[0：len（byrows [row]） - 1] bycols：= strings.Split（byrows [row]，， -1）为col：= 0; col< MATSIZE; col ++ { matrix [row] [col]，_ = strconv.Atoi（bycols [col]）} } PrintMatrix（矩阵） sum，len：= SolveMatrix（矩阵） fmt.Printf（len：％d，sum：％d \ n，len，sum）} func PrintMatrix（mat [MATSIZE] [MATSIZE] int）{ for r：= 0; r< MATSIZE; r ++ { for c：= 0; c< MATSIZE; c ++ { fmt.Printf（％d，mat [r] [c]）} fmt.Print（\\\）} } func SolveMatrix（mat [MATSIZE] [MATSIZE] int）（int，int）{ var PQ pqueue.PQueue var firstNode pqueue.Node var endNode pqueue.Node msm1：= MATSIZE - 1 firstNode.Init（0，0，mat [0] [0]，0） endNode.Init（msm1 ，msm1，mat [msm1] [msm1]，0） if PQ.IsEmpty（）{//编译器关于未使用的变量stfu fmt.Print（empty） PQ.Push（firstNode）//问题 返回0，0 }

$ b

问题是，在编译时我得到错误信息：

[〜/ Code / Euler / 81] $ make 6g -o pqueue.6 Node.go PQueue.go 6g main.go main.go：58 ：在函数参数中隐式赋值pqueue.Node的未导出的字段行：make [***]错误1

并发表评论出PQ.Push（firstNode）确实符合编译器。但我不明白为什么我首先得到错误信息。推并不以任何方式修改参数。

更新：为了未来在搜索中遇到这种情况，充满了严重的误解。请看下面的一个更实用的模板： Node.go：

//节点.go 包pqueue 导入fmt 类型节点struct {行int col int myVal int sumVal int parent * Node } func NewNode（r，c，mv，sv int，n * Node）* Node { return & Node {r，c，mv，sv，n} } func（n * Node）等式（o * Node）bool { return n.row = = o.row&& n.col == o.col } func（n * Node）String（）string { return fmt.Sprintf（{％d，％d，％ d，％d}，n.row，n.col，n.myVal，n.sumVal）} func（n * Node）Row（）int {返回n.row } func（n * Node）Col（）int { return n.col } func（n * Node）SetParent（p * Node）{ n.parent = p } func（n * Node）Parent（）* Node {返回n.parent } func（n * Node）MyVal（）int { return n.myVal } func（n * Node）SumVal（）int { return n.sumVal } func（n * Node）SetSumVal（sv int）{ n。 sumVal = sv }

PQueue.go：

// PQueue.go 包pqueue 类型PQueue [] *节点 func（ pq * PQueue）IsEmpty（）bool { return len（* pq）== 0 } func（pq * PQueue）Push（i interface {}）{a：= * pq n：= len（a）a = a [0：n + 1] r：= i。（* Node）a [n] = r * pq = a } func（pq * PQueue）Pop（）interface { } {a：= * pq * pq = a [0：len（a）-1] r：= a [len（a）-1] return r $ b func（pq * PQueue）Len（）int { return len（* pq）} // post： true iff is i less than j func（pq * PQueue）Less（i，j int）bool { I：=（* pq）[i] J：=（* pq ）[j] return（I.sumVal + I.myVal）< （J.sumVal + J.myVal）} func（pq * PQueue）Swap（i，j int）{（* pq）[i]，（* pq）[j] =（* pq）[j]，（* pq）[i] } func（pq * PQueue）String（）string { var build string ={ for _，v：= range * pq { build + = v.String（）} build + =} $ return b

解决方案

package main var PQ pqueue.PQueue var firstNode pqueue.Node PQ.Push（firstNode）

变量 firstNode 通过值传递，这意味着有一个隐含的参数赋值给参数in函数调用 PQ.Push（firstNode）。类型 pqueue.Node 包含不是从 package pqueue中导出的私有字段，例如 row to package main ：在函数参数中隐式赋值pqueue.Node的未导出字段'row'。

在 Node.go 中，将此函数添加到 package pqueue ：

func NewNode（）* Node { return& Node {} } func NewPQueue（）* PQueue { return& PQueue {} }

然后。在 package main 中，你可以这样写：

PQ：= pqueue。 NewPQueue（） firstNode：= pqueue.NewNode（） PQ.Push（firstNode）

In the big picture, I'm trying to implement Dijkstra's algorithm using a priority queue.

According to members of golang-nuts, the idiomatic way to do this in Go is to use the heap interface with a custom underlying data structure. So I have created Node.go and PQueue.go like so:

//Node.go package pqueue type Node struct { row int col int myVal int sumVal int } func (n *Node) Init(r, c, mv, sv int) { n.row = r n.col = c n.myVal = mv n.sumVal = sv } func (n *Node) Equals(o *Node) bool { return n.row == o.row && n.col == o.col }

And PQueue.go:

// PQueue.go package pqueue import "container/vector" import "container/heap" type PQueue struct { data vector.Vector size int } func (pq *PQueue) Init() { heap.Init(pq) } func (pq *PQueue) IsEmpty() bool { return pq.size == 0 } func (pq *PQueue) Push(i interface{}) { heap.Push(pq, i) pq.size++ } func (pq *PQueue) Pop() interface{} { pq.size-- return heap.Pop(pq) } func (pq *PQueue) Len() int { return pq.size } func (pq *PQueue) Less(i, j int) bool { I := pq.data.At(i).(Node) J := pq.data.At(j).(Node) return (I.sumVal + I.myVal) < (J.sumVal + J.myVal) } func (pq *PQueue) Swap(i, j int) { temp := pq.data.At(i).(Node) pq.data.Set(i, pq.data.At(j).(Node)) pq.data.Set(j, temp) }

And main.go: (the action is in SolveMatrix)

// Euler 81 package main import "fmt" import "io/ioutil" import "strings" import "strconv" import "./pqueue" const MATSIZE = 5 const MATNAME = "matrix_small.txt" func main() { var matrix [MATSIZE][MATSIZE]int contents, err := ioutil.ReadFile(MATNAME) if err != nil { panic("FILE IO ERROR!") } inFileStr := string(contents) byrows := strings.Split(inFileStr, "\n", -1) for row := 0; row < MATSIZE; row++ { byrows[row] = (byrows[row])[0 : len(byrows[row])-1] bycols := strings.Split(byrows[row], ",", -1) for col := 0; col < MATSIZE; col++ { matrix[row][col], _ = strconv.Atoi(bycols[col]) } } PrintMatrix(matrix) sum, len := SolveMatrix(matrix) fmt.Printf("len: %d, sum: %d\n", len, sum) } func PrintMatrix(mat [MATSIZE][MATSIZE]int) { for r := 0; r < MATSIZE; r++ { for c := 0; c < MATSIZE; c++ { fmt.Printf("%d ", mat[r][c]) } fmt.Print("\n") } } func SolveMatrix(mat [MATSIZE][MATSIZE]int) (int, int) { var PQ pqueue.PQueue var firstNode pqueue.Node var endNode pqueue.Node msm1 := MATSIZE - 1 firstNode.Init(0, 0, mat[0][0], 0) endNode.Init(msm1, msm1, mat[msm1][msm1], 0) if PQ.IsEmpty() { // make compiler stfu about unused variable fmt.Print("empty") } PQ.Push(firstNode) // problem return 0, 0 }

The problem is, upon compiling i get the error message:

[~/Code/Euler/81] $ make 6g -o pqueue.6 Node.go PQueue.go 6g main.go main.go:58: implicit assignment of unexported field 'row' of pqueue.Node in function argument make: *** [all] Error 1

And commenting out the line PQ.Push(firstNode) does satisfy the compiler. But I don't understand why I'm getting the error message in the first place. Push doesn't modify the argument in any way.

UPDATE: For the sake of those who come across this in searches in the future, the code above is chock full of gross misconceptions. Take a look below for a much more useful template to work off of: Node.go:

// Node.go package pqueue import "fmt" type Node struct { row int col int myVal int sumVal int parent *Node } func NewNode(r, c, mv, sv int, n *Node) *Node { return &Node{r, c, mv, sv, n} } func (n *Node) Eq(o *Node) bool { return n.row == o.row && n.col == o.col } func (n *Node) String() string { return fmt.Sprintf("{%d, %d, %d, %d}", n.row, n.col, n.myVal, n.sumVal) } func (n *Node) Row() int { return n.row } func (n *Node) Col() int { return n.col } func (n *Node) SetParent(p *Node) { n.parent = p } func (n *Node) Parent() *Node { return n.parent } func (n *Node) MyVal() int { return n.myVal } func (n *Node) SumVal() int { return n.sumVal } func (n *Node) SetSumVal(sv int) { n.sumVal = sv }

PQueue.go:

// PQueue.go package pqueue type PQueue []*Node func (pq *PQueue) IsEmpty() bool { return len(*pq) == 0 } func (pq *PQueue) Push(i interface{}) { a := *pq n := len(a) a = a[0 : n+1] r := i.(*Node) a[n] = r *pq = a } func (pq *PQueue) Pop() interface{} { a := *pq *pq = a[0 : len(a)-1] r := a[len(a)-1] return r } func (pq *PQueue) Len() int { return len(*pq) } // post: true iff is i less than j func (pq *PQueue) Less(i, j int) bool { I := (*pq)[i] J := (*pq)[j] return (I.sumVal + I.myVal) < (J.sumVal + J.myVal) } func (pq *PQueue) Swap(i, j int) { (*pq)[i], (*pq)[j] = (*pq)[j], (*pq)[i] } func (pq *PQueue) String() string { var build string = "{" for _, v := range *pq { build += v.String() } build += "}" return build }

解决方案

package main var PQ pqueue.PQueue var firstNode pqueue.Node PQ.Push(firstNode)

The variable firstNode is passed by value which means that there is an implicit assignment of the argument to the parameter in the function call PQ.Push(firstNode). The type pqueue.Node contains private fields such as row which are not exported from package pqueue to package main: "implicit assignment of unexported field 'row' of pqueue.Node in function argument."

In Node.go, add this function to package pqueue:

func NewNode() *Node { return &Node{} }

In PQueue.go, add this function to package pqueue:

func NewPQueue() *PQueue { return &PQueue{} }

Then. in package main, you can write:

PQ := pqueue.NewPQueue() firstNode := pqueue.NewNode() PQ.Push(firstNode)