基于Python的數據結構課程

裘宗燕

（北京大學數學學院，北京100871）

0 引言

越來越多的高校開設了Python編程課程，國際上已有很多學校將Python作為第一門計算機科學技術課的語言，講授基本編程的思想、概念和技術。這種做法不可避免地帶來一個問題：這門課程怎樣與后續課程銜接，首先是怎樣與數據結構課程銜接。我們使用Python語言講授過幾次計算機基礎課，包括基本編程課和數據結構課，并編寫出版了相關教材[1]，發現用Python講授數據結構課程的現實情況：與原來基于C語言等的課程相比，該課程有哪些優勢，又有哪些需要特別關注和解決的問題。

1 Python與數據結構

數據結構課程大約于20世紀70年代從發達國家的計算機科學系起步，最初使用偽代碼討論和分析，相關教學和教材很大程度上受到文獻[2]的影響。隨著高級語言的廣泛使用，數據結構課程的教學逐漸轉向以高級語言作為討論工具。文獻[3]中提出的觀點被廣泛接受，對數據結構課程的發展產生了很大影響。一時之間，絕大多數數據結構課程都轉向采用Pascal語言。后來，抽象數據類型（ADT）的思想逐漸被數據結構教材和課程所采用。20世紀90年代以后，隨著C語言的使用日益廣泛和Pascal日漸衰落，越來越多的國內外高校改用C語言教授數據結構課程，而后又有其他語言逐漸加入。目前，數據結構課程使用的主要語言包括C、C++、Java等。

隨著越來越多的高校開始使用Python講授第一門程序設計課程，用Python討論數據結構的問題也被提上議事日程。為了深入探討有關情況，我們首先回答幾個經常聽到的問題，網上對于這些問題也有許多討論。

第1個常見的問題：Python的表和字典就是數據結構課程中討論的典型數據結構，學習Python編程之后就已經會用了，還需要學習數據結構課程嗎？我們的回答是，當然需要。一方面，數據結構是計算機科學知識體系中最重要的環節之一，其核心問題是討論數據組織和管理的思想和技術、計算復雜性的概念和分析等，這些都是計算機科學技術領域最重要的基礎知識，而表、字典等只是傳播上述核心知識和技術的媒介，是課程所討論的典型實例，Python的程序設計基礎和相關課程既不能提供上述重要知識和相關技術，又不可能代替數據結構課程；另一方面，要用好Python語言并發揮其作用，必須理解數據結構的一般性知識和Python的特殊情況，編程語言是非常復雜的工具，編程是最復雜的工作，缺乏對所用語言的理解是做不好編程的，數據結構課程則能幫助學生深入理解Python的表、字典等組合類型。因此，基于Python的數據結構課程教學需要兼顧這兩方面的需求。

第2個常見的問題：用Python語言討論數據結構的可行性。依據我們的理解和經驗來判斷，這種做法確實可行。目前，國際上已經出版了許多使用Python語言講授數據結構相關內容的教材，如在亞馬遜網站上可以查到文獻[4-6]，但是國內至今未出版中文翻譯版本。我們已經使用Python講授過幾次數據結構課程，并編寫出版了相關教材[1]。此外，還可以找到國外同行研究這個問題的論文，如文獻[7]，也可以找到國外一些知名高校發布的有關使用Python講授CS2的消息[8]。這些情況都說明，使用Python講授數據結構課程的做法是可行的。當然，不同語言有各自的特點，應用于同一門課程時，也需要考慮其特點，揚長避短。如前所述，這門課程應該是數據結構基礎知識和Python的結合，用Python講授數據結構既有優勢，又有劣勢。

第3個常見的問題：學習數據結構課程對于使用Python開發程序（軟件）有特殊意義嗎，特別是使用Python語言討論的課程？對此，我們的回答是肯定的。因為除了講授計算機科學技術的一般性作用之外，這門課程還對提升學生使用Python工作的能力產生重要影響，主要體現在以下3個方面。

（1）有助于學生理解Python程序的行為，理解怎樣寫好Python程序。

（2）幫助學生在使用Python編程的過程中作出正確的設計選擇，并為這些選擇提供本質性的判斷根據。例如，保存一批數據時，選用標準類型的表或字典，還是自己開發專門結構，并知悉原因；向表中加入元素應該用哪個操作等。

（3）有助于識別程序中的效率陷阱。Python程序中很容易創建各種復雜數據對象，這種便利如果使用不當，很可能嚴重影響程序的效率和可用性。

2 用Python講授數據結構課程的目標、優勢和困難

基于Python的數據結構課程的教學目標應包含以下3方面。

（1）清晰介紹數據結構課程的基本理論內容。這些內容與具體語言無關，包括數據結構和算法的基本概念，相應的理論問題（復雜性等），數據結構的基本構造技術，各種典型數據結構的原理、性質、基本使用和基本實現技術等。

（2）基于Python語言討論數據結構的實現技術，既要體現一般的數據結構技術，又要充分發揮Python的優點，展示有用的設計和Python編程技術，還應說明在Python程序里使用數據結構解決問題時可能遇到的問題、分析和思考的方法、解決問題的方法等。

