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