主要内容

• 数据结构概述
• Scala的集合分支
• 定长数组
• 变长数组
• 数组转换
• 多维数组
• 和 Java 数组的互操作
• 元组
• 序列
• 集
• 映射
• 集合操作的通用方式
• 集合转换的通用算子
• 特殊集合分支线程安全的集合

学习目标

• 理解数据结构
• 了解Scala中数据结构的实现
• 掌握Scala常见数据结构(集合)的操作

数据结构与集合

1. 数据结构概述

1.1 数据结构（Data Structure）

• 数据结构讨论的是在抽象层面上一组具有一定关系的数据元素的存储及处理。
  1. 数据元素之间逻辑关系的分类，每种逻辑关系对应的操作。
  2. 每种逻辑关系在计算机内部的存储模式。
  3. 对应于每种存储模式和操作的实现过程。

1.2 逻辑结构（Logical Structure）

• 描述描述数据元素之间的逻辑关系，是数据结构研究的子范畴。
• 逻辑结构分为线性结构、树状结构、集合结构和图状结构四类。
• 数据结构研究并给出每种逻辑结构的处理方法。

1.2.1 线性结构（Linear Structure）

• 一对一关系

• 同一数据集合中的元素排成一个有序的序列。

• 序列的第一个元素称起始结点（Initial Node），最后一个元素称终端结点（Terminal Node）。

• 任意一对相邻元素，前者是后者的直接前驱（Directly Predecessor），后者是前者的直接后继（Directly Successor）

• 起始结点只有直接后继没有直接前驱，终端结点只有直接前驱没有直接后继。

• 除起始节点和终端节点外，每个元素都只有一个直接前驱和一个直接后继。

1.2.2 树状结构（Tree）

• 一对多关系
• 同一集合中除了特殊的根（Root）元素之外，每个元素有且仅有一个直接前驱，后继数目不限。
• 根元素没有直接前驱。

1.2.3 集合结构（Set structure）

• 松散的逻辑结构

• 处于同一数据集合中的元素之间除同属于该集合这一联系外没有其他的关系。

• 集合结构通常需要借助其他数据结构，比如线性结构和树。

• 唯一专用于集合类型的数据结构是哈希表。

1.2.4 图状结构（Graphic Structure）

• 多对多关系
• 数据集合中每个元素的直接前驱和直接后继数目都不限。

1.3 存储结构（Storage Structure）

• 逻辑结构在计算机内的存储方式
• 包括数据元素的存储和数据元素之间的关系。
• 为了便于计算，有时还会增加一些辅助信息。

1.3.1 顺序存储（Sequence Storage）

• 所有的结点存储存放在一块连续的存储区域中，用存储结点的位置来体现结点之间逻辑关系的存储方式。

1.3.2 链接存储（Link Storage）

• 用指针指出存储结点间关系的存储方法。

1.3.3 索引存储（Index Storage）

• 分别存放数据元素和元素间关系的存储方式。

1.3.4 哈希存储（Hash Storage）

• 又称为散列存储。

2. Scala的集合

2.1 集合继承层次

• Scala 同时支持可变集合和不可变集合，不可变集合从不可变，可以安全 的并发访问。

• 两个主要的包：

  • 不可变集合：scala.collection.immutable

  • 可变集合：scala.collection.mutable

  • Scala 优先采用不可变集合。集合主要分为三大类：序列、集、映射。

  • 所有集合都扩展自 Iterable 特质。对于几乎所有的集合类，Scala 都同时提供了可变和不可变的版本。

• 不可变集合继承层次

• 可变集合继承层次

• Seq
  是一个线性表。IndexedSeq 是一个线性表能够通过整形下标快速访问元素。

• Set
  是一个没有先后次序的值集合。在 SortedSet 中，元素以某种排过序的顺序被访问。

• Map
  是一组键值对偶，SortedMap按照键的排序访问其中的实体。

• 每个 Scala 集合特质或者类都有一个带有 Apply 方法的伴生对象（类似于静态方法），这个 apply 方法可以用来构建该集合中的实体。这样的设计叫“统一创建原则”。

2.2 数组

2.2.1 定长数组

• 如果需要一个定长数组，可以使用 Scala 中的 Array，Array 以 java 数组 的方式实现。

