基于python語言版“數據結構與算法”的教學改革與實踐

陳仕軍，陶茂虎，王 前

(湖北文理學院 數學與統計學院，湖北 襄陽 441053)

“數據結構與算法”是信息與計算科學專業的重要基礎課，具有理論抽象、實踐性強、內容多的特點，課程的教與學難度大。對于如何提高該課程的教學質量和提升學生的學習效果，已有一些教學改革的研究和探索。趙蕓和徐興[1]提出基于翻轉課堂和成果教學的新模式，提高學生的學習主動性。萬曉輝[2]提出了基于雨課堂的混合式教學方式，提升教學效果。王青松等[3]提出以真實問題為導向的教學模式。王曙燕等[4]提出基于“賦能教育”的混合教學模式設計方法，采用線上與線下相結合的教學過程。熊回香和葉佳鑫[5]將信息管理類專業知識與課程教學相結合，對課程教學體系做了改革實踐。李禾和柳成行[6]以“少教多學”為理念，強調學生在學習中的主體性作用，進行了全面的教學改革。劉俊杰和胡忠望[7]也提出了線上線下相結合的教學模式，來改善教學效果。任永強等[8]介紹了基于超星學習通移動教學的課程教學體系構建。陳黎黎和國紅軍[9]提出了基于OBE理念的教學改革實踐，取得了較好效果。牛犇等[10]挖掘思政教育資源，融入到課程教學，實現課程的價值引領。廖國富[11]從“教”與“學”兩個角度分析了當前數據結構教學中的問題，還提出了問題導入法、演示法等一些有效教學方法。舒清錄和廖明梅[12]強調了以培養“計算思維”為核心的課程教學改革。這些教學研究從不同層面進行了探索研究，相關經驗和成果值得借鑒，但由于針對的學生群體不同，學生群體的基礎和目標不盡相同，而且不同學校采用的程序設計語言也有差別，因此難以有通用的最有效方法。目前，采用最多的程序設計基礎語言有C、C++、Java。基于python語言版“數據結構與算法”的課程教學改革與研究，相對比較少。

近年來，省屬地方高校辦學思路逐漸轉變為培養應用型人才，隨之而來的課程改革也傾向于開設更多與就業市場關系更緊密的應用性課程。然而，課時總數限制使得“數據結構與算法”等理論基礎課的教學課時不斷被壓縮[11]，教師對于教學成效的壓力越來越大。以筆者所在學校信息與計算科學專業為例，以前的“數據結構與算法”課程分為2門課開設，其中“數據結構”為72學時，“算法設計與分析”為54課時，總共126課時。專業課程改革后，2門課合并為“數據結構與算法”，縮短到90個課時。2019年人才培養方案新修訂后，進一步壓縮課時，調整為80個課時。同時，隨著本專業辦學越來越側重于數據分析、人工智能等方向，信息與計算科學專業將python作為本專業的基礎程序語言，“數據結構與算法”也轉變為采用python版的教材。很多學生對python語言編程掌握不熟練的條件下，就進入“數據結構與算法”的課程學習，如何使絕大多數學生理解并掌握好這門課，教師面臨很大的教學壓力。為了在總學時有限的條件下，引導學生熟練掌握“數據結構與算法”課程的核心內容，筆者經過近四年的教學實踐，探索出一些可行而有效的教學方法。主要有以下幾個方面：第一，將“數據存儲、操作以及時間復雜度”的核心思想和內容放在中心位置，并將其貫穿于各章節的教學始終；第二，采取“從易到難”的漸進式教學方式，基于重要性和學生的易接受度來選取適合的教學內容和材料；第三，教學過程中，采用“圖形化教學、黑板繪圖展示”的教學方式，要求學生“動手畫圖”進行學習，深化對存儲和操作的理解；第四，增加實踐性教學課時，采用“易于理解和實現的示例”作為實驗內容，讓學生能真正熟練掌握后，再逐步推廣到更加復雜的數據結構與算法示例。

1 強化程序設計基礎和數據結構的核心思想

1.1 強化python程序設計基礎

