梁智學(xué) 賈滿磊

摘 要： 數(shù)據(jù)結(jié)構(gòu)課程的教學(xué)在應(yīng)用型本科院校存在著較大難度。為此，分析了該課程的教學(xué)現(xiàn)狀，并以軟件學(xué)院Java數(shù)據(jù)結(jié)構(gòu)課程改革作為參考，給出了該課程改革的思路。簡(jiǎn)化了該課程中相關(guān)理論性、抽象性知識(shí)的講解，結(jié)合開(kāi)發(fā)的需求，擴(kuò)大數(shù)據(jù)結(jié)構(gòu)課程中的數(shù)據(jù)結(jié)構(gòu)范疇，引入第三方增強(qiáng)型數(shù)據(jù)結(jié)構(gòu)，比如apache的集合類(lèi)，并加強(qiáng)其實(shí)際應(yīng)用的講解。實(shí)踐證明，該方法能夠降低數(shù)據(jù)結(jié)構(gòu)的教學(xué)難度，提高學(xué)生的實(shí)踐動(dòng)手能力，進(jìn)而提高其就業(yè)競(jìng)爭(zhēng)力。

關(guān)鍵詞： 應(yīng)用型本科院校； 數(shù)據(jù)結(jié)構(gòu)； 課程改革； Common Collections

中圖分類(lèi)號(hào)：TP311.5 文獻(xiàn)標(biāo)志碼：A 文章編號(hào)：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 引言

數(shù)據(jù)結(jié)構(gòu)課程是計(jì)算機(jī)相關(guān)專(zhuān)業(yè)的一門(mén)核心基礎(chǔ)課，其教學(xué)目的是使學(xué)生學(xué)會(huì)分析計(jì)算機(jī)所加工處理的數(shù)據(jù)的數(shù)據(jù)結(jié)構(gòu)特性，為軟件開(kāi)發(fā)過(guò)程中涉及的數(shù)據(jù)選擇適當(dāng)?shù)倪壿嫿Y(jié)構(gòu)、存儲(chǔ)結(jié)構(gòu)及相應(yīng)的算法，并初步掌握算法的時(shí)間效率分析和空間效率分析的技術(shù)。數(shù)據(jù)結(jié)構(gòu)課程涉及到離散數(shù)學(xué)、可計(jì)算性理論、算法復(fù)雜性等理論知識(shí)。對(duì)于學(xué)生來(lái)說(shuō)，該課程理論性強(qiáng)，較抽象和深?yuàn)W，同時(shí)，學(xué)生對(duì)算法設(shè)計(jì)或程序設(shè)計(jì)中的技巧也會(huì)感到難以理解和掌握。因此，相當(dāng)一部分學(xué)生覺(jué)得理解書(shū)上的基本概念并不難，可是一到解決具體問(wèn)題時(shí)就感到困難重重，對(duì)于有一定難度的算法設(shè)計(jì)題更是無(wú)從下手[1，2]。

應(yīng)用型本科人才的培養(yǎng)目標(biāo)是知識(shí)、能力、素質(zhì)和諧發(fā)展的高素質(zhì)人才，是介于傳統(tǒng)學(xué)科型人才與職業(yè)技能型人才的“中間型人才”，要求既有本科人才的學(xué)科教育特征，又有應(yīng)用人才的職業(yè)教育特性[3]。著重培養(yǎng)學(xué)生解決實(shí)際問(wèn)題的能力是職業(yè)教育的主要特性，也是應(yīng)用型本科院校最需要加強(qiáng)的部分。根據(jù)軟件行業(yè)一線開(kāi)發(fā)人員的開(kāi)發(fā)經(jīng)驗(yàn)的調(diào)查，在大型的復(fù)雜的數(shù)據(jù)面前，使用傳統(tǒng)的數(shù)據(jù)結(jié)構(gòu)來(lái)處理顯得力不從心，如果使用自己開(kāi)發(fā)數(shù)據(jù)結(jié)構(gòu)來(lái)處理數(shù)據(jù)，就需要耗費(fèi)大量的時(shí)間和精力，同時(shí)在效率和安全性上也難以保證。比較好的解決辦法是引入第三方增強(qiáng)型的數(shù)據(jù)結(jié)構(gòu)，這樣既能很好地解決問(wèn)題，又能提高工作效率。

