前言我们长期从事数据结构、算法的教学和程序设计竞赛的训练,教学和训练的实践使我们产生了对程序设计、数据结构和算法的教学模式进行改革的想法。1)在课程中增加思维方式和解题策略的引导,引导学生思考各类数据结构、算法的本质特征是什么,将“知识体系结构的掌握”与“思维方式的训练”结合起来。我们认为,评价一个人的专业能力要看以下两个方面:①知识体系结构。他能用哪些知识解决问题,或者说,哪些是他所真正掌握并能应用而不仅仅是他学过的知识?②思维方式。在他面对问题,特别是不太标准化的问题的时候,他解决问题的策略是什么?比如,面对的问题为什么要采用这样的数据结构表示,而不宜采用那样的数据结构表示?当有多个数据结构可用时,怎样权衡时间复杂度、空间复杂度、编程复杂度和思维复杂度四个因素,寻找最合适的数据结构?等等。2)在课程和训练中全部采用程序设计竞赛的试题作为案例来进行教学。传统教学着重于理论教学和笔试,可能会使学生浑然不知程序设计语言、数据结构、算法在现实生活中究竟有什么用处,也就失去了学习的意义。陆游诗云:“纸上得来终觉浅,绝知此事要躬行。”案例教学是通过模拟或者重现现实生活中的一些场景,让学生把自己置入问题情境之中,通过思考、讨论和上机编程来进行学习的方式:学生拿到试题后,先进行审题(What to do),然后考虑如何采用数据结构和算法来解决问题(How to do),这无形中激发了学生的求知欲望,加深了学生对知识的理解;在给出了通过编程解决问题的方法后,学生还要经过编程,将解决方法变为解决问题的程序,并进行调试,在允许的时间和空间范围内通过测试用例(Implementation)。这个“认识–实践–再认识–再实践”的过程,应视为知识理解上的一种提高,知识学习与应用能力间的一种转变和升华。程序设计竞赛是通过编程解决问题的比赛。从20世纪80年代末期到现在,各类大学生程序设计竞赛、各种在线比赛以及中学生信息学奥林匹克竞赛构成了浩如烟海的试题库。这些来自全球各地且凝聚了无数命题者的心血和智慧的试题,为相关知识创设了丰富有趣的问题背景,而且针对这些试题有许多在线测试平台,学生可以通过这些平台测试自己编写的程序。因此,这些试题不仅可以用于程序设计竞赛选手的训练,而且可以用于程序设计语言、数据结构、算法的教学和实验,能够系统、全面地提高学生通过编程解决问题的能力。3)从程序设计的本质上说,程序设计是技术。正因为程序设计是技术,所以,要磨炼学生的程序设计能力。首先是要求学生练习、练习、再练习;其次是要安排学生系统地练习。程序设计的知识体系可以概括为“算法+数据结构=程序”这一公式,这也是计算机科学与技术的知识体系结构的核心。所谓系统地练习,就是在试题及其测试数据、解答程序以及解题分析的引导之下,通过解题系统地磨炼学生应用算法和数据结构各个知识点解决实际问题的能力,从而有效地掌握程序设计的知识体系。基于上述想法,我们规划了“大学程序设计课程与竞赛训练教材”系列,并于2012年出版了该系列的第一本著作《数据结构编程实验:大学程序设计课程与竞赛训练教材》。随后,在中国台湾,由碁峰出版了该书的繁体版《提升程式設計的資料結構力:國際程式設計競賽之資料結構原理、題型、解題技巧與重點解析》;在美国,由CRC Press出版了该书的英文版《Data Structure Practice : for Collegiate Programming Contests and Education》,并在全球发行。目前,该书在境内外广受读者的欢迎和好评。在此基础上,我们根据境内外的同学和同行在使用该书的过程中提出的意见及建议,以及计算机科学技术和程序设计竞赛的发展,我们这几年在阿曼、中国台湾和香港、美国、马来西亚、孟加拉国等国家和地区的讲学和访学工作,对该书进行了“脱胎换骨”的改进,最终出版了《数据结构编程实验:大学程序设计课程与竞赛训练教材》第2版。本书根据数据结构的知识体系结构,按照循序渐进的原则,分四大篇(历练基本编程能力、线性数据结构的编程实验、树的编程实验、图的编程实验)15章组织内容。每一章在介绍了相关的数据结构知识后,给出了相应的实验范例,并在最后一节给出相关题库。相应于本书的第1版,我们除了修正原有的小错误、笔误以及改进了一些表述外,较大的改进如下:在第一篇的第3章中,由原来的“简单递归的编程实验”完善为“递归与回溯的编程实验”。在第二篇的第4章中,将“在数组中快速查找指定元素”和“通过数组分块技术优化算法”的实验范例融合到原有的内容中;在第5章的队列编程实验中,完整地给出了三种队列形式即顺序队列、优先队列、双端队列的实验范例。在第三篇的第8章中,加入了“用四叉树求解二维空间问题”的实验范例;在第10章,在已有的二叉排序树和二叉堆的编程实验基础上,给出兼具二叉排序树和二叉堆性质的树堆的实验范例。在第四篇中,加入第15章“应用状态空间搜索编程”。我们对浩如烟海的ACM程序设计竞赛区预赛、总决赛、各大学程序设计竞赛、在线程序设计竞赛以及中学生信息学奥林匹克竞赛的试题进行了分析和整理,从中精选出227道试题作为书中内容。其中88道试题作为实验范例,每道试题不仅有详尽的解析,还给出带有详细注释的参考程序;139道作为题库试题,所有试题都有清晰的提示,同时对第1版的读者反映的题库中一些“看了提示也很难编程”的较难的试题给出了带详尽注解的解答程序(或者直接给出,或者作为电子版随试题原版给出)。书中每道题都注明了试题来源和在线测试网址,学生可以通过在线测试平台测试自己编写的程序。本书的网站(www.hzbook.com)提供了所有试题的英文原版以及大部分试题的官方测试数据和解答程序。本书既可以用于大学程序设计课程的教学和实验,又可以用于程序设计竞赛的训练。对于本书,我们的使用建议是:书中每章的实验范例可以用于程序设计语言、数据结构课程的教学、实验和上机作业,以及程序设计竞赛选手掌握知识点的入门训练;而在每章最后给出的“相关题库”中的试题则可以作为程序设计竞赛选手的专项训练试题,以及学生进一步提高编程能力的练习题。根据本书第1版的使用情况,本书也非常适合学生自学,在知识背景、试题、测试数据、解题分析或提示的支持之下,即使没有老师、没有同伴,同学们也能够系统、全面地提高自己的编程能力。本书是在复旦大学程序设计集训队长期活动的基础上积累而成的。感谢复旦大学计算机学院2006级、2007级、2008级同学,他们在使用本书第1版的讲义稿过程中提出了宝贵的意见和建议。感谢阿拉法特·居来提、姚哲云、张昊同学,他们编写了本书第1版的所有程序。感谢使用本书第1版的读者们,他们提出的宝贵意见和建议对第2版和英文版的出版贡献巨大。感谢Stony Brook University的Steven Skiena教授、Rezaul Chowdhury教授,Texas State University的C. Jinshong Hwang教授、Ziliang Zong教授和Hongchi Shi教授,German Unive-rsity of Technology in Oman的Rudolf Fleischer教授,以及North South University的Abul L. Haque教授和Shazzad Hosain教授,他们为本书英文版的试用和改进提供了平台。感谢中国台湾、中国香港、孟加拉国、马来西亚邀请我讲学的李哲荣、廖宜恩、杨昌彪、林盈达、李淑敏、傅楸善、曹建农等教授和参加我的讲学的老师和同学,这几年,我们并肩作战,风雨同舟,而他们在使用本书第2版书稿的过程中也提出了宝贵意见和建议,为本书第2版的完成做出了不可或缺的贡献。由于时间和水平所限,书中肯定夹杂了不少缺点和错误,表述不当和笔误也在所难免,热忱欢迎学术界同仁和读者赐正。如果您在阅读中发现了问题,恳请通过书信或电子邮件告诉我们,以便我们及时整理成勘误表放在本书的网站上,供广大读者查询更正。我们更期望读者对本书提出建设性意见,以便再版时改进。我们的联系方式如下:通信地址:上海市邯郸路220号复旦大学计算机科学技术学院 吴永辉 (邮编:200433)电子邮件:yhwu@fudan.edu.cn吴永辉 王建德2016年6月于上海