首先，重點補充python程序設計的基礎知識。引導學生扎實掌握python內置的常用數據結構，如列表list、字符串str、元組tuple的應用。同時，強化學生熟練應用python內置class編程的能力。class適合于描述抽象的數據結構，其中屬性對應數據結構的數據及其存儲定義，方法對應數據結構中的增加、刪除、查找數據等操作。

1.2 將數據結構的核心思想和內容貫穿于教學始終

學習“數據結構與算法”的目標是更高效地存儲和組織數據，特別是處理數據的增、刪、查、排序等各種操作功能，從而能高效的解決實際問題。如圖1所示，數據及數據關系的存儲方式(兩種存儲方式)、數據操作的算法時間復雜度，是該課程的核心思想和內容，將其貫穿于教學始終。

圖1 貫穿課程的核心思想和內容

為了讓學生深刻掌握該思想和內容，教學中需要強化如下兩點。

1)強化對python內置list數據結構的理解，是延伸到其他順序存儲數據類型的基礎。python內置多種抽象的數據類型，尤其是屬于一種順序線性表的list，為構造其他復雜數據類型提供了便利。因此，讓學生掌握對list的各種操作函數是后續數據結構中應用順序數據存儲的基礎。同時，為了讓學生理解算法時間復雜度的概念，以list的各種操作為例說明算法復雜度的計算方法，進而掌握for、while等循環程序結構(包括嵌套結構)的算法復雜度。

2)強化對節點和鏈表概念的理解，它們是后續延伸到其他鏈式數據結構的基礎。除了順序存放數據采用list實現外，鏈式存儲是另一種關鍵的數據存儲方式。鏈式存儲中，單個數據均存儲于節點中，各數據之間的前后或父子等關系，通過節點中的“鏈接”屬性來表達。因此，以單鏈表為例，引導學生掌握節點和鏈式存儲的概念，然后拓展到雙鏈表、循環鏈表。對于單鏈表的數據結構，特別強調頭節點的設置與作用。要求學生在學習和實踐中，多思考從各種操作的算法時間復雜度，不斷理解和掌握順序線性表和鏈表的本質、優缺點和適用場景。

2 精簡教學內容，按難度漸進式教學，強化知識模塊的關聯性

2.1 精簡教學內容，按難度漸進式教學

從以往的教學實踐經驗中發現，學生不必學習太多內容，但務必要能扎實掌握，以便增強自信心，提高學習興趣。學生如果能真正掌握幾種相對簡單的數據結構與算法，則不難推廣和學習更復雜的數據結構與算法。同時，教學選材要兼顧知識點的漸進深入和上機實踐的難度。筆者通過近四年的教學與實踐，考慮從易到難，探索出按照如下的教學內容模塊順序進行，基本能達到較好的教學效果。

在圖2中，單向實心箭頭表示講授知識模塊的順序，而帶虛線的反向箭頭表示與前面所學知識點相關聯，這樣使學生逐漸形成更加系統化的數據結構知識體系。例如，對二叉樹進行深度搜索和廣度搜索時，適合于應用前面的棧和隊列解決問題，從而進一步深化對棧和隊列的理解與應用。在講授平衡二叉搜索樹時，加深對前面搜索和排序算法的理解，通過算法分析與比較，能進一步加深對算法復雜度的認識。同時也體會到平衡二叉樹與前面的list和鏈表的本質差別。

圖2 漸進式教學內容分步圖

2.2 強化知識模塊的漸進性和關聯性

1)棧和隊列的概念與實踐。棧和隊列的概念相對比較簡單，但仍有部分學生在學習棧和隊列時，不能理解棧和隊列的增加、刪除數據等操作過程。為此，需要強調棧屬于“后進先出”的功能性數據結構，并采用一些簡單的示例說明其適用場景。例如，將十進制數轉化為二進制數，采用除以2取余數法，將所得余數進行倒置，則得到二進制數。利用棧的“后進先出”原理，這一過程容易理解和實現，也體現了棧的特點；再以約瑟夫環問題為例，說明利用隊列的“先進先出”性質解決此類問題的便捷性。后期在學習二叉樹和圖的節點遍歷搜索時，強化學生對于棧和隊列應用場景的理解。