（3）認真分析Python語言中的各種組合數據結構（作為理論數據結構的具體實現）的想法、具體設計和實現，各方面的實際性質、優缺點、使用時需要注意的問題等。

用Python講授數據結構課程有許多優勢，最重要的優勢來自Python語言設計的很多特征可以在數據結構課程中發揮作用。

（1）Python的面向對象機制可以作為ADT（抽象數據類型）的具體體現，用于實現各種數據結構和支持封裝。類定義中的實例方法可用于實現數據結構操作；繼承用于擴充已定義的部件，實現擴充（或部分修改）的新數據結構等。

（2）Python的生成器函數可用于實現各種容器結構都需要的遍歷操作，使自定義的容器類型可以平滑地納入Python語言的基本編程模型。

（3）Python變量、參數和對象屬性都沒有類型限制，因此Python里定義的函數和對象方法都具有通用性，能操作任何滿足需要的對象且只要求被操作對象提供所需操作，自定義數據結構能保存任何類型的數據元素。

（4）由于上述通用性，教科書里、課堂上和學生工作中開發的各種組件，如函數、類等，只要定義合適，就能作為輔助性數據結構直接用于后續工作，用于實現更復雜的數據結構和操作，或直接支持數據結構的應用。這使學生能看到從簡單到復雜的軟件開發過程，看到自己編寫的程序能真正得到應用，更有成就感。

用Python講授數據結構也存在一些困難，主要困難源自Python語言的高級和抽象。做算法（程序）的復雜性分析時，首先要確定基本操作和基本數據單元，它們必須具有O(1)復雜性。在C語言等較低級的語言里，基本操作都是O(1)操作；Python作為比較高級的語言，屏蔽了重要的實現細節，表面上看似很簡單的操作，內部實現可能很復雜，如==判斷、整數加法等，都不一定是O(1)操作。組合數據類型的廣泛使用，進一步增加了復雜性分析的難度，用Python講授課程時需要特別注意這些問題。

3 用Python講授數據結構課程的實踐和體會

我們用自己編寫的材料講授了幾次數據結構課程，教學效果總體上是非常正面的：學生反應比較積極，做作業也很有興趣，完成了不少有一定復雜性的工作。

與基于C語言的課程相比，有關數據結構理論的抽象討論可以基本照搬。有關抽象數據類型的介紹可以更有針對性，ADT描述可以參考Python類定義做些調整，如增加self參數等。前面章節實現的數據結構可以直接用于后面數據結構或應用問題，看到做出的東西有實用性，學生也覺得更親切。如果出現基本數據結構不能滿足需要的情況，也很容易擴充調整，如實現哈夫曼樹時，要比較兩棵二叉樹根數據的大小，可以用優先隊列保存二叉樹要檢查隊列元素個數。實現這種功能的基礎是面向對象的繼承，以及函數和數據結構的通用性。

目前，數據結構教材上討論的內容和習題，用Python來解決大多比較方便，程序代碼比用C語言要短，概念和結構更清晰，尤其是能更好地反映算法的精髓，有利于學生學習。數據結構課程中一些不好用C語言處理的問題，在基于Python的課程中則能很自然地處理，如操作錯誤的處理——棧空時彈出可以用Python異常機制描述，符合軟件實踐的需要，既規范又方便。

4 關于課程中幾個具體問題的考慮和建議

數據結構課程的內容和結構成型于20世紀70～80年代，且在那之后沒有太大變化，國內也出版了一些使用比較廣泛的教材。隨著軟件領域研究和實踐的發展，有些過去不受重視的問題現在變得非常重要，一些理論觀點和方法也需要得到重視。

4.1 正則表達式和模式匹配

數據結構課程應該加入有關正則表達式的討論。實際上，正則表達式才是當前業界廣泛使用的模式匹配概念的基礎，而且已成為實際軟件開發中的重要工具。正則表達式這個概念特別應該納入專業教學，且比較適合放入數據結構課程，它既有數據結構問題，又有算法問題。我們編寫的教材中，“字符串”一章里介紹了正則表達式。在Python里處理這個問題比較方便，我們首先應該推廣模式匹配概念，引進正則表達式的概念，先介紹簡化的正則表達式的匹配算法，再介紹Python的正則表達式包re。通過介紹這個典型正則表達式包的各個細節，幫助學生了解實際軟件開發中使用的正則表達式及其模式匹配功能。

4.2 動態順序表

現有教材大多采用固定大小的數組實現元素個數可變的數據結構，如順序表。在C語言里這樣做，主要原因是做法比較簡單，但是在實際應用中，能隨著元素增加而自動增大容量的“動態順序表”已是當前各種基本類型庫的標準配置。Python標準類型list就是動態順序表，動態增長規則和性質也是與數據結構有關的重要知識。

在C語言里實現動態順序表并不難，但是代碼比較繁瑣；采用動態增長技術改造所有可能受容量限制的數據結構，也會帶來一些麻煩。在基于Python的課程或教材中，這個問題則比較容易處理，這主要得益于Python標準類型的內在功能。

