數(shù)據(jù)結(jié)構(gòu)實(shí)驗(yàn)課程教學(xué)方法探索

陳紅梅，肖清，王麗珍，孔兵

(云南大學(xué) 信息學(xué)院，云南 昆明 650091)

數(shù)據(jù)結(jié)構(gòu)是計(jì)算機(jī)程序設(shè)計(jì)的重要理論和技術(shù)基礎(chǔ)。數(shù)據(jù)結(jié)構(gòu)課程的主要目標(biāo)是培養(yǎng)學(xué)生的數(shù)據(jù)抽象能力和程序設(shè)計(jì)能力。數(shù)據(jù)結(jié)構(gòu)實(shí)驗(yàn)課程是數(shù)據(jù)結(jié)構(gòu)課程的重要補(bǔ)充，有助于訓(xùn)練學(xué)生的數(shù)據(jù)抽象能力和程序設(shè)計(jì)能力，提升學(xué)生利用計(jì)算機(jī)分析和解決應(yīng)用問題的實(shí)踐能力。云南大學(xué)信息學(xué)院計(jì)算機(jī)科學(xué)與技術(shù)專業(yè)的新教學(xué)計(jì)劃將數(shù)據(jù)結(jié)構(gòu)課程及數(shù)據(jù)結(jié)構(gòu)實(shí)驗(yàn)課程的教學(xué)安排從二年級(jí)下學(xué)期調(diào)整至一年級(jí)下學(xué)期。由于學(xué)生系統(tǒng)學(xué)習(xí)專業(yè)知識(shí)的時(shí)間不長(zhǎng)，增加了數(shù)據(jù)結(jié)構(gòu)的教學(xué)難度，有必要調(diào)整教學(xué)內(nèi)容，探索合適的教學(xué)方法。

1 數(shù)據(jù)結(jié)構(gòu)實(shí)驗(yàn)課程教學(xué)中的問題

1.1 學(xué)生的C 語言基礎(chǔ)薄弱

數(shù)據(jù)結(jié)構(gòu)實(shí)驗(yàn)選用C 語言作為實(shí)驗(yàn)平臺(tái)，然而學(xué)生的C 語言基礎(chǔ)薄弱，主要體現(xiàn)在:1)對(duì)指針本質(zhì)的理解不夠清晰。當(dāng)實(shí)現(xiàn)數(shù)據(jù)的動(dòng)態(tài)分配順序存儲(chǔ)結(jié)構(gòu)及鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)時(shí)，指針的理解及應(yīng)用是基礎(chǔ)。然而學(xué)生經(jīng)常混淆變量、指針、指針變量，導(dǎo)致實(shí)驗(yàn)不能順利進(jìn)行，甚至無法進(jìn)行。2)對(duì)函數(shù)參數(shù)的應(yīng)用不夠靈活。當(dāng)實(shí)現(xiàn)操作算法時(shí)，函數(shù)參數(shù)的理解及應(yīng)用是基礎(chǔ)。但是學(xué)生對(duì)指針變量的參數(shù)理解模糊，不能靈活利用指針變量在函數(shù)中修改數(shù)據(jù)元素及其關(guān)系。

1.2 學(xué)生缺乏算法設(shè)計(jì)基礎(chǔ)

數(shù)據(jù)結(jié)構(gòu)與算法相輔相成，但學(xué)生缺乏算法設(shè)計(jì)基礎(chǔ)，不能透徹理解某些算法思想，例如:1)遞歸。遞歸是許多問題的描述工具，也是計(jì)算機(jī)解決問題常用的設(shè)計(jì)工具，譬如，樹結(jié)構(gòu)可采用遞歸定義，二叉樹的構(gòu)造及遍歷可采用遞歸算法，但學(xué)生不能清晰地表達(dá)算法的遞歸結(jié)構(gòu)及遞歸出口。2)動(dòng)態(tài)規(guī)劃。動(dòng)態(tài)規(guī)則是計(jì)算機(jī)解決多階段決策最優(yōu)化問題的常用策略，譬如，帶權(quán)有向無環(huán)圖的關(guān)鍵路徑、最短路徑求解都可采用動(dòng)態(tài)規(guī)劃算法，但學(xué)生不能清楚地給出算法的動(dòng)態(tài)規(guī)劃遞推式及初始條件。

1.3 學(xué)生不能較好地融會(huì)貫通各個(gè)知識(shí)點(diǎn)