2)遞歸與二叉樹。二叉樹屬于非線性結構，其數據關系和相關操作比線性結構更復雜，所需的基礎知識和擴展內容也更多，包括遞歸、深度遍歷、廣度遍歷、棧和隊列的應用、各種特定的二叉樹結構及應用等。同時，這些知識內容的編程實現過程也要復雜很多。考慮到課時限制和大部分學生的知識接受能力有限，講授時必須有所取舍。因此，在前期學習時，重點引導學習遞歸、二叉樹的遍歷、完全二叉樹、堆的概念及操作，后期學有余力時再延伸到平衡二叉樹。

首先，以簡易小問題為例，例如階乘、單鏈表求長度、漢諾塔盤片移動問題等，引導學生掌握遞歸的基本思想和程序實現方法。然后在此基礎上，講解二叉樹的數據結構和常用深度遍歷方法，強化遞歸應用的思維訓練。對于完全二叉樹，通過分析節點數和層數的關系，說明其線性存儲的優點。再由完全二叉樹推廣到堆的概念，引導學生掌握堆實現優先隊列、操作與實現方法，加深對二叉樹應用的理解。對于平衡二叉樹，不僅操作更加復雜，而且會用到搜索和排序的知識，因此先只講授基本概念，后期學有余力時再加深理解。

3)簡單搜索和排序算法。搜索(或查找、遍歷)是解決很多問題的基礎操作。對于線性的數據結構進行順序搜索，直觀易理解，學生都能輕松掌握。對于有序線性結構的二分搜索，采用以方程求根的二分搜索算法舉例，說明其相似性。同時，要讓學生理解查找和搜索的區別與聯系，并了解其方法具有多樣性。

排序算法比較多，由于學時有限，有必要做精簡，要求學生學會2種排序算法：冒泡排序與快速排序。冒泡排序的原理簡單直觀，是學習排序算法的基礎，也是和其他排序進行復雜度對比時常用的算法。由于前期的“python語言程序設計”課程中會介紹冒泡排序，因此難度相對較低，只要再簡單復習，學生能夠熟練掌握。再從算法復雜度角度分析，說明冒泡排序是一種效率不高的排序算法(O(n*n))。而快速排序具有高效率的特點，時間復雜度低(O(n*logn))，但其算法實現過程稍顯復雜。講解時多分配學時，讓學生真正理解，并能編程實現。在此基礎上，其他排序算法(插入排序、希爾排序、歸并排序)，均可以通過自學理解。

4)以二叉樹為例，掌握深度遍歷和廣度(或寬度)遍歷的思想與方法，加深對遞歸、棧以及隊列的理解與應用。引導學生從線性結構的遍歷，延伸到非線性結構的遍歷。二叉樹和圖作為兩種典型的非線性結構，遍歷其節點時，采用深度遍歷或者廣度遍歷算法。利用畫圖方式，逐步展示兩種算法的區別。在程序實現時，考慮兩種編程方法，即遞歸和非遞歸。采用遞歸方式，更加直觀，但需要對遞歸有較深的認識。采用非遞歸方式，則需要對棧和隊列有熟練理解。對二叉樹的深度遍歷和廣度遍歷的練習，能讓學生加深對遞歸、棧和隊列等內容的理解。

5)學會圖的基本存儲與操作、圖節點的遍歷與搜索、最小生成樹和最短路問題。圖數據結構是相對較復雜的數據結構，但又是解決很多與網絡相關復雜問題的基礎。首先，要掌握圖的存儲和操作，然后從二叉樹的遍歷方法推廣到圖的遍歷方法，使得學生理解圖的深度搜索和廣度搜索算法的思想和方法，這是對圖操作的基礎。圖的應用內容非常多，根據實際情況，讓學生掌握最小生成樹和最短路問題的算法及其代碼實現。

