裘宗燕

（北京大學(xué)數(shù)學(xué)學(xué)院，北京100871）

0 引言

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

1 Python與數(shù)據(jù)結(jié)構(gòu)

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

隨著越來越多的高校開始使用Python講授第一門程序設(shè)計課程，用Python討論數(shù)據(jù)結(jié)構(gòu)的問題也被提上議事日程。為了深入探討有關(guān)情況，我們首先回答幾個經(jīng)常聽到的問題，網(wǎng)上對于這些問題也有許多討論。

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

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

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

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

（2）幫助學(xué)生在使用Python編程的過程中作出正確的設(shè)計選擇，并為這些選擇提供本質(zhì)性的判斷根據(jù)。例如，保存一批數(shù)據(jù)時，選用標(biāo)準(zhǔn)類型的表或字典，還是自己開發(fā)專門結(jié)構(gòu)，并知悉原因；向表中加入元素應(yīng)該用哪個操作等。

（3）有助于識別程序中的效率陷阱。Python程序中很容易創(chuàng)建各種復(fù)雜數(shù)據(jù)對象，這種便利如果使用不當(dāng)，很可能嚴(yán)重影響程序的效率和可用性。

2 用Python講授數(shù)據(jù)結(jié)構(gòu)課程的目標(biāo)、優(yōu)勢和困難

基于Python的數(shù)據(jù)結(jié)構(gòu)課程的教學(xué)目標(biāo)應(yīng)包含以下3方面。

（1）清晰介紹數(shù)據(jù)結(jié)構(gòu)課程的基本理論內(nèi)容。這些內(nèi)容與具體語言無關(guān)，包括數(shù)據(jù)結(jié)構(gòu)和算法的基本概念，相應(yīng)的理論問題（復(fù)雜性等），數(shù)據(jù)結(jié)構(gòu)的基本構(gòu)造技術(shù)，各種典型數(shù)據(jù)結(jié)構(gòu)的原理、性質(zhì)、基本使用和基本實現(xiàn)技術(shù)等。

（2）基于Python語言討論數(shù)據(jù)結(jié)構(gòu)的實現(xiàn)技術(shù)，既要體現(xiàn)一般的數(shù)據(jù)結(jié)構(gòu)技術(shù)，又要充分發(fā)揮Python的優(yōu)點，展示有用的設(shè)計和Python編程技術(shù)，還應(yīng)說明在Python程序里使用數(shù)據(jù)結(jié)構(gòu)解決問題時可能遇到的問題、分析和思考的方法、解決問題的方法等。

（3）認(rèn)真分析Python語言中的各種組合數(shù)據(jù)結(jié)構(gòu)（作為理論數(shù)據(jù)結(jié)構(gòu)的具體實現(xiàn)）的想法、具體設(shè)計和實現(xiàn)，各方面的實際性質(zhì)、優(yōu)缺點、使用時需要注意的問題等。

用Python講授數(shù)據(jù)結(jié)構(gòu)課程有許多優(yōu)勢，最重要的優(yōu)勢來自Python語言設(shè)計的很多特征可以在數(shù)據(jù)結(jié)構(gòu)課程中發(fā)揮作用。

（1）Python的面向?qū)ο髾C制可以作為ADT（抽象數(shù)據(jù)類型）的具體體現(xiàn)，用于實現(xiàn)各種數(shù)據(jù)結(jié)構(gòu)和支持封裝。類定義中的實例方法可用于實現(xiàn)數(shù)據(jù)結(jié)構(gòu)操作；繼承用于擴充已定義的部件，實現(xiàn)擴充（或部分修改）的新數(shù)據(jù)結(jié)構(gòu)等。

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

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

（4）由于上述通用性，教科書里、課堂上和學(xué)生工作中開發(fā)的各種組件，如函數(shù)、類等，只要定義合適，就能作為輔助性數(shù)據(jù)結(jié)構(gòu)直接用于后續(xù)工作，用于實現(xiàn)更復(fù)雜的數(shù)據(jù)結(jié)構(gòu)和操作，或直接支持?jǐn)?shù)據(jù)結(jié)構(gòu)的應(yīng)用。這使學(xué)生能看到從簡單到復(fù)雜的軟件開發(fā)過程，看到自己編寫的程序能真正得到應(yīng)用，更有成就感。

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

3 用Python講授數(shù)據(jù)結(jié)構(gòu)課程的實踐和體會

我們用自己編寫的材料講授了幾次數(shù)據(jù)結(jié)構(gòu)課程，教學(xué)效果總體上是非常正面的：學(xué)生反應(yīng)比較積極，做作業(yè)也很有興趣，完成了不少有一定復(fù)雜性的工作。

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

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

4 關(guān)于課程中幾個具體問題的考慮和建議

數(shù)據(jù)結(jié)構(gòu)課程的內(nèi)容和結(jié)構(gòu)成型于20世紀(jì)70～80年代，且在那之后沒有太大變化，國內(nèi)也出版了一些使用比較廣泛的教材。隨著軟件領(lǐng)域研究和實踐的發(fā)展，有些過去不受重視的問題現(xiàn)在變得非常重要，一些理論觀點和方法也需要得到重視。

