首页 > 代码库 > Scala 的list

Scala 的list

9.1 使用列表

  列表类型:跟数组一样,列表也是同质化的(homogeneous)。即所有元素都要是同种类型。

  列表结构:所有列表由两部分组成:Nil 和 ::(cons)。

  基本操作:主要有三个:head , tail , isEmpty 。这些都定义在List Object里。head 和 tail只能用在非空列表里。可以用“插入排序”的例子来进行说明。

  模式匹配:::在Scala标准库里是一个case class 。所以可以使用用模式匹配

 

9.2 List类的定义

  List是一个抽象类。List里定义了很多方法,解释如下:

  分解列表

  啮合(zipping lists):把两个List结合成一个列表对,如,有列表:xs = List(X1 , ... Xn) 和 ys = List(y1 , ... , yn) , xs zip ys,则生成List对:List((X1 , Y1), ... (Xn , Yn))

  操作列表:跟其他中缀操作符一样,::实现为一个对象的方法。Scala里以“:”结尾的操作符都被当成右操作符,也就是从右往左运算。

  连接列表:“:::”操作符可以用来连接两个列表。

  反转列表:另一个有用的操作就是反转(reversal)。给出了一种reverse方法的实现,但是这种方法跟List的长度成正比,不是很有效。之后会给出一种只有线性关系的实现。

def reverse[A](xs : List[A]) : List[A] = xs match{  case Nil => Nil   case x :: xs => reverse(xs) ::: List(x)}

 

9.3 例子:归并排序(merge sort)

  之前的插入排序(insertion sort)虽然简单,但不是很有效。平均复杂度与输入列表的长度的平方成正比。一个比插入排序更好的算法是“归并排序”。工作原理如下:

  一,如果这个List有0个或者1个元素,那么它是已经排好的,可以直接返回这个列表。稍长的列表可以分成两部分,每部分包含大概原List一半的长度内容。每个子列表被一个递归的排序调用进行排序,然后两个排序好的列表被一个合并操作合并在一起。

  对于一个归并排序的实现,我们仍然要指定元素类型,同时也要有用来做比较(comparison)的函数,用来确定排序规则。一个实现如下:

 
  def msort[A](less: (A, A) => Boolean)(xs: List[A]): List[A] = {    def merge(xs1: List[A], xs2: List[A]): List[A] =      if (xs1.isEmpty) xs2      else if (xs2.isEmpty) xs1      else if (less(xs1.head, xs2.head)) xs1.head :: merge(xs1.tail, xs2)      else xs2.head :: merge(xs1, xs2.tail)    val n = xs.length / 2    if (n == 0) xs    else merge(msort(less)(xs.take(n)), msort(less)(xs.drop(n)))  }

msort的定义用到了柯里化,所以可以这样使用:

