重新审视数据结构——评《数据结构基础》新版

谢勰 龙启铭

摘要:本文从课程和研究的角度重新审视数据结构,基于“重新将数据结构作为计算机科学的一个重要研究主题”的观点,提炼出“数据结构”的教学目的——让学生学会选择使用数据结构并能对其设计与分析。本文简述了《数据结构基础》及其译本的出版历程,以及其以严谨性、启发性和趣味性等畅销至今的重要特色。

关键词:数据结构;教学改革;教材研究

中图分类号: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.