1 傳統(tǒng)的Java數(shù)據(jù)結(jié)構(gòu)教學(xué)

傳統(tǒng)的數(shù)據(jù)結(jié)構(gòu)教學(xué)主要是對(duì)表、樹(shù)、圖、棧和隊(duì)列的數(shù)據(jù)結(jié)構(gòu)的講解，其講解的內(nèi)容通常是對(duì)于數(shù)據(jù)結(jié)構(gòu)的定義和實(shí)現(xiàn)，具體內(nèi)容如表1所示[4]。

表1 傳統(tǒng)的Java數(shù)據(jù)結(jié)構(gòu)及其講授內(nèi)容

[傳統(tǒng)數(shù)

據(jù)結(jié)構(gòu)＼&Java;中的常

見(jiàn)數(shù)據(jù)結(jié)構(gòu)＼&講授內(nèi)容＼&

線性表＼&Array;＼&講授Array數(shù)組的定義、實(shí)現(xiàn)及其查詢(xún)、排序、刪除等操作的實(shí)現(xiàn)。＼&LinkedList;＼&線性鏈表的定義、實(shí)現(xiàn)過(guò)程以及增加、刪除、修改、查詢(xún)一個(gè)元素的實(shí)現(xiàn)過(guò)程。＼&Stack;＼&棧的實(shí)現(xiàn)原理及其實(shí)現(xiàn)過(guò)程。出棧、壓棧操作的實(shí)現(xiàn)過(guò)程。＼&Queue;＼&隊(duì)列的實(shí)現(xiàn)原理及其實(shí)現(xiàn)過(guò)程。入隊(duì)、出隊(duì)操作的實(shí)現(xiàn)過(guò)程。＼&

樹(shù)＼&TreeSet;＼&樹(shù)集的基本操作如添加、刪除、包含。＼&TreeMap;＼&樹(shù)映射的存、取、刪除、主鍵包含等操作。＼&圖＼&HashMap;＼&HashMap;的實(shí)現(xiàn)過(guò)程及其存、取、刪除、遍歷等操作。＼&表＼&HashTable;＼&HashTable;的實(shí)現(xiàn)過(guò)程及其存、取、刪除、遍歷等操作。＼&

集合＼&Vector;＼&Vector;的實(shí)現(xiàn)過(guò)程以及其存、取、刪除、遍歷等操作。＼&ArrayList;＼&ArrayList;的實(shí)現(xiàn)過(guò)程以及其存、取、刪除、遍歷等操作。＼&HashSet;＼&HashSet;的實(shí)現(xiàn)過(guò)程以及其存、取、刪除、遍歷等操作。＼&]

在傳統(tǒng)的數(shù)據(jù)結(jié)構(gòu)課程講授中，更傾向于各種數(shù)據(jù)結(jié)構(gòu)的具體實(shí)現(xiàn)過(guò)程，而對(duì)分析數(shù)據(jù)結(jié)構(gòu)特性，以及為數(shù)據(jù)選擇適當(dāng)?shù)慕Y(jié)構(gòu)等方面關(guān)注較少，與實(shí)際應(yīng)用，特別是對(duì)大型數(shù)據(jù)結(jié)構(gòu)的處理應(yīng)用結(jié)合更少。

舉兩個(gè)例子來(lái)說(shuō)明。

例1：在應(yīng)用開(kāi)發(fā)中，經(jīng)常應(yīng)用到代碼-名稱(chēng)匹配的問(wèn)題，通過(guò)代碼找到對(duì)應(yīng)的名稱(chēng)，可以采用傳統(tǒng)的數(shù)據(jù)結(jié)構(gòu)map中的HashMap輕松解決，但如果需要代碼-名稱(chēng)雙向匹配，即通過(guò)代碼能找到名稱(chēng)，通過(guò)名稱(chēng)也可以找到代碼，對(duì)于這種問(wèn)題的處理，用傳統(tǒng)的數(shù)據(jù)結(jié)構(gòu)，比如Java中的HashMap來(lái)解決是比較困難的。

