亓 璐

(濟(jì)寧學(xué)院計算機(jī)科學(xué)系，山東 濟(jì)寧 273155)

《數(shù)據(jù)結(jié)構(gòu)》課程教學(xué)改革探討

亓 璐

(濟(jì)寧學(xué)院計算機(jī)科學(xué)系，山東 濟(jì)寧 273155)

針對《數(shù)據(jù)結(jié)構(gòu)》課程教學(xué)中存在的問題，提出了如下改革措施：運用生活和科研案例，激發(fā)學(xué)生的學(xué)習(xí)興趣；使用面向?qū)ο蟮奶匦?，挖掘知識點之間的關(guān)系，使學(xué)生建立課程的整體知識框架；轉(zhuǎn)變學(xué)生的學(xué)習(xí)思路，使其重視概念的理解；采用圖解法使程序分析中的抽象問題具體化，幫助學(xué)生編寫代碼。實踐表明，采取上述措施和方法，有效地提高了課堂教學(xué)效率。

數(shù)據(jù)結(jié)構(gòu)；面向?qū)ο螅话咐虒W(xué)；圖解法；實驗教學(xué)

《數(shù)據(jù)結(jié)構(gòu)》是計算機(jī)專業(yè)課程體系中一門非常重要的基礎(chǔ)課程，其一方面能擴(kuò)展和深化《離散數(shù)學(xué)》、《程序設(shè)計語言》等課程中的基本理論和方法，另一方面能為學(xué)生學(xué)習(xí)《操作系統(tǒng)》、《編譯原理》和《數(shù)據(jù)庫》等后續(xù)課程奠定堅實的理論與實踐基礎(chǔ)[1]。通過該課程的學(xué)習(xí)，使學(xué)生能從數(shù)據(jù)結(jié)構(gòu)的角度出發(fā)，為現(xiàn)實問題所涉及的數(shù)據(jù)選擇合適的邏輯結(jié)構(gòu)、存儲結(jié)構(gòu)，設(shè)計出合理、可行的算法，并編寫出正確、清晰和高質(zhì)量的程序，提高算法設(shè)計能力和工程實踐能力[2]。由于該課程的傳統(tǒng)課堂教學(xué)模式過于注重介紹基本內(nèi)容和講解習(xí)題，忽視對學(xué)生實踐能力的培養(yǎng)，導(dǎo)致學(xué)生學(xué)習(xí)該課程時感到枯燥乏味，學(xué)習(xí)積極性不高。因此，如何激發(fā)學(xué)生的學(xué)習(xí)興趣并增強(qiáng)學(xué)生解決實際問題的能力，是一個亟待解決的問題。為此，筆者從理論教學(xué)和實驗教學(xué)2個方面、多個角度對傳統(tǒng)課堂教學(xué)方法進(jìn)行了改革和創(chuàng)新?。

1 《數(shù)據(jù)結(jié)構(gòu)》理論教學(xué)改革

1.1引用生活實例激發(fā)學(xué)生的學(xué)習(xí)興趣

《數(shù)據(jù)結(jié)構(gòu)》課程內(nèi)容豐富，知識點之間的關(guān)系錯綜復(fù)雜。要取得好的教學(xué)效果，首先要激發(fā)學(xué)生的學(xué)習(xí)興趣。由于數(shù)據(jù)結(jié)構(gòu)是在現(xiàn)實生活中總結(jié)出來的，所以在課堂教學(xué)中應(yīng)適當(dāng)引入生活實例，通過“聯(lián)想”式的啟發(fā)，將抽象的理論知識轉(zhuǎn)化成學(xué)生容易理解和感興趣的內(nèi)容，從而調(diào)動學(xué)生的學(xué)習(xí)積極性[3]。例如，在講解采用開放定址法解決散列表的沖突時，可以用學(xué)生在圖書館占位為例進(jìn)行說明。當(dāng)學(xué)生來到圖書館選中一個坐位將要坐下時，發(fā)現(xiàn)桌上寫著“占位，謝謝合作”，此即散列表中的沖突。如何解決上述問題呢？一種處理方式是觀察右邊的位子是否被占，如果也被占，再觀察右邊下一個位子，依次類推，而往右查看下一個位子就是線性探測法的+1，+2，+3，…。另一種處理方式是先觀察左邊的位子是否被占，再觀察右邊的位子是否被占，此即二次探測再散列的+1和-1。這樣通過列舉與學(xué)生生活緊密聯(lián)系的實例，可以輕松愉快地理解所學(xué)知識。

1.2培養(yǎng)學(xué)生面向?qū)ο蟮乃季S方式

