重新審視數(shù)據(jù)結構——評《數(shù)據(jù)結構基礎》新版

謝勰 龍啟銘

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

關鍵詞:數(shù)據(jù)結構;教學改革;教材研究

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

1引言

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

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

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

2一本歷久彌新的教材

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

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

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

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

3數(shù)據(jù)結構的“圣經(jīng)本”

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

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

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

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

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

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

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

4百科全書式組織

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

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

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

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

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

5新版本,新譯本

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

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

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

6總結與展望

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

此外,《數(shù)》的姐妹篇《計算機算法》也于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. 數(shù)據(jù)結構基礎[M]. 程惟寧,譯. 北京:新時代出版社,1983.

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

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