例2：電子商務(wù)中經(jīng)常用到在線購(gòu)物車(chē)。在線購(gòu)物車(chē)處理中，經(jīng)常需要把一個(gè)對(duì)象的多個(gè)拷貝加入到一個(gè)集合類(lèi)（比如Java中的ArrayList）中，開(kāi)發(fā)人員將對(duì)象加入到ArrayList過(guò)程中，然后每添加一次都要進(jìn)行一下迭代，來(lái)判斷是否添加了給定類(lèi)型的對(duì)象。這種方法存在的缺點(diǎn)就是內(nèi)存消耗比較大，速度和效率上也存在著不足。

使用傳統(tǒng)的數(shù)據(jù)結(jié)構(gòu)方法在解決上述兩個(gè)問(wèn)題時(shí)，顯的有點(diǎn)力不從心，或者是在資源和效率等方面存在著不足，這時(shí)就需要引入第三方增強(qiáng)型的數(shù)據(jù)結(jié)構(gòu)框架，比如Java數(shù)據(jù)結(jié)構(gòu)中引如Appache Commons中的Collections類(lèi)庫(kù)。從而能夠方便、高效地解決上述等問(wèn)題。

2 Appache Common Collections

Commons是Apache公司的一個(gè)項(xiàng)目，主要關(guān)注Java組件的可重用方面，Collections是Appache Commons項(xiàng)目中的一個(gè)組件，是一個(gè)用來(lái)處理集合Collection的開(kāi)源工具包。

Java集合框架是JDK1.2版本以后增加的主要內(nèi)容。這些集合框架中包含了許多功能強(qiáng)大的數(shù)據(jù)結(jié)構(gòu)，從而為Java應(yīng)用的開(kāi)發(fā)提供了便利。Commons Collections是一款建立在JDK類(lèi)的基礎(chǔ)上，提供新的接口，實(shí)現(xiàn)類(lèi)和工具包的開(kāi)源集合框架。它包含很多新的特性，比如集合中的Bag接口存放著一個(gè)對(duì)象的多個(gè)副本，比如Buffer接口提供先進(jìn)先出的可變隊(duì)列、多種比較器、多種迭代器等。表2列出了Commons-collections框架中的部分主要的類(lèi)及其應(yīng)用。

表2 Commons-collections中的部分主要類(lèi)及其應(yīng)用

[部分包＼&主要的類(lèi)＼&主要應(yīng)用＼&collections;＼&ArrayStack;＼&適用用單線程環(huán)境. ＼&BeanMap;＼&可以將Map作為一個(gè)JavaBean來(lái)使用＼&ExtendedProperties;＼&一個(gè)屬性鍵可對(duì)應(yīng)多個(gè)值＼&FastArrayList;， FastHashMap＼&適用于多線程環(huán)境 ＼&bag;＼&HashBag;， TreeBag＼&該包中只存放一個(gè)對(duì)象的拷貝和一個(gè)計(jì)數(shù)器＼&bidimap;＼&TreeBidiMap;＼&可以根據(jù)鍵和值進(jìn)行排序＼&collection;＼&CompositeCollection;＼&可以創(chuàng)建集合的集合＼&SynchronizedCollection;＼&可以使存在的集合線程安全＼&TransformedCollection;＼&當(dāng)向集合中添加對(duì)象時(shí)，可轉(zhuǎn)換對(duì)象數(shù)據(jù)類(lèi)型。＼&Iterators;＼&ArrayIterator;＼&實(shí)現(xiàn)對(duì)任意array的迭代＼&LoopingIterator;＼&實(shí)現(xiàn)循環(huán)迭代功能＼↦＼&MultiKeyMap;＼&多個(gè)key可以映射一個(gè)map＼&LazyMap;＼⤅中的鍵/值對(duì)一開(kāi)始并不存在，當(dāng)被調(diào)用到時(shí)才創(chuàng)建＼&BidiMap;＼&雙向Map，可以通過(guò)Key找到Value，也可以通過(guò)Value找到Key＼&MultiMap;＼&一個(gè)Key指向一組對(duì)象＼&]

