数据结构编程实验：大学程序设计课程与竞赛训练教材 第3版

定　　价：139 元

• 作者：吴永辉,王建德
• 出版时间：2021/8/1
• ISBN：9787111687429
• 出 版 社：机械工业出版社

• 中图法分类：TP311.12 
• 纸张：胶版纸
• 开本：16开

内容简介

本书针对大学程序设计竞赛和课程教学，基于数据结构的知识体系结构和循序渐进的原则组织内容，包括基本编程能力训练、线性数据结构的编程、树的编程、图的编程。在每一章中，先介绍了相关的数据结构知识后，然后给出相应的范例；在每章的结尾给出相关题库。

序 言

《数据结构编程实验》是大学程序设计课程与竞赛训练教材系列的部著作。在出版本书第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）
电子邮件：[e-mail]

吴永辉　　
2020年9月30日于上海　　

注：本书试题的在线测试地址如下。
在线评测系统简称网址
北京大学在线评测系统POJhttp://poj.org/
浙江大学在线评测系统ZOJhttps://zoj.pintia.cn/home
UVA在线评测系统UVAhttp://uva.onlinejudge.org/　http://livearchive.onlinejudge.org/
Ural在线评测系统Uralhttp://acm.timus.ru/
HDOJ在线评测系统HDOJhttp://acm.hdu.edu.cn/

目 录

前言
篇　训练基本编程能力的实验
第1章　简单计算的编程实验 2
1.1　改进程序书写风格 2
1.2　正确处理多个测试用例 4
1.3　在实数和整数之间转换 10
1.4　二分法、实数精度 13
1.5　相关题库 20
第2章　简单模拟的编程实验 30
2.1　直叙式模拟 30
2.2　筛选法模拟 33
2.3　构造法模拟 35
2.4　相关题库 37
第3章　递归与回溯法的编程实验 44
3.1　计算递归函数 45
3.2　求解递归数据 47
3.3　用递归算法求解问题 49
3.4　回溯法 55
3.5　相关题库 63
本篇小结 69
第二篇　线性表的编程实验
第4章　应用直接存取类线性表编程 72
4.1　数组应用的四个典型范例 72
4.1.1　日期计算 72
4.1.2　高精度运算 78
4.1.3　多项式的表示与处理 86
4.1.4　数值矩阵运算 91
4.2　字符串处理 96
4.2.1　使用字符串作为存储结构 96
4.2.2　字符串的模式匹配 97
4.2.3　使用Manacher算法求长回文子串 103
4.3　在数组中快速查找指定元素 107
4.4　通过数组分块技术优化算法 109
4.5　相关题库 113
第5章　应用顺序存取类线性表编程 149
5.1　顺序表的应用 149
5.2　栈应用 158
5.3　队列应用 166
5.3.1　顺序队列 166
5.3.2　优先队列 176
5.3.3　双端队列 180
5.4　相关题库 183
第6章　应用广义索引类线性表编程 192
6.1　使用词典解题 192
6.2　应用散列技术处理字符串 197
6.3　使用散列表与散列技术解题 202
6.4　相关题库 210
第7章　线性表排序的编程实验 217
7.1　利用STL中自带的排序功能编程 217
7.2　应用排序算法编程 222
7.3　相关题库 226
本篇小结 247
第三篇　树的编程实验
第8章　采用树结构的非线性表编程 250
8.1　用树的遍历求解层次性问题 250
8.2　用树结构支持并查集 258
8.3　用树状数组统计子树权和 266
8.4　用四叉树求解二维空间问题 272
8.5　用Trie树查询字符串 280
8.6　用AC自动机进行多模式匹配 284
8.7　相关题库 292
第9章　应用二叉树的基本概念编程 324
9.1　普通有序树转化为二叉树 324
9.2　应用典型二叉树 327
9.3　计算二叉树路径 333
9.4　通过遍历确定二叉树结构 339
9.5　相关题库 344
第10章　应用经典二叉树编程 348
10.1　二叉搜索树 348
10.2　二叉堆 355
10.3　树堆 363
10.3.1　树堆的概念和操作 363
10.3.2　非旋转树堆 370
10.4　赫夫曼树 379
10.4.1　赫夫曼树 379
10.4.2　多叉赫夫曼树 381
10.5　AVL树 384
10.6　伸展树 389
10.7　相关题库 397
本篇小结 411
第四篇　图的编程实验
第11章　应用图的遍历算法编程 414
11.1　BFS算法 414
11.2　DFS算法 425
11.3　拓扑排序 433
11.3.1　删边法 433
11.3.2　采用DFS计算拓扑排序 436
11.3.3　反向拓扑排序 440
11.4　计算图的连通性 443
11.5　Tarjan算法 450
11.6　相关题库 468
第12 章　应用小生成树算法编程 489
12.1　Kruskal算法 489
12.2　Prim算法 491
12.3　生成树 496
12.4　相关题库 500
第13章　应用路算法编程 507
13.1　Warshall算法和Floyd-Warshall算法 507
13.2　Dijkstra算法 514
13.3　Bellman-Ford算法 519
13.4　SPFA算法 523
13.5　相关题库 527
第14章　二分图、网络流算法编程 535
14.1　二分图匹配 535
14.1.1　匈牙利算法 535
14.1.2　Hall婚姻定理 541
14.1.3　KM算法 544
14.2　计算网络流 551
14.2.1　网络流 551
14.2.2　小费用流 560
14.3　相关题库 570
第15 章　应用状态空间搜索编程 583
15.1　构建状态空间树 583
15.2　优化状态空间搜索 590
15.2.1　剪枝 591
15.2.2　定界 595
15.2.3　A*算法? 603
15.2.4　IDA*算法 612
15.3　在博弈问题中使用游戏树 623
15.4　相关题库 638
本篇小结 658