數據結構與算法課程面向實踐的教學方法研究

梁 冰，馮 林，杜 猛，李 航

（大連理工大學 創新創業學院，遼寧 大連 116024）

0 引言

數據結構與算法作為計算機專業的核心課程，是計算機專業人才培養的基石，從事計算機學科的信息處理、人工智能、數據庫、操作系統、圖形圖像等方面的研究，都離不開數據結構和算法的應用[1]。隨著計算機處理的數據量越來越大，對處理數據的程序效率也提出了更高的需求，計算機專業人才應具有扎實的編碼能力和算法知識，并通過程序實現能夠讓計算機高效、準確地執行人們的想法和構思，這是計算機專業培養的重要目標[2-4]。

數據結構與算法作為一門實踐性很強的專業技術基礎課程，是培養學生計算思維、算法設計與實現能力的重要課程，包括C語言程序設計、數據結構、算法設計等。采用筆試的傳統方式考核學生的知識掌握能力，考試能得高分的學生卻不能編寫一條簡單的程序，這完全背離計算機專業對人才培養的目標，授課教師在理論與實踐教學的探索中不斷改革創新，培養學生理論素養與實踐能力[5-7]。

熟練掌握計算機的經典算法是學生今后從事各方面工作和研究的專業基礎[8-10]。IT公司在招聘時，無不把考察學生的算法知識作為重點，尤其在人工智能和大數據的時代，算法在提高程序效率方面起著舉足輕重的作用。計算機的經典算法體現著科學家的智慧和思維，通過對經典算法的學習可以培養學生的思維能力和解決問題的能力。更重要的是，對于算法的學習，不僅僅要理解算法的理論，更要能夠將算法實現并應用于解決實際問題當中，這才算達到了熟練掌握算法的培養目標[11-12]。

1 理論教學內容與實踐教學緊密相連

1.1 按專題講授經典算法

講授經典算法時按專題劃分，可以較為全面地講授各類別的經典算法，擴展學生的知識面，培養學生計算機思維，為今后學習與研究打下堅實基礎。

數據結構專題，包括棧、隊列、二叉樹、二叉搜索樹、堆、優先隊列、圖、并查集、線段樹、樹狀數組。

排序算法專題，包括冒泡排序選擇排序、插入排序、歸并排序、快速排序、計數排序、基數排序。

算法設計類型專題，包括枚舉、遞推、遞歸、貪心、分治、模擬、哈希、二分。

搜索算法專題，包括寬度優先搜索、深度優先搜索、剪枝（A*、IDA*）算法。

動態規劃（Dynamic Programming，DP）專題，包括背包DP、狀態壓縮DP、樹狀DP、概率DP。

圖論專題，包括圖的最短路算法（Dijkstra、SPFA、Floyd_warshall）、最小生成樹算法（Prime、Kruskal）、圖的最大流算法（Ford-Fulkerson、Dinic）、二分圖匹配算法、最小費用流算法、圖的強連通分量分解算法。

字符串專題，包括字符串匹配算法、后綴數組、AC自動機、后綴自動機。

數論專題，包括最大公約數、擴展歐幾里得算法、線性方程與同余方程、乘法逆元、中國剩余定理、質數篩法、歐拉函數、高斯消元。

計算幾何專題，包括點線形的數據結構表示、線段相交問題、多邊形求面積、點與多邊形的位置關系、圓、凸包、半平面交。

組合數學專題，包括排列組合母函數、整數拆分、Stirling數和Catalan、容斥原理和莫比烏斯反演、群論和polya定理。

1.2 講授例題來源于在線評測系統中經典題目

課上每個算法所講解的例題來自在線評測系統（Online Judge），在線評測系統上的題目一般會綜合多個算法知識，從中精選例題進行講解，有助于學生溫故知新、融會貫通。通過可執行C++、Java等代碼對算法實現進行講解，經過課上的學習，課后學生也有興趣通過在線評測系統實現課上的例題，并在系統上提交。在線評測系統所返回結果可以幫助學生更深入地理解算法的思想，并達到熟練掌握算法的學習目標。

1.3 講解算法使用C++、Java等語言描述的可執行代碼

講解算法實現時，使用編譯通過的可執行代碼，可以培養學生讀寫代碼的能力。確保學生能夠通過計算機語言將算法原理描述出來，并能夠順利通過編譯，使計算機正確的執行。教師應強調只有通過計算機語言正確實現了經典算法的思想，才算真正地掌握算法，完成了算法學習的目標。

