Java语言程序设计实用教程（ 第三版） 高职软件专业 赵从军 第10章 数据结构与集合类.ppt

尚辅网 尚辅网 Java语言程序设计实用教程 第10章 数据结构与集合类 Java的数据结构 动态内存分配 动态内存分配 动态内存分配就是指在程序执行的过程中动态地分配或者回收存储空间的分配内存的方法。 不需要预先分配存储空间 分配的空间可以根据程序的需要扩大或缩小 操作运算符new用于动态分配内存，如果内存不足，new将会引发出一个OutOfMemoryError错误 见P235例子 链表类（LinkedList） 链表 链表是由若干个称为结点的对象组成的自我引用的线性集合数据结构，结点之间通过引用链连接，即链式存贮。 单链表 循环链表 双链表 优点：插入、删除的效率高，空间的利用率高 单链表（P235，图10-1） 单链表：每个结点含有一个数据和下一个结点的引用 结点的组成： 结构图示： 循环链表(P236,图10-3) 循环链表：在单链表中，最后一个结点包含的引用是第一个结点 结构图示： 双链表 双链表：每个结点含有一个数据和下一个结点的引用以及前一个结点的引用 结点的组成： 结构图示： LinkedList类 LinkedList类用于创建链表数据结构。 P237表10-1列举了构造方法和常用方法 其中： add、addFirst、addLast方法用于建立链表 get、getFirst和getLast方法得到某位置处的元素 set方法用于设置元素的值 remove、removeFirst和removeLast用于删除元素 P238例10-1 P238例10-1补充说明：接口回调 接口回调是指：可以把使用实现了某一接口的类创建的对象的引用赋给该接口声明的接口变量，那么该接口变量就可以调用被类实现的接口的方法。实际上，当接口变量调用被类实现的接口中的方法时，就是通知相应的对象调用接口的方法，这一过程称为对象功能的接口回调。 接口回调的例子 接口回调的例子（续） P238例10-2补充说明：迭代器 为了实现对集合类型数据的遍历，我们经常使用到了Iterator(迭代器)。使用迭代器，你不需要干涉其遍历的过程，只需要每次取出一个你想要的数据进行处理即可。 Iterator接口是单向迭代器：不能更改元素 ListIterator接口进一步扩展了Iterator，为双向迭代器：可更改元素 对LinkedList类来说，通过listIterator()取得其迭代器 hasNext()和next()方法，可以实现顺序向后遍历 hasPrevious()和previous()方法，可以实现逆向（顺序向前）遍历 堆栈类（Stack） 堆栈 堆栈是一种受约束的链表形式，新结点在链表的头部被加入到堆栈，并且只能从链表的头部，即堆栈的顶部删除 只能在固定一端进行插入和删除操作 后进先出（LIFO） 允许进行插入和删除操作的一端称为栈顶，另一端称为栈底 见P240图10-7 Stack类（P241,表10-2） Stack 类通过五个操作对类 Vector 进行了扩展 ，允许将向量视为堆栈。 push方法把数据压入栈顶 pop方法删除栈顶的数据 peek 方法取栈顶点的数据，但不删除 empty 方法测试堆栈是否为空 search 方法在堆栈中查找项并确定到栈顶距离 Vector类（P242,表10-3） Vector 类可以实现可增长的对象数组（并不具备堆栈特性）。与数组一样，它包含可以使用整数索引进行访问的组件。但Vector 的大小可以根据需要增大或缩小，以适应创建 Vector 后进行添加或移除项的操作。 每个向量会试图通过维护 capacity 和 capacityIncrement 来优化存储管理。capacity 始终至少应与向量的大小相等；这个值通常比后者大些，因为随着将组件添加到向量中，其存储将按 capacityIncrement 的大小增加存储块。应用程序可以在插入大量组件前增加向量的容量；这样就减少了增加的重分配的量。（见构造函数） addElement将指定的对象添加到此向量的末尾，将其大小增加 1。 elementAt返回指定索引处的对象 Vector举例（不建议实现例10-3） 队列 队列 队列是一种顺序表，其中的项在队列的尾部插入，从头部取出，即先进先出（first-in,first-out:FIFO）的数据结构。 双队列：代表双端队列，元素可从队列的两端插入和删除（见P246，图10-10） 优先队列：加入到队列的项有一个与其相关的优先级，它确定处理和删除每个元素的次序 分时系统 操作系统的调度程序 打印池应用 高优先级的元素先处理，如果两个元素有相同的优先级，先来的元素先处理 Queue和Deque接口（P247，表10-4） Queue接口：为用户定义了队列的基本操作，例