數(shù)據(jù)結(jié)構(gòu)的教學(xué)內(nèi)容覆蓋圖論、數(shù)據(jù)存儲(chǔ)、程序語言、算法等。學(xué)生普遍覺得知識(shí)點(diǎn)多且難，不能較好地融會(huì)貫通這些知識(shí)點(diǎn)，例如:1)兩種存儲(chǔ)結(jié)構(gòu)。順序和鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)是數(shù)據(jù)元素及其關(guān)系在計(jì)算機(jī)中的兩種表示方法，學(xué)生不能體會(huì)兩種存儲(chǔ)結(jié)構(gòu)對(duì)算法效率的影響，由于恐懼指針，總是優(yōu)先選用順序存儲(chǔ)結(jié)構(gòu)。2)多種查找方法。查找是具有廣泛應(yīng)用背景的問題，查找方法也是種類繁多，學(xué)生不清楚數(shù)據(jù)結(jié)構(gòu)對(duì)查找效率的影響，總是優(yōu)先選擇容易實(shí)現(xiàn)的查找算法。

2 數(shù)據(jù)結(jié)構(gòu)實(shí)驗(yàn)課程教學(xué)方法的探索與實(shí)踐

2.1 層次+插入式教學(xué)

數(shù)據(jù)結(jié)構(gòu)覆蓋的學(xué)科寬泛，學(xué)生對(duì)某些知識(shí)掌握不好，甚至尚未學(xué)習(xí)，但我們不能面面俱到地向?qū)W生灌輸這些知識(shí)。一方面，由于知識(shí)的開放性，不可能這樣做;另一方面，數(shù)據(jù)結(jié)構(gòu)本身有相對(duì)獨(dú)立的教學(xué)內(nèi)容。于是，我們將教學(xué)內(nèi)容分為核心內(nèi)容與邊緣內(nèi)容兩塊，嘗試了層次+播入式教學(xué)。

將核心內(nèi)容分為基礎(chǔ)、擴(kuò)展、綜合三個(gè)層次，基礎(chǔ)知識(shí)點(diǎn)是所有學(xué)生必須掌握的，擴(kuò)展知識(shí)點(diǎn)是為了培養(yǎng)學(xué)生能力應(yīng)該掌握的，綜合知識(shí)點(diǎn)是為了提升學(xué)生能力需要掌握的。學(xué)生也可分層，基礎(chǔ)較弱的學(xué)生至少必須掌握基礎(chǔ)知識(shí)點(diǎn)，能力較強(qiáng)的學(xué)生可逐步達(dá)到擴(kuò)展或綜合層次。這樣，不僅可消除基礎(chǔ)較弱學(xué)生的畏懼心理，增強(qiáng)自信心，也可激發(fā)能力較強(qiáng)學(xué)生的挑戰(zhàn)心理，提高積極性［1］。

對(duì)于邊緣內(nèi)容，采用“被動(dòng)、懶惰的”插入式教學(xué)，即直到用時(shí)才教學(xué)并側(cè)重基本概念、原理和方法的介紹，更多地鼓勵(lì)學(xué)生通過查資料、討論、實(shí)踐等方式自主學(xué)習(xí)［2］。例如指針，我們會(huì)總結(jié)式地復(fù)習(xí):變量是一塊內(nèi)存空間，有“在哪里”“有多大”兩個(gè)特征，它的地址稱為指針，它的大小由數(shù)據(jù)類型決定，指針變量也是一個(gè)變量，可存儲(chǔ)一個(gè)相應(yīng)數(shù)據(jù)類型變量的地址。然后，安排實(shí)驗(yàn)，要求學(xué)生采用單鏈表完成學(xué)生信息表的構(gòu)造、插入、刪除及修改等任務(wù)，驅(qū)動(dòng)學(xué)生自主復(fù)習(xí)、實(shí)踐體會(huì)。最后，通過討論解決遇到的問題。這種方式既可節(jié)省課時(shí)，也可避免一刀切，學(xué)生還可檢驗(yàn)自己是否真正理解指針。

2.2 案例+啟發(fā)式教學(xué)

