1JDK中的数据结构
数据结构是数据元素之间的关系。从概念和实现两个角度，可将数据结构分为数据的逻辑结构和数据的存储结构。按照数据元素之间前驱和后继关系来分，数据的逻辑结构可分为以下4种：集合（Set）、线性表（List）、树（Tree）和图（Graph）[2]。数据的存储结构主要包括数据元素本身的存储以及数据元素之间关系表示。数据元素之间的关系在计算机中主要有两种不同的表示方法：顺序映像和非顺序映像，并由此得到两种不同的存储结构：顺序存储结构和链式存储结构。JavaJDK为常用的数据结构定义了一些接口（Interface）和实现（Implementation）。这些接口、实现类以及常用的排序、查找等算法统称为JavaCollections框架（JavaCollectionsFramework）。Collections框架的设计目的是要满足如下目标：高性能、一致性、扩展性和轻松编程。Java程序员在具体应用时，不必考虑数据结构和算法实现细节，只需要用这些类创建出来一些对象，然后直接应用即可[3]。Java中把一组对象称为Collection，也就是说，Collection是对象的容器。Java对Collection中的对象没有任何前驱、后继以及重复性的约束，只是约束了对象类型E。Collection接口定义了其上的3类操作：针对单个元素的基本操作、迭代器和Collection对象之间的批量操作。基本操作包括增加、删除、判断是否包含某个元素、判断是否为空、容器中当前元素的个数、清空等。批量操作包括：合并两个Collection容器、从一个容器中移走一些元素、保留两个容器中相同的元素、判断一个容器中的元素是否完全包含在另外一个容器中等。接口Collection<E>的子接口有Set<E>和List<E>。集合（Set）在Collection的基础之上增加了“不允许重复元素”的约束；而List则在Collection基础之上增加了“元素之间具有前驱、后继关系”的约束：除了第一个元素外，所有元素具有唯一的前驱；除了最后一个元素外，所有元素具有唯一后继。如果仅关心数据元素是否出现，而不关心数据元素之间的次序，则应使用Set<E>。Java为集合接口提供了两个基本的实现：HashSet<E>和Tree<Set>。HashSet<E>是Set<E>接口的典型实现，大多使用集合的场合就是使用这个实现类。HashSet实现类按哈希算法来存储集合中的元素，因此具有很好的查找性能。HashSet不能记忆元素之间的顺序，包括插入顺序。其子类LinkedHashSet<E>也是根据元素hashCode值来决定元素存储位置，但它同时使用链表维护元素的次序，这样使得能够记忆插入顺序。由于LinkedHashSet需要维护元素的插入顺序，所以性能略低于HashSet，但遍历集合里的全部元素性能较好。实现类TreeSet<E>可以确保集合元素处于排序状态，TreeSet并不是根据元素的插入顺序进行排序，而是根据元素的实际值来进行排序的。TreeSet采用红黑树的数据结构对元素进行排序，并要求添加进TreeSet中的对象必须实现CompareTo<E>接口。List<E>接口作为Collection<E>接口的子接口，可以使用Collection接口中的全部方法。但是List接口中定义了元素位置和元素范围的概念，使得List可以根据元素位置索引（index）来插入、替换、删除集合元素以及查找指定对象的位置。ArrayList<E>实现类基于数组实现了List接口，其内部封装了一个动态再分配的数组。每个ArrayList对象都有一个capacity属性，这个属性表示它们所封装的数组的长度，当添加元素超过长度时，capacity会自动增长，其默认值为10。LinkedList<E>内部以链表来保存集合中的元素，因此随机访问容器时的性能较差，但在插入、删除元素时性能较好。Queue<E>接口用于定义队列这种数据结构，队列是“先进先出”的容器，通常不允许随机访问其中的元素。Java中的队列接口Queue<E>没有继承List接口，而是直接继承了Collection接口。如果使用具有固定容量的队列，则应使用offer()来加入元素，使用poll()来获取并移出元素，因为add()和remove()方法在因容量原因失败时抛出异常。如果只是访问队首而不移出该元素，使用element()或者peek()方法。LinkedList<E>类实现了Queue<E>接口，因此我们可以把LinkedList当成Queue来用。PriorityQueue是一个比较标准的队列实现类，它并不是按加入队列的顺序，而是按队列元素的大小来记忆队列元素的顺序。因此当调用peek方法或者poll方法来取出队列中的元素时，并不是取出最先进入队列的元素，而是取出队列中最小的元素。Stack<E>实现了List<E>接口，提供了push和pop操作限制线性表中元素的插入和删除只能在线性表的同一端进行。JDK1.6引入的ArrayDequ<E>实现类被优先推荐作为栈使用。ArrayDeque<E>实现了Deque<E>接口。Deque<E>接口定义了双端队列，双端队列中的元素可以从两端弹出，其限定插入和删除操作在表的两端进行。JavaJDK中没有直接提供树和图的接口和实现类，但是可以通过研究TreeMap的源代码学习操作树的一般编写模式。综上，数据结构与Java面向对象程序设计两门课程内容的衔接见表1。
2面向数据结构衔接的Java课程实施方案
Java面向对象程序设计为1学期的课程。总课时为讲授54学时、实验32学时。其中，与数据结构知识点紧密相关的JavaCollections框架部分为讲授6学时、实验4学时。在讲授环节，按照表1列出的顺序进行。在实验环节完成与授课内容相关的验证性实验。在课程设计实践环节，要求学生使用Java设计常见算法，然后阅读JDK提供的源代码进行对照。具体方案如图1所示。比如，在java.util.Collections类中提供了数据结构中学生已经学过的常见算法，如二分查找、计算元素频数、查找最大/最小元素、反转线性表、按照指定距离旋转线性表、随机排列线性表、交换指定位置上的两个元素以及排序等。注意，在Java6中Collections.sort()使用的是MergeSort；而在Java7中，内部实现换成了TimSort。要求学生按照这些API文档说明，首先按照数据结构课程中的知识设计自己的算法实现，然后与API源代码进行比较。由于学生使用C语言版的数据结构教材，所以在面向Collection编程之前，作为过渡，先让学生面向数组编程。哈希表是一种重要的数据结构，也是实现集合的基本途径之一。通过研究HashSet的源代码，可以让学生理解为什么每个对象都要有hashcode()方法，以及哈希表的编码特点。由于HashSet的实现是基于HashMap的，所以研究HashSet就要研究HashMap。Map是一种典型的名值对类型，它提供一种Key-Value对应保存的数据结构。客户程序通过Key值来访问对应的Value，这个接口并没有继承Collection这接口；而其他的类或者接口，不管是List、Set、Stack等都继承或实现了Collection。TreeMap和HashMap算是Java集合类里面比较有难度的数据结构。HashMap元素存取的时间复杂度一般是O(1)，而TreeMap内部对元素的操作复杂度为O(logn)。TreeMap记忆了顺序，TreeSet内部的实现使用了TreeMap。
3结语
数据结构与程序类课程的关系问题愈来愈引起关注[4-6]，我们提出面向数据结构知识体系的Java课程教学与数据结构课程的衔接方案。这个教学方案已经在河北师范大学本科计算机专业实施三届，取得了较好的效果，学生对算法的理解加深了，解决问题的自信心增强了，也建立了工程意识。
作者：董东 单位：河北师范大学 数学与信息科学学院
