本书根据数据结构的知识结构，按照循序渐进的原则分四篇（历练基本编程能力、线性数据结构的编程实验、树的编程实验、图的编程实验）15章组织内容。每章为相关数据结构知识提供了大量的实验范例，并且建立了试题库。其中实验范例有88道，每道试题不仅有详尽的解析，还给出了带有详细注释的参考程序；题库有139道试题，所有试题都有清晰的提示。

从20世纪80年代末期到现在，各类大学生程序设计竞赛、各种在线比赛以及中学生信息学奥林匹克竞赛蓬勃展开，这些比赛通过设置丰富有趣的问题背景考察参赛者编程解决问题的能力，也对数据结构、算法等课程的教学产生了一定的影响。本书作者长期从事数据结构、算法的教学和程序设计竞赛的训练，在实践中总结出一套能激发学生兴趣的系统性学习和训练方法。作者基于实践规划并出版了 “大学程序设计课程与竞赛训练教材”系列图书，有效提高学生通过编程解决实际问题的能力。
本书第1版在国内及阿曼、美国、马来西亚、孟加拉国等国家和地区的高校试用，收到了良好的效果。作者根据国内外的同行及读者在使用过程中提出的意见和建议，进行了大幅度的修改，形成第2版。
新版的主要特色包括：
强调思维方式和解题策略的引导，通过对例题的分析促动学生思考各类数据结构、算法的本质特征，综合时间复杂度、空间复杂度、编程复杂度、思维复杂度等多方面因素选择最适合的解决方案。
对ACM程序设计竞赛、各类大学生程序设计竞赛、在线程序设计竞赛以及中学生信息学奥林匹克竞赛的试题进行了分析和整理，从中精选出200余道作为书中的例题，每道例题给出详尽的解析和标有详细注释的参考程序。
增加了当前热点的人工智能领域相关的数据结构题目，有利于读者未来从事该领域的研发工作。
本书提供丰富的配套学习资源（读者可从华章网站下载），包括所有试题的英文原版以及大部分试题的官方测试数据和解答程序。利用本书及配套的学习资源，读者完全可以通过自学来系统、全面地提升编程能力。

前
吴永辉 博士，复旦大学计算机科学技术学院副教授。2001~2012年担任复旦大学ACM程序设计竞赛队教练，并在总决赛上获得佳绩；2013年起担任ACM-ICPC Asia Council委员、ICPC Asia Programming Contest 1st Training Committee-Chair。2013年起应邀赴阿曼、中国台湾、中国香港、孟加拉国、马来西亚、美国Stony Brook University做访问学者，指导境外高校的队伍在程序设计竞赛中取得优异的成绩。出版“大学程序设计课程与竞赛训练教材”系列图书，并在2016年出版本书的英文版《Data Structure Practice: for Collegiate Programming Contests and Education》。

王建德 信息学奥林匹克竞赛金牌教练，国务院特殊津贴专家，中学特级教师。他所辅导的学生曾在国际信息学竞赛（IOI）中获得7金、3银、2铜的优异成绩，先后出版了24本关于程序设计和算法的图书。“大学程序设计课程与竞赛训练教材”系列图书的主要作者。

我们长期从事数据结构、算法的教学和程序设计竞赛的训练，教学和训练的实践使我们产生了对程序设计、数据结构和算法的教学模式进行改革的想法。
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月于上海

注：本书试题的在线测试地址如下：
在线评测系统 简称 网址
北京大学在线评测系统 POJ http://poj.org/
浙江大学在线评测系统 ZOJ http://acm.zju.edu.cn/onlinejudge/
UVA在线评测系统 UVA http://uva.onlinejudge.org/　http://livearchive.onlinejudge.org/
Ural在线评测系统 Ural http://acm.timus.ru/
SGU在线评测系统 SGU http://acm.sgu.ru/

计算机\程序设计

从20世纪80年代末期到现在，各类大学生程序设计竞赛、各种在线比赛以及中学生信息学奥林匹克竞赛层出不穷，这些比赛通过设置丰富有趣的问题背景考察参赛者编程解决问题的能力，也对数据结构、算法等课程的教学产生了一定的影响。本书作者长期从事数据结构、算法的教学和程序设计竞赛的训练，在实践中总结出一套能激发学生兴趣的系统性学习和训练方法。基于作者的实践，规划并出版了 “大学程序设计课程与竞赛训练教材”系列图书，有效提高学生通过编程解决实际问题的能力。
本书第1版在国内及阿曼、中国台湾、中国香港、美国、马来西亚、孟加拉国等国家和地区的高校试用，收到了良好的效果。作者根据国内外的同行及读者在使用过程中提出的意见和建议，进行了大幅度的修改，形成第2版。
新版的主要特色包括：
强调思维方式和解题策略的引导，通过对例题的分析促动学生思考各类数据结构、算法的本质特征，综合时间复杂度、空间复杂度、编程复杂度、思维复杂度等多方面因素选择最适合的解决方案。
对ACM程序设计竞赛、各大学程序设计竞赛、在线程序设计竞赛以及中学生信息学奥林匹克竞赛的试题进行了分析和整理，从中精选出200余道试题作为书中的试题，每道试题给出详尽的试题解析和标有详细注释的参考程序。
增加了当前热点的人工智能领域相关的数据结构题目，有利于读者未来从事该领域的研发工作。
本书提供丰富的配套学习资源，包括所有试题的英文原版以及大部分试题的官方测试数据和解答程序。利用本书及配套的学习资源，读者完全可以通过自学来系统、全面地提升编程能力。

