重新審視數據結構——評《數據結構基礎》新版

謝勰 龍啟銘

摘要:本文從課程和研究的角度重新審視數據結構,基于“重新將數據結構作為計算機科學的一個重要研究主題”的觀點,提煉出“數據結構”的教學目的——讓學生學會選擇使用數據結構并能對其設計與分析。本文簡述了《數據結構基礎》及其譯本的出版歷程,以及其以嚴謹性、啟發性和趣味性等暢銷至今的重要特色。

關鍵詞:數據結構;教學改革;教材研究

中圖分類號:G642文獻標識碼:B

1引言

提起“數據結構”,大多數人都認為它是一門基礎性課程。從某種角度看,“數據結構”有點像“高等數學”,一是兩者內容大多早已成熟,二是它們都積累了大量習題可供學生練習。這樣一來,應試傾向的“數據結構”課程應運而生,無論是在教學和學習中,這種傾向性都非常明顯。比如在鏈表這部分內容的講授中,教師一般會給出各種不同的鏈表變種作為習題。又比如在討論二叉樹遍歷時,學生要花費大量精力去學習各種遍歷的非遞歸形式。雖然學習這些內容可以提高邏輯思維能力,但學習“數據結構”的目的是為程序設計、更是為算法設計而服務,因此其重點應放在如何挑選或設計合適的數據結構,而不是把大量精力花在這些不太實用的細節問題上。

另一方面,數據結構還有許多值得研究的問題。許多數據結構不但性能優越,而且構造精巧,比如二項堆與Fibonacci堆。而發展成熟的數據結構很快便可應用于工業界,如STL中的vector容器。研究人員不但需要設計新的數據結構以獲得好的性能,并且還要對它們進行細致的分析以了解其性能極限(即下界問題)。此外,目前有若干專門的學術會議致力于數據結構的設計與分析,如交替舉辦的The Workshop on Algorithms and Data Structures (WADS)和The Scandinavian Workshop on Algorithm Theory(SWAT)。今年是WADS舉辦20周年,這也充分說明了數據結構這個經典的主題依然有著蓬勃的生命力。

因此,在數據結構的教學過程中,我們需要一本合適的數據結構教材,既能學習到如何使用和選擇數據結構,還能深入了解數據結構的設計與分析。

2一本歷久彌新的教材

關于“數據結構”,最權威的闡述當推Knuth的The Artof Computer Programming第1卷(首版于1968年出版,這也是關于數據結構最早的著作),此書對數據結構作了簡潔精當的講解。但該書過于簡略,對于初學者來說難度較大。

1976年,Computer Science Press出版了由Ellis Horowitz和Sartaj Sahni編著的《數據結構基礎》,(下文簡稱《數》)此書相比Knuth的巨著而言則顯得較為平易近人,不但內容詳實、深入,而且覆蓋面很廣。因此,《數》一面世便受到了極大的歡迎,總印數高達約10萬冊,在當時已屬天文數字。另外,該書的姐妹篇《計算機算法基礎》于1978年出版,此書秉承了《數》的優點,也是一本暢銷教材。不夸張地說,這兩本書不但是優秀的教材,還是小型的百科全書,暢銷也在意料之中。

20世紀80年代正是Pascal語言風靡全球之時,而首版《數》是以SPARK語言描述算法,所以作者于1983年推出了《數》的Pascal版,直到1994年,一共出了4版。其間作者還推出了《數》的IBM-PC Turbo Pascal版。進入20世紀90年代后,上面兩位作者和Susan Anderson-Freed合作,推出了《數》的C語言版,又與Dinesh Mehta合作編寫了《數》的C++語言版,該書版本之多也說明了它受歡迎的程度很高。

時至2006年,也就是《數》出版30年后,作者重新推出了《數》的C++語言第2版,在2007年又推出了《數》的C語言新版。一本計算機教材延綿30余年且不斷更新,這是不多見的。

3數據結構的“圣經本”

在網絡上搜索“資料結構”(即數據結構)和“圣經本”,便能找到眾多成功考生的經驗之談,而他們無一例外地都會提到《數》。原來,中國臺灣地區的許多大學和研究所都非常推崇《數》,并在其碩士入學考試資料結構這個科目中指定《數》英文版為標準參考書,考生們自然是人手一冊,而此書也被譽為“資料結構的圣經本”。單就其作為教材生命力旺盛這一點而言,《數》就能擔得起“圣經本”這一稱號。