4.1 正則表達(dá)式和模式匹配

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

4.2 動態(tài)順序表

現(xiàn)有教材大多采用固定大小的數(shù)組實現(xiàn)元素個數(shù)可變的數(shù)據(jù)結(jié)構(gòu)，如順序表。在C語言里這樣做，主要原因是做法比較簡單，但是在實際應(yīng)用中，能隨著元素增加而自動增大容量的“動態(tài)順序表”已是當(dāng)前各種基本類型庫的標(biāo)準(zhǔn)配置。Python標(biāo)準(zhǔn)類型list就是動態(tài)順序表，動態(tài)增長規(guī)則和性質(zhì)也是與數(shù)據(jù)結(jié)構(gòu)有關(guān)的重要知識。

在C語言里實現(xiàn)動態(tài)順序表并不難，但是代碼比較繁瑣；采用動態(tài)增長技術(shù)改造所有可能受容量限制的數(shù)據(jù)結(jié)構(gòu)，也會帶來一些麻煩。在基于Python的課程或教材中，這個問題則比較容易處理，這主要得益于Python標(biāo)準(zhǔn)類型的內(nèi)在功能。

4.3 分償（平攤，amotized）復(fù)雜性

傳統(tǒng)數(shù)據(jù)結(jié)構(gòu)課程只討論一次數(shù)據(jù)結(jié)構(gòu)操作的復(fù)雜性，但在當(dāng)前的軟件領(lǐng)域，一系列操作的平均復(fù)雜性也是很重要的概念。這個概念被稱為平攤復(fù)雜性，典型例子是對動態(tài)順序表的尾端插入。如果采用正確的容量擴大策略，大多數(shù)操作只有O(1)開銷，高代價操作越來越稀少，而平攤復(fù)雜性仍然是O(1)。按目前數(shù)據(jù)結(jié)構(gòu)課程的討論，在動態(tài)順序表的尾部插入操作，最壞情況時間復(fù)雜性是O(n)，但是這樣不僅不能很好地反映該操作的性質(zhì)，還不能將其與其他插入?yún)^(qū)分開。平攤復(fù)雜性已成為當(dāng)前軟件領(lǐng)域考查數(shù)據(jù)結(jié)構(gòu)實現(xiàn)的重要指標(biāo)，課程中應(yīng)加入這方面內(nèi)容。此外，學(xué)習(xí)Python的數(shù)據(jù)結(jié)構(gòu)也必須理解平攤復(fù)雜性的概念。

4.4 錯誤處理

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

4.5 面向?qū)ο蠹夹g(shù)的作用

一方面，我們應(yīng)該在數(shù)據(jù)結(jié)構(gòu)的設(shè)計和構(gòu)造中充分展示面向?qū)ο缶幊碳夹g(shù)的作用，說明基于已有的類擴充，通過繼承、擴充、方法覆蓋等，可以非常簡單方便地解決遇到的問題，而不需要重新定義。很多新數(shù)據(jù)結(jié)構(gòu)可以定義為已有數(shù)據(jù)結(jié)構(gòu)的擴充，在需要某種輔助性數(shù)據(jù)結(jié)構(gòu)，而已有結(jié)構(gòu)不能完全滿足需要時，可以很方便地予以調(diào)整。例如，繼承簡單鏈接表，定義帶尾指針的鏈接表；繼承簡單鏈接表，定義循環(huán)鏈接表；繼承簡單鏈接表及其結(jié)點，定義雙向鏈接表的結(jié)點和雙向鏈接表等。

另一方面，課程中應(yīng)該盡可能實現(xiàn)通用算法，一種數(shù)據(jù)結(jié)構(gòu)的不同實現(xiàn)盡可能采用公共接口，這樣能使一組算法應(yīng)用于不同的數(shù)據(jù)結(jié)構(gòu)實現(xiàn)。例如，圖的最常見表示是鄰接矩陣和鄰接表，一種合理的做法是定義兩個表示圖的類，它們的內(nèi)部實現(xiàn)分別采用不同技術(shù)，但是提供統(tǒng)一的接口；開發(fā)圖算法時，所有算法都基于圖類的公共接口來定義，使這些算法能應(yīng)用于采用不同內(nèi)部表示的圖。采用面向?qū)ο蠹夹g(shù)，既方便開發(fā)實例，又可以展示面向?qū)ο蠹夹g(shù)的威力和Python語言的能力，Python的通用性本質(zhì)也起到重要作用。

5 結(jié)語

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

國內(nèi)各院校在使用C語言教授數(shù)據(jù)結(jié)構(gòu)課程方面已經(jīng)有了很多積累，包括被廣泛使用的教材、練習(xí)題目以及各種教學(xué)支持系統(tǒng)的建設(shè)。改用Python教授基礎(chǔ)課程時，這些方面基本是空白。如果有更多院校選擇這樣的課程體系，就需要更多人力和物力的投入；開展相關(guān)建設(shè)，需要更多人參與，課程內(nèi)容和教材也需要進(jìn)一步建設(shè)、修改和完善。

[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]裘宗燕.數(shù)據(jù)結(jié)構(gòu)和算法:Python語言描述[M].北京:機械工業(yè)出版社,2016.

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