在數(shù)據(jù)結(jié)構(gòu)中，抽象數(shù)據(jù)類型充分概括數(shù)據(jù)結(jié)構(gòu)定義中的數(shù)據(jù)對象、數(shù)據(jù)關(guān)系和操作3個方面。以往教學(xué)時用學(xué)生比較熟悉的C語言對抽象數(shù)據(jù)類型進(jìn)行描述，由于C語言的局限性，其不能準(zhǔn)確、有效地表現(xiàn)抽象數(shù)據(jù)類型的思想，而C++或Java中類的特性與抽象數(shù)據(jù)類型的抽象性和封裝性相符合[4]，因此，利用面向?qū)ο蠓椒ê虲++語言來描述數(shù)據(jù)結(jié)構(gòu)可以提高課堂教學(xué)效率。這種改變，不僅有助于挖掘數(shù)據(jù)結(jié)構(gòu)中隱藏其中的關(guān)系，而且能夠培養(yǎng)學(xué)生面向?qū)ο蟮乃季S分析方式以及注重可復(fù)用構(gòu)件的思想。例如，棧是操作受限的線性表，如果把線性表的表頭定義為棧底，表尾定義為棧頂，那么入棧操作等價于在線性表的表尾進(jìn)行插入操作，出棧操作等價于在線性表的表尾進(jìn)行刪除操作，因此可以引導(dǎo)學(xué)生將線性表理解為基類，將棧作為線性表的派生類對待。在線性表操作的基礎(chǔ)上再實現(xiàn)棧的操作，可以加深學(xué)生對程序設(shè)計的模塊化和結(jié)構(gòu)化的認(rèn)識。這樣找到即將講解的棧和已講解的線性表的關(guān)系，增強(qiáng)了知識點的連貫性，使學(xué)生對新知識更容易理解。

1.3加強(qiáng)整體知識框架的構(gòu)建

數(shù)據(jù)結(jié)構(gòu)課程理論知識龐雜、分散，如果知識點的因果關(guān)系、內(nèi)在邏輯關(guān)系沒理順的話，學(xué)生學(xué)習(xí)起來會感覺很困難。為此，需要分析各種邏輯結(jié)構(gòu)之間以及各章節(jié)知識點之間的關(guān)系，采用縱橫對比的方法將分散的的概念和運算納入完整的學(xué)科體系中，從而建構(gòu)起完整知識結(jié)構(gòu)框架[5]。

橫向?qū)Ρ确矫?，以線性表為例，可從線性表的順序存儲結(jié)構(gòu)和鏈?zhǔn)酱鎯Y(jié)構(gòu)2個方面出發(fā)，分析算法的優(yōu)缺點，從而弄清楚知識點的前因后果，將順序表、單鏈表、循環(huán)鏈表和雙向鏈表“串聯(lián)”起來。當(dāng)在線性表的順序存儲(順序表)中插入、刪除一個數(shù)據(jù)元素操作時，“驚動”了其他許多數(shù)據(jù)元素，因而需要移動大量數(shù)據(jù)元素。為了解決順序表動態(tài)操作效率低的問題，可引入鏈?zhǔn)酱鎯?。鏈?zhǔn)酱鎯χ械膯捂湵硗ㄟ^指針“順藤摸瓜”找到下一個數(shù)據(jù)元素，但無法找到其直接前驅(qū)元素，為此引入循環(huán)鏈表。循環(huán)鏈表雖然能夠?qū)崿F(xiàn)找到任何一個數(shù)據(jù)元素的前驅(qū)結(jié)點，但是時間復(fù)雜度比較大，為此通過改進(jìn)結(jié)點，增加指向前驅(qū)的指針域，進(jìn)而形成雙向鏈表。雙向鏈表的2個指針域可以容易地找到任何一個數(shù)據(jù)元素的前驅(qū)和后繼，時間復(fù)雜度都降為O(1)。這并不能說明雙向鏈表是十全十美的，也存在不足，存儲密度不緊密就是其中一個方面。順著該線索，引導(dǎo)學(xué)生發(fā)現(xiàn)順序表的優(yōu)點。經(jīng)過深入分析，使學(xué)生對各種存儲方式做到“心中有數(shù)”，這樣在處理實際問題時才能“揚長避短”。

縱向?qū)Ρ确矫?，以線性結(jié)構(gòu)和樹形結(jié)構(gòu)為例，對上述2種原本不相干的結(jié)構(gòu)進(jìn)行分析，發(fā)現(xiàn)它們存在相似的地方：線性結(jié)構(gòu)除了首元素外具有唯一的前驅(qū)，樹形結(jié)構(gòu)除了根結(jié)點外具有唯一的雙親；線性結(jié)構(gòu)除了尾元素外具有唯一的后繼，樹形結(jié)構(gòu)除了葉子結(jié)點外具有多個孩子。因此，線性結(jié)構(gòu)的前驅(qū)相當(dāng)于樹形結(jié)構(gòu)的雙親，線性結(jié)構(gòu)的后繼相當(dāng)于樹形結(jié)構(gòu)的孩子。這樣，樹形結(jié)構(gòu)中形式上只有左孩子或只有右孩子的單支二叉樹，本質(zhì)上其實是線性結(jié)構(gòu)。