隨手翻開《數》新版前幾章,所見內容似乎是老生常談,如稀疏矩陣的操作、多項式運算、迷宮問題、表達式求值等。這些問題在許多國內的教材中也有詳細的論述,于是有些讀者可能會覺得《數》“盛名之下,其實難副”。實際上,國內的數據結構教材大多是依據《數》為藍本編寫而成。要是仔細比對,會發現這些教材無論是從結構編排上,還是從內容選擇上,都與《數》極為類似,由此可見《數》的影響力之大。選擇此書作為教材藍本的原因之一,應該是《數》的講授方式類似前蘇聯的教科書,全面、詳細、深入,因此它便作為范本一直流傳。由于該書的前幾章都是其1976年版中已經過精心錘煉的經典內容,因此在新版中未作較大改動。新版的更新主要從“樹”這一章開始,而此后的內容相當豐富,不但可作為教材,還能可供專業人士參考之用,確為同類之翹楚,后文將對此以專節論述。

事實上,《數》之所以得到教師的厚愛,其原因不僅僅是它的內容遠比一般教材豐富,我們試舉幾例以說明《數》的特色所在。

(1) 書中對樹的定義是“A tree is a finite set of one or more nodes …”,請注意這里不嫌麻煩地強調了“一個或更多結點”。這個定義與Knuth的書中所給出的權威定義基本類似,但許多教材視而不見,早已拋棄了“樹不能為空”的這個限制。這說明《數》體會到了這個細節問題,也即以森林的觀點來看待樹。此限制意味著存在空森林(恰好對應空二叉樹),但不存在空樹。從集合的觀點看,樹是基本元素/實體,不可為虛空,但允許定義空集/空森林。此乃該書特色之一——嚴謹性。

(2) 書中在數組的編程題中給了一道隨機行走問題,此題雖不難,但能引發學生展開深入思考:① 如何利用數組高效表示幾何結構。雖然普通的矩形網格很容易表示,但實際上,許多復雜幾何或空間結構仍可用數組精巧地表示,這也是作者的用意之所在;② 進行隨機模擬的重要性。這里雖然只實現了簡單的仿真,但仿真這個主題在書中多次出現,還給出了多個編程題以供練習。而在仿真中特別強調效率,選用好的數據結構(如優先級隊列)能極大提高仿真速度;③ 對于更復雜的圖上隨機行走問題,應如何結合后文中表示圖的數據結構進行優化,這也非常值得思考。此乃該書特色之二——啟發性。

(3) 書中在棧和隊列的編程題中要求實現紙牌游戲,而該游戲直到現在依然非常流行,在各種操作系統中也都是必備的附加軟件。紙牌游戲的實現只需要綜合使用棧和隊列的ADT即可搭建完畢,完成此實驗不但能獲得樂趣,而且還能對ADT的功用更為明了,可謂一舉兩得。相信講授此部分內容時,打開操作系統所帶的紙牌游戲演示,一定能引起學生的極大興趣。此乃該書特色之三——趣味性。

《數》中的此類實例不勝枚舉,在此不多贅述。

4百科全書式組織

《數》的特色在于其全面、詳細、深入,這也是它作為參考書的優勢。一方面,《數》對許多數據結構給出了詳細的描述,這樣使用和挑選數據結構的范圍就不會局限于常用的那些基礎結構。比如講解樹結構時,《數》以較大的篇幅作了相當詳細的描述,還列出了不相交集和選拔樹,以供讀者選用。另一方面,《數》對許多結構給出了性能分析,它雖然不像原始文獻那么詳細,但也足以讓讀者明了。比如在講樹的計數時,有些書上只是給出結果,而《數》則通過簡單的遞歸式求解獲得了Catalan數,讓讀者不至于感到此數的突兀。

最值得一提的是《數》關于堆結構和查找結構部分的講解,這兩類結構是現代數據結構中最重要的兩部分,書中對此著墨最深。新版中刪除了一些用處不大的堆結構,加入了較為有用的配對堆并更換了最小—最大堆。講授堆時,仍從重要的分攤復雜度入手,詳細講解了二項堆、Fibonacci堆、配對堆,并給出了相應的分攤復雜度,后面又介紹了最小—最大堆的幾種實例,需要從事仿真、算法設計的讀者基本都能中獲取所想要了解的內容。而對于查找結構部分,新版則將一章擴充為三章,系統地闡述了各種查找結構。先詳細闡述內存中的查找,又轉向外存中的查找,最后著重講解了數字/字符查找,尤其是trie和后綴樹這兩類結構。此外,在查找結構中,作者還以互聯網中的包轉發作為應用實例。

當然,作為教材的《數》還不足以反映數據結構的全貌。在編寫此書的過程中,作者意猶未盡,還主持編寫了一本系統闡述數據結構理論和應用的“百科全書”,全面、系統地闡述了各種數據結構,并給出了眾多實際應用。有興趣的讀者學完《數》后,自然想了解更多、更深的內容,不妨去翻看這本“百科全書”。

