應(yīng)用型本科院校數(shù)據(jù)結(jié)構(gòu)課程教學改革

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

關(guān)鍵詞： 應(yīng)用型本科院校； 數(shù)據(jù)結(jié)構(gòu)； 課程改革； 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 引言

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

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

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

傳統(tǒng)的數(shù)據(jù)結(jié)構(gòu)教學主要是對表、樹、圖、棧和隊列的數(shù)據(jù)結(jié)構(gòu)的講解，其講解的內(nèi)容通常是對于數(shù)據(jù)結(jié)構(gòu)的定義和實現(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中的常

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

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

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

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

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

舉兩個例子來說明。

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

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

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

2 Appache Common Collections

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

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

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

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

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

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

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

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

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

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

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

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

為了解決例1中的問題，實現(xiàn)既能通過Key找到Value，又能通過Value找到Key功能，如果使用傳統(tǒng)的Java中數(shù)據(jù)結(jié)構(gòu)，需要建立兩個HashpMap，一個HashMap中的Value值同作為另外一個HashMap的Key值。使用org.apache.commons.collections.bidimap包中的類，就能使問題變得非常簡單，bidimap包中的BidMap類就可直接滿足Key值和Value值相互查找的功能。使用BidMap類來實現(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中的問題，如果采用傳統(tǒng)的Java數(shù)據(jù)結(jié)構(gòu)，使用ArrayList類來實現(xiàn)，需要在對象加入到ArrayList過程中，每添加一次都要進行一下迭代，來判斷是否添加了給定類型的對象。如果采用org.apache.commons.collections.bag包中的類，就能使問題變得非常簡單。一個比較好的設(shè)計就是只保存一個對象的拷貝，而在添加同樣類型的實體時，只是增加計數(shù)器的值。hashbag和treebag類（分別基于hashmap和treemap）很好的滿足了這個需求。用Java代碼很容易實現(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

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

5 結(jié)束語

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

參考文獻：

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

[4] 金靜梅.Java集合框架在Web開發(fā)中的應(yīng)用[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