吴永辉　 王建德　编著：暂无简介

前言
第一篇　历练基本编程能力
第1章　简单计算的编程实验　　2
1.1　改进程序书写风格的实验范例　　2
1.2　正确处理多个测试用例的实验范例　　4
1.3　提高实数精度的实验范例　　7
1.4　使用二分法提高计算时效的实验范例　　9
1.5　相关题库　　13
第2章　简单模拟的编程实验　　24
2.1　直叙式模拟的实验范例　　24
2.2　筛选法模拟的实验范例　　27
2.3　构造法模拟的实验范例　　29
2.4　相关题库　　31
第3章　递归与回溯的编程实验　　38
3.1　计算递归函数的实验范例　　39
3.2　求解递归数据的实验范例　　40
3.3　用递归算法求解问题的实验范例　　42
3.4　回溯法的实验范例　　45
3.5　相关题库　　54
本篇小结　　62
第二篇　线性数据结构的编程实验
第4章　应用直接存取类线性表编程　　64
4.1　数组应用的四个典型范例　　64
4.2　字符串处理的实验范例　　86
4.3　在数组中快速查找指定元素的实验范例　　93
4.4　通过数组分块技术优化算法的实验范例　　95
4.5　相关题库　　98
第5章　应用顺序存取类线性表编程　　135
5.1　顺序表应用的实验范例　　135
5.2　栈应用的实验范例　　141
5.3　队列应用的实验范例　　148
5.4　相关题库　　164
第6章　应用广义索引类线性表编程　　172
6.1　使用词典解题的实验范例　　172
6.2　使用散列表与散列技术解题的实验范例　　179
6.3　相关题库　　190
第7章　线性表排序的编程实验　　196
7.1　利用STL中自带的排序功能编程的实验范例　　196
7.2　应用排序算法编程的实验范例　　202
7.3　相关题库　　205
本篇小结　　226
第三篇　树的编程实验
第8章　采用树结构的非线性表编程　　228
8.1　用树的遍历求解层次性问题的实验范例　　228
8.2　用树结构支持并查集的实验范例　　237
8.3　用树状数组统计子树权和的实验范例　　243
8.4　用四叉树求解二维空间问题的实验范例　　248
8.5　相关题库　　255
第9章　应用二叉树的基本概念编程　　284
9.1　普通有序树转化为二叉树的实验范例　　284
9.2　计算二叉树路径的实验范例　　287
9.3　通过遍历确定二叉树结构的实验范例　　289
9.4　相关题库　　292
第10章　应用经典二叉树编程　　296
10.1　二叉排序树的实验范例　　296
10.2　二叉堆的实验范例　　301
10.3　树堆的实验范例　　311
10.4　赫夫曼树的实验范例　　322
10.5　相关题库　　325
本篇小结　　341
第四篇　图的编程实验
第11章　应用图的遍历算法编程　　344
11.1　BFS算法的实验范例　　344
11.2　DFS算法的实验范例　　348
11.3　拓扑排序的实验范例　　350
11.4　计算无向图的连通性的实验范例　　357
11.5　相关题库　　365
第12章　应用最小生成树算法编程　　387
12.1　Kruskal算法的实验范例　　387
12.2　Prim算法的实验范例　　390
12.3　相关题库　　393
第13章　应用最佳路径算法编程　　402
13.1　Warshall算法和Floyd-Warshall算法的实验范例　　402
13.2　Dijkstra算法的实验范例　　408
13.3　Bellman-Ford算法的实验范例　　412
13.4　SPFA的实验范例　　417
13.5　相关题库　　421
第14章　应用特殊图的经典算法编程　　430
14.1　二分图匹配的实验范例　　430
14.2　计算网络最大流的实验范例　　433
14.3　相关题库　　445
第15章　应用状态空间搜索编程　　459
15.1　构建状态空间树的实验范例　　459
15.2　优化状态空间搜索的实验范例　　469
15.3　博弈问题中使用游戏树的实验范例　　495
15.4　相关题库　　504
本篇小结　　515
参考文献　　517