概要集合与数据结构动态表示队列与堆栈树与图-天津大学计算机学院.PPT

第12章 集合 概要 集合 集合是一个对象，用于存储其他对象 集合通常提供增加、删除以及其他一些管理所包含元素的服务 集合中的元素有时是有序的，有时是无序的 有些集合是同构的，即这些集合中存储的对象类型相同；有些集合是异构的。 抽象 有许多不同的方法来实现集合 数据结构应该是抽象的 即, 应该隐藏不必要的细节 我们需要分离结构的界面（接口）与底层的实现 这有助于管理复杂并且可以在不必修改接口的情况下改变实现 抽象数据类型 抽象数据类型 (ADT)是一个有组织的信息集合与管理这些信息的一系列操作。 这些操作定义了抽象数据类型的接口 从某种意义上说，抽象数据类型的实现并不重要，只要它完成了接口 由于内部细节的采用封装机制，所以对象是建立抽象数据类型的完美机制 概要 动态结构 静态数据结构具有固定的长度 这与静态修饰符的含义有所不同 数组是静态的；当你定义了数组包含的元素的个数后，数组大小不允许改变 动态数据结构在运行期间可以更具需要增加和减少 通过链表来实现动态数据结构 对象引用 回顾一下，对象引用是一个存储对象地址的变量 引用也被称为指针 下面是一个引用的图形化描述: 对象引用 对象引用常用于创建对象间的链接 假设一个Student类包含指向另一个Student对象的引用： 对象引用 引用可以创建很多链式结构，例如 链表: Magazine 集合 我们来看一个Magazine 对象集合，由MagazineList 类管理,MagazineList类包含一个名为MagazineNode的私有的内部类 由于MagazineNode类对于MagazineList而言是私有的，所以MagazineList 的方法可以直接访问MagazineNode的数据而不违反封装 参见 MagazineRack.java (第418页) 参见MagazineList.java (第419页) 参见Magazine.java (第420页) 其他动态列表 某些情况，使用双向链表会更加方便 其他动态列表 有时，在链表中增加一个头节点会使处理过程更加方便 头节点包含指向链表第一个节点和最后一个的引用以及链表中节点的数目 概要 典型数据结构 现在我们来了解其他一些典型的数据结构 典型的线性数据结构包括队列和栈 典型的非线性数据结构包括树和图 队列 队列与链表类似，但是只能在队尾增加元素并且只能从队首删除元素 称作FIFO数据结构：先进，先出(First-In, First-Out) 类似：银行柜台窗口前排队 队列 通常队列可以有如下操作: 入队：在队尾增加一个元素 出对：从队首移出一个元素 清空：如果队列为空，返回true 可以使用单链表实现队列；如果引用从前指向后，那么效率非常高 队列也可以使用数组实现 堆栈 堆栈抽象数据类型也是线性的，这与队列或者链表类似。 但是只能在堆栈顶部删除或者增加元素 因此称作LIFO ：后进，先出（Last-In, First-Out） 类似：橱柜中的一堆盘子，将要支付的一堆帐单，仓库中的一堆干草捆 堆栈 堆栈数据结构: 堆栈 堆栈的一些操作: 压入 – 将一个元素压入栈顶 弹出 – 从栈顶移出一个元素 读栈顶元素 – 读取栈顶元素，但书并不从栈顶移出 清空 – 如果堆栈为空，返回 true 堆栈可以使用单链表实现；引用指针从头指向尾或者从后指向前并不重要 堆栈也可以使用数组实现，但是新元素应该移入数组下一个可用位置而不是数组尾部 堆栈 java.util 包中包含了一个实现堆栈数据结构的Stack类 类似于ArrayList 的操作, Stack的操作也是对象引用 参考 Decode.java (第424页) 概要 树 树是非线性数据结构，由根节点和其他形成层次结构多级附加节点构成 没有子节点称作叶子节点 除根节点和叶子节点外，其他节点称作内部节点 通常一棵树中,每个节点都有很多子节点 二叉树 二叉树中，每一个节点不能有超过两个的子节点 二叉树可以被递归定义。即使它是空二叉树（基本事件）或者由一个根节点和两个二叉树子树构成 树可以使用动态链表来实现，也可以使用数组实现 对于二叉树而言，只需要存储两个链接，分别指向左节点和右节点 图 图是一个非线性结构 与树或者二叉树不同，图没有根 图中的任意一个节点通过边可以与其他节点相连 类似：地图上的告诉公路系统连接着城市 图 在一个有向图或者图表上，每个边都有一个特定的方向 带有方向的边有时称为弧 类似：机场间的航线 图 图或表都可以通过动态链表或者数组实现 通常，应该选择方便操作并且使实现更加方便的方式 概要 集合类 Java标准类库包含一些类来表示集合，通常我们可以参考Java 集合API 大多数类名表明了集合类型以及基本实现方法，例如 ArrayList类与Lin