需要指出的是,目前,北美的許多大學基本都將數據結構按難度拆分成兩部分:基本內容與面向對象程序設計一起講授;而高等內容則融入算法設計與分析的課程。每個大學所采用的教材也各有不同,而傳統名校還特別偏愛本校教授編寫的教材,既難且深,還特別側重自己的研究方向(比如Maryland大學的Hanan Samet教授就特別偏重空間數據結構)。然而,值得我們注意的是,許多學者正積極倡導重新審視數據結構,將注意力放在如何挑選出合適的數據結構、設計并分析數據結構性能上,也即重新將數據結構作為計算機科學的一個重要研究主題。這種關于數據結構的新思路的重點在于:不要過多地將數據結構與面向對象揉合,要關注數據結構本身。事實上,作者的這種“百科全書”式努力的目的,正是為了讓更多的人關注數據結構本身,而不是將數據結構和面向對象程序設計視為一體。從這個觀點看,作者確實用心良苦。

當然,國內對于“數據結構”一直相當重視,各校都將其作為重要的基礎課單獨開設。而關于數據結構的這種新思路,不但值得借鑒,而且非常適宜于目前的課程設置。因此,我們需要一本純粹的數據結構教材。考慮到國內的“數據結構”課程一直以《數》為范本,換言之,此書和目前國內的教學內容相當貼近,在不進行大改動的情況下,在“數據結構”的講授和學習中采用這本教材,不但可以鍛煉學生的基本能力,還將對他們今后的研究工作大有裨益。

5新版本,新譯本

最早的《數》中文譯本(對應1976年的英文版)于1983年出版,該譯本極大地推動了數據結構在國內的普及,功不可沒。此版的特色是對某些數據結構進行了公理化定義,如今的教材已不再講解此內容。

2009年,清華大學出版社一次性引入《數》的兩個版本(C語言版和C++語言版),分別由朱仲濤和張力老師翻譯,該譯本不但準確流暢,而且風趣詼諧。值得一提的是,朱仲濤所翻譯的《數據結構基礎(C語言版)》全書均采用LaTeX排版,還自行繪制了所有插圖,從而使整本書異常精美。事實上,《數》英文版的版式略顯粗糙,朱仲濤的譯本從某種意義上說是對原書的再創作。翻看良久,確實嘆服譯者的敬業精神,這在當前的計算機專業圖書翻譯中是相當少見的。

目前,研究生入學考試在計算機專業課程中采用了統一考試的方式,不過2009年的考試成績卻不盡如人意,原因大約是沒有一本統一教材的緣故。我們不去評論考試形式的優劣,但準備考試的考生不妨以這本數據結構“圣經本”的譯本作為教材,認真學習、備考,也許會有意想不到的效果。

6總結與展望

“數據結構”課程也需要不斷改革和發展,但我們肯定不能完全照搬北美各大學的做法。從教材上說,從一本改良的教材入手,在此基礎上逐步改進,或許能創出適合于自己的教材,進而推廣先進的教學方式。《數》優點突出,尤其適合國內的數據結構教學現狀,確實是一本難得的優秀教材,值得推廣使用。

此外,《數》的姐妹篇《計算機算法》也于2008年推出了新版,我們希望盡快看到它的中譯本。

參考文獻:

[1] D. E. Knuth. The Art of Computer Programming Volume 1: Fundamental Algorithms[M]. 3rd ed . Addison Wesley, 1997.

[2] Hanan Samet. Foundations of Multidimensional and Metric Data Structures[M]. Morgan Kaufmann,2006.

[3] Dinesh P. Mehta, Sartaj Sahni. Handbook of Data Structures and Applications[M]. CRC, 2004.

[4] Hanan Samet. Data Structures Course 2003 [EB/OL].http://www.cs.umd.edu/class/fall2003/cmsc420-0101/.

[5] Peter Brass. Advanced Data Structure[M]. Cambridge University Press,2008.

[6] Ellis Horowitz, Sartaj Sahni. 數據結構基礎[M]. 程惟寧,譯. 北京:新時代出版社,1983.

[7] Ellis Horowitz, Sartaj Sahni, Susan Anderson-Freed. 數據結構(C語言版)[M]. 朱仲濤,譯. 2版. 北京:清華大學出版社,2009.

[8] Ellis Horowitz, Sartaj Sahni, Dinesh Mehta. 數據結構(C++語言版)[M]. 張力,譯. 2版. 北京:清華大學出版社,2009.