3 課程內(nèi)容置換

從表2可以看出，Common-Collections中的數(shù)據(jù)結(jié)構(gòu)是在基本數(shù)據(jù)結(jié)構(gòu)的基礎(chǔ)上進(jìn)行封裝、擴(kuò)展，能夠針對(duì)某種復(fù)雜的數(shù)據(jù)結(jié)構(gòu)進(jìn)行簡(jiǎn)化處理，功能更加強(qiáng)大，是對(duì)傳統(tǒng)數(shù)據(jù)結(jié)構(gòu)的一種有效補(bǔ)充，在對(duì)大型復(fù)雜數(shù)據(jù)進(jìn)行處理時(shí)，可選的數(shù)據(jù)結(jié)構(gòu)更加靈活，更具有針對(duì)性。

為了使學(xué)生能夠在學(xué)習(xí)數(shù)據(jù)結(jié)構(gòu)課的同時(shí)，對(duì)其他增強(qiáng)型的擴(kuò)展的第三方數(shù)據(jù)結(jié)構(gòu)有一定的了解，在授課時(shí)，可以將傳統(tǒng)數(shù)據(jù)結(jié)構(gòu)中的部分內(nèi)容進(jìn)行刪減，替換為第三方數(shù)據(jù)結(jié)構(gòu)的部分內(nèi)容，從而保證數(shù)據(jù)結(jié)構(gòu)的總學(xué)時(shí)保持不變[5]。建議替換的內(nèi)容如表3所示，也可根據(jù)實(shí)際情況進(jìn)行相應(yīng)的替換。

表3 建議替換內(nèi)容

[數(shù)據(jù)結(jié)構(gòu)＼&取消內(nèi)容＼&增加內(nèi)容＼&線性鏈表＼&線性鏈表自身的實(shí)現(xiàn)原理以及其增、刪、改、查等具體的操作，只關(guān)注其提供的操作方法。＼&Common-Collections;中的相關(guān)類(lèi)，比如ArrayStack，F(xiàn)astArrayList等。＼&樹(shù)＼&樹(shù)的實(shí)現(xiàn)原理、樹(shù)的存儲(chǔ)結(jié)構(gòu)、樹(shù)的遍歷等，只關(guān)注樹(shù)提供的方法即可。＼&Commons; Collections中的類(lèi)比如：TreeList，TreeBag和TreeBidiMap等。＼&圖＼&圖的實(shí)現(xiàn)原理、存儲(chǔ)結(jié)構(gòu)及遍歷等內(nèi)容。＼&Commons; Collections中的相關(guān)類(lèi)：

比如bidimap，MultiKeyMap等。＼&集合＼&集合的實(shí)現(xiàn)原理、存儲(chǔ)、迭代等內(nèi)容。＼&Commons; Collections中的相關(guān)類(lèi)，比如ArrayIterator、LoopingIterator等。＼&]

4 新舊課程內(nèi)容比較

如果采用Appache中的新的數(shù)據(jù)結(jié)構(gòu)，例子1、2中的問(wèn)題就能夠很容易得到解決，而如果采用傳統(tǒng)的Java中的數(shù)據(jù)結(jié)構(gòu)來(lái)解決的話，在實(shí)現(xiàn)的過(guò)程中會(huì)存在著一定的難度及較大的工作量，在效率和資源等方面也存在著不足。

