鹿旸++刁明光

摘要：分析了“數(shù)據(jù)結(jié)構(gòu)”課程的特點(diǎn)、經(jīng)典算法的教學(xué)和實(shí)踐現(xiàn)狀，針對存在的問題，以改進(jìn)經(jīng)典算法講解為基礎(chǔ)，討論了如何培養(yǎng)學(xué)生的編程思維，并進(jìn)一步探討了實(shí)踐教學(xué)的組織和設(shè)計(jì)。

關(guān)鍵詞：數(shù)據(jù)結(jié)構(gòu)；經(jīng)典算法；編程思維

中圖分類號：G642.0 文獻(xiàn)標(biāo)志碼：A 文章編號：1674-9324（2017）37-0136-02

“數(shù)據(jù)結(jié)構(gòu)”是計(jì)算機(jī)專業(yè)的一門核心課程。該課程不僅是程序設(shè)計(jì)的基礎(chǔ)，而且是設(shè)計(jì)和實(shí)現(xiàn)編譯原理、操作系統(tǒng)、數(shù)據(jù)庫系統(tǒng)等系統(tǒng)程序和大型應(yīng)用程序的重要基礎(chǔ)[1]。數(shù)據(jù)結(jié)構(gòu)教材以數(shù)據(jù)的邏輯結(jié)構(gòu)為主線，依次介紹線性結(jié)構(gòu)和非線性結(jié)構(gòu)。在各種數(shù)據(jù)結(jié)構(gòu)介紹時再討論其存儲結(jié)構(gòu)以及相關(guān)算法，最后介紹查找和排序算法，知識框架體系完善清晰[2]。教學(xué)的突出難點(diǎn)是知識的抽象性和動態(tài)性，尤其涉及大量抽象數(shù)據(jù)類型及經(jīng)典算法。本文是作者九年來的授課小結(jié)，從教學(xué)方法和經(jīng)典算法的講解方法入手，進(jìn)行了教學(xué)和實(shí)踐的探討。

一、傳統(tǒng)教學(xué)方法存在的問題

1.缺乏良好的解題習(xí)慣。課程的教學(xué)要求之一是訓(xùn)練學(xué)生進(jìn)行復(fù)雜程序設(shè)計(jì)的技能和培養(yǎng)良好程序設(shè)計(jì)的習(xí)慣，其重要程度決不亞于知識傳授。在學(xué)習(xí)數(shù)據(jù)結(jié)構(gòu)之前，學(xué)生學(xué)習(xí)了C和C++兩門編程語言，但沒有進(jìn)行系統(tǒng)的訓(xùn)練，也沒有形成規(guī)范的編程習(xí)慣。很多同學(xué)拿到題目直接編寫代碼，在寫代碼的過程中邊寫邊想，然后反復(fù)修改代碼，造成程序結(jié)構(gòu)混亂、可讀性差、調(diào)試?yán)щy。尤其在解決大規(guī)模輸入的復(fù)雜問題時，更容易造成程序癱瘓。

2.課堂算法講解不透徹。在課程中，各種數(shù)據(jù)結(jié)構(gòu)都有相關(guān)算法，此外還有查找和排序算法。因此，算法部分占了課程相當(dāng)大的比例。這其中很多經(jīng)典算法都極具代表性，使用了大量的編程技巧，這些是算法的精華部分。如果授課教師只對書中的算法進(jìn)行流程講解，不揭示編程技巧的話，那么學(xué)生也只能死記硬背，學(xué)習(xí)不到算法的精華，對提高編程能力毫無幫助。而且死記硬背的方式也容易讓學(xué)生喪失學(xué)習(xí)的興趣。

3.缺少綜合性實(shí)驗(yàn)題目。通常練習(xí)冊中會按照章節(jié)安排實(shí)驗(yàn)題目，題目內(nèi)容針對本章知識點(diǎn)，針對性強(qiáng)，而且和書上的例題有相似之處。因此，學(xué)生在做這些分章節(jié)的小程序時，過度依賴課本中的范例，甚至不假思索，照搬照抄，編程思維得不到很好的鍛煉，而且也體會不到處理大規(guī)模輸入的復(fù)雜問題時，數(shù)據(jù)結(jié)構(gòu)體現(xiàn)出來的優(yōu)勢。

