我对“客户邀请”有疑问,其中一个人可以邀请另一个人,并且邀请仅在被邀请人邀请某人时才有效。
为了解决这个问题,我想写一个树算法而不是图算法。
我正在尝试用 Scala 编写这个树结构,我是这样开始的:
case class MyNode(key:Int, children:Option[List[MyNode]] = None)
class MyNodeManager {
def find(key: Int, tree: Option[List[MyNode]]) = tree match {
case None => None
case (h :: t) =>
println("aa")
/*if(h.key == key)
Option(h)
else
find(h ::: t)
*/
}
}
输入将是这样的:
val invites = List((1, 2), (1, 3), (3, 6))
我想使用 Option[List[MyNode]],因为子节点是可选的,如果节点已被邀请,我想将值设置为一个空列表而不是 None。
树是解决我的问题的最佳结构,还是我应该去图或类似的东西(图中的一个节点可以有多个子节点?)?另一个问题……这些行 (h::t) 和 (h::: t) 有什么区别?
以下代码存在编译错误:
Error:(16, 13) constructor cannot be instantiated to expected type;
found : scala.collection.immutable.::[B]
required: Option[List[MyNode]]
case (h :: t) =>
^
如何使用 Option[List]?
最佳答案
应该是
def find(key: Int, tree: Option[List[MyNode]]) = tree match {
case None => None
case Some(h :: t) =>
println("aa")
/*if(h.key == key)
Option(h)
else
find(h ::: t)
*/}
你匹配的是选项对象而不是元组。 这场比赛并不详尽,因为你错过了
case Some(Nil) => ....
我发现只使用没有可选的列表会更好。这主要是关于语义的。可选意味着有些东西是空的。我们有空列表(Nil)的值,所以我们不需要使用额外的对象来标记这种情况。空列表应该足够了
::: 函数在您的列表前面添加给定列表的元素。这个函数只是用来连接两个列表
:: 是在列表开头添加元素的函数。
同样在 Scala 中,:: 是一个有头和尾的案例类。如果您想了解更多关于 List 实现的信息,我建议您阅读 https://www.amazon.com/Functional-Programming-Scala-Paul-Chiusano/dp/1617290653
关于algorithm - Scala 树/图实现,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/40398669/