《Java开发技术 普通高等教育十一五 国家级规划教材 教学课件 ppt 作者 魏勇 第九章 数据结构》由会员分享，可在线阅读，更多相关《Java开发技术 普通高等教育十一五 国家级规划教材 教学课件 ppt 作者 魏勇 第九章 数据结构（57页珍藏版）》请在金锄头文库上搜索。
1、 261 第九章第九章 数据结构数据结构 ? 数据结构接口 ? 具体的数据结构 ? 数据结构平台 ? 算法 数据结构是计算机专业的一门重要课程，Java 的数据结构有自身特点。首先不象 C 或其它语言，Java 没有提供指针，实现链式存储结构是用自引用类实现的。其次 Java 提 供的类已经实现了很多数据结构的内容，程序员可以直接使用。 详细地论述数据结构不是本章的目的，这里我们只介绍标准 Java 库提供的最基本的数 据结构，讲述如何利用 Java 编程语言实现各种传统的数据结构。 面向对象编程(OOP)把数据封装在类中，如何在类中有效地组织数据在编程中很重要。 在类中组织数据对实现类中的方
2、法及它们的性能将会产生很大的影响。 9.1 Java 数据结构框架数据结构框架 早期的标准 Java 库只为最有用的数据结构提供了为数不多的一组类，这些数据结构包 括：Vector、Stack、Hashtable、BitSet 和 Enumeration 接口(它提供一个抽象机制访问任 意数据结构的数据元素)。之后，Java 设计者一直致力于推出一套综合的数据结构，并提出 了抽象数据类型（ADT）的概念。在 Java 中，常常使用一个接口来给出一个操作集合而不 需要透露这些操作实现的细节。 线性表，堆栈和队列是最基本的数据结构，实现的方法很多，本章的很多例子将会讲到 如何用 Java 实现这些
3、基本的数据结构。 一个线性表是有限个元素的集合， 其元素以线性的方式进行排列并提供对它的元素的直 接访问。一个堆栈是一个后进先出（LIFO）的有序线性表，元素从堆栈头加入，并从堆栈 头取出。一个队列是一个先进先出的有序线性表，元素从队列尾加入，并从队列头取出。 Java 2 软件开发包（SDK）提供了一些新类来支持大多数常用的 ADT。这些类被称为 Java 集合类（类似于 MFC 中的集合类），它们协同工作从而形成 Java 数据结构框架。这 个数据结构框架提供了一套将数据表示成所谓的集合抽象数据的接口和类。 下面我们将更深入的学习 Java 数据结构框架中更多的类。 9.1.1 接口接口
4、Java 数据结构框架中主要包括 8 个接口。 262 Collection Set List SortedSet Map SortedMap Iterator ListIterator 图 9- 1 Java 数据库架构中包括的接口 1) Collection 接口 基本的接口 java.util.Collection 被用来表示任意的成组的对象，也就是元素。这个接口 提供基本的诸如添加，删除，和查询这样的操作。Collection 接口还提供了一个 iterator 方 法。iterator 方法返回 java.util.Iterator 接口的一个实例。利用 Iterator 接口的 h
5、asNext, next 和 remove 方法，可以从头到尾循环遍历一个 Collection 对象中的实例并能够安全的删除 iterator(游标)所表示的元素。 Collection 有两种基本方法： boolean add(Object element); Iterator iterator(); add()方法把对象添加到相应的数据结构， 如果添加成功， 就返回 true； 否则， 返回 false。 例如，把一个对象添加到一个集合中，而集合已包含了这个对象，add()方法就返回 false， 因为集合中不允许有相同元素。 2) Map 接口 Map 接口是另外一个基本接口，Map
6、也用 add()方法向一个数据结构中插入元素： boolean add(Object element) 对于由关键字/值构成的数据结构，插入其元素用 put()方法，而不是 add()方法： boolean put(Object key, Object value) 3) Iterator 接口 Iterator()方法返回一个实现了 Iterator 接口的对象，可以用这个对象依次访问数据结构 的元素。 Iterator 接口有三种基本方法： Object next() boolean hasNext() void remove() Iterator 接口的 next()及 hasNext(
7、)方法和 Enumeration 接口的 nextElement()及 hasMoreElements()方法的功能相同。 重复调用 next()方法可依次访问数据结构的元素，并在访问到数据结构尾部时，抛出 NosuchElementException 异常。因而，调用 next()方法前应调用 hasNext()方法。如果还 有这个 Iterator 对象未访问到的元素，hasNext()方法返回 true，否则返回 false。如果要访 问某个数据结构中的所有元素，在满足 hasNext()方法返回 true 的条件下，用一个 Iterator 对象反复调用 next()即可。 Itera
8、tor iter = c.iterator( ); while (iter.hasNext( ) 263 Object obj = iter.next(); ： remove()方法用于删除最后一次调用next()方法返回的对象。 这个方法必须紧跟在next() 方法后面。如果最后一次访问元素后和调用这个方法之前数据结构已经改变，那么会抛出 IllegalStateException 异常。 Java 数据结构库提供的指针和其他库提供的指针存在着很大的区别。Java 库提供的指 针采用了不同的工作方式， 元素访问和位置变换紧密地联系在一起， 访问元素的唯一方法是 调用 next()，并由 ne
9、xt()方法把指针移动到下一个位置。 Java 库提供的指针不是指向某个元素，而是指向两个元素之间。当调用 next()方法时， 指针就跳过下一个元素，并返回它刚跳过的元素地址。 图 9- 2 移动指针 调用 remove()方法时一定要小心。因为 remove()方法总是删除最后一次调用 next()方 法返回的元素。如果想删除某个特定位置的元素，首先要跳过这个元素。例如，删除一个数 据结构中的第一个元素，需执行如下步骤： Iterator it = c.iterator( ); it.next(); /跳过第一个元素 it.remove ( ); /删除第一个元素 remove()方法依赖
10、于 next()方法。 在调用 remove()方法之前不调用 next()方法是不合法 的。如果这样做，会抛出 IllegalStateException 异常。 如果要删除两个相邻元素，不能连续地调用 remove()方法。所以调用 remove()方法前 必须先调用 next()方法跳过要删除的元素。 it.remove(); it.next(); it.remove( ); /ok 下面的方法把一个数据结构的所有元素装入到另一个数据结构： ： public static boolean addAll (Collection to, Collection from) Iterator i
11、ter = from.iterator( ) ; boolean modified = false; while(iter.hasNext() if (to.add(iter.next ( ) modified = true ; return modified; ： 把一个元素成功地添加到某个数据结构， add()方法返回 true。 因为 Collection 和 Iterator 接口已经提供了诸如 add()和 next()这样的基本方法，可以在此基础上实现适用于任何数据 结构的类似上面的实用方法。 Java 库的设计人员认为一些方法很实用，因而他们就在 Java 库中直接提供了这些方
12、法。这样，用户就不必重复地编写这些方法，addAll()方法就是其中的一个。 264 4) List List 接口继承了 Collection 接口并定义了一个允许相同元素存在的有序集合。List 接口 还附加了一些使用一个数值型索引值并基于元素在线性表中的位置来操作 Collection 中元 素的方法。这些操作包括 add,get,set 和 remove。 List接口还提供了listIterator方法。 这个方法返回java.util.ListIterator 接口的一个实例， 这个实例能够让你从头至尾或者从尾至头的遍历一个线性表。 列表是一种有序的数据结构(ordered col
13、lection)。在列表中，每个元素都被放于一个合 适的位置。有两种方法用于查找元素应处的位置：整数索引和列表指针。List 接口定义了一 些随机访问方法： void add(int index, Object element) Object get(int index) void remove(int index) Java 数据结构框架提供了对 List 接口的两个实现：LinkedList（链表）和 ArrayList（数 组列表，即静态列表）。这两个实现都支持对其元素的随机访问。一个 ArrayList 实例支持 数组风格的操作并支持数组大小的改变操作。 一个 LinkedList 的
14、实例则提供了在列表开始和 结尾添加，删除和提供元素的显式的支持。使用这些新方法，一个程序员可以简单的把一个 LinedList 当做堆栈或者队列使用，如下： ： LinkedList aQueue = new LinkedList(aCollection); aQueue.addFirst(newElement); Object anElement = aQueue.removeLast(); LinkedList aStack = new LinkedList(aCollection); aStack.addFirst(newElement); Object anElement= aStac
15、k.removeFirst(); ： 5) ListIterator java.util.ListIterator 继承了 java.util.Iterator 接口。因此，它支持对它代表的 Collection 中的元素的添加和修改。 下面的例子演示了如何从后向前遍历一个列表的元素。 要完成这个工作， 必须在遍历开 始之前把 ListIterator 定位于列表最后一个元素之后。 ： ListIterator iter = aList.listIterator(aList.size(); while (iter.hasPrevious() System.out.println(iter.pr
16、evious().toString(); ： Listlterator 接口也定义了 add()方法，它把一个元素插入指针指示的位置前面： void add(Object element 6) Set 接口 Set 接口等同于 Collection 接口， 只是它的方法定义更严密。 Set 接口的 add()方法不会 把集合中已有元素再次插入集合；它的 equals()方法是这样定义的：两个集合 A 和 B 相等 表示一个元素在集合 A 中也一定在集合 B 且 A 和 B 的元素个数相同，但元素的顺序无关紧 要；它的 hashCode()方法应这样定义：相同的元素产生相同的哈希码。 既然方法名字相同， 为什么还要创建单独的 Set 接口呢？因为不是所有的数据结构都是 265 集合。创建 Set 接口有利于程序员编写只适用于集合的方法。 7) SortedSet 和 SortedMap 接口 SortedSet 和 SortedMap 接口定义了用于排序的比较对象及获取数据结构子集视图的 方法。 9.1.2 实现接口的类实现接口的类