案例教學(xué)可使學(xué)生明確學(xué)習(xí)的動(dòng)機(jī)、意義，明了知識(shí)點(diǎn)的重要性、必要性，激發(fā)學(xué)習(xí)熱情。此外，圍繞案例，學(xué)生還可了解各個(gè)知識(shí)點(diǎn)的聯(lián)系，融會(huì)貫通這些知識(shí)點(diǎn)，使得學(xué)習(xí)更有系統(tǒng)性。案例設(shè)計(jì)應(yīng)該具有針對(duì)性、系統(tǒng)性，即案例應(yīng)該緊緊圍繞即將教學(xué)的知識(shí)點(diǎn)，盡可能覆蓋相關(guān)的知識(shí)點(diǎn)［3］。教學(xué)方法應(yīng)該采用啟發(fā)式教學(xué)，即與學(xué)生互動(dòng)地分析案例，引導(dǎo)學(xué)生思考需要解決什么問題、如何解決這些問題，進(jìn)而導(dǎo)出知識(shí)點(diǎn)。這種方式既傳授了知識(shí)點(diǎn)，又培養(yǎng)了學(xué)生分析及解決問題的能力［3］。下面給出兩個(gè)示例。

2.2.1 動(dòng)態(tài)規(guī)劃

我們可采用一個(gè)小型案例:2階Fibonacci第n項(xiàng)計(jì)算，公式如下:

首先，根據(jù)公式(1)給出遞歸方法，即原問題fn可分解為兩個(gè)子問題fn－1和fn－2，原問題的答案可通過子問題的結(jié)果計(jì)算，而且子問題與原問題是同類型問題，可類似地遞歸計(jì)算，直至問題足夠簡(jiǎn)單，即直至遞歸出口f0和f1。然后，通過計(jì)算f5分析遞歸方法存在的問題。如圖1(a)所示，在計(jì)算f5時(shí)，有許多子問題被重復(fù)計(jì)算，如f2被計(jì)算了3次。隨著n的增加，問題更加突顯，嚴(yán)重影響效率。接著，通過討論給出如圖1(b)所示的動(dòng)態(tài)規(guī)劃方法，即顛倒計(jì)算方向，將自頂而下計(jì)算變?yōu)樽缘锥嫌?jì)算，每個(gè)子問題僅計(jì)算一次并將解保存在表中，當(dāng)需要再次計(jì)算該子問題時(shí)，通過查表獲得其解，從而避免重復(fù)計(jì)算。最后，總結(jié)動(dòng)態(tài)規(guī)劃方法:如果原問題可分解為若干相互重疊子問題，并且問題具有最優(yōu)子結(jié)構(gòu)性質(zhì)，則可根據(jù)動(dòng)態(tài)規(guī)劃遞推式，從初始條件開始，自底而上計(jì)算子問題，并將解保存以避免重復(fù)計(jì)算。

2.2.2 存儲(chǔ)結(jié)構(gòu)

我們可采用一個(gè)綜合案例:圖書信息管理。首先給出:圖書信息表的邏輯結(jié)構(gòu)可認(rèn)為是線性表。其次討論:當(dāng)在圖書信息表中插入或刪除圖書信息時(shí)，選擇什么存儲(chǔ)結(jié)構(gòu)較好?大部分學(xué)生會(huì)認(rèn)為鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)較好，因?yàn)樵诰€性表中插入或刪除元素時(shí)，順序存儲(chǔ)結(jié)構(gòu)會(huì)導(dǎo)致大量元素移動(dòng)，效率較低，而鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)只需修改指針，效率較高。接著討論:當(dāng)在圖書信息表中查詢圖書信息時(shí)，鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)如何?這時(shí)，大部分學(xué)生又會(huì)認(rèn)為還是順序存儲(chǔ)結(jié)構(gòu)較好，因?yàn)榭蓪?duì)元素排序之后采用折半查找提高查找效率，而鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)只能采用順序查找，效率較低。然后總結(jié):當(dāng)線性表頻繁插入或刪除元素時(shí)，鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)較優(yōu);當(dāng)頻繁查找時(shí)，順序存儲(chǔ)結(jié)構(gòu)較優(yōu)，即兩種存儲(chǔ)結(jié)構(gòu)各有優(yōu)劣，需要根據(jù)應(yīng)用，選擇適當(dāng)?shù)拇鎯?chǔ)結(jié)構(gòu)。最后還可進(jìn)一步擴(kuò)展討論:能否為圖書信息表建立索引以提高查找效率、圖書信息能否組織成樹結(jié)構(gòu)、能否采用二叉排序樹提高查找效率等等。

