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

梁智學(xué) 賈滿磊

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

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

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

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

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

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

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

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

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

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

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

舉兩個(gè)例子來說明。

例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)常需要把一個(gè)對象的多個(gè)拷貝加入到一個(gè)集合類（比如Java中的ArrayList）中，開發(fā)人員將對象加入到ArrayList過程中，然后每添加一次都要進(jìn)行一下迭代，來判斷是否添加了給定類型的對象。這種方法存在的缺點(diǎn)就是內(nèi)存消耗比較大，速度和效率上也存在著不足。

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

2 Appache Common Collections

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

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

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

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

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

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

為了使學(xué)生能夠在學(xué)習(xí)數(shù)據(jù)結(jié)構(gòu)課的同時(shí)，對其他增強(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)類，比如ArrayStack，F(xiàn)astArrayList等。＼&樹＼&樹的實(shí)現(xiàn)原理、樹的存儲結(jié)構(gòu)、樹的遍歷等，只關(guān)注樹提供的方法即可。＼&Commons; Collections中的類比如：TreeList，TreeBag和TreeBidiMap等。＼&圖＼&圖的實(shí)現(xiàn)原理、存儲結(jié)構(gòu)及遍歷等內(nèi)容。＼&Commons; Collections中的相關(guān)類：

比如bidimap，MultiKeyMap等。＼&集合＼&集合的實(shí)現(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)來解決的話，在實(shí)現(xiàn)的過程中會(huì)存在著一定的難度及較大的工作量，在效率和資源等方面也存在著不足。

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

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

5 結(jié)束語

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

參考文獻(xiàn)：

[1] 季曉慧，王群.“數(shù)據(jù)結(jié)構(gòu)”課程教學(xué)初探[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].浙江大學(xué)出版社，2007.11：74-75

[4] 金靜梅.Java集合框架在Web開發(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