算法(4th ed)(140):基础——背包、队列和栈 5.4

阅读数:13 2019 年 11 月 6 日 07:41

算法(4th ed)(140):基础——背包、队列和栈 5.4

(综述)

在本节中,我们所学习的支持泛型和迭代的背包、队列和栈的实现所提供的抽象使我们能够编写简洁的用例程序来操作对象的集合。深入理解这些抽象数据类型非常重要,这是我们研究算法和数据结构的开始。原因有三:第一,我们将以这些数据类型为基石构造本书中的其他更高级的数据结构;第二,它们展示了数据结构和算法的关系以及同时满足多个有可能相互冲突的性能目标时所要面对的挑战;第三,我们将要学习的若干算法的实现重点就是需要其中的抽象数据类型能够支持对对象集合的强大操作,这些实现正是我们的起点。

数据结构

我们现在拥有两种表示对象集合的方式,即数组和链表(如表 1.3.7 所示)。Java 内置了数组,链表也很容易使用 Java 的标准方法实现。两者都非常基础,常常被称为顺序存储链式存储。在本书后面部分,我们会在各种抽象数据类型的实现中将多种方式结归并扩展这些基本的数据结构。其中一种重要的扩展就是各种含有多个链接的数据结构。例如,3.2 节和 3.3 节的重点就是被称为二叉树的数据结构,它由含有两个链接的结点组成。另一个重要的扩展是复合型的数据结构:我们可以使用背包存储栈,用队列存储数组,等等。例如,第 4 章的主题是图,我们可以用数组的背包表示它。用这种方式很容易定义任意复杂的数据结构,而我们重点研究抽象数据类型的一个重要原因就是试图控制这种复杂度。

表 1.3.7 基础数据结构

数据结构 优点 缺点
数组 通过索引可以直接访问任意元素 在初始化时就需要知道元素的数量
链表 使用的空间大小和元素数量成正比 需要通过引用访问任意元素

我们在本节中研究背包队列时描述数据结构和算法的方式是全书的原型(本书中的数据结构示例见表 1.3.8)。在研究一个新的应用领域时,我们将会按照以下步骤识别目标并使用数据抽象解决问题:

  • 定义 API;
  • 根据特定的应用场景开发用例代码;
  • 描述一种数据结构(一组值的表示),并在 API 所对应的抽象数据类型的实现中根据它定义类的实例变量
  • 描述算法(实现一组操作的方式),并根据它实现类中的实例方法
  • 分析算法的性能特点。

在下一节中,我们会详细研究最后一步,因为它常常能够决定哪种算法和实现才是解决现实应用问题的最佳选择。

表 1.3.8 本书所给出的数据结构举例

数据结构 章节 抽象数据类型 数据表示
父链接树 1.5 UnionFind 整型数组
二分查找树 3.2、3.3 BST 含有两个链接的结点
字符串 5.1 String 数组、偏移量和长度
二叉堆 2.4 PQ 对象数组
散列表(拉链法) 3.4 SeparateChainingHashST 链表数组
散列表(线性探测法) 3.4 LinearProbingHashST 两个对象数组
图的邻接链表 4.1、4.2 Graph Bag 对象的数组
单词查找树 5.2 TrieST 含有链接数组的结点
三向单词查找树 5.3 TST 含有三个链接的结点

评论

发布