4.3 分償（平攤，amotized）復雜性

傳統數據結構課程只討論一次數據結構操作的復雜性，但在當前的軟件領域，一系列操作的平均復雜性也是很重要的概念。這個概念被稱為平攤復雜性，典型例子是對動態順序表的尾端插入。如果采用正確的容量擴大策略，大多數操作只有O(1)開銷，高代價操作越來越稀少，而平攤復雜性仍然是O(1)。按目前數據結構課程的討論，在動態順序表的尾部插入操作，最壞情況時間復雜性是O(n)，但是這樣不僅不能很好地反映該操作的性質，還不能將其與其他插入區分開。平攤復雜性已成為當前軟件領域考查數據結構實現的重要指標，課程中應加入這方面內容。此外，學習Python的數據結構也必須理解平攤復雜性的概念。

4.4 錯誤處理

專業基礎課應該教給學生正確的編程理念，現有課程在某些問題上沒有很好地給予處理。當前最受重視的問題之一是程序安全，其中最主要的問題就是正確處理程序運行中的錯誤，數據結構中操作失敗是典型的運行時錯誤。對于這個問題，傳統C語言教材采用的方式或是不理會，或是輸出信息報錯，又或是直接調用exit(1)之類語句終止，這些都是錯誤做法，實際程序操作中不能采用。要在C語言中貫徹一套正確并合理的錯誤處理理念，會遇到許多困難，也太繁瑣。新型語言，如Python的異常機制支持處理運行時錯誤，而且很容易使用，能給學生傳播正確的理念和技術。

4.5 面向對象技術的作用

一方面，我們應該在數據結構的設計和構造中充分展示面向對象編程技術的作用，說明基于已有的類擴充，通過繼承、擴充、方法覆蓋等，可以非常簡單方便地解決遇到的問題，而不需要重新定義。很多新數據結構可以定義為已有數據結構的擴充，在需要某種輔助性數據結構，而已有結構不能完全滿足需要時，可以很方便地予以調整。例如，繼承簡單鏈接表，定義帶尾指針的鏈接表；繼承簡單鏈接表，定義循環鏈接表；繼承簡單鏈接表及其結點，定義雙向鏈接表的結點和雙向鏈接表等。

另一方面，課程中應該盡可能實現通用算法，一種數據結構的不同實現盡可能采用公共接口，這樣能使一組算法應用于不同的數據結構實現。例如，圖的最常見表示是鄰接矩陣和鄰接表，一種合理的做法是定義兩個表示圖的類，它們的內部實現分別采用不同技術，但是提供統一的接口；開發圖算法時，所有算法都基于圖類的公共接口來定義，使這些算法能應用于采用不同內部表示的圖。采用面向對象技術，既方便開發實例，又可以展示面向對象技術的威力和Python語言的能力，Python的通用性本質也起到重要作用。

5 結語

Python語言正越來越多地應用在計算機科學技術基礎課程甚至是第一門課程中，這種安排必然會對計算機專業的其他課程產生影響。在研究Python語言的教學使用和生態培育時，必須關注這些問題。如果我們把Python作為計算機科學技術專業第一門課程的工作語言，就必須研究如何用Python教授數據結構課程；如果采用其他語言，數據結構的課程只能推后，還須補充其他語言的知識，這也會對整個專業教育產生影響。我們基于教學經驗和思考，討論了基于Python的數據結構課程的內容設計和教學目標，研究了以Python作為數據結構課程基礎的實際可行性和實施中的主要關注點，分析了用Python開設數據結構課程的優勢和難點，以及一些重要問題的處理方法。

國內各院校在使用C語言教授數據結構課程方面已經有了很多積累，包括被廣泛使用的教材、練習題目以及各種教學支持系統的建設。改用Python教授基礎課程時，這些方面基本是空白。如果有更多院校選擇這樣的課程體系，就需要更多人力和物力的投入；開展相關建設，需要更多人參與，課程內容和教材也需要進一步建設、修改和完善。

[1]AhoAV,HopcroftJE,JeffreyD.Ullman:Thedesignandanalysisofcomputeralgorithms[M].Boston:Addison-Wesley,1974.

[2]WirthN.Algorithms+datastructures=programs[M].UpperSaddleRiver:Prentice-Hall,1976.

[3]MillerBN,RanumDL.ProblemsolvingwithalgorithmsanddatastructuresusingPython[M].2ed.Franklin:Beedleamp;Associates,2011.[4]BakaB.Pythondatastructuresandalgorithms[M].Birmingham:PacktPublishing,2017.

[5]LeeKD,HubbardS.DatastructuresandAlgorithmswithPython(undergraduatetopicsincomputerscience)[M].Berlin:Springer,

20 15.

[6]裘宗燕.數據結構和算法:Python語言描述[M].北京:機械工業出版社,2016.

[7]AgarwalKK.PythonforCS1,CS2andbeyond[J].ConsortiumforComputingSciencesinColleges,2005,20(4):262-270.