前言

《数据结构编程实验》是“大学程序设计课程与竞赛训练教材”系列的第一部著作。在出版本书第1版的时候，我们的初心是基于程序设计竞赛的试题，以全面、系统地磨炼和提高学生通过编程解决问题的能力为目标，出版既能用于大学程序设计类课程的教学和实验，又能用于程序设计竞赛选手训练的系列著作。

经过多年的努力，“大学程序设计课程与竞赛训练教材”系列不断完善。这套教材基于以下指导思想：

1）程序设计竞赛是“通过编程解决问题”的竞赛。国际大学生程序设计竞赛（International Collegiate Programming Contest，ICPC）和中学生国际信息学奥赛（International Olympiad in Informatics，IOI）在20世纪80年代中后期走向成熟之后，30多年来积累了海量的试题。这些来自全球各地、凝聚了无数命题者心血和智慧的试题，不仅可以用于程序设计竞赛选手的训练，而且可以用于程序设计类课程的教学和实验，能够系统、全面地提高学生通过编程解决问题的能力。

2）我们认为，评价一个人的专业能力要看两个方面：①知识体系，他能用哪些知识去解决问题，或者说，哪些是他真正掌握并能应用的知识，而不仅仅是他学过什么知识；②思维方式，当他面对问题，特别是不太标准化的问题的时候，解决问题的策略是什么。对于程序设计竞赛选手，要求的知识体系可以概括为1984年图灵奖得主Nicklaus Wirth提出的著名公式“算法+数据结构=程序”，这也是计算机学科知识体系的核心部分。因此，本系列的前两部著作分别是《数据结构编程实验》和《算法设计编程实验》。对于需要采用某些策略进行求解的程序设计试题，比如，不采用常用的数据结构或者解题的算法要进行优化等，我们对相关试题进行分析、整理，编写了本系列的第三部著作《程序设计解题策略》。

3）从本质上说，程序设计是技术。所以，首先牢记学习编程要不断“实践，实践，再实践”。本系列选用大量程序设计竞赛的试题，以案例教学的方式进行教学实验并安排学生进行解题训练。其次，“以系统的方法实践”。本系列基于高校通常采用的教学大纲，以系统、全面提高学生通过编程解决问题的能力为目标，以程序设计竞赛的试题以及详细的解析、带注解的程序作为实验，在每一章的结束部分给出相关题库以及解题提示，并对大部分试题给出官方的测试数据。

基于上述指导思想，我们在中国大陆出版了本系列的简体中文版，在中国台湾地区出版了繁体中文版，在美国由CRC Press出版了英文版。

对于本书，我们在机械工业出版社出版了第1版和第2版，在中国台湾地区出版了繁体版的第1版和第2版。2016年，我们在CRC Press出版了本书的英文版Data Structure Practice:for Collegiate Programming Contest and Education。在本书的中、英文版广泛使用的基础上，我们对第2版进行了脱胎换骨的改进，编写了本书的第3版。

本书基于数据结构课程的知识体系，采用循序渐进的原则编写而成。全书分四篇（共15章），即训练基本编程能力的实验、线性表的编程实验、树的编程实验和图的编程实验。在每一章中，首先介绍相关的数据结构知识，然后给出相应的实验范例，并在章末给出相关题库。

第一篇“训练基本编程能力的实验”适合刚学会程序设计语言的读者。这部分包括3章：第1章“简单计算的编程实验”、第2章“简单模拟的编程实验”和第3章“递归与回溯法的编程实验”。与本书第2版相比，这一篇对正确处理多个测试用例、在实数和整数之间转换、二分法、实数精度、递归、回溯的实验做了较大改进。

数据结构分为3类，即线性表、树和图，分别在本书的第二篇“线性表的编程实验”、第三篇“树的编程实验”和第四篇“图的编程实验”中按知识体系展开实验，而排序和搜索的实验则是和具体的数据结构结合，在相应的章节里加以介绍。

第二篇“线性表的编程实验”包括4章：第4章“应用直接存取类线性表编程”给出数组和字符串的实验；第5章“应用顺序存取类线性表编程”介绍链接存储结构（指针）、栈、队列的实验；第6章“应用广义索引类线性表编程”包含词典解题和散列技术的实验；第7章“线性表排序的编程实验”从使用STL完成排序以及编程实现排序算法两方面给出线性表排序的实验。与本书第2版相比，本篇对高精度运算、栈、队列等的实验做了较大改进，并增加了Manacher算法和应用散列技术处理字符串的实验。

