摘 要： 数据结构课程的教学在应用型本科院校存在着较大难度。为此，分析了该课程的教学现状，并以软件学院Java数据结构课程改革作为参考，给出了该课程改革的思路。简化了该课程中相关理论性、抽象性知识的讲解，结合开发的需求，扩大数据结构课程中的数据结构范畴，引入第三方增强型数据结构，比如apache的集合类，并加强其实际应用的讲解。实践证明，该方法能够降低数据结构的教学难度，提高学生的实践动手能力，进而提高其就业竞争力。
关键词： 应用型本科院校； 数据结构； 课程改革； Common Collections
中图分类号：TP311.5 文献标志码：A 文章编号：1006-8228（2013）02-50-02
Reform of curriculum teaching of Java data structure course for application-oriented institutes
Liang Zhixue， Jia Manlei
（Nanyang Institution of Techonlogy， Nanyang， Henan 473000， China）
Abstract： It has certain difficulty in teaching data structure in vocational colleges. Based on analyzing current teaching pattern and curriculum reform of java data structure in software school in Nanyang Institute of Technology， some ideas of curriculum reform， such as reducing the explanation of the theoretical and abstract knowledge， are proposed. By studying the practical needs of the major front-line software developers， the teaching content of data structures is expanded. Strong third-party data structures are introduced like apache Commons-Collections， to strengthen the teaching of realistic application. The result shows that the reform can reduce the teaching difficulty of data structure， enhance the practical ability of the students and improve their competitiveness.
Key words： application-oriented institutes； date structure； curriculum reform； Common Collections
0 引言
数据结构课程是计算机相关专业的一门核心基础课，其教学目的是使学生学会分析计算机所加工处理的数据的数据结构特性，为软件开发过程中涉及的数据选择适当的逻辑结构、存储结构及相应的算法，并初步掌握算法的时间效率分析和空间效率分析的技术。数据结构课程涉及到离散数学、可计算性理论、算法复杂性等理论知识。对于学生来说，该课程理论性强，较抽象和深奥，同时，学生对算法设计或程序设计中的技巧也会感到难以理解和掌握。因此，相当一部分学生觉得理解书上的基本概念并不难，可是一到解决具体问题时就感到困难重重，对于有一定难度的算法设计题更是无从下手[1，2]。
应用型本科人才的培养目标是知识、能力、素质和谐发展的高素质人才，是介于传统学科型人才与职业技能型人才的“中间型人才”，要求既有本科人才的学科教育特征，又有应用人才的职业教育特性[3]。着重培养学生解决实际问题的能力是职业教育的主要特性，也是应用型本科院校最需要加强的部分。根据软件行业一线开发人员的开发经验的调查，在大型的复杂的数据面前，使用传统的数据结构来处理显得力不从心，如果使用自己开发数据结构来处理数据，就需要耗费大量的时间和精力，同时在效率和安全性上也难以保证。比较好的解决办法是引入第三方增强型的数据结构，这样既能很好地解决问题，又能提高工作效率。
1 传统的Java数据结构教学
传统的数据结构教学主要是对表、树、图、栈和队列的数据结构的讲解，其讲解的内容通常是对于数据结构的定义和实现，具体内容如表1所示[4]。
表1 传统的Java数据结构及其讲授内容
[传统数
据结构＼&Java中的常
见数据结构＼&讲授内容＼&
线性表＼&Array＼&讲授Array数组的定义、实现及其查询、排序、删除等操作的实现。＼&LinkedList＼&线性链表的定义、实现过程以及增加、删除、修改、查询一个元素的实现过程。＼&Stack＼&栈的实现原理及其实现过程。出栈、压栈操作的实现过程。＼&Queue＼&队列的实现原理及其实现过程。入队、出队操作的实现过程。＼&
树＼&TreeSet＼&树集的基本操作如添加、删除、包含。＼&TreeMap＼&树映射的存、取、删除、主键包含等操作。＼&图＼&HashMap＼&HashMap的实现过程及其存、取、删除、遍历等操作。＼&表＼&HashTable＼&HashTable的实现过程及其存、取、删除、遍历等操作。＼&
集合＼&Vector＼&Vector的实现过程以及其存、取、删除、遍历等操作。＼&ArrayList＼&ArrayList的实现过程以及其存、取、删除、遍历等操作。＼&HashSet＼&HashSet的实现过程以及其存、取、删除、遍历等操作。＼&]
在传统的数据结构课程讲授中，更倾向于各种数据结构的具体实现过程，而对分析数据结构特性，以及为数据选择适当的结构等方面关注较少，与实际应用，特别是对大型数据结构的处理应用结合更少。
举两个例子来说明。
例1：在应用开发中，经常应用到代码-名称匹配的问题，通过代码找到对应的名称，可以采用传统的数据结构map中的HashMap轻松解决，但如果需要代码-名称双向匹配，即通过代码能找到名称，通过名称也可以找到代码，对于这种问题的处理，用传统的数据结构，比如Java中的HashMap来解决是比较困难的。
例2：电子商务中经常用到在线购物车。在线购物车处理中，经常需要把一个对象的多个拷贝加入到一个集合类（比如Java中的ArrayList）中，开发人员将对象加入到ArrayList过程中，然后每添加一次都要进行一下迭代，来判断是否添加了给定类型的对象。这种方法存在的缺点就是内存消耗比较大，速度和效率上也存在着不足。
使用传统的数据结构方法在解决上述两个问题时，显的有点力不从心，或者是在资源和效率等方面存在着不足，这时就需要引入第三方增强型的数据结构框架，比如Java数据结构中引如Appache Commons中的Collections类库。从而能够方便、高效地解决上述等问题。
2 Appache Common Collections
Commons是Apache公司的一个项目，主要关注Java组件的可重用方面，Collections是Appache Commons项目中的一个组件，是一个用来处理集合Collection的开源工具包。
Java集合框架是JDK1.2版本以后增加的主要内容。这些集合框架中包含了许多功能强大的数据结构，从而为Java应用的开发提供了便利。Commons Collections是一款建立在JDK类的基础上，提供新的接口，实现类和工具包的开源集合框架。它包含很多新的特性，比如集合中的Bag接口存放着一个对象的多个副本，比如Buffer接口提供先进先出的可变队列、多种比较器、多种迭代器等。表2列出了Commons-collections框架中的部分主要的类及其应用。
表2 Commons-collections中的部分主要类及其应用
[部分包＼&主要的类＼&主要应用＼&collections＼&ArrayStack＼&适用用单线程环境. ＼&BeanMap＼&可以将Map作为一个JavaBean来使用＼&ExtendedProperties＼&一个属性键可对应多个值＼&FastArrayList， FastHashMap＼&适用于多线程环境 ＼&bag＼&HashBag， TreeBag＼&该包中只存放一个对象的拷贝和一个计数器＼&bidimap＼&TreeBidiMap＼&可以根据键和值进行排序＼&collection＼&CompositeCollection＼&可以创建集合的集合＼&SynchronizedCollection＼&可以使存在的集合线程安全＼&TransformedCollection＼&当向集合中添加对象时，可转换对象数据类型。＼&Iterators＼&ArrayIterator＼&实现对任意array的迭代＼&LoopingIterator＼&实现循环迭代功能＼&map＼&MultiKeyMap＼&多个key可以映射一个map＼&LazyMap＼&Map中的键/值对一开始并不存在，当被调用到时才创建＼&BidiMap＼&双向Map，可以通过Key找到Value，也可以通过Value找到Key＼&MultiMap＼&一个Key指向一组对象＼&]
3 课程内容置换
从表2可以看出，Common-Collections中的数据结构是在基本数据结构的基础上进行封装、扩展，能够针对某种复杂的数据结构进行简化处理，功能更加强大，是对传统数据结构的一种有效补充，在对大型复杂数据进行处理时，可选的数据结构更加灵活，更具有针对性。
为了使学生能够在学习数据结构课的同时，对其他增强型的扩展的第三方数据结构有一定的了解，在授课时，可以将传统数据结构中的部分内容进行删减，替换为第三方数据结构的部分内容，从而保证数据结构的总学时保持不变[5]。建议替换的内容如表3所示，也可根据实际情况进行相应的替换。
表3 建议替换内容
[数据结构＼&取消内容＼&增加内容＼&线性链表＼&线性链表自身的实现原理以及其增、删、改、查等具体的操作，只关注其提供的操作方法。＼&Common-Collections中的相关类，比如ArrayStack，FastArrayList等。＼&树＼&树的实现原理、树的存储结构、树的遍历等，只关注树提供的方法即可。＼&Commons Collections中的类比如：TreeList，TreeBag和TreeBidiMap等。＼&图＼&图的实现原理、存储结构及遍历等内容。＼&Commons Collections中的相关类：
比如bidimap，MultiKeyMap等。＼&集合＼&集合的实现原理、存储、迭代等内容。＼&Commons Collections中的相关类，比如ArrayIterator、LoopingIterator等。＼&]
4 新旧课程内容比较
如果采用Appache中的新的数据结构，例子1、2中的问题就能够很容易得到解决，而如果采用传统的Java中的数据结构来解决的话，在实现的过程中会存在着一定的难度及较大的工作量，在效率和资源等方面也存在着不足。
为了解决例1中的问题，实现既能通过Key找到Value，又能通过Value找到Key功能，如果使用传统的Java中数据结构，需要建立两个HashpMap，一个HashMap中的Value值同作为另外一个HashMap的Key值。使用org.apache.commons.collections.bidimap包中的类，就能使问题变得非常简单，bidimap包中的BidMap类就可直接满足Key值和Value值相互查找的功能。使用BidMap类来实现该功能的主要代码如下：
BidiMap bd=new TreeBidiMap（）；
bd.put（"FIVE"， "5"）；
bd.get（"Five"）； //returns "6"
bd.getKey（"5"）； //returns "SIX"
bd.removeValue（"5"）； //removes the mapping
BidiMap inverse=bidi.inverseBidiMap（）； //returns a map with
keys and values swapped
为了解决例2中的问题，如果采用传统的Java数据结构，使用ArrayList类来实现，需要在对象加入到ArrayList过程中，每添加一次都要进行一下迭代，来判断是否添加了给定类型的对象。如果采用org.apache.commons.collections.bag包中的类，就能使问题变得非常简单。一个比较好的设计就是只保存一个对象的拷贝，而在添加同样类型的实体时，只是增加计数器的值。hashbag和treebag类（分别基于hashmap和treemap）很好的满足了这个需求。用Java代码很容易实现该功能。
Bag ordereproducts=new HashBag（）；
ordereproducts.add（object1）；
ordereproducts.add（object2）；
ordereproducts.add（object3）；
ordereproducts.add（object4）；
…
// Object1，object2…may be different objects or multiple
copies of an object
通过比较可以发现，在解决例1和例2问题的过程中，采用传统的数据结构增加了程序的复杂度及代码量，同时在效率和性能上也有所降低，内存消耗也比较大；而采用增强型的第三方数据结构如Appache来解决上述问题时，则能很好地规避上述不足，充分提高程序的性能及开发的效率。从学生的动手能力培养以及处理实际大型数据的能力上来看，置换后的课程比置换前存在着更多的优势。
5 结束语
基于本文提出的数据结构教学改革方法已经在南阳理工学院软件学院部分班级试用，目前已经有一届毕业生。根据进入软件公司从事软件开发的毕业生反馈情况来看，新的数据结构教学方法能够解决实际软件开发中的大型数据的结构处理问题，增强他们软件开发经验，提高他们的就业竞争力。但从考研的学生角度来看，减少数据结构的具体实现过程的讲解，存在一定的不足。如何能够在保证学时不变的情况下，兼顾到考研学生情况，是今后需要研究实践的课题。
参考文献：
[1] 季晓慧，王群.“数据结构”课程教学初探[J].中国地质教育，2009.1：149-152
[2] Zhixue Liang. Curriculum Programme of Career-oriented JavaSpecialty Guided by Principles of Software Engineering. ICETC，2010.1：592-596
[3] 钱国英，徐立清，应雄.高等教育转型与应用型本科人才培养[M].浙江大学出版社，2007.11：74-75
[4] 金静梅.Java集合框架在Web开发中的应用[J].计算机时代，2010.6：31-32
[5] Hongfei Sun， Huijuan Wu， Min Liu . “Data Structure” CurriculumReform and Foreign Language Teaching Research. ETCS，2010.2：762-765