序言

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

这些年来，我们编著“大学程序设计课程与竞赛训练教材”系列，其指导思想是：

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

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

（3）程序设计，从其本质上说，是技术。所以，首先，“Practice, Practice, and Practice!”。本系列选用大量的程序设计竞赛的试题，以案例教学的方式，来进行教学实验和安排学生解题训练。其次，“Practice in a systematic way.”。本系列基于传统的教学大纲，以系统、全面提高学生编程解决问题的能力为目标，以程序设计竞赛的试题以及详细的解析、带注解的程序作为实验；并在每一章的结束部分，给出相关题库以及解题提示；并对大部分试题给出官方的测试数据。

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

这些年来，我们在机械工业出版社出版《数据结构编程实验：大学程序设计课程与竞赛训练教材》的第一版和第二版；并在台湾出版该书的繁体版《提升程式設計的資料結構力：國際程式設計競賽之資料結構原理、題型、解題技巧與重點解析》的第一版和第二版。2016年，我们在CRC Press出版该书的英文版《Data Structure Practice: for Collegiate Programming Contest and Education》。在该书的中、英文版这些年来在境内外广泛使用的基础上，我们对第二版进行了脱胎换骨的改进，编写《数据结构编程实验：大学程序设计课程与竞赛训练教材》的第3版。

《数据结构编程实验：大学程序设计课程与竞赛训练教材》（第3版）基于数据结构的知识体系结构和循序渐进的原则，分四大篇：基本编程能力的实验、线性数据结构的编程实验、树的编程实验、图的编程实验，共十五章。在每一章中，首先给出若干实验范例：在介绍了相关的数据结构知识后，给出了相应的实验范例；在每章的最后一节给出相关题库。

第一篇《历练基本编程能力》适用于刚学会程序设计语言的同学，分为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道试题为题库试题，所有试题都有清晰的提示。

在本书的网站中提供了所有试题的英文原版以及大部分试题的官方测试数据和解答程序。

这些年，我们秉承“不忘初心，方得始终”的思想，完善和改进我们的系列著作，也得到了广大的海内外同仁情义相挺。

感谢Stony Brook University的Steven Skiena教授和Rezaul Chowdhury教授；Texas State University的C. Jinshong Hwang教授、Ziliang Zong教授和Hongchi Shi教授；German University of Technology in Oman的Rudolf Fleischer教授；他们为本书英文版书稿的试用和改进提供了英语为母语或官方语言的平台。

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

特别感谢两岸四地的同仁们和我一起创建ACM-ICPC亚洲训练联盟，不仅为本书书稿，也为我的系列著作及其课程建设提供了一个实践的平台。

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

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

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

     吴永辉   王建德

                                                 2020-9-30于上海

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

在线评测系统

简称

网址

北京大学在线评测系统

POJ

http://poj.org/

浙江大学在线评测系统

ZOJ

https://zoj.pintia.cn/home

UVA在线评测系统

UVA

http://uva.onlinejudge.org/  http://livearchive.onlinejudge.org/

Ural在线评测系统

Ural

http://acm.timus.ru/

HDOJ在线评测系统

HDOJ

http://acm.hdu.edu.cn/ 

目录

序言

第一篇  历练基本编程能力

第1章 简单计算的编程实验

1.1改进程序书写风格的实验范例

1.2正确处理多个测试用例的实验范例

1.3在实数和整数之间转换的实验范例

1.4二分法、实数精度的实验范例

1.5 相关题库

第2章 简单模拟的编程实验

2.1直叙式模拟的实验范例

2.2筛选法模拟的实验范例

2.3构造法模拟的实验范例

2.4相关题库

第3章 递归与回溯的编程实验

3.1计算递归函数的实验范例

3.2求解递归数据的实验范例

3.3用递归算法求解问题的实验范例

3.4 回溯法的实验范例

3.5 相关题库

本篇小结

第二篇 线性表的编程实验

第4章 应用直接存取类线性表编程

4.1数组应用的四个典型范例

4.1.1日期计算

4.1.2 高精度运算

4.1.3  多项式的表示与处理

4.1.4  数值矩阵运算

4.2字符串处理的实验范例

4.2.1  使用字符串作为存储结构

4.2.2  字符串的模式匹配

4.2.3  使用Manacher算法求最长回文子串

4.3在数组中快速查找指定元素的实验范例

4.4通过数组分块技术优化算法的实验范例

4.5相关题库

第5章 应用顺序存取类线性表编程

5.1顺序表应用的实验范例

5.2栈应用的实验范例

5.3队列应用的实验范例

5.3.1顺序队列

5.3.2优先队列

5.3.3双端队列

5.4相关题库

第6章 应用广义索引类线性表编程

6.1使用词典解题的实验范例

6.2 应用散列技术处理字符串的实验范例

6.3 使用散列表与散列方法解题的实验范例

6.4 相关题库

第7章 线性表排序的编程实验

7.1 利用STL中自带的排序功能编程的实验范例

7.2 应用排序算法编程的实验范例

7.3相关题库

本篇小结

第三篇  树的编程实验

第8章 采用树结构的非线性表编程 

8.1 用树的遍历求解层次性问题的实验范例

8.2 用树结构支持并查集的实验范例

8.3 用树状数组统计子树权和的实验范例

8.4 用四叉树求解二维空间问题的实验范例

8.5 应用Trie树查询字符串的实验范例

8.6 应用AC自动机进行多模式匹配的实验范例

8.7 相关题库

第9章 应用二叉树的基本概念编程 

9.1 普通有序树转化为二叉树的实验范例

9.2 应用典型二叉树的实验范例

9.3 计算二叉树路径的实验范例

9.4 通过遍历确定二叉树结构的实验范例

9.5 相关题库

第10章 应用经典二叉树编程

10.1 二叉搜索树的实验范例

10.2 二叉堆的实验范例

10.3 树堆的实验范例

10.3.1  树堆

10.3.2  可持久化树堆（非旋转树堆）

10.4 哈夫曼树的实验范例

10.4.1  哈夫曼树

10.4.2  多叉哈夫曼树

10.5 AVL树的实验范例

10.6 伸展树的实验范例

10.7 相关题库

本篇小结

第四篇  图的编程实验

第11章 应用图的遍历算法

11.1 BFS算法的实验范例

11.2 DFS算法的实验范例

11.3 拓扑排序的实验范例

11.3.1 删边法

11.3.2 采用DFS计算拓扑排序

11.3.3 反向拓扑排序

11.4 计算图的连通性的实验范例

11.5 Tarjan算法的实验范例

11.6 相关题库

第12章 应用最小生成树算法编程

12.1 Kruskal算法的实验范例

12.2 Prim算法的实验范例

12.3 最大生成树

12.4相关题库

第13章 应用最佳路算法编程

13.1 Warshall算法和Floyd-Warshall算法的实验范例

13.2 Dijkstra算法的实验范例

13.3 Bellman-Ford算法的实验范例

13.4 SPFA算法的实验范例

13.5 相关题库

第14章 二分图、网络流算法编程

14.1 二分图匹配的实验范例

14.1.1 匈牙利算法

14.1.2  Hall婚姻定理

14.1.3  KM算法

14.2计算网络最大流的实验范例

14.2.1  网络最大流

14.2.2  最小费用最大流

14.3 相关题库

第15章  应用状态空间搜索编程

15.1 构建状态空间树的实验范例

15.2 优化状态空间搜索的实验范例

15.2.1  剪枝

15.2.2  定界

15.2.3  A*算法

15.2.4  IDA*算法

15.3 博弈问题中使用游戏树的实验范例

15.4 相关题库

本篇小结