1.4 注重講解算法復雜度的分析以及算法的優化方法

圖論中很多經典算法的講授需要詳細講解復雜度，比如同樣是圖的最短路算法，Bellman-Ford算法的復雜度是O(|V||E|)，而Dijkstra算法的復雜度是O(|E|log|V|)，后者更高效地計算最短路的長度；圖中的網絡流算法，Ford-Fulkerson算法的復雜度為O(F|E|)，而Dinic算法復雜度為O(|E||V|2)，后者在實際應用中速度非?？?。如果解決問題的算法不是最優的，那么在線評測系統是不會通過的，系統會返回Time Limit Exceeded（TLE）：程序運行時間超出了題目的規定。對于解決問題的算法只有滿足時間復雜度和空間復雜度的情況，系統才會返回通過：“Accepted（AC）：在規定的時間內不超出內存限制的條件下得出滿足題目要求的結果”。

2 面向實踐的教學方法

2.1 講授算法時以現實中遇到的實際問題為切入點

教師鼓勵學生在課后閱讀相關的算法在實際生產和生活中應用的文獻資料，學生能夠更好地理解算法的功能和意義，加深理解算法，提升學生學習算法的熱情。如，將快速冪求模算法運用于著名的RSA公鑰加密方法中，鼓勵學生課后查找RSA公鑰加密方法的相關資料進行學習。最大流最小割算法應用于優化圖像分割方法，像Photoshop、美圖秀秀等基于交互式分割得到目標的功能基本源于圖像分割。字符串匹配算法Boyer-Moore用于文本編輯器的“查找”功能、論文查重等。

2.2 引導學生主動學習與自學

計算機領域需要學習的經典算法非常多，如果不能引導學生自己深入的學習，教師在有限的課堂時間內是無法將所有的經典算法傳授給學生的，并且單一的講授效果并不好，不能調動學生積極的思考。因此，提綱挈領地講授經典算法的思想和精髓，調動起學生的興趣，通過主動學習與實現更多的相關算法是有限課堂時間內的首要任務。如棧和隊列的應用和實現方式上有很多相似的原理，可以講授棧的實現方式，而隊列的實現方式留給學生自學，一是提升學生學習的主動性，積極思考；二是避免相似內容講解時學生精神不集中。

2.3 采用引導式及互動式教學

在授課時，教師準備好可以和學生積極互動的知識點，調動學生積極思考，調動起學生學習的興趣。一些知識點的講解也很合適與學生互動，如在講解算法的時間復雜度時，教師以快速冪運算算法為例，對于逐次相乘的算法，需要循環n次，才能獲得結果，因此算法復雜度是O(n)，而將n次冪用二進制表示之后，算法又需要循環多少次便可以得到計算結果？有了這樣的啟發，可以激發學生思考、師生進行互動。

2.4 答疑與探討

教師將每一個經典算法介紹之后，會給學生一個提問和探討的機會：學生有什么知識點沒有聽明白，這樣可以了解學生理解問題困難的點，下次授課可以詳細介紹；學生也會提出教師沒有深入講授的知識點，完善教學講授的要點，實現教學相長。

3 基于在線評測系統的實驗平臺建設與實驗教學開展

3.1 在線評測系統的課程實驗平臺建設的必要性

建設在線評測系統（Online Judge，OJ）實驗平臺對提升程序設計類課程的實驗效果是非常有效的。在沒有在線評測系統之前，對數據結構與算法實驗課程中學生實驗結果的可行性考核是不強的，編譯系統對程序的考察只是編譯結果是否正確，對于算法的時間復雜度和空間復雜度的考核沒有一個嚴格的標準，教師對班級每位學生程序的驗證所耗費的時間是不可估量的。

3.2 在線評測系統的特點和性能

在線評測系統是ACM-ICPC國際大學生程序設計競賽的比賽系統，OJ系統的應用使比賽結果公平、公正、公開，不受人為因素影響，這項賽事吸引了全球大學生的積極參與，也使得ACM國際大學生程序設計競賽成為全球最具影響力的大學生程序設計競賽[13-14]。在線評測系統能夠自動評判代碼的正確性，并將評判結果返回參賽選手。自動評測系統只反饋以下結果。