val nums = new Array[Int](10)

2.2.2 变长数组

• 变长数组可以使用 ArrayBuffer，Java 中有 ArrayList，

import scala.collection.mutable.ArrayBuffer
val b = ArrayBuffer[Int]()

• Array 与 ArrayBuffer 的互转：

ArrayBuffer = Array.toBuffer
Array = ArrayBuffer.toArray\

• 数组遍历:

for (i <- 0 until a.length)
  println(i + ": " + a(i))

for (elem <- a)
  println(elem)

2.2.3 数组转换

• 转换动作不会修改原数组，而是产生一个新的数组。

2.2.4 多维数组

• 和 Java 一样，多维数组通过数组的数组来实现，可以用 ofDim 方法。

val matrix = Array.ofDim[Double](3, 4)

• 赋值：

matrix(row)(column) = 17.29

2.2.5 和 Java 数组的互操作

• Scala 数组是通过 Java 进行实现的，所以可以进行互相转换操作，使用 scala.collection.convert. AsJavaConverters 或者 AsScalaConverters 进行转换

import scala.collection.JavaConverters._
import scala.collection.mutable.ArrayBuffer

val command = ArrayBuffer("ls", "-al", "/")
val pb = new ProcessBuilder(command.asJava) // Scala to Java

val cmd : Buffer[String] = pb.command().asScala // Java to Scala

cmd == command

2.3 元组

• 元组是不同类型的值的聚集

• 元组使用 _1,_2,_3 来访问

注意，元组是从 1 开始不是 0;你可以把 t._2 改写成 t _2 但不能是 t_2;元组可用 于函数需要返回不止一个值得情况；使用元组的原因之一是把多个值绑在一起，以便他们能够被一起处理。

拉链操作：

2.4 集

• 集是不重复元素的集合。集不保留顺序，默认是以哈希集实现。

• 如果想要按照已排序的顺序来访问集中的元素，可以使用 SortedSet（已排序数据集），已排序的数据集是用红黑树实现的。

2.5 映射

2.5.1 映射操作

• 映射就是 key-value 的集合，就类似于 Java 中的 Map。

• 构造：

  • 不可变构造映射

    val scores = Map("Alice" -> 10, "Bob" -> 3, "Cindy" -> 8)

  • 可变映射

    val scores1 = scala.collection.mutable.Map("Alice" -> 10, "Bob" -> 3, "Cindy" -> 8)

  • 空映射

    val scores2 = new scala.collection.mutable.HashMap[String, Int]

  • 对偶

    "Alice" -> 10

  • 对偶元组

    val scores3 = Map(("Alice", 10), ("Bob", 3), ("Cindy", 8))

• 获取值：

  val bobsScore = scores("Bob")

  如果映射中没有值，则会抛出异常，使用 contains 方法检查是否存在key。如果通过 映射.get(键) 这样的调用返回一个 Option 对象，要么是Some，要么是 None。

• 更新值：

  scores1("Bob") = 10

• 如果 Bob 没有则新增。或者

  scores1 += ("Bob" -> 10, "Fred" -> 7)
  scores1 -= "Alice"

• 你不能更新一个不可变映射，但是可以获取一个修改过的新映射。

  val newScores = scores + ("Bob" -> 10, "Fred" -> 7) // New map with update

• 迭代映射：

  for ((k, v) <- scores) println(k + " is mapped to " + v)
  for (v <- scores.keys) println(v)
  for (v <- scores.values) println(v)

注意，不可变映射也可以调用方法，只不过产生新的映射。新映射和老映射共享大 部分结构。可变映射是在原映射基础上进行修改。

2.6 队列

• 队列是一个先进先出的结构：

2.7 堆栈

• Stack 是一个先进后出的结构：

2.8 列表

• 如果 List 为空，用 Nil 来表示。

2.9 添加去除元素操作符

2.10 常用方法

2.11 线程安全的集合

• 在多线程进行集合操作时，并发问题很突出，Scala 类库提供了 6 个并发 特质，

• 可以通过混入这些集合，让集合的操作变成同步的：

val scores = new scala.collection.mutable.HashMap[String,Int] with
  scala.collection.mutable.SynchronizedMap[String,Int]