6)平衡二叉樹和哈希表。這部分數據結構相對更加抽象、操作更復雜，不管理論還是實踐都是難度最大的部分。因此，在學生前期基礎掌握比較扎實的情況下，再進行講解，學生更容易接受。在學習平衡二叉樹(重點是二叉查找樹)時，對比前面已學的查找算法，從時間復雜度體會二叉查找樹的高效率。學習哈希表時，進一步體會其查找效率的優勢，并掌握其適用場景。其他內容，如哈夫曼樹、字符串匹配算法等，根據學生掌握情況和課時剩余情況，進行引導學習即可。

3 教學方法與教學過程的改進

3.1 圖形化教學、黑板繪圖展示，要求學生草稿紙上繪圖、理解

傳統采用PPT教學的方法，課程內容進度較快，不能詳細演示，學生對內容掌握不牢固。教師采用黑板上“邊講解、邊繪圖”的教學方法，會具有更好的效果。“好記性趕不上爛筆頭”，要求學生帶草稿紙，繪圖體會數據結構的數據存儲方式和操作過程。在對數據結構的理論掌握的基礎上，再進行實驗實踐。事實證明，這種“腦子想、紙上畫”的教學學習方法，能讓學生更容易理解和掌握。

3.2 教學過程與教學環節設計改進

1)以問題為導向，以易理解和操作的示例為主線，增加實驗課時，強調學生的實踐能力。傳統的實驗課程示例，一般規模較大，操作復雜，程序代碼長，一次實驗難以完成，使得學生體會不到數據結構編程的樂趣和成就感。為此，基于近些年的實踐教學經驗，構建出一些學生易理解、易操作的教學實踐示例。例如，以學生信息中的單科成績排序為例，說明python的list和sort函數的使用方法；為掌握遞歸的思路和方法，以n階乘、漢諾塔以及二叉樹的遍歷的算法為例，體會遞歸的不同適用場景；以十進制轉二進制為例，讓學生體會棧的操作與應用；進一步拓展到將棧應用于迷宮問題。

2)應用多種數據結構進行對比，讓學生深刻體會到操作時間復雜度的差異。為此，也構造出一些易于理解和實現的示例。例如，利用自然數1、2、…、n求和，體會程序循環累加和數學公式計算之間的計算效率差別，進而說明計算時間復雜度的重要性；以約瑟夫問題為例，采用list、循環鏈表、隊列，來從時間復雜度角度體會不同數據結構的優缺點；以優先隊列為例，采用list實現和采用堆實現進行對比，體會堆具有時間復雜度低的優點；利用冒泡排序和快速排序進行對比，體會不同排序算法之間的效率差異；以數據的插入、刪除和查找為例，分別比較list和二叉查找樹之間的效率差異。

4 近四年來的教學成效

通過近四年的教學改革與實踐，學生學習數據結構與算法課程的積極性有明顯提升，對基礎數據結構與算法的理解和掌握程度，也越來越深。在試卷難度不變的條件下，最近四年的期末考試成績如表1所示。

表1 近四年的“數據結構與算法”期末考試成績

從近四年的期末考試成績看，考試卷面平均分、總成績平均分、優秀占比，總體上均有一定幅度的穩步提升。教學效果，有了明顯的改善。同時，總成績的不及格比例也呈下降趨勢。在后期，在教學實踐改革中，要進一步精選知識點和示例，引入更多圖形化展示方法，更加生動展示課程特點，提升教學效果。

5 結語

通過近四年的“數據結構與算法”教學實踐經驗，提出了一些課程內容與方法的改進措施。主要是精簡教學內容，采用由易到難漸進式教學、圖形化教學展示，以容易理解和實現的示例作為實驗重點，不斷提高學生的學習興趣。從近幾屆學生的反饋和期末成績來看，教學改革與實踐具有較好的成效。近些年，互聯網發展迅猛，網絡課堂也是線下教學的重要補充。對于如何合理利用好網絡資源和網絡教學，做好“數據結構與算法”課程的線上和線下相結合，還需要不斷探索和實踐，以進一步提高教學質量。