第三篇“树的编程实验”包括3章：第8章“采用树结构的非线性表编程”、第9章“应用二叉树的基本概念编程”和第10章“应用经典二叉树编程”。相比于本书第2版，本篇对并查集、树状数组、二叉树路径和遍历、二叉搜索树、树堆、赫夫曼树的实验做了较大改进，并增加了用Trie树查询字符串、用AC自动机进行多模式匹配、应用典型二叉树、AVL树、伸展树的实验。

第四篇“图的编程实验”包括5章：第11章“应用图的遍历算法编程”、第12章“应用最小生成树算法编程”、第13章“应用最佳路算法编程”、第14章“二分图、网络流算法编程”和第15章“应用状态空间搜索编程”。相比于本书第2版，本篇对BFS、DFS、拓扑排序、最佳路、二分图、网络流、优化状态空间搜索、游戏树的实验做了较大改进，并增加了计算图的连通性、Tarjan算法、最大生成树的实验。

本书可用作高校数据结构、程序设计语言以及离散数学等课程的实验教材，也可用作程序设计竞赛选手的系统训练参考书籍。对于本书，我们的使用建议是：书中各章的实验范例可以用于数据结构、程序设计语言以及离散数学相关课程的教学、实验和上机作业，以及程序设计竞赛选手掌握相关知识点的入门训练；每章最后给出的相关题库中的试题可以作为程序设计竞赛选手的专项训练试题，以及学生进一步提高编程能力的练习题。

我们对浩如烟海的ACM-ICPC程序设计竞赛区预赛和总决赛、各种大学生程序设计竞赛、在线程序设计竞赛以及中学生信息学奥林匹克竞赛的试题进行了分析和整理，从中精选出306道试题作为本书的试题。其中，160道试题为实验范例试题，每道试题不仅有详尽的解析，还给出标有详细注释的参考程序；另外的146道试题为题库试题，所有试题都有清晰的提示。

在华章网站（www.hzbook.com）上提供了本书所有试题的英文原版描述以及大部分试题的官方测试数据和解答程序。限于篇幅，书中部分实验范例试题的参考程序未放在书中，而是以PDF文件的形式和试题的英文原版描述一起作为本书附加资源，读者可从华章网站下载这些资源。

这些年来，我们秉承“不忘初心，方得始终”的思想，不断地完善和改进系列著作。我们也得到了海内外各位同人的鼎力相助。感谢石溪大学的Steven Skiena教授和Rezaul Chowdhury教授，得克萨斯州立大学的C.Jinshong Hwang教授、Ziliang Zong教授和Hongchi Shi教授，德国科技大学阿曼分校的Rudolf Fleischer教授，他们为本书英文版书稿的试用和改进做了大量工作。

感谢组织程序设计训练营集训并邀请我使用本书书稿讲学的香港理工大学曹建农教授、台北商业大学彭胜龙教授、西北工业大学姜学峰教授和刘君瑞教授、宁夏理工学院副校长俞经善教授、中国矿业大学毕方明教授，以及中国矿业大学徐海学院刘昆教授等。感谢卢森堡大学博士生张一博、香港中文大学博士生王禹对于本书第3版的编写提出的建设性意见。

特别感谢中国大陆及中国台湾、中国香港、中国澳门的同人和我一起创建ACM-ICPC亚洲训练联盟，联盟的创建不仅为本书书稿，也为系列著作及其课程建设提供了一个实践的平台。

由于时间和水平所限，书中难免存在缺点和错误，表述不当和笔误也在所难免，欢迎学术界同人和读者不吝指正。如果你在阅读中发现了问题，恳请通过电子邮件告诉我们，以便我们在课程建设和中、英文版再版时改进。联系方式如下：

通信地址：上海市邯郸路220号复旦大学计算机科学技术学院　吴永辉（邮编：200433）

电子邮件：yhwu@fudan.edu.cn

吴永辉

2020年9月30日于上海

注：本书试题的在线测试地址如下。