val intSort = msort((x : Int , y : Int) => x < y)val reverseSort = msort((x : Int , y : Int) => x > y



val list=List(1 to 20 by 2:_*)
val list1=list++List(21,22)
println("list1="+list1)
val list2=22+:21+:list
println("list2="+list2)
val list3=list--List(19,20)
println("list3="+list3)
val list4=list-19-20
println("list4="+list4)
val list5=list:::List(21,22)
println("list5="+list5)
val list6=22::21::list
println("list6="+list6)
val list7=list.break(_>10)
println("list7="+list7)
val list8=list.companion(4,5)
println("list8="+list8)
val list9=list.drop(5)
println("list9="+list9)
val list10=list.dropWhile(_<10)
println("list10="+list10)
val list11=List("a","b").mapConserve(_.toUpperCase())
println("list11="+list11)
val list12=list.remove(_%5==0)
println("list12="+list12)
val list13=(15::list).removeDuplicates
println("list13="+list13)
val list14=list.reverse
println("list14="+list14)
val list15=list.slice(2,6)
println("list15="+list15)
 
 
结果
 
list1=List(1, 3, 5, 7, 9, 11, 13, 15, 17, 19, 21, 22)
list2=List(22, 21, 1, 3, 5, 7, 9, 11, 13, 15, 17, 19)
list3=List(1, 3, 5, 7, 9, 11, 13, 15, 17)
list4=List(1, 3, 5, 7, 9, 11, 13, 15, 17)
list5=List(1, 3, 5, 7, 9, 11, 13, 15, 17, 19, 21, 22)
list6=List(22, 21, 1, 3, 5, 7, 9, 11, 13, 15, 17, 19)
list7=(List(1, 3, 5, 7, 9),List(11, 13, 15, 17, 19))
list8=List(4, 5)
list9=List(11, 13, 15, 17, 19)
list10=List(11, 13, 15, 17, 19)
list11=List(A, B)
list12=List(1, 3, 7, 9, 11, 13, 17, 19)
list13=List(15, 1, 3, 5, 7, 9, 11, 13, 17, 19)
list14=List(19, 17, 15, 13, 11, 9, 7, 5, 3, 1)
list15=List(5, 7, 9, 11)
 
 
 
 
代码
 
val list16=list.sort((x,y)=>x>y)
println("list16="+list16)
val list17=list.span(_<10)
println("list17="+list17)
val list18=list.splitAt(8)
println("list18="+list18)
val list19=list.stringPrefix
println("list19="+list19)
val list20=list.take(5)
println("list20="+list20)
val list21=list.takeRight(5)
println("list21="+list21)
val list22=list.takeWhile(_<15)
println("list22="+list22)
val list23=list.toList
println("list23="+list23)
val list24=list.toStream
println("list24="+list24)
val list25=list++:List(21,22)
println("list25="+list25)
val list26=list./:(0)((x,y)=>x+y)
println("list26="+list26)
val list27=list./:\(0)((x,y)=>x+y)
println("list27="+list27)
val list28=list.:\(0)((x,y)=>x+y)
println("list28="+list28)
val list29=list.:\(0)((x,y)=>x+y)
println("list29="+list29)
val list30=list:+20:+21
println("list30="+list30)
 
 
结果
 
list16=List(19, 17, 15, 13, 11, 9, 7, 5, 3, 1)
list17=(List(1, 3, 5, 7, 9),List(11, 13, 15, 17, 19))
list18=(List(1, 3, 5, 7, 9, 11, 13, 15),List(17, 19))
list19=List
list20=List(1, 3, 5, 7, 9)
list21=List(11, 13, 15, 17, 19)
list22=List(1, 3, 5, 7, 9, 11, 13)
list23=List(1, 3, 5, 7, 9, 11, 13, 15, 17, 19)
list24=Stream(1, ?)
list25=List(1, 3, 5, 7, 9, 11, 13, 15, 17, 19, 21, 22)
list26=100
list27=100
list28=100
list29=100
list30=List(1, 3, 5, 7, 9, 11, 13, 15, 17, 19, 20, 21)
 
 
代码3
val list31=list.addString(new StringBuilder("a"))
println("list31="+list31)
val list32=list.apply(5)
println("list32="+list32)
val list33=list.canEqual("")
println("list33="+list33)
val list34=list.collect{case i:Int => i+"b"}
println("list34="+list34)
val list35=list.andThen(_<10).isDefinedAt(10)
println("list35="+list35)
val list36=list.collectFirst{case i:Int => i+"b"}
println("list36="+list36)
val list37=list.take(3).combinations(2).toList
println("list37="+list37)
val list38=list.compose(list.reverse)
println("list38="+list38)
val list39=list.contains(9)
println("list39="+list39)
val list40=list.containsSlice(List(1,3))
println("list40="+list40)
val array=new Array[Int](10)
list.copyToArray(array)
println("array="+array.mkString(","))
list.copyToArray(array,5)
println("array="+array.mkString(","))
list.copyToArray(array,1,3)
println("array="+array.mkString(","))
val buff=new ListBuffer[Int]();
list.copyToBuffer(buff)
println("buff="+buff)
val list41=list.corresponds(list)(_>=_)
println("list41="+list41)
val list42=list.count(_<15)
println("list42="+list42)
val list43=list.diff(List(1,5,11))
println("list43="+list43)
val list44=list.distinct
println("list44="+list44)
val list45=list.dropRight(3)
println("list45="+list45)
 
 
结果3
 
list31=a135791113151719
list32=11
list33=true
list34=List(1b, 3b, 5b, 7b, 9b, 11b, 13b, 15b, 17b, 19b)
list35=false
list36=Some(1b)
list37=List(List(1, 3), List(1, 5), List(3, 5))
list38=<function1>
list39=true
list40=true
array=1,3,5,7,9,11,13,15,17,19
array=1,3,5,7,9,1,3,5,7,9
array=1,1,3,5,9,1,3,5,7,9
buff=ListBuffer(1, 3, 5, 7, 9, 11, 13, 15, 17, 19)
list41=true
list42=7
list43=List(3, 7, 9, 13, 15, 17, 19)
list44=List(1, 3, 5, 7, 9, 11, 13, 15, 17, 19)
list45=List(1, 3, 5, 7, 9, 11, 13)
 

Scala 的list