圖1 動(dòng)態(tài)規(guī)劃案例(2階Fibonacci第n項(xiàng)計(jì)算)

2.3 任務(wù)驅(qū)動(dòng)式教學(xué)

根據(jù)核心內(nèi)容的三個(gè)層次，實(shí)驗(yàn)題目也分為基礎(chǔ)、擴(kuò)展、綜合三類。類似教學(xué)案例，擴(kuò)展、綜合類實(shí)驗(yàn)題目也要具有一定的針對(duì)性、系統(tǒng)性。通常，學(xué)生在任務(wù)驅(qū)動(dòng)下，通過課后查資料、討論、實(shí)踐等方式自主完成實(shí)驗(yàn)，然后課上討論遇到的問題、交流獲得的經(jīng)驗(yàn)，進(jìn)行相互學(xué)習(xí)［2］。下面給出線性表的基礎(chǔ)、擴(kuò)展、綜合實(shí)驗(yàn)題目示例:1)基礎(chǔ)實(shí)驗(yàn)題目:假設(shè)每個(gè)學(xué)生的成績(jī)信息包括學(xué)號(hào)(唯一)、語文、數(shù)學(xué)、英語、總分、平均分。構(gòu)造學(xué)生成績(jī)信息表，并實(shí)現(xiàn)學(xué)生成績(jī)信息表的插入、刪除、修改、排序及顯示功能。2)擴(kuò)展實(shí)驗(yàn)題目:構(gòu)造一元多項(xiàng)式P= p0+p1x+p2x2+p3x3+…+pnxn，并實(shí)現(xiàn)一元多項(xiàng)式的相加及顯示功能。3)綜合實(shí)驗(yàn)題目:一個(gè)整型變量所能表示的數(shù)據(jù)范圍是有限的，如32位整型變量的數(shù)據(jù)范圍是－232—(232－1)，如果數(shù)據(jù)超出變量的數(shù)據(jù)范圍，則數(shù)據(jù)不能直接存儲(chǔ)及處理，實(shí)現(xiàn)任意長(zhǎng)整數(shù)的存儲(chǔ)及相加功能。

3 結(jié)語

隨著新教學(xué)計(jì)劃的執(zhí)行，我們?cè)诿嫦蛞荒昙?jí)學(xué)生的數(shù)據(jù)結(jié)構(gòu)實(shí)驗(yàn)課程教學(xué)中遇到了新問題，針對(duì)這些問題，我們調(diào)整了教學(xué)內(nèi)容，探索了合適的教學(xué)方法，并在兩屆4個(gè)班中進(jìn)行了實(shí)踐，取得了良好的教學(xué)效果，增強(qiáng)了學(xué)生自信心，提高了學(xué)習(xí)積極性，發(fā)揮了實(shí)驗(yàn)教學(xué)在能力培養(yǎng)中的作用。學(xué)生不僅學(xué)習(xí)了核心內(nèi)容、邊緣內(nèi)容，大部分學(xué)生還學(xué)會(huì)了通過查資料、討論、實(shí)踐等方式自主學(xué)習(xí)，培養(yǎng)了學(xué)生的學(xué)習(xí)能力。通過教學(xué)案例和實(shí)驗(yàn)任務(wù)，學(xué)生清楚了數(shù)據(jù)結(jié)構(gòu)的重要性，一部分學(xué)生還較系統(tǒng)地掌握了所學(xué)內(nèi)容，初步具有了數(shù)據(jù)抽象能力和程序設(shè)計(jì)能力，培養(yǎng)了學(xué)生利用計(jì)算機(jī)分析和解決應(yīng)用問題的實(shí)踐能力。

［1］賈銀江，賀莉莉，鄭萍.數(shù)據(jù)結(jié)構(gòu)實(shí)驗(yàn)的分層次教學(xué)［J］.計(jì)算機(jī)教育，2014(4):60－62.

［2］趙耀紅，孫宇.數(shù)據(jù)結(jié)構(gòu)實(shí)驗(yàn)教學(xué)的實(shí)踐與探索［J］.長(zhǎng)春大學(xué)學(xué)報(bào):自然科學(xué)版，2012(4):413－415.

［3］丁海燕，袁國武，周小兵，等.高級(jí)語言程序設(shè)計(jì)案例教學(xué)模式的探討［J］.計(jì)算機(jī)教育，2011(8):65－68.