二、教學(xué)方法探索

1.培養(yǎng)良好的分析問題的習(xí)慣。如圖1所示，遇到問題時，學(xué)生習(xí)慣性地直接編碼，并在代碼上不斷修改，沒有良好的編程習(xí)慣，往往解決問題事倍功半。在授課過程中，對每一個問題，教師要嚴(yán)格按照“抽象數(shù)據(jù)對象→分析邏輯關(guān)系→選取物理結(jié)構(gòu)→分析解題思路→畫流程圖→分析時間復(fù)雜度→多種解法比較→確定解題方案→編寫代碼（可省略）”[3]的思路進(jìn)行分析和講解，最終完成算法。其中，在“選取物理結(jié)構(gòu)”環(huán)節(jié)，要充分分析操作特征，設(shè)計(jì)合理的存儲結(jié)構(gòu)服務(wù)于后續(xù)算法。在“分析解題思路”和“畫流程圖”環(huán)節(jié)，首先提煉解題步驟，形成流程圖，然后使用編程技巧優(yōu)化流程，重點(diǎn)優(yōu)化循環(huán)結(jié)構(gòu)，并逐步修改流程圖，最終確定。在分析過程中，應(yīng)啟發(fā)學(xué)生的解題思路，鼓勵大家多角度分析問題，提出不同的解決方案，并應(yīng)一并列出，逐一分析解題步驟和時間復(fù)雜度，最后做一比較。這樣，將編程思維從課堂的講授延伸至實(shí)踐環(huán)節(jié)的動手操作，鞏固了學(xué)習(xí)效果。這樣學(xué)生不僅對算法印象深刻，更能培養(yǎng)良好的思維習(xí)慣，從而真正提高解決問題的能力。

2.強(qiáng)調(diào)經(jīng)典算法中的編程技巧。書中選用算法多為經(jīng)典算法，其中不乏經(jīng)過多次優(yōu)化、多次驗(yàn)證的高效率算法。這些算法在優(yōu)化過程中使用了很多編程技巧。教師在授課過程中，應(yīng)重點(diǎn)介紹算法的優(yōu)化方法，并引導(dǎo)學(xué)生對程序進(jìn)行自查和優(yōu)化，養(yǎng)成良好的習(xí)慣[4]。

以冒泡排序經(jīng)典算法為例，首先講解算法的思想“依次比較兩兩相鄰記錄，若反序，則交換位置，直至有序”。并且舉例動態(tài)演示。然后讓同學(xué)嘗試將操作流程轉(zhuǎn)換成算法。要求同學(xué)設(shè)計(jì)出流程圖，如果課堂上有條件可以編程序?qū)崿F(xiàn)。然后選取同學(xué)的例子做展示，有如圖2所示算法。

本算法中有兩個循環(huán)結(jié)構(gòu)，應(yīng)逐個解析。第一個循環(huán)結(jié)構(gòu)表示算法經(jīng)過n-1趟完成排序，通過舉反例，說明根據(jù)輸入數(shù)列不同，排序趟數(shù)也不同，最少一趟就能完成排序，顯然第一個循環(huán)存在冗余。然后引導(dǎo)學(xué)生一起改進(jìn)算法，此循環(huán)要解決的是“結(jié)束狀態(tài)”的判定問題，引出編程技巧“狀態(tài)判定問題，通過操作特征找條件”。根據(jù)算法的“比較”和“交換”操作特征，分析得出“結(jié)束條件”為：經(jīng)過一趟排序，如果沒有發(fā)生交換操作，就說明已經(jīng)有序，結(jié)束算法。經(jīng)改進(jìn)后的第一個循環(huán)如圖3所示。同樣，第二個循環(huán)結(jié)構(gòu)也存在冗余。通過分析，引出編程技巧“范圍劃定問題，通過操作特征找邊界”。經(jīng)編程技巧優(yōu)化后的程序如圖4所示。最后，比較改進(jìn)前和改進(jìn)后算法的時間復(fù)雜度，然后給定一個輸入數(shù)列，比較兩個算法的實(shí)際運(yùn)行時間。結(jié)果顯示，雖然沒有改變算法的時間復(fù)雜度，但通過剔除冗余循環(huán)，縮減了算法的運(yùn)行時間，提高了執(zhí)行效率。通過對學(xué)生程序的優(yōu)化和實(shí)驗(yàn)測試，學(xué)生能夠直觀地認(rèn)識到使用編程技巧的好處，且印象深刻。