為了解決例1中的問(wèn)題，實(shí)現(xiàn)既能通過(guò)Key找到Value，又能通過(guò)Value找到Key功能，如果使用傳統(tǒng)的Java中數(shù)據(jù)結(jié)構(gòu)，需要建立兩個(gè)HashpMap，一個(gè)HashMap中的Value值同作為另外一個(gè)HashMap的Key值。使用org.apache.commons.collections.bidimap包中的類(lèi)，就能使問(wèn)題變得非常簡(jiǎn)單，bidimap包中的BidMap類(lèi)就可直接滿足Key值和Value值相互查找的功能。使用BidMap類(lèi)來(lái)實(shí)現(xiàn)該功能的主要代碼如下：

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中的問(wèn)題，如果采用傳統(tǒng)的Java數(shù)據(jù)結(jié)構(gòu)，使用ArrayList類(lèi)來(lái)實(shí)現(xiàn)，需要在對(duì)象加入到ArrayList過(guò)程中，每添加一次都要進(jìn)行一下迭代，來(lái)判斷是否添加了給定類(lèi)型的對(duì)象。如果采用org.apache.commons.collections.bag包中的類(lèi)，就能使問(wèn)題變得非常簡(jiǎn)單。一個(gè)比較好的設(shè)計(jì)就是只保存一個(gè)對(duì)象的拷貝，而在添加同樣類(lèi)型的實(shí)體時(shí)，只是增加計(jì)數(shù)器的值。hashbag和treebag類(lèi)（分別基于hashmap和treemap）很好的滿足了這個(gè)需求。用Java代碼很容易實(shí)現(xiàn)該功能。

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

通過(guò)比較可以發(fā)現(xiàn)，在解決例1和例2問(wèn)題的過(guò)程中，采用傳統(tǒng)的數(shù)據(jù)結(jié)構(gòu)增加了程序的復(fù)雜度及代碼量，同時(shí)在效率和性能上也有所降低，內(nèi)存消耗也比較大；而采用增強(qiáng)型的第三方數(shù)據(jù)結(jié)構(gòu)如Appache來(lái)解決上述問(wèn)題時(shí)，則能很好地規(guī)避上述不足，充分提高程序的性能及開(kāi)發(fā)的效率。從學(xué)生的動(dòng)手能力培養(yǎng)以及處理實(shí)際大型數(shù)據(jù)的能力上來(lái)看，置換后的課程比置換前存在著更多的優(yōu)勢(shì)。

5 結(jié)束語(yǔ)

基于本文提出的數(shù)據(jù)結(jié)構(gòu)教學(xué)改革方法已經(jīng)在南陽(yáng)理工學(xué)院軟件學(xué)院部分班級(jí)試用，目前已經(jīng)有一屆畢業(yè)生。根據(jù)進(jìn)入軟件公司從事軟件開(kāi)發(fā)的畢業(yè)生反饋情況來(lái)看，新的數(shù)據(jù)結(jié)構(gòu)教學(xué)方法能夠解決實(shí)際軟件開(kāi)發(fā)中的大型數(shù)據(jù)的結(jié)構(gòu)處理問(wèn)題，增強(qiáng)他們軟件開(kāi)發(fā)經(jīng)驗(yàn)，提高他們的就業(yè)競(jìng)爭(zhēng)力。但從考研的學(xué)生角度來(lái)看，減少數(shù)據(jù)結(jié)構(gòu)的具體實(shí)現(xiàn)過(guò)程的講解，存在一定的不足。如何能夠在保證學(xué)時(shí)不變的情況下，兼顧到考研學(xué)生情況，是今后需要研究實(shí)踐的課題。

參考文獻(xiàn)：

[1] 季曉慧，王群.“數(shù)據(jù)結(jié)構(gòu)”課程教學(xué)初探[J].中國(guó)地質(zhì)教育，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] 錢(qián)國(guó)英，徐立清，應(yīng)雄.高等教育轉(zhuǎn)型與應(yīng)用型本科人才培養(yǎng)[M].浙江大學(xué)出版社，2007.11：74-75

[4] 金靜梅.Java集合框架在Web開(kāi)發(fā)中的應(yīng)用[J].計(jì)算機(jī)時(shí)代，2010.6：31-32

[5] Hongfei Sun， Huijuan Wu， Min Liu . “Data Structure” CurriculumReform and Foreign Language Teaching Research. ETCS，2010.2：762-765