1.4注重基本概念的理解

2 《數(shù)據(jù)結(jié)構(gòu)》實驗教學(xué)改革

由于《數(shù)據(jù)結(jié)構(gòu)》是一門理論與實踐緊密結(jié)合的課程，因而要求學(xué)生既能掌握基本的理論知識，還能上機(jī)編程實現(xiàn)算法。為了提高學(xué)生的程序設(shè)計能力，可以采用算法自然語言、C++語言并配合相應(yīng)示意圖的教學(xué)方式，具體內(nèi)容如下。

2.1示意圖法在隊列初始化中的應(yīng)用

隊列是操作受限的線性表，在隊頭出隊列、在隊尾入隊列。在實現(xiàn)隊列初始化時，首先明確目標(biāo)，即最終形成空隊列(見圖1)；然后將算法自然語言描述“翻譯”成C++語言，畫出對應(yīng)的示意圖。每更新一次示意圖，都要與圖1對照，找出差異，完善程序，步驟如下：

1)生成一個結(jié)點：Node *front=new Node；(見圖2)。

2)指針域為空： front->next=Null(見圖3)。

3)隊尾指向頭結(jié)點：rear=front；(見圖4)。

最后將算法最終生成圖與圖1對比，如果兩者相同，則程序完成；如果兩者不相同，找出差別，完善程序，直到與圖1完全相同為止。

圖1 空隊列 圖2 生成結(jié)點 圖3 設(shè)置指針域 圖4 設(shè)置隊尾指針

2.2示意圖法在順序表初始化中的應(yīng)用

順序表是指用一組地址連續(xù)的存儲空間依次存放線性表中的數(shù)據(jù)元素，其包含以下重要信息：開辟一塊地址連續(xù)的存儲空間；開辟空間大小；將數(shù)據(jù)元素放入其中；放入數(shù)據(jù)元素的個數(shù)。據(jù)此建立對應(yīng)類，elem為開辟存儲空間的首地址，listsize為空間大小，length為存放數(shù)據(jù)元素的個數(shù)。因此建立類list為：

Class list{

private

int length;

int listsize;

圖5 開辟空間 圖6 空間為100

T *elem;

}

順序表的初始化就是實現(xiàn)順序表概念的4個方面，即為類中3個變量賦值：

1)開辟地址連續(xù)的空間：elem=new T[listsize];(見圖5)。

2)空間大小為100：listsize=100;(見圖6)。

3)初始狀態(tài)不存放數(shù)據(jù)元素：length=0。

3 結(jié) 語

為了提高《數(shù)據(jù)結(jié)構(gòu)》課程教學(xué)質(zhì)量，筆者提出一些針對性的改革措施。教學(xué)實踐表明，采取教學(xué)改革措施后，提高了課堂教學(xué)效率，明顯改善教學(xué)效果，因而受到學(xué)生的認(rèn)可。今后，應(yīng)在培養(yǎng)學(xué)生的編程能力方面繼續(xù)探索，從而進(jìn)一步提高學(xué)生的實踐創(chuàng)新素質(zhì)。

[1]劉馨月,張憲超,于紅.數(shù)據(jù)結(jié)構(gòu)與算法核心課程建設(shè)[J].計算機(jī)教育,2011(6):65-68.

[2] 張小剛,李向陽.《數(shù)據(jù)結(jié)構(gòu)》課程教學(xué)改革探討與實踐[J].塔里木大學(xué)學(xué)報,2008,20(2)：93-95.

[3] 陳越,何欽銘,馮雁.“數(shù)據(jù)結(jié)構(gòu)”綜合性課程設(shè)計教學(xué)探索與實踐[J].計算機(jī)教育,2008(8):54-55.

[4] 殷人昆.數(shù)據(jù)結(jié)構(gòu)(用面向?qū)ο蠛?C++描述)[M]. 北京:清華大學(xué)出版社,2007.

[5] 青宇航.關(guān)于《數(shù)據(jù)結(jié)構(gòu)》現(xiàn)代教學(xué)方法的探索[J].教育與職業(yè),2007,59(8):151-152.

[編輯] 李啟棟

10.3969/j.issn.1673-1409(N).2012.11.062

N4

A

16731409(2012)11N18603