類似的例子還有在順序查找算法中，通過使用監(jiān)視哨，簡化while循環(huán)判定條件的編程技巧；線性表GetElem算法中，合并兩個并列循環(huán)的編程技巧等等。配合編程技巧的講解，在實(shí)踐環(huán)節(jié)設(shè)置題目，進(jìn)一步強(qiáng)化這些技巧的使用，使學(xué)生熟練掌握。學(xué)生學(xué)習(xí)算法的目的是要學(xué)會其中的編程技巧，活學(xué)活用，這樣才能寫出高效、優(yōu)質(zhì)的算法。

3.設(shè)置綜合型題目。教師應(yīng)適當(dāng)設(shè)置包含多個知識點(diǎn)且有多種解法的題目，鍛煉學(xué)生綜合運(yùn)用知識解決問題的能力，并給學(xué)生留出發(fā)揮創(chuàng)造力的空間。例如“走迷宮問題”，對已知的二維迷宮求通路。學(xué)生可以選擇用不同的數(shù)據(jù)結(jié)構(gòu)表示迷宮作為程序輸入，然后選擇用深度優(yōu)先或者廣度優(yōu)先遍歷的算法來得到路徑，最后用圖形界面將迷宮顯示出來。再例如“最少換乘次數(shù)”問題，已知地點(diǎn)和公交線路，求某兩地點(diǎn)間的最少換乘次數(shù)。學(xué)生需要在問題中抽象出適當(dāng)?shù)膶ο蠛完P(guān)系，將地點(diǎn)和線路表示在圖形結(jié)構(gòu)中，然后可以選擇圖的廣度優(yōu)先遍歷方法，或者改進(jìn)求單源最短路徑的Dijkstra算法，比較它們，選擇更優(yōu)算法。

在實(shí)踐環(huán)節(jié)，可以將學(xué)生分為若干個團(tuán)隊(duì)，團(tuán)隊(duì)成員要按照規(guī)范的解題思路提出個人的見解，而后互相比較和討論，最終擇優(yōu)給出完整的解題步驟和算法。這樣，學(xué)生在充分的討論過程中，會比較存儲結(jié)構(gòu)的差異和不同算法的性能，進(jìn)一步鞏固了書本知識，鞏固編程技巧，同時鍛煉了團(tuán)隊(duì)合作能力。

“數(shù)據(jù)結(jié)構(gòu)”課程在計(jì)算機(jī)學(xué)科中的地位十分重要，教師在教學(xué)過程中應(yīng)著力培養(yǎng)學(xué)生分析和解決問題的能力。這需要教師在授課和實(shí)踐環(huán)節(jié)加強(qiáng)編程思維的訓(xùn)練，并不斷督促，完善自己的教學(xué)方法，以達(dá)到更優(yōu)的教學(xué)質(zhì)量。

參考文獻(xiàn)：

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

[2]張銘，趙海燕，王騰蛟.北京大學(xué)“數(shù)據(jù)結(jié)構(gòu)與算法”教學(xué)設(shè)計(jì)[J].計(jì)算機(jī)教育，2008，（20）：5-11.

[3]孟凡榮，張斌，楊雷.計(jì)算思維在數(shù)據(jù)結(jié)構(gòu)中的實(shí)踐探索[J].教育教學(xué)論壇，2015，（10）：117-120.

[4]張乃孝.數(shù)據(jù)結(jié)構(gòu)體系分析[J].計(jì)算機(jī)研究與發(fā)展，1988，（05）：36-40.endprint