Accepted（AC），在規定的時間內不超出內存限制的條件下得出滿足題目要求的結果。

Presentation Error（PE），在規定的時間內不超出內存限制的條件下得出結果，但是同正確的結果相比結果的格式存在問題。

Time Limit Exceeded（TLE），程序運行時間超出了題目的規定。

Memory Limit Exceeded（MLE），程序在編譯或者運行期間向操作系統申請的內存超出了題目的規定。

Wrong Answer（WA），在規定的時間內不超出內存限制的條件下得出結果，但是同正確的結果相比存在較大差別。

Runtime Error（RE），程序運行期間訪問非法內存。

Output Limit Exceeded（OLE），程序輸出結果文件過大，超出評測系統限制。

Compile Error（CE），程序編輯錯誤。

評測系統不僅能夠評測程序的正確性，更重要的是可以對程序的時間復雜度和空間復雜度進行評測，如果程序雖然能夠通過編譯，但時間復雜度或空間復雜度高于題目要求，是不能通過的。正是評測系統這一功能的設定使學生對算法的復雜度有了前所未有的重視，加強了學生對算法的理解和學習的深度。

3.3 基于在線評測系統的實驗課程開展方法

按照課堂教學中講授的每個算法，為學生在OJ中設定相應的經典題目作為實驗內容。教師可以根據OJ對學生提交題目的判定結果總結出學生在代碼編寫中常常出現的錯誤，從而重點講解，及時糾正學生常犯的錯誤。

評測系統對程序及時詳細的反饋，對學生的學習是一種積極的鼓勵與促進，更是杜絕了學生在學習算法時的淺嘗輒止，因為一知半解學習所得到的結果不會是最優的。在線評測系統返回給學生不同類型的判定結果，培養了學生對算法精益求精、深入研究、理解透徹的學習習慣，這對學生是受益終生的。

4 課程考核方式改革

在總成績中加大編碼和算法實現成績所占的比例，引導學生重視編碼能力的鍛煉：①將實驗課程的成績和課后OJ系統中所留的作業成績納入到期末總成績；②期中考試采取線上OJ題目考核的方式，考核學生的實踐編碼能力；③期末考試采用筆試的方式。

課程總成績各項所占比例：①實驗成績15%；②作業 15%；③期中線上考試1成績20%；期中線上考試2成績20%；④期末成績，期末采用筆試的方式，占30%。其中，實驗、作業、期中競賽在OJ上完成。

從課程總成績中實踐考核內容所占的比例可以看出，計算機專業的學生如果不重視本課程的實踐特性，不能一點一滴的提升自己的編程能力，課程是很難獲得高分的。課程的最終成績能夠客觀反映學生的編碼能力和程序設計能力，避免出現試卷能夠獲得高分卻無法實現一些簡單算法的現象。學生在學習這門實踐性很強的課程時，單純的筆試考核方式容易造成學生學習方法和學習重點的方向上的錯誤，因此，通過在線評測系統加大客觀評估學生實際編程能力的上機考核方式，使學生在課程學習中，重視上機調試程序和算法的實現與應用。

5 結語

數據結構與算法課程講授了非常重要和實用的計算機算法，能將算法靈活應用的基礎就是不僅能夠掌握算法的思想，更要能夠編碼實現算法。筆者提出的面向實踐的教學方法，引導學生在學習這門課時重視理論與實踐相結合，不僅是學習算法的理論，更重要的是編碼實現算法及算法在解決實際問題中的應用，而且算法在實踐中應用更能加深學生對算法思想的理解，相輔相成。

面向實踐的教學方法經過多年在理論教學和實驗教學的應用，在計算機人才培養上取得了明顯的效果，學生具有編程能力強、算法知識面廣且扎實、專業素質高的特點，因此在保研和就業中具有很強的競爭力。知名高校和企業越來越看重學生的算法能力，考核學生的算法能力是很重要的一項。在目前大數據和人工智能的環境下，沒有算法的程序已不能滿足實際應用的需求了，學生的編程能力和算法實現能力，無時無刻不在科研和研發中發揮著重要的作用。因此，具有編程能力強、算法基礎扎實的計算機專業學生成為名校和名企的搶手人才，大連理工大學的畢業生獲得了來自清華、北大、上海交通大學、美國加州大學等名校的保研資格以及來自谷